module Main where

-- This is my fast solution to the first question from
-- google's treasure hunt at 
-- http://treasurehunt.appspot.com/historic/robot/
--
-- Compile it as 'ghc paths.hs' then run ./a.out
main :: IO()
main = putStrLn $ show (google_paths 100000 100000)

-- Identify the index into Pascal's triangle which 
-- represents the solution of an NxM board
google_paths :: Integer -> Integer -> Integer
google_paths rows cols =
   pascal_triangle_entry (rows + cols - 1 - 1) ((min rows cols) - 1)

-- Compute the c'th column on row r of Pascal's triangle
-- using the iterative technique described on Wikipedia
-- (implemented using tail recursion and strictness for speed)
pascal_triangle_entry :: Integer -> Integer -> Integer
pascal_triangle_entry r c = go 1 1
 	where
		go i acc | i > c = acc 
		         | True  = go (i + 1) $! (acc * (r + 1 - i)) `div` i