Send your feedback or ask for help here!
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.
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:
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
Also consider drawing a sketch.
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.
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.
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.
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.