<html><head></head><body><div class="yahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><div dir="ltr" data-setdir="false">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?</div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">The problem requires that you calculate solutions for 1..n <span><span style="color: rgb(0, 0, 0); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;">so you need to keep track of all intermediate values. The program fails the speed test for</span></span> 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.</div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">My current attempt looks like this:</div><div dir="ltr" data-setdir="false">----</div><div dir="ltr" data-setdir="false"> <div dir="ltr" data-setdir="false"> <div><div>import Control.Monad</div><div><br></div><div>main :: IO ()</div><div>main = do</div><div> line <- getLine</div><div> let n = read line :: Integer</div><div> putStr $ unlines $ map show $ reverse $ solveK n</div><div><br></div><div><br></div><div>solveK :: Integer -> [Integer]</div><div>solveK k</div><div> | k == 1 = [0]</div><div> | otherwise = (solveFrameK k + head (solveK (k-1))) : solveK (k-1)</div><div><br></div><div>-- Returns list of knight moves in the upper right (k-1) x (k-1) portion of the board excluding the first column and first row</div><div>moveKnightUR :: Integer -> (Integer, Integer) -> [(Integer, Integer)]</div><div>moveKnightUR k (c, r) = do</div><div> (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)]</div><div> guard (c' `elem` [2..k] && r' `elem` [2..k])</div><div> return (c', r')</div><div> </div><div>-- Returns list of left and bottom border squares for k x k board in (col, row) format with (1, 1) being the lower left square</div><div>genBorder :: Integer -> [(Integer, Integer)]</div><div>genBorder k = [(1, a) | a <- [1..k]] ++ [(a, 1) | a <- [2..k]]</div><div><br></div><div>-- Formula for combinations C(n, r)</div><div>combinations :: Integer -> Integer -> Integer</div><div>combinations n r = product [1..n] `div` (product [1..(n-r)] * product [1..r])</div><div><br></div><div>-- 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) region</div><div>solveFrameK :: Integer -> Integer</div><div>solveFrameK k</div><div> | k == 1 = 0</div><div> | k == 2 = 6</div><div> | otherwise = ((combinations (2*k-1) 2) - 2) + (k-1) * (k-1) * (2*k-1) - sum (map (toInteger . length) (map (moveKnightUR k) (genBorder k)))</div></div>----</div></div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false">Julian</div></div></body></html>