Feel free to send your feedback or ask some help here!
My code fails on big lists. How can I know if it is a issue with the execution time or the memory usage.
For information, I use a recursive graph scan, which is maybe the problem.
I use a recursive reverse dijkstra-ish algorithm. What’s important is not the method, it is more like an alpha beta pruning.
You need to stop recursing on rooms that are useless, that way you are sure to pass the 9870 rooms tests in less than half a second.
1 Like
Thank you, I will have to make reseaches and optimisations, I like that.
By the way, it there a way to know how much mem and time the script consumes in order to know in which direction I need to go?
not that i know of, i’m afraid
Thanks. Dijkstra’s algorithm is really very fast: 9870 - 0.05 seconds.(PHP)
2 Likes
Hello,
I have problem with test Multiple entries
I’m use TOPO sort and DP.
Here’s my path
50 <-- 41 <-- 32 <-- 25 <-- 18 <-- 12 <-- 7 <-- 4 <-- 1 <-- 63<<<<
368 321 294 251 211 180 142 121 85 56
And here is ans
51 <-- 41 <-- 32 <-- 25 <-- 18 <-- 12 <-- 7 <-- 4 <-- 1 <-- 63<<<<
358 321 294 251 211 180 142 121 85 56
input
41 27 50 51
…
…
50 47 E E
51 37 E E
EDIT:
Sorry, machine start at 0 @@
Need clarification of the sample example. Why the answer is 88? I got 145 in this way:
0 -> 1 -> 3 -> 7 -> 12 -> 8 ->13 -> 9 -> 14 -> E
(17, ‘0’)
(32, ‘1’)
(52, ‘3’)
(71, ‘7’)
(88, ‘12’)
(100, ‘8’)
(119, ‘13’)
(130, ‘9’)
(145, ‘14’)
(145, ‘E’)
Many thanks!
zsong, the graph is directed, you cannot go from 13 to 9.
Moreover, the general problem is NP-hard.
It says that “Some doors open in one direction only” in fact it “All doors open in one direction only”. In this case, we have direct acyclic graph, for witch the problem is P. That’s why CvxFous’s dijkstra-ish works well.
2 Likes
I used a very simple depth-first search with additional backtracking if I already found a better solution for the room I’m checking, and all tests pass
My solution was inspired by Project Euler’s problem number 67, not recursive, instead DP.
1 Like
I don’t really get how to solve this problem. As far as I understand, we have to find the path with maximum weight from node ‘0’ to node ‘E’.
This problem should be similar to finding a shortest path (using e.g. dijkstra) on a graph with inverted weights.
I did just that. First tests succeed, and then failures, starting at test ‘55 rooms’.
To be sure that I did not have a bug in my Dijkstra implementation, I used a python library that has shortest path algorithm builtin (networkx) and it found the same result as me.
What am I missing here?
In general, finding a longest path is not equivalent to finding a shortest path with inverted weights. For a counter example, take a graph with all weights equal to 1: then any shortest path would be a longest path?
You could say that the longest path problem is equivalent to finding a shortest path with opposite weights, but it doesn’t make the problem any easier to solve, since shortest-path algorithm usually rely on the weights being positive.
Sorry, I meant opposite weights, no inverted weights, you’re right.
When using dijkstra, on a directed acyclic graph such as in this puzzle, there should be no problem finding the shortest path this way.
Still, the problem persist. Using opposite weights with Dijkstra (my own implementation, or the one of an external library) I do not find the proper solution. I guess I’m missing something in the problem. How is this problem different than finding the longest weighted path?
Even on an acyclic graph, I don’t think that Dijkstra can work with negative weights: the whole point of the algorithm is that it considers vertices closest from S first.
More precisely, at any given step, if the first vertex in the queue is at distance d from S, it means that all vertices that are at distance less than d have already been visited. For example at the very first step, the closest neighbor of S is also the vertex closest to S. If you allow negative weights, it is not true anymore (all neighbors of this neighbor will be closer to S).
If it helps, you may visualize it in terms of algorithm “goals”: the goal of Dijkstra’s algorithm is to visit as few vertices at it can, before concluding that the shortest path has been found. But how do you want to ensure that you have found the longest path in a (connected) graph without visiting all vertices in G?
That being said, this problem can definitely be solved with methods very similar to those of Dijkstra’s algorithm. 
Yes, DP for Project Euler 18/67 works perfectly for all the cases but the “Square building”. For that one you may notice that the sum of money for each room is the same and = 1.
1 Like
The test cases are too trivial, don’t even challenge the true potential of an algorithm.
Try these custom test cases and see if you could pass them:
" 1 | 2 " in the output below means, either room 1 or room 2 can be used since they amount to the same value
"Custom Test Case 1"
Input
15
0 17 1 2
1 15 3 4
2 15 4 5
3 20 6 7
4 12 7 8
5 11 8 9
6 18 10 11
7 19 11 12
8 12 12 13
9 11 13 14
10 13 E E
11 14 E E
12 17 E E
13 19 2 E
14 15 E E
Output
127
0 => 1 | 2 => 4 => 8 => 13 => 2 => 5 => 9 => 14 => E
"Custom Test Case 2"
Input
15
0 17 1 2
1 15 3 4
2 15 4 5
3 20 6 7
4 12 7 8
5 11 8 9
6 18 10 11
7 19 11 12
8 12 12 13
9 11 13 14
10 13 E E
11 14 E E
12 17 E E
13 19 1 2
14 15 E E
Output
146
0 => 1 | 2 => 4 => 8 => 13 => 1 => 3 => 7 => 12 => E
To anyone of you who uses some variant of Dijstra-ish algorithm, I doubt these test cases will pass but let me know, I might be wrong - sometimes more than ever.
3 Likes
My Dijstra-ish algorithm fails, but I think that you would have to warp the space, to make that kind of room connections(13 19 1 2).
Dunno if it was Dijkstra-ish or not, but a simple recursive DFS got 56%, and doing it in reverse got 100. 150ms execution on the big puzzle using C#.
Indeed, the test cases seemed overly simple for me too!
I believe the confusion arises because the problem statement is not very clear.
This bit: Several doors can lead to one room but due to the layout of the building it is impossible for Bender to go through the same room twice.
What the author probably meant is that the room graph is topologically sortable (e.g. with no cycles).
It was hard to spot at the first glance. What I initially thought it meant is that I’m not allowed to go through the same room twice…
P.S. As it was stated somewhere above, the variant of the problem with cycles is general and is considered NP-hard, hence it would be unsolvable in a given amount of time for given constraints (N < 10000).
EDIT: Turned out, the topological sort is unnecessary because of trivial test cases and the fact that Bender always starts from room 0.
4 Likes