

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/cgibin/mailman/listinfo/beginners


On 20200628 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/cgibin/mailman/listinfo/beginners


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, IrfonKim Ahmad < [hidden email]> wrote:
On 20200628 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/cgibin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgibin/mailman/listinfo/beginners


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 (k1)...?  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 (k1))) : solveK (k1)
 Returns list of knight moves in the upper right (k1) x (k1) 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]) [(c1, r+2), (c+1, r+2), (c+2, r+1), (c+2, r1), (c+1, r2), (c2, 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..(nr)] * product [1..r])
 Calculates additional number of two knight placements along the left and bottom border and from that border into the upper right (k1) x (k1) region solveFrameK :: Integer > Integer solveFrameK k  k == 1 = 0  k == 2 = 6  otherwise = ((combinations (2*k1) 2)  2) + (k1) * (k1) * (2*k1)  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, IrfonKim Ahmad < [hidden email]> wrote:
On 20200628 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/cgibin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgibin/mailman/listinfo/beginners


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 (n4)x(n4) subboard 2. The squares bordering this central subboard 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 n1 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/cgibin/mailman/listinfo/beginners

