# [Community Puzzle] The Hidden Fortress

Coding Games and Programming Challenges to Code Better

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.