Hi - I'm working through these problems using Haskell and was curious if anyone else is doing that. I'm currently stuck on the Two Knights problem. I have implemented a solution using recursion but it's not fast enough to pass the tests. Has anyone been able to solve this problem using Haskell? Looking for some optimization tips. I'm not sure if there's a better way to implement the recursive algorithm - is it doing unnecessary work?
The problem requires that you calculate solutions for 1..n so you need to keep track of all intermediate values. The program fails the speed test for n=10000 -- it needs to complete in less than a second. I hold out hope that it's doable in Haskell but I can't figure it out. The algorithm uses the solution for the (k-1)x(k-1) board and adds the additional possibilities when you add a new left column and bottom row to make a kxk board.
My current attempt looks like this:---- import Control.Monad
main :: IO ()main = do line <- getLine let n = read line :: Integer putStr $ unlines $ map show $ reverse $ solveK n
solveK :: Integer -> [Integer]solveK k | k == 1 = [0] | otherwise = (solveFrameK k + head (solveK (k-1))) : solveK (k-1)
-- Returns list of knight moves in the upper right (k-1) x (k-1) portion of the board excluding the first column and first rowmoveKnightUR :: Integer -> (Integer, Integer) -> [(Integer, Integer)]moveKnightUR k (c, r) = do (c', r') <- [(c-1, r+2), (c+1, r+2), (c+2, r+1), (c+2, r-1), (c+1, r-2), (c-1, r-2), (c-2, r-1), (c-2, r+1)] guard (c' `elem` [2..k] && r' `elem` [2..k]) return (c', r') -- Returns list of left and bottom border squares for k x k board in (col, row) format with (1, 1) being the lower left squaregenBorder :: Integer -> [(Integer, Integer)]genBorder k = [(1, a) | a <- [1..k]] ++ [(a, 1) | a <- [2..k]]
-- Formula for combinations C(n, r)combinations :: Integer -> Integer -> Integercombinations n r = product [1..n] `div` (product [1..(n-r)] * product [1..r])
-- Calculates additional number of two knight placements along the left and bottom border and from that border into the upper right (k-1) x (k-1) regionsolveFrameK :: Integer -> IntegersolveFrameK k | k == 1 = 0 | k == 2 = 6 | otherwise = ((combinations (2*k-1) 2) - 2) + (k-1) * (k-1) * (2*k-1) - sum (map (toInteger . length) (map (moveKnightUR k) (genBorder k)))----
Julian
