Cómo minimizar la distancia recorrida en el problema de dos huevos

Para concretar, supongamos que comenzamos con todos los huevos en el suelo a la altura 0 (un huevo caído desde la altura 0 no se romperá), y las ventanas están en alturas 1, …, 100 (un huevo caído desde cualquiera de estas alturas puede puede no romperse). Esta es una función de Haskell (lenguaje de programación) para calcular una estrategia óptima usando programación dinámica: lleva 1023 movimientos en el peor de los casos:

import Data.MemoTrie data Solution = Solution {moves :: Int, floors :: [Int]} | Impossible deriving (Eq, Ord, Show) solve, solve' :: Int -> Int -> Int -> Int -> Int -> Solution solve = mup (mup memo3) solve' solve' held dropped height lo hi | hi == lo = Solution 0 [] | otherwise = minimum $ Impossible : [Solution (height + moves) (0 : floors) | dropped >= 1, Solution moves floors = 1, height' <- [lo + 1..hi], Solution moves1 _ <- [solve (held - 1) dropped height' lo (height' - 1)], Solution moves2 floors <- [solve (held - 1) (dropped + 1) height' height' hi]] 

 λ> solve 2 0 0 0 100 Solution {moves = 1023, floors = [32,45,0,55,63,0,70,76,0,81,85,0,89,92,0,95,97,0,99,100]} 

Si bien todavía hay dos huevos intactos, la estrategia es

• soltar huevos de las alturas 32 y 45,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 55 y 63,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 70 y 76,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 81 y 85,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 89 y 92,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 95 y 97,
• volver a la altura 0 para recuperar los huevos,
• soltar huevos de las alturas 99 y 100.

Soluciones con diferentes números de huevos:

 λ> solve 3 0 0 0 100 Solution {moves = 434, floors = [45,65,74,0,83,89,93,0,97,99,100]} λ> solve 4 0 0 0 100 Solution {moves = 270, floors = [47,65,77,85,0,93,97,99,100]} λ> solve 5 0 0 0 100 Solution {moves = 238, floors = [1,2,3,53,69,0,85,93,97,99,100]} λ> solve 6 0 0 0 100 Solution {moves = 174, floors = [1,2,3,4,5,37,0,69,85,93,97,99,100]} λ> solve 7 0 0 0 100 Solution {moves = 100, floors = [37,69,85,93,97,99,100]} 

Obviamente, no podemos hacer mejor que 100 con cualquier cantidad de huevos.