module Problem2 where
-- for Haskell info visit www.haskell.org

import Data.Array

type Square = (Int, Int)

e1 :: Square
e1 = (5,1)

onBoard :: Square -> Bool
onBoard (x,y) = (x>=1) && (x<=8) && (y>=1) && (y<=8)

boardBounds :: ((Int, Int), (Int, Int))
boardBounds = ((1,1),(8,8))

type MarkedBoard = Array Square Integer

initialBoard :: MarkedBoard
initialBoard = array boardBounds  
               [(s, if s==e1 then 1 else 0) | s <- range boardBounds]

type RevMoveFunc = Square -> [Square]
  -- function which maps a square to a list off squares from which it
  -- can be reached

updateBoard :: RevMoveFunc -> MarkedBoard -> MarkedBoard
  -- given a board with every square marked with the number of paths
  -- which reach it after n moves yields a board with every square
  -- marked with the number of paths which reach it after n+1 moves
updateBoard f b = b // [(s, sum [b!s' | s'<-f s]) | s <- indices b]

king, lazyking, queen, lazyqueen :: RevMoveFunc

king s = filter onBoard $ steps s 1 
  -- an ordinary chess king

lazyking s
    = s : king s
  -- a king which is also allowed to not move at any given move

queen s = filter onBoard $ concatMap (steps s) [1..7]
lazyqueen s = s:queen s
  -- same for a queen

steps :: Square -> Int -> [Square]
steps (x,y) i = [(x-i,y-i),(x,y-i),(x+i,y-i),
                 (x-i,y),          (x+i,y),
                 (x-i,y+i),(x,y+i),(x+i,y+i)]


solve :: RevMoveFunc -> Int -> Integer
  -- How many paths reach the eigths row after n moves?
solve f n = sum [b!(x,8) | x <- [1..8]]
    where b = iterate (updateBoard f) initialBoard !! n

{- example session (also works well with hugs)

$ ghci Problem2
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Problem2         ( Problem2.hs, interpreted )
Ok, modules loaded: Problem2.
*Problem2> solve king 7
1994
*Problem2> solve king 8
30280
*Problem2> solve lazyking 8
46232
*Problem2> solve queen 7
339934673
*Problem2> solve lazyqueen 7
457872199
*Problem2> solve queen 100
1148411858161688271726445791658282269648909701234982618112683105194160818962047912539842384144861118972094188981819575450334818854976969

-}