Blunder - Episode 2 - Puzzle discussion

Puzzles
#21

I am using a BFS, each unvisited node updates its sum to the maximum of its parents’ sum added to the node’s money. My algorithm works for all cases except the square building case, where it outputs 39. very weird behavior. anyone got a clue ? thanks

#22

okay so i think my algorithm works only on special cases of layouts … because for the square building you can either go from 0 to 39 through one door 0->39 or 0->1->2->3 … -> 37 -> 38 -> 39 … with bfs when it calculates the max of 39’s parents it will be max(1,0) since 38 wouldnt be calculated by that time…
I heard topo sort is one way… but i dont understand it ?

EDIT: okay i found it, the solution was very simple… just a dfs

1 Like
#23

how to do it in reverse?

#24

Just like it sounds… instead of doing pathfinding from the entrance to the various exits and picking one, you go from the exits to the entrance. You have to tweak the evaluation a bit but it’s the same basic concept.

My memory is fuzzy on why I did it that way, but I think it made it easier to cut out parts of the map and shave time.

I suspect it could be done the other way too, but in this case I found an answer that worked and moved on.

#25

oh, thanks very much…I’d been too stupid to ask this(though I finally made a little change to dfs and passed all the test but failed on TwistedWhisper’s two test cases)

#26

Dynamic Programming is even faster :smiley: 23 milliseconds(Javascript)

1 Like
#27

I arrived to the exact same solution :slight_smile:

I called it “cached recursion” but the right term for it I believe is “memoization” ("…In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again…")

A naive implementation (recursive function composed of 2 lines of code) worked perfect, but was way too slow because of the nature of the problem(s).

#28

I started doing a custom implementation of Dijkstra looking for longest path instead of shortest, but it was not working on all test cases, and it was awfully slow.
Then i realized by reading this thread and also checking that memoization and recursion was suggested by CG that a much simpler solution would work much better \o/

#29

Here’s the way I solve it.

At first, because the problem description said that we could use BFS and Dijkstra, I try to do something similar to Dijkstra. Except that, as anyone said, it doesn’t work for longuest path finding.
Does anyone manage to do some Dijkstra like algo?

Then, I did a BFS with the following logic: if the node I’m in was already visited with a higher score, I won’t explore this path any further.
With that logic, all tests pass, except the last one.
Funny thing is: by changing the BFS to a DFS, it works for all tests. That’s strange because it’s BFS that it’s advised in the description.

1 Like
#30

Description says “Some doors open in one direction only”. It presumes that there are 2-way doors, but in that case you could go back to the same room twice. So what?

#31

Dynamic Programming made this puzzle trivial. I spent more time on Don’t Panic v2 :slight_smile:

#32

I failed this one 2 years ago, tried it again this week, but I didnt’ know how to solve it fast enough. It was because I though that I had to check if Bender was going back to a previously seen room. I thought that there could be cycles in the graph, but I had to check that the longest path hadn’t any. And I think it’s an NP-complete problem, which is why my algorithm was so low. Because I had to store each path leading to a room and how many money there was on that path.

But when I saw that you were talking about problems in Project Euler, I understood that in fact that’s the structure of the graph that ensures that there is no cycle. From that, it was easy to solve it.

1 Like
#33

ahhh crap, when i read the statement : “due to the layout of the building it is impossible for Bender to go through the same room twice” i thought there must be loops within the rooms and Bender would have to find another way to get out of that loop if there’s one (bad english knowledge :stuck_out_tongue: )… it turns out it means that there’s no loops in the map. solved using simple dp :slight_smile:

which is for each room from the first one, we store the best total money we can find if we go to that room,
if we found a better total value of that room, upgrade the value of it and all the rooms after,
since there’re no loops, we don’t need to worry about running into an infinite runtime :smiley:
if we found an exit, store the value and keep upgrading the value if there’s a better value.

#34

I use a simple BFS, but I time out in 45% cases.
Any suggestions?
I was thinking of backtracking from the end, or maybe dynamic programming + backtracking.
Any help will be appreciated :slight_smile:

#35

To find the sum of money in many rooms, you can store partial addition results for reuse.
e…g.
if you have already calculated the sum of room1+room2, store it. When you need to calculate room1+room2+room3, you retrieve the existing [1+2] result to add to room3, instead of adding all over again.

#36

okay thanks a lot :slight_smile:

#37

I struggled a bit (okay, 2 bits…) with this puzzle, but in the end it turned out, the solution is much simpler than I thought midway.

Some unnecessary side-trip I took:

  • Instead of shortest path, we need maximum cost path -> let’s negate the weights -> but Dijkstra algorithm does not work for negative weights.
  • If deducting all weights from a BIG number, that keeps all weights positive, but in this case the solution is not correct, because result depends on the number of rooms involved in the path, not just the weights.
  • Implemented Floyd-Warshall algorithm based on wikipedia pseudocode. Fine results, works for negative weights, but timeouts at 5000 rooms because it is O(v^3) computational complexity.
  • Implemented Bellman-Ford algorithm (again, based on wikipedia pseudo code). Fine results, O(v * e) complexity, still timeouts.
  • Only then I realized, that a simple depth-first-search does the trick, if I store the best partial results for all rooms and trim the search tree if current moneypot is worse than the best found so far for the current room.

But at least now I have a bunch of generic graph algorithm implementations in PHP which I can reuse…

PS: After spending such excessive time on Bender Episode 2, I was surprised to see that Bender Episode 3 is completely unrelated and could be solved in 10 minutes…

1 Like
#38

I use Dijkstra’s algorithm too.However, I can’t pass the 55Room , the result I got is less than answer.I don’t understand what it wrong.

#39

At first I thought this task was perfect candidate for Dijkstra’s algorithm. It turned not that Dijkstra’s algorithm is not good to find the longest path in a graph, I still don’t quite understand why, maybe it is something related with NP-completeness, which not clear area to me. I’ll be happy if someone could refer some good and clear resource about NP-completeness. I think to read “Introduction to Algorithms” Book by Charles E. Leiserson and hope there are some nice explanations.

At the end the I solve the task with topologically sorting the Rooms and then iterate the sorted rooms and store the most money for each neighbor from the current Room (which is kind of Dijkstra iterating).

#41

I got the same problem! 348 instead of 358 ?