Search code examples
haskellfunctional-programmingtowers-of-hanoi

Towers of Hanoi - List of moves, check if valid

I'm struggling with a programming task in Haskell. I have to write a function:

move ::([Move],Towers) -> ([Move],Towers)

which takes a list of moves and a game configuration. The function has to check if the first move is valid and then executes this move. Below you can see a possible output of that function. I'm pretty new to Haskell and this programming task is way to much for me. I don't know how and where to start. What are the basic strategies to solve that problem. I really want to learn it and I would be happy if you can make me some suggestions.

Thanks

 type Position = Int
 type Move     = (Position,Position)
 type Towers   = ([Int],[Int],[Int])

 hanoi :: Int -> Position -> Position -> [Move]
 hanoi 1 i j = [(i, j)]
 hanoi n i j = (hanoi (n-1) i other) ++ [(i, j)] ++ (hanoi (n-1) other j)
     where
        other = 1+2+3-i-j

Output of: move ::([Move],Towers) -> ([Move],Towers)

> hanoi 3 1 3 [(1,3),(1,2),(3,2),(1,3),(2,1),(2,3),(1,3)]
> move (it, ([1,2,3],[],[])) ([(1,2),(3,2),(1,3),(2,1),(2,3),(1,3)],([2,3],[],[1])) 
> move it ([(3,2),(1,3),(2,1),(2,3),(1,3)],([3],[2],[1]))
> move it ([(1,3),(2,1),(2,3),(1,3)],([3],[1,2],[]))
> move ([(1,4)],([3],[1,2],[])) ([],*** Exception: Move not valid!
> move ([(1,2),(1,3)],([3,4],[1,2],[])) ([(2,3)],([4],*** Exception: Disc is to big!
Solution 
  • move ::([Move],Towers) -> ([Move],Towers)
move ([],t) = ([],t)
move (x:xs,t) = move (xs,move1 x t)

move1::Move->Towers->Towers
move1 (i,j) (a,b,c)
    | i==1 && j==2 && not (null a) = if inf a b then (tail a,head a:b,c) else error "Disk too large"
    | i==1 && j==3 && not (null a) = if inf a c then (tail a,b,head a:c) else error "Disk too large"
    | i==2 && j==1 && not (null b) = if inf b a then (head b:a,tail b,c) else error "Disk too large"
    | i==2 && j==3 && not (null b) = if inf b c then (a,tail b,head b:c) else error "Disk too large"
    | i==3 && j==1 && not (null c) = if inf c a then (head c:a,b,tail c) else error "Disk too large"
    | i==3 && j==2 && not (null c) = if inf c b then (a,head c:b,tail c) else error "Disk too large"
    | otherwise = error "Move not valid"

inf :: [Int]->[Int]->Bool
inf a b = null b || head a < minimum b