I've simplified and optimized it slightly (no need to use a monad for moveKnightUR) but overall it's still not fast enough to pass the CSES test. I'm wondering if the recursion is somehow inefficient because of two instances of solveK (k-1)...?---- 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) = filter (\(c', r') -> c' `elem` [2..k] && r' `elem` [2..k]) [(c-1, r+2), (c+1, r+2), (c+2, r+1), (c+2, r-1), (c+1, r-2), (c-2, r+1)] -- 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
On Sunday, June 28, 2020, 04:27:07 PM PDT, Julian Ong