https://www.codingame.com/training/medium/battle-tower
Send your feedback or ask for help here!
Created by @java_coffee_cup,validated by @Niako,@Azkellas and @Klemek.
If you have any issues, feel free to ping them.
1 Like
i spent way too much time on this before i understood that the problem was to have an exit at the end of each corridor rather than having an exit in or adjacent to every cell.
I focused too much on this rule:
c. compiling with above regulations means that if a cell is not adjacent to a cell with an emergency exit, then it must have one.
Which also has (i believe) a typo, it should read complying rather than compiling, not only is it slightly incorrect it also makes it seem like rule c. is the combination of rules a. and b. => therefore only need to consider rule c.
Still a great puzzle at the end of the day. Thanks for making it.
1 Like
Thank you finding the typo early. Now fixed.
I keep rule b and c there (which could result in the same meaning) because I do not want to restrict codersâ approach. I have tried both ways - to find adj cells from the standing point of a cell, or to find both adj cells from each corridor - both work, according to how you have designed the data structure.
I was trying to remove adj cells from the child list and leave them in the parent list when I had misunderstood the problem. I was trying solve an illogical problem anyhow, because trying to have an emergency exit one node away in a maze is why you shouldnât let a programmer design safety mechanisms. Clearly having an emergency exit where you just came from or where you are going is a much more logical safety mechanism. I am even more satisfied by the problem than I was when completing it.
For anyone who isnât sure that they understand the problem, use the Line 1 test case to see if your approach or understanding yields the correct answer:
10
1 1 2
2 2 1 3
3 2 2 4
4 2 3 5
5 2 4 6
6 2 5 7
7 2 6 8
8 2 7 9
9 2 8 10
10 1 9
Answer:
5
Also consider drawing a sketch.
Glhf
The tag of âGreedy Algorithmâ seems misleading. It will guide some coders down the wrong path. The algorithm needed here will always give the most optimal result (albeit NP-Hard). unlike a Greedy algorithm which may give a ânearâ optimal solution.
1 Like
There are plenty of algorithms in Graphs. Many of them can be classified as âgreedyâ.
Some well-known greedy ones are MST, Dijkstra, cycle test, etc.
âGreedyâ is not acedemically defined well. Some people describe it as âelegant and intutitivly understandable approachesâ, but yet it is still unprecise.
There can be argument about whether an approach is greedy or not.
So I am not surprised you are not agreeing to the tag âgreedyâ.
The NP-complete solution is to treat each cell to have options of true or false. When there are 100 cells, we just need to test 2^100 combinations to find out the minimum one.
Simple. Just too slow to be usable.
So the âgreedyâ tag is to indicate there are better approaches.
The approach I used happens to be greedy in nature (remember definition of greedy is unprecise) and I believe it always gives the absolute minimum value, not only an optimal near-correct value.
You may have another âgreedyâ approach in mind that gives a near optimal solution.
Anyway, the tag is just a vague description of possibility. Not a restriction.
Another quality puzzle from @java_coffee_cup, much appreciated!
As usual, I was struggling with this one for several weeks. Wanted to color every second level vertex by a BFS walk, a completely wrong approach. I could finally solve it only when I figured out the proper name of the graph problem behind this puzzle (might be a spoiler to put it here) and found the relevant Wikipedia page. I am not sure I could figure it out without this. In retrospect, I agree with java_coffee_cup that the algo can be called greedy, because of the way it selects the next vertex to process.
2 Likes
Iâm having difficulties understanding the 3rd test (line) answer.
All cells are line up from cell 1 to cell 10, so it seems to me that the optimal solution is to put an exit in cell 2 (covers 1 and 3), one in cell 5 (covers 4 and 6), one in cell 8 (covers 7 and 9) and finally one in either cell 9 or 10 to cover 10.
For a total of 4 emergency exits, but the expected answer is 5. What am I getting wrong ?
Edit : found it, at least one end of a corridor must connect to a cell with an emergency exit. I wasnât picturing that much of an emergency cover 
Having exits in 2 and 5, will leave 3 and 4 without exit, which is against the rule âat least one end of a corridor must connect to a cell with an emergency exit.â.- the corridor between 3 and 4 is breaking the rule.
1 Like
Hi TBali, can you post the Wikipedia link, its quite difficult to figure out
The underlying graph theory problem is called âminimum vertex coverâ. The approximative method works fine here. However, instead of taking just âarbitrary edgeâ in the algo, in case of a tree graph there is a natural âgreedyâ way of how to select the next edge to process. Sorry if I am cryptic, donât want to disclose full solution here. If figured out what to do, the full solution is very short, it was 30-40 lines for me including I/O.
5 Likes
It can be simply solved greedily with few lines of code. The following link might help.
https://visualgo.net/en/mvc?slide=6
Very nice problem. My own first solution was very near the best solution but not quite. After writing down the mathmatical properties of this game I found the right approch. Very short and elegant!
For a total of 4 emergency exits, but the expected answer is 5. What am I getting wrong ?
I had exactly the same problem: got fixated on the idea of making sure every cell was next to an escape exit, paid no attention to the poor corridorsâŚ
3 Likes
It would be nice to have an intermediary test between star and medium 1. Something like
7
1 1 2
2 4 1 3 4 6
3 1 2
4 2 2 5
5 1 4
6 2 2 7
7 1 6
with answer 3 if I am guessing correctly (I still havenât coded anything yet)
2 Likes
Answer is indeed 3.
Iâm sorry but as stated by Djoums, rule c is indeed written in a misleading way.
complying with above regulations means that if a cell is not adjacent to a cell with an emergency exit, then it must have one
The solution of the line with 4 doors is compliant with statement c (every cell is adjacent to a cell with an emergency exit or has one itself) but not b (some corridors do not have a connection to a cell with an exit). Solving it for statement c alone leads to minimal vertex cover problem solution. With statement b, it does not. So the two situations (corridor/cell point of view) are not equivalent.
The two rules are different.
âb implies câ cannot be interpreted as âb equals câ or âc implies bâ.
The statements are logically sound, no misleading.
1 Like
I just want to say wow on this greedy one.
I tried so many ways to figure it out using papers and excel and several algorithms when suddenly this morning while still in bed the solution came to me and it is so so so simple once you got it (To get it was the hard part, once you got it then it is very simple to code it).
Thank you for this puzzle.
2 Likes
So I am a little stuck right now.
My approach was to iterate over all the nodes, and then set an exit to the nodes which connect to the most other nodes. Take that one out of the equation and continue on, then when only isolated nodes are left over add an exit to those. This actually works for about half the test cases but ends up with a few extra exits after the medium 3 test case and I am not sure how to deal with this.
I tried to think off some way which would break my approach on a smaller scale but I canât figure it out.
Donât need a solution but if anyone knows a simple case where my approach goes wrong so that I can understand what exactly isnât working, Iâd appreciated that 