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

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Doug McIlroy

> I'm currently stuck on the Two Knights problem.

Having placed one knight on the board, in how many
places can you put the other?

Doug McIlroy
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

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

Julian Ong
There are 8 possibilities and then you can filter them by column and row values depending on the region of the board you’re interested in.

Julian

On Jun 28, 2020, at 8:26 AM, Doug McIlroy <[hidden email]> wrote:


> I'm currently stuck on the Two Knights problem.

Having placed one knight on the board, in how many
places can you put the other?

Doug McIlroy

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

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

Irfon-Kim Ahmad
In reply to this post by Doug McIlroy
On 2020-06-28 11:26 a.m., Doug McIlroy wrote:

      
I'm currently stuck on the Two Knights problem.
Having placed one knight on the board, in how many
places can you put the other?

If you check the website indicated, it's a slight variation on that:

"Your task is to count for the number of ways two knights can be placed on a chessboard so that they do not attack each other."

The input is n (an integer that can range from 1 to 10000), the output is a single integer for each value from 1 to n, one per line, the memory limit is 512MB, and the maximum runtime is 1.00 seconds.



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

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

Julian Ong
I realized I did not answer the question Doug posed, but the algorithm as originally presented works correctly and calculates correctly the number of possible knight pairings for each k x k board and generates the correct output requested by the problem.

The issue is still that, as I have implemented it in Haskell, it doesn't run fast enough to pass the automated CSES testing for n=10000. I am very curious whether it's possible to pass the speed testing for this problem using Haskell and if so how.

On Sunday, June 28, 2020, 09:49:02 AM PDT, Irfon-Kim Ahmad <[hidden email]> wrote:


On 2020-06-28 11:26 a.m., Doug McIlroy wrote:

      
I'm currently stuck on the Two Knights problem.
Having placed one knight on the board, in how many
places can you put the other?

If you check the website indicated, it's a slight variation on that:

"Your task is to count for k=1,2,,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other."

The input is n (an integer that can range from 1 to 10000), the output is a single integer for each value from 1 to n, one per line, the memory limit is 512MB, and the maximum runtime is 1.00 seconds.



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

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

Julian Ong
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 row
moveKnightUR :: 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 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)))
----

Julian

On Sunday, June 28, 2020, 04:27:07 PM PDT, Julian Ong <[hidden email]> wrote:


I realized I did not answer the question Doug posed, but the algorithm as originally presented works correctly and calculates correctly the number of possible knight pairings for each k x k board and generates the correct output requested by the problem.

The issue is still that, as I have implemented it in Haskell, it doesn't run fast enough to pass the automated CSES testing for n=10000. I am very curious whether it's possible to pass the speed testing for this problem using Haskell and if so how.

On Sunday, June 28, 2020, 09:49:02 AM PDT, Irfon-Kim Ahmad <[hidden email]> wrote:


On 2020-06-28 11:26 a.m., Doug McIlroy wrote:

      
I'm currently stuck on the Two Knights problem.
Having placed one knight on the board, in how many
places can you put the other?

If you check the website indicated, it's a slight variation on that:

"Your task is to count for k=1,2,,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other."

The input is n (an integer that can range from 1 to 10000), the output is a single integer for each value from 1 to n, one per line, the memory limit is 512MB, and the maximum runtime is 1.00 seconds.



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: CSES programming problems at https://cses.fi/problemset/ [Two Knights]

Julian Ong
In reply to this post by Julian Ong
Update: Doug showed me a fast algorithm that does the trick. It doesn't use recursion. For an nxn board, the algorithm counts the possibilities given a knight in each of these regions:

1.    The central (n-4)x(n-4) sub-board
2.    The squares bordering this central sub-board but excluding the four "corners" where the row and column squares intersect
3.    The edge squares adjacent to the ones in #2
4.    The four "corners" excluded in #2 that are one square diagonal from each of the four corners of the nxn board
5.    The eight edge squares adjacent to the four corners of the nxn board
6.    The four corners of the nxn board

Sum these and divide by two (because the two knights are interchangeable) and you can calculate the solution very quickly for any nxn. Mapping this over [1..n] will provide the required output. My takeaway from this is that using the solution to case n-1 in order to solve case n may not be the most efficient way to do things. Sometimes just solving for case n from scratch is faster.

Thanks Doug.

Julian

On Sunday, June 28, 2020, 09:00:53 AM PDT, Julian Ong <[hidden email]> wrote:


There are 8 possibilities and then you can filter them by column and row values depending on the region of the board you’re interested in.

Julian

On Jun 28, 2020, at 8:26 AM, Doug McIlroy <[hidden email]> wrote:


> I'm currently stuck on the Two Knights problem.

Having placed one knight on the board, in how many
places can you put the other?

Doug McIlroy

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners