Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @pardouin,validated by @Westicles,@Zorg1 and @UnicornP.
If you have any issues, feel free to ping them.
1 Like
Really great puzzle! Loved it… but it utterly defeated me for a few days 
Thank you so much for the exercise!
3 Likes
Hint: You can think of the 3x3 matrix as [ [x1,x2,x3], [x4,x5,x6], [x7,x8,x9] ] so you can set up 9 equations with 9 unknowns.
3 Likes
That’s what I did. And I solved it with a Gaussian-Jordan-Algorithm which is available in numerous languages. (I used Java.)
Running the tests in IntelliJ showed for all correct results.
But the 31x31 testcases 7 and 8 failed in the CodinGame environment due to bad performance. 31 times 31 = 961 variables.
I am wandering whether there are more efficient solving algorithms…
I used python and specifically numpy.linalg.solve()
Interesting… just noticed that from all solutions there is only a single Java solution. Could it be that it’s really only a question of the efficiency of the language? I’ll give it a trial…
Thanks for the hint.
1 Like
Great puzzle! 
I was very proud of solving it in 10 lines of code with numpy.linalg.solve()
And then I checked other people’s solution and they do it in 9 lines of code with no library 
3 Likes
The aggregation is a linear operation, so we are just applying a matrix. And it so happens that it’s invertible and the coefficient can be calculated.
Also I’m the only one doing it in Javascript…
Yes it works but there’s a much more efficient solution in O(n^2).
The linear algebra solution is fine but it requires already O(n^4) for computing the matrix alone.
4 Likes
Thank you for this puzzle pardouin! I had a lot of fun finding the solution. It took a while before I realized the obvious, when I read the comment about quadratic complexity ^^.
1 Like
Thanks for this puzzle that ruin my night trying to put the equation in my head. I needed finally a paper to write it down and that is great.
For others, there is solution faster that the linalg approach.
And I do not measure the solution to it number of line but to it’s readability, complexity and documentation.
Continuing the discussion from [Community Puzzle] The Hidden Fortress:
So what what this O(n^2) solution.
Even if the event is over, it’s still a classic puzzle so the solution cannot be given here on the forum.
Only thing I can tell is that if you manage to compute how many fortresses there are in every row/column, then you can deduce where they are.
Why did you not put a number of fortresses in each cell, I mean, not just 0 or 1?
I think that would have been the same difficulty, there is not an exploit of knowing the solutions can be only 0/1 instead of any number, right?
Yes the same solution would work also for multiple fortresses in the same cell.
As you say, it doesn’t change the problem.
But I prefer it this way cause I actually made a playabke version of it where you must click on fortresses cells as fast as possible.
Having to enter a number instead of just clicking would kill the flow.
2 Likes
Okay no problem, I just found a O(n^2) solution.
I am trying to solve this one (with np.linalg.solve), but I am encountering strange behaviour. For the third test, when I run the code in my own IDE, I get the right solution, but for some reason the exact same code gives different output when I use it in the CodinGame IDE.
I will not share my code here, in case it does resemble the answer, but in general, I use np.linalg.solve for equations equal to the input data. My code works for test 1 and test 2, but for test3 my code in my own IDE gives as solution the correct one (flattened [0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]), but in the CodinGame IDE it gives me [0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0].
It is currently ruining my night, so I hope someone can help me – I am of course willing to share my code.
Ahum - nevermind. Instead of deleting this comment, I will keep it up to remind myself of my stupidity. I should not turn the solution into integer before having it rounded.