https://www.codingame.com/training/hard/binary-extension
Send your feedback or ask for help here!
Created by @mouton5000,validated by @eulerscheZahl,@Xophe and @rozbrajaczpoziomow.
If you have any issues, feel free to ping them.
My code solves every test and validation, as shown by the video of the path taken from origin to destination. But after the goal has been reached, I get a time-out error. However, every test is solved in a matter of a few milliseconds. Even hard-coded solutions for the simple tests time out. I tried ending with and without a new line, but to no avail. I had a puzzle a long time ago where the software was waiting for some additional character, but I can’t figure with this puzzle what character needs to be added, if this is indeed the issue. Any thought?
Never mind. I didn’t realize that I needed to reach all the destinations, not just one.
My first attempt at solving this was super simple and seemed to work well, but then got tripped up because the solutions sometimes used more nodes than necessary. This is because each node has multiple parents, so eager search can find sub optimal solutions.
I managed to fix it but the solution isn’t particularly elegant. Would love to see a good solution. So far there is only one other solution and it seems to have some of the same issues as mine.
So, I don’t know what counts as a “good” solution. The problem is very similar to the space of Steiner tree problems, which tend to be either NP-hard or NP-complete. But there are some examples that do end up being polynomial. If this particular problem is NP-complete, say, then you either have to do brute force as efficiently as you can or you do an approximation solution, which may not hit the optimal answer.
Maybe there’s a trick I’m not getting though, and there’s a polynomial solution out there for this one?
My own approach was to first trim away parts of the grid that certainly can’t be part of the solution, then mark things that absolutely must be part of the solution, and then just for the remaining bits, use brute force to search for the smallest subtrees to add onto the solution to get complete goal coverage.
Not a programmer, first time seeing a binary tree, had to read the problem for 2 days straight and had to switch from C++ to my comfort language C#… this is what I got.
My initial solution was a Goal to root pathfinder algorithm:
- Create a pathfinding algorithm that runs from goal to root
- Store all possible paths from each goal up to root
- If a path is the unique solution to a goal, just add it straight up
- Sort remaining paths in very specific ways:
-
- By least solutions: goals that have the least solutions are processed first
-
- By least nodes: paths that have the least nodes are processed first
-
- By busy node: paths that use nodes that appear a lot in other paths
-
- By collisions: paths that collide the most with existing solutions
Then I realized that for this to work I had to run it at least 3 times because due to the symmetry of the goal distribution in certain cases, the number of solutions and node usage for certain goals is exactly the same.
This thing works, but it is extremely inefficient:
- Need to be run multiple times
- Need to allocate a bunch of paths and a bunch of solutions
- Need to compute and allocate busy node count
- Need to allocate solution nodes in a flat list to make the tree once solutions are solved
The other solution is just Brute Forcing it. Make an algorithm that just goes down and each time it does, it tries to open 3 new trees: one that goes left, one that goes right and one that goes both ways. This method is not as brutish as it seems because we can limit the tree growth in a number of ways:
- When encountering bombs
- When it exits the allowed game coordinates
- When it reaches all goals
- When it has no more N moves remaining to continue.
The only scenario where I can imagine brute force not wining would be in a extremely big gamespace with no bombs, unlimited N moves, and only one goal at the bottom. This is because brute forcing in this context would grow exponentially by a factor of 3 because it creates 3 new trees per processed node, while my pathfinder algorithm would do exactly the same thing but by a factor of 1, and it would trim the bottom left and right corners since it runs from goal to root.
My solution will be the pathfinder thing since there is already a solution in C# that brute force it, by @eulerscheZahl no less.
TL:DR: just brute force it I guess?
1 Like
I have passed the test cases, so I decided to submit my code, and TADA, 50% unfortunately, I tried to see why my code doesn’t solve the test cases in the submit part, and after some debug I found out that the given n in the test Four goals, bomb at center is n = 14, but I see it is impossible to reach all the four goals with just 14 numbers at least for me, I think n must be equal to 15, as shown in the grid below :
0 0 0 0 8 0 0 0 0
0 0 0 7 0 9 0 0 0
0 0 6 0 0 0 10 0 0
0 1 0 0 0 B 0 15 0
0 0 2 0 0 0 11 0 0
0 0 0 4 0 0 0 13 0
0 0 3 0 5 0 12 0 14
@mouton5000
Your tree has a depth 7, in the testcase, the given height is 6, which fine for n = 14.
No I am talking about the test after you submit your code, its height is 7.
as you can see it here : Four goals, bomb at center
You can solve that testcase with 14, the root node is 1 with a single child.
1 Like
Thank you a lot, you are a life saver 