La carrera de Collatz

PorJosé A. Alonso 4-abril-201811-abril-2018

Sea f la siguiente función, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

La carrera de Collatz consiste en, dada una lista de números ns, sustituir cada número n de ns por f(n) hasta que alguno sea igual a 1. Por ejemplo, la siguiente sucesión es una carrera de Collatz

   [ 3, 6,20, 49, 73]
   [10, 3,10,148,220]
   [ 5,10, 5, 74,110]
   [16, 5,16, 37, 55]
   [ 8,16, 8,112,166]
   [ 4, 8, 4, 56, 83]
   [ 2, 4, 2, 28,250]
   [ 1, 2, 1, 14,125]

[ 3, 6,20, 49, 73]

[10, 3,10,148,220]

[ 5,10, 5, 74,110]

[16, 5,16, 37, 55]

[ 8,16, 8,112,166]

[ 4, 8, 4, 56, 83]

[ 2, 4, 2, 28,250]

[ 1, 2, 1, 14,125]

En esta carrera, los ganadores son 3 y 20.

Definir la función

   ganadores :: [Int] -> [Int]

1	ganadores :: [Int] -> [Int]

tal que (ganadores ns) es la lista de los ganadores de la carrera de Collatz a partir de la lista inicial ns. Por ejmplo,

   ganadores [3,6,20,49,73]  ==  [3,20]

1	ganadores [3,6,20,49,73] == [3,20]

Soluciones

ganadores :: [Int] -> [Int]
ganadores xs = selecciona xs (final xs)

-- (final xs) es el estado final de la carrera de Collatz a partir de
-- xs. Por ejemplo,
--    final [3,6,20,49,73]  ==  [1,2,1,14,125]
final :: [Int] -> [Int]
final xs | elem 1 xs = xs
         | otherwise = final [siguiente x | x <- xs]

-- (siguiente x) es el siguiente de x en la carrera de Collatz. Por
-- ejemplo, 
--    siguiente 3  ==  10
--    siguiente 6  ==  3
siguiente :: Int -> Int
siguiente x | even x    = x `div` 2
            | otherwise = 3*x+1

-- (selecciona xs ys) es la lista de los elementos de xs cuyos tales que
-- los elementos de ys en la misma posición son iguales a 1. Por ejemplo,
--    selecciona [3,6,20,49,73] [1,2,1,14,125]  ==  [3,20]
selecciona :: [Int] -> [Int] -> [Int]
selecciona xs ys =
  [x | (x,y) <- zip xs ys, y == 1]

ganadores :: [Int] -> [Int]

ganadores xs = selecciona xs (final xs)

-- (final xs) es el estado final de la carrera de Collatz a partir de

-- xs. Por ejemplo,

-- final [3,6,20,49,73] == [1,2,1,14,125]

final :: [Int] -> [Int]

final xs | elem 1 xs = xs

| otherwise = final [siguiente x | x <- xs]

-- (siguiente x) es el siguiente de x en la carrera de Collatz. Por

-- ejemplo,

-- siguiente 3 == 10

-- siguiente 6 == 3

siguiente :: Int -> Int

siguiente x | even x = x `div` 2

| otherwise = 3*x+1

-- (selecciona xs ys) es la lista de los elementos de xs cuyos tales que

-- los elementos de ys en la misma posición son iguales a 1. Por ejemplo,

-- selecciona [3,6,20,49,73] [1,2,1,14,125] == [3,20]

selecciona :: [Int] -> [Int] -> [Int]

selecciona xs ys =

[x | (x,y) <- zip xs ys, y == 1]

5 Comentarios

ganadores :: [Int] -> [Int]
ganadores =
  map fst
  . filter ((== 1) . snd)
  . until (any ((== 1) . snd)) (map f)
  . map ((,) <*> id)
  where f (x,n) | even n    = (x,div n 2)
                | otherwise = (x,3*n+1)

ganadores :: [Int] -> [Int]

ganadores =

map fst

. filter ((== 1) . snd)

. until (any ((== 1) . snd)) (map f)

. map ((,) <*> id)

where f (x,n) | even n = (x,div n 2)

| otherwise = (x,3*n+1)

Responder

import Data.List (findIndices)

ganadores :: [Int] -> [Int]
ganadores xs = [xs !! x | x <- indicesCollatz xs]
  where indicesCollatz xs |elem 1 xs = findIndices (==1) xs
                          |otherwise = indicesCollatz (map f xs)
                           where f x | even x    = div x 2
                                     | otherwise = 3*x+1

import Data.List (findIndices)

ganadores :: [Int] -> [Int]

ganadores xs = [xs !! x | x <- indicesCollatz xs]

where indicesCollatz xs |elem 1 xs = findIndices (==1) xs

|otherwise = indicesCollatz (map f xs)

where f x | even x = div x 2

| otherwise = 3*x+1

Responder

ganadores :: [Int] -> [Int]
ganadores xs = [x | (x,y) <- (until (any ((== 1) . snd)) (map f)) (map toPar xs), y==1]
  where f (x,n) | even n    = (x,div n 2)
                | otherwise = (x,3*n+1)
        toPar x = (x,x)

ganadores :: [Int] -> [Int]

ganadores xs = [x | (x,y) <- (until (any ((== 1) . snd)) (map f)) (map toPar xs), y==1]

where f (x,n) | even n = (x,div n 2)

| otherwise = (x,3*n+1)

toPar x = (x,x)

Responder

ganadores :: [Int] -> [Int]
ganadores xs = [snd q | q <- ys, t <- zs, fst q == fst t, snd t == 1]
  where ys = zip [1..] xs
        zs = zip [1..] (resultadocarrera xs)

resultadocarrera :: [Int] -> [Int]
resultadocarrera xs = aux xs
  where aux ys | 1 `elem` ys = ys
               | otherwise = aux (map f ys)
                 where f x | even x = x `div` 2
                           | otherwise = (x * 3) + 1

ganadores :: [Int] -> [Int]

ganadores xs = [snd q | q <- ys, t <- zs, fst q == fst t, snd t == 1]

where ys = zip [1..] xs

zs = zip [1..] (resultadocarrera xs)

resultadocarrera :: [Int] -> [Int]

resultadocarrera xs = aux xs

where aux ys | 1 `elem` ys = ys

| otherwise = aux (map f ys)

where f x | even x = x `div` 2

| otherwise = (x * 3) + 1

Responder

ganadores :: [Int] -> [Int]
ganadores xs = aux $ zip xs xs
  where aux ys | (not.null) gs = (snd.unzip) gs
               | otherwise = aux collatzada
          where gs = [(a,b) | (a,b) <- ys, a == 1]
                collatzada = [(collatz a, b) | (a,b) <- ys]
                collatz x | even x = div x 2
                          | otherwise = 3 * x + 1

ganadores :: [Int] -> [Int]

ganadores xs = aux $ zip xs xs

where aux ys | (not.null) gs = (snd.unzip) gs

| otherwise = aux collatzada

where gs = [(a,b) | (a,b) <- ys, a == 1]

collatzada = [(collatz a, b) | (a,b) <- ys]

collatz x | even x = div x 2

| otherwise = 3 * x + 1

Responder

La carrera de Collatz

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico