Números construibles como sumas de dos dados

9 Comentarios

1. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles a b = aux a (0:construibles a b) b (0:construibles a b) where aux a (x:xs) b (y:ys) | p == q = p:aux a xs b ys | p > q = q:aux a (x:xs) b ys | otherwise = p:aux a xs b (y:ys) where p = a + x q = b + y esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == last (takeWhile (x>=) (construibles a b))

   1 2 3 4 5 6 7 8 9 10 11

   construibles  :: Integer -> Integer -> [Integer] construibles a b = aux a (0:construibles a b) b (0:construibles a b)       where aux a (x:xs) b (y:ys) | p == q = p:aux a xs b ys                                   | p > q = q:aux a (x:xs) b ys                                   | otherwise = p:aux a xs b (y:ys)                             where p = a + x                                   q = b + y                                      esConstruible :: Integer -> Integer -> Integer -> Bool                           esConstruible a b x = x == last (takeWhile (x>=) (construibles a b))

   Responder

   1. Haskell

      -- Definición mejorada: construibles :: Integer -> Integer -> [Integer] construibles a b = t where t = aux a (0:t) b (0:t) aux a (x:xs) b (y:ys) | p == q = p:aux a xs b ys | p > q = q:aux a (x:xs) b ys | otherwise = p:aux a xs b (y:ys) where p = a + x q = b + y esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == head (dropWhile (x>) (construibles a b))

      1 2 3 4 5 6 7 8 9 10 11 12 13

      -- Definición mejorada: construibles  :: Integer -> Integer -> [Integer] construibles a b = t       where t = aux a (0:t) b (0:t)             aux a (x:xs) b (y:ys) | p == q = p:aux a xs b ys                                   | p > q = q:aux a (x:xs) b ys                                   | otherwise = p:aux a xs b (y:ys)                             where p = a + x                                   q = b + y                                      esConstruible :: Integer -> Integer -> Integer -> Bool                           esConstruible a b x = x == head (dropWhile (x>) (construibles a b))

      Responder

2. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles a b = (intercala xs . intercala zs) ys where xs = map (*b) [1..] ys = map (*a) [1..] zs = [x+y | x<-xs, y<-ys] intercala (x:xs) (y:ys) | x < y = x : intercala (xs) (y:ys) | x > y = y : intercala (x:xs) (ys) | x == y = x : intercala xs ys esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == (head . dropWhile (<x) . construibles a) b

   1 2 3 4 5 6 7 8 9 10 11 12

   construibles :: Integer -> Integer -> [Integer] construibles a b = (intercala xs . intercala zs) ys                 where                  xs = map (*b) [1..]                  ys = map (*a) [1..]                  zs = [x+y | x<-xs, y<-ys]                  intercala (x:xs) (y:ys) | x < y  = x : intercala (xs) (y:ys)                                          | x > y  = y : intercala (x:xs) (ys)                                          | x == y = x : intercala xs ys   esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == (head . dropWhile (<x) . construibles a) b

   Responder

3. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles x y = aux x y x y (x+y) (x+y) where aux x y a b n m | l == a = l : aux x y (x+a) b n m | l == b = l : aux x y a (y+b) n m | otherwise = l : aux x y a b (n+x) (m+y) where l = minimum [a,b,n,m] esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible x y z = z `elem` takeWhile (<(z+1)) (construibles x y)

   1 2 3 4 5 6 7 8 9

   construibles  :: Integer -> Integer -> [Integer] construibles x y = aux x y x y (x+y) (x+y) where aux x y a b n m | l == a = l : aux x y (x+a) b n m                        | l == b = l : aux x y a (y+b) n m                        | otherwise = l : aux x y a b (n+x) (m+y)                    where l = minimum [a,b,n,m]   esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible x y z = z `elem` takeWhile (<(z+1)) (construibles x y)

   Responder

4. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles a b = intercala xs (intercala zs ys) where xs = scanl1 (+) [b,b..] ys = scanl1 (+) [a,a..] zs = (+) <$> xs <*> ys intercala :: Ord a => [a] -> [a] -> [a] intercala (x:xs) (y:ys) | x < y = x : intercala (xs) (y:ys) | x > y = y : intercala (x:xs) (ys) | x == y = x : intercala xs ys esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = (head (dropWhile (<x) (construibles a b))) == x

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   construibles :: Integer -> Integer -> [Integer] construibles a b = intercala xs (intercala zs ys)                 where                  xs = scanl1 (+) [b,b..]                  ys = scanl1 (+) [a,a..]                  zs = (+) <$> xs <*> ys   intercala :: Ord a => [a] -> [a] -> [a]         intercala (x:xs) (y:ys) | x < y  = x : intercala (xs) (y:ys)                         | x > y  = y : intercala (x:xs) (ys)                         | x == y = x : intercala xs ys   esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = (head (dropWhile (<x) (construibles a b))) == x

   Responder

5. Haskell

   import Data.List.Utils (merge) -- elegante pero poco eficiente construibles :: Integral a =>a ->a ->[a] construibles a b = foo 0 where foo n = bar (n + a) `merge` bar (n + b) bar n = n: foo n -- eficiente pero fea construibles' :: Integral a =>a ->a ->[a] construibles' a b = filter (esConstruible a b) [1..] -- debe haber algún caso en que será lenta, pero en general es rápida con -- números de miles de dígitos esConstruible :: Integral a =>a ->a ->a ->Bool esConstruible a b n = esConstruible1 a n || esConstruible1 b n || (r == 0 && esConstruible2 (a `div` d) (b `div` d) n') where d = gcd a b (n', r) = n `divMod` d esConstruible1 :: Integral a =>a ->a ->Bool esConstruible1 a n = n `mod` a == 0 esConstruible2 :: Integral a =>a ->a ->a ->Bool esConstruible2 a b n | a > b = esConstruible2 b a n | otherwise = or [esConstruible1 a (n - i * b) | i <-[1..n `div` b]] -- muchas oportunidades de optimización (ej. saltar multiplos comunes)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   import Data.List.Utils (merge)     -- elegante pero poco eficiente construibles :: Integral a =>a ->a ->[a] construibles a b = foo 0              where foo n = bar (n + a) `merge` bar (n + b)                    bar n = n: foo n     -- eficiente pero fea construibles' :: Integral a =>a ->a ->[a] construibles' a b = filter (esConstruible a b) [1..]         -- debe haber algún caso en que será lenta, pero en general es rápida con -- números de miles de dígitos esConstruible :: Integral a =>a ->a ->a ->Bool esConstruible a b n = esConstruible1 a n || esConstruible1 b n || (r == 0 && esConstruible2 (a `div` d) (b `div` d) n')   where d = gcd a b         (n', r) = n `divMod` d   esConstruible1 :: Integral a =>a ->a ->Bool esConstruible1 a n = n `mod` a == 0   esConstruible2 :: Integral a =>a ->a ->a ->Bool esConstruible2 a b n   | a > b     = esConstruible2 b a n   | otherwise = or [esConstruible1 a (n - i * b) | i <-[1..n `div` b]] -- muchas oportunidades de optimización (ej. saltar multiplos comunes)

   Responder

6. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles a b = mezclaTodas (as:bs:[map (+x) bs | x <-as]) where as = map (*a) [1..] bs = map (*b) [1..] mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | x == y = x : mezcla xs ys | x > y = y : mezcla (x:xs) ys mezclaTodas :: Ord a => [[a]] -> [a] mezclaTodas = foldr1 xmezcla where xmezcla (x:xs) ys = x : mezcla xs ys esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b n = n == head (dropWhile (<n) suc) where suc = construibles a b

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   construibles  :: Integer -> Integer -> [Integer] construibles a b = mezclaTodas (as:bs:[map (+x) bs | x <-as])   where as = map (*a) [1..]         bs = map (*b) [1..]   mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)                      | x == y = x : mezcla xs ys                      | x > y  = y : mezcla (x:xs) ys   mezclaTodas :: Ord a => [[a]] -> [a] mezclaTodas = foldr1 xmezcla     where xmezcla (x:xs) ys = x : mezcla xs ys   esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b n = n == head (dropWhile (<n) suc)   where suc = construibles a b

   Responder

7. Haskell

   import Data.List esConstruible x f g | x < n = False | x `mod` p == 0 = True | x `mod` n == 0 = True | x < p && x `mod`n /= 0 =False | abs(head(reverse (takeWhile (< (-p+1))(iterate (+n) (-x))))) `mod` p == 0 = True | abs (head(reverse (takeWhile (< (-n+1))(iterate (+p) (-x))))) `mod` n == 0 = True | otherwise = False where n = minimum [f, g] p = maximum [f,g] construibles f g = [x | x <- [n..] , esConstruible x f g == True] where n = minimum [f,g]

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   import Data.List   esConstruible x f  g   | x < n  = False   | x `mod` p == 0 = True   | x `mod` n == 0 = True   | x < p && x `mod`n /= 0 =False   | abs(head(reverse (takeWhile (< (-p+1))(iterate (+n) (-x))))) `mod` p == 0 = True   | abs (head(reverse (takeWhile (< (-n+1))(iterate (+p) (-x))))) `mod` n == 0 = True   | otherwise = False   where n = minimum [f, g]         p = maximum [f,g]   construibles f g = [x | x <- [n..] , esConstruible x f g == True]   where n = minimum [f,g]

   Responder

8. Haskell

   construibles :: Integer -> Integer -> [Integer] construibles x y = m : aux x y [min x y] where m = min x y aux a b xs | a `elem` xs && b `elem` xs = r : aux a b (r:xs) | a `elem` xs = c : aux a b (c:xs) | b `elem` xs = d : aux a b (d:xs) where r = minimum ([ z | x <- xs, let z = x + a, not (z `elem` xs)] ++ [ z' | x <- xs, let z' = x + b, not (z' `elem` xs)]) c = minimum (b : [ z | x <- xs, let z = x + a, not (z `elem` xs)]) d = minimum (a : [ z | x <- xs, let z = x + b, not (z `elem` xs)]) esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == (head $ dropWhile (< x) (construibles a b))

   1 2 3 4 5 6 7 8 9 10 11 12

   construibles :: Integer -> Integer -> [Integer] construibles x y =  m : aux x y [min x y]              where m = min x y                    aux a b xs | a `elem` xs && b `elem` xs = r : aux a b (r:xs)                               | a `elem` xs                = c : aux a b (c:xs)                               | b `elem` xs                = d : aux a b (d:xs)                              where r = minimum ([ z | x <- xs, let z = x + a, not (z `elem` xs)] ++ [ z' | x <- xs, let z' = x + b, not (z' `elem` xs)])                                    c = minimum (b : [ z | x <- xs, let z = x + a, not (z `elem` xs)])                                    d = minimum (a : [ z | x <- xs, let z = x + b, not (z `elem` xs)])                    esConstruible :: Integer -> Integer -> Integer -> Bool esConstruible a b x = x == (head $ dropWhile (< x) (construibles a b))

   Responder