CSES programming problems at https://cses.fi/problemset/
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:
main :: IO ()
main = do
line <- getLine
let n = read line :: Integer
putStr $ unlines $ map show $ reverse $ solveK n
solveK :: Integer -> [Integer]
| k == 1 = 
| 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 row