CSES programming problems at https://cses.fi/problemset/

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

CSES programming problems at https://cses.fi/problemset/

Julian Ong
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 row
moveKnightUR :: 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 square
genBorder :: Integer -> [(Integer, Integer)]
genBorder k = [(1, a) | a <- [1..k]] ++ [(a, 1) | a <- [2..k]]

-- Formula for combinations C(n, r)
combinations :: Integer -> Integer -> Integer
combinations 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) region
solveFrameK :: Integer -> Integer
solveFrameK 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)))


Beginners mailing list
[hidden email]