Personal tools

Haskell Quiz/Numeric Maze/Solution Dolio

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(new)
m
Line 1: Line 1:
-
This is a simple breadth-first search with some pruning. It avoids visiting numbers that have already been seen in a shorter sequence, and trims in too-large values (I noticed that no shortest sequences in that case seemed to use numbers greater than 2*max(init, target) + 2, so such values could be discarded).
+
This is a simple breadth-first search with some pruning. It avoids visiting numbers that have already been seen in a shorter sequence, and trims in too-large values (I noticed that no shortest sequences seemed to use numbers greater than 2*max(init, target) + 2, so such values could be discarded).
<haskell>
<haskell>

Revision as of 19:36, 5 November 2006

This is a simple breadth-first search with some pruning. It avoids visiting numbers that have already been seen in a shorter sequence, and trims in too-large values (I noticed that no shortest sequences seemed to use numbers greater than 2*max(init, target) + 2, so such values could be discarded). 

{-# OPTIONS_GHC -fglasgow-exts #-}
 
module Main where
import Control.Monad
import Data.IntSet (fromList, insert, empty, notMember, union)
import Data.List (findIndex)
import Data.Ratio
import System
 
search init target = reverse . map numerator $ search' [[init % 1]] (fromList [init])
 where
 t = target % 1
 search' ls s
    | Just i <- findIndex ((==t) . head) ls = ls !! i
    | otherwise = search' ls' s'
  where
  s' = s `union` fromList (map (numerator . head) ls')
  ls' = do l@(h:_) <- ls
           n <- [h + 2, h * 2, h / 2]
           guard (denominator n == 1)
           guard (numerator n `notMember` s)
           guard (if target > init then  n < 2*t + 1 else n < 2*(init%1) + 3)
           return (n:l)
 
main = do [i, t] <- fmap (map read) getArgs
          print $ search i t
Retrieved from "http://www.haskell.org/haskellwiki/Haskell_Quiz/Numeric_Maze/Solution_Dolio"