We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Digits Square Board
Digits Square Board
Sort by
recency
|
12 Discussions
|
Please Login in order to post a comment
Here is Digits Square Board problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-digits-square-board-problem-solution.html
First full score Python 3 solution for this problem:
According to the leaderboard no other Python3 solution was fast enough for all test cases (test case 3 with 10 boards of size 30x30 IS tough).
After some tests and optimization I finally succeeded with it and now take the liberty of throwing that code at you ;-)
How can i return the result ? after I have fixed it I'm trying to return the result but every time it's show me an issue I tryed to return as a list like ['Second','First'] or string like 'Second\nFirst' but nothing happen.
I wonder what the time limit/estimate for a single 30x30 matrix in Python 3 is.
I used a single bytes sequence to store the matrix' bits (rows first), so I would only need to split it once to make a horizontal cut. For the vertical cuts I transposed the matrix first, so that would only need to be cut once.
I cached the already found Grundy numbers in a dict, so I wouldn't need to traverse them again.
So far, I got it down to a consistent 7.3 s on a random matrix on my machine, but that still fails tests 3 and 4. I ran out of ideas.
Should I be using a different data structure? I tried the same algorithm, but storing data as an integer, setting the individual bits, but that turned out to be way slower.
My thoughtprocess:
You have to convert the game to nim. Since, a board is broken down into 2. So, let us assume the no. of piles to be 2. Now, comes the no. of stones in each pile. That depends on how you split it up.
For a N X M board, you can either split it row wise or column wise.
Row-wise: N-1
Column-wise: M-1
Total no. of ways: N+M-2
So, for a N X M board, you need to check the xor of the grundy values of the two sub-rectangles and if there isn't a single combination that gives a non-zero value, then surely the first player looses.
Now comes the assigning of grundy number to each sub-rectangle-
Base Case: If there is no non-primes at all. Assign this a Grundy value=0.
For the rest, assign them a Grundy value equal to the mex of the set containing the combinations of all the spilts in it. (Xor of the Grundy values of the individual triangles.)
So, the no. of splits can be considered the no. of stones in the rectangle or pile!
Hope that helps :)