You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
44 lines
1.3 KiB
44 lines
1.3 KiB
{


A Solution to rubyquiz 60 (http://rubyquiz.com/quiz60.html)




You have a starting point and a target. You have a set of three operations:


double


halve (Odd numbers cannot be halved)


add_two


Problem: Move from the starting point to the target, minimizing the number of operations.




This solution finds the shortest path using A* search with cost of each operation


as one and the heuristic as the absolute of log of the ratio of the target


and start numbers.




Usage: bin/NumericMaze 2 9




Copyright 2012 Abhinav Sarkar <abhinav@abhinavsarkar.net>


}




module NumericMaze (solve, main) where




import AStar


import Control.Monad (when)


import System.Environment (getArgs)




data Op = Double  Halve  AddTwo




execute :: Integral a => a > Op > a


execute n Double = 2 * n


execute n Halve = let (q, r) = n `divMod` 2 in if r == 0 then q else n


execute n AddTwo = n + 2




solve start end =


astar start end


(\n > zip (map (execute n) [Double, Halve, AddTwo]) (repeat 1))


(\a b > abs $ logBase 2 (fromIntegral b / fromIntegral a))




main = do


(start : end : _) < fmap (map read) getArgs




when (start <= 0  end <= 0) (error "Error: The numbers must be positive")




case solve start end of


Nothing > putStrLn "No solution"


Just (_, solution) > putStrLn . unwords . map show $ solution 