language: Haskell (ghc-6.8.2)
date: 126 days 7 hours ago
link:
visibility: public 
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

import Data.Maybe
data Instruction = X | Y deriving Show
 
instance Eq Instruction where
    X == X = True
    Y == Y = True
    _ == _ = False
 
 
instance Ord Instruction where
    Y <= X = False
    _ <= _ = True
    
data BTree a = Branch a (BTree a) (BTree a)
 
language (p, x, y) = Branch (p, x, y) (language (X:p, x + y, y)) (language (Y:p, x, x + y))
languageExprs = language ([], 1, 1)
 
minLength [] = Nothing
minLength x  = Just $ flip foldl1 x (\a b -> if length a < length b then a else b)
 
breadthSearch (Branch (p, x, y) lf rt) target
  | x == target = Just p
  | x < target && y < target = minLength $ catMaybes $ [breadthSearch lf target, breadthSearch rt target]
  | otherwise = Nothing
 
main = do
  value <- getContents
  print $ breadthSearch languageExprs (read value)