import Test.Hspec
import Data.List
import Data.Array

-- Usy dynamic programming to avoid redoing same job multiple times.
-- Array is very slow in here...
paths_cache :: Int -> Array (Int, Int) Int
paths_cache m = array ((0,0),(mx,my)) 
    (((mx,my),1) :
     [((mx,j),1) | j <- [0..(my-1)]] ++ -- last column is 1s
     [((i,my),1) | i <- [0..(mx-1)]] ++ -- last row is 1s
     [((i,j),(paths_cache m)!(i+1,j) + (paths_cache m)!(i,j+1)) | i <- reverse [0..(mx-1)], j <- reverse [0..(my-1)]])
        where mx = m
              my = m

--
-- Same as 2d array implementation logic, but based on lists
--

-- Just generate 1 line above based on current.
gen_prev_row :: [Int] -> [Int]
gen_prev_row (a:[]) = [a]
gen_prev_row (a:xa) = next_element : new_tail 
    where new_tail = (gen_prev_row xa)
          next_element = (head new_tail) + a

-- Generate matrix of paths_number
paths_cache_2 :: Int -> Int -> [[Int]]
paths_cache_2 0 y = [take (y+1) (cycle [1])]
paths_cache_2 x y = [gen_prev_row last_line] ++ matrix_bottom
    where matrix_bottom = paths_cache_2 (x-1) y
          last_line = head matrix_bottom

-- Same 2d list but nicer definition.
paths_cache_3_ mx my = [take (my+3) (cycle [1])] ++ [ 1 : [matrix!!(i-1)!!j + matrix!!i!!(j-1)| j <- [1..my] ] | i <- [1..mx]]
    where matrix = paths_cache_3_ mx my

-- just reverse order in rows and collumns
paths_cache_3 mx my = reverse (map (reverse) (paths_cache_3_ mx my))


-- (x, y) coordinates on the grid
-- (max x, max y) max grid coordinates (grid size)
-- res number of paths, that can be created by right, down steps
lattice_paths_count_ :: (Int, Int) -> (Int, Int) -> Int
lattice_paths_count_ (x,y) (mx,my)
    | (x == mx) && (y == my) = 1 
    | (x == mx) && (y /= my) = lattice_paths_count_ (x,y+1) (mx,my)
    | (x /= mx) && (y == my) = lattice_paths_count_ (x+1,y) (mx,my)
    | otherwise = 0
                + lattice_paths_count_ (x+1,y) (mx,my)
                + lattice_paths_count_ (x,y+1) (mx,my)

-- x - Grid size
-- res = number of paths to get to the end of the grid
lattice_paths_count :: Int -> Int
-- lattice_paths_count s = lattice_paths_count_ (0,0) (s,s)
-- lattice_paths_count s = paths_caches ! (0,0)
-- lattice_paths_count s = (paths_cache_2 s s !! 0) !! 0
lattice_paths_count s = (paths_cache_3 s s !! 0) !! 0

-- Tests + result print
main = hspec $ do
    describe "Dummy" $ do
        it "dummy test" $ do
            True `shouldBe` True
    describe "Euler test" $ do
        it "lattise paths for 2x2 grid" $ do
            True `shouldBe` (lattice_paths_count 2) == 6
    describe "Euler actual problem" $ do
        it "sum of big numbers" $ do
            putStrLn ("res = " ++ show (lattice_paths_count 20))
