IM GONNA SAY IT :marseyraging:

>be me, day 16 of AOC

>write a solution to part one that only considers nodes with values > 0

>runs pretty quickly, could be better

>get to part two, considering two players

>:marseyclueless: obviously it is equivalent to a single player playing the game twice and not visiting previously visited nodes, right?

>try solution on test input, doesn't work

>shit, forgot about the case where the players run out of time before reaching the end

>rewrite algorithim for two players (tedious af)

>press run

one eternity later

>shit, guess I need to improve the algorithim

>rewrite the algorithm to use a matrix of distances instead of recomputing the distance each time

>part 1 runs 21x faster :marseywholesome:

>:marseyclueless: surely this is the correct implementation

one eternity later

>what the frick do they want from me

>how could i possibly do this any faster

>wonder if there is a linear time solution i'm missing

>scrawl a page of nonsense with matrices, realize that none of it matters because it would be running slower than my interpretation

:#marseygiveup:

>fine, i'll check the solution thread on rdrama

>see a comment from @ihsoy

I solve part two simply by dfs through the part once, and then if time gets to zero, i restart the dfs.

>wtf, that doesn't work, i already tried that on the test input

>try it on the actual input

>mfw it works

>mfw i wasted hours because the test input was nothing like the actual input

I'M GOING TO KILL YOU SANTA CLAUS!!!!!!!!!!!

75
Jump in the discussion.

No email address required.

mfw i wasted hours because the test input was nothing like the actual input

It works on test input of course. Something tells me that you parsed it by hand and made a mistake.

Jump in the discussion.

No email address required.

:marseyconfused: pretty sure it doesn't. The problem is that in the test input, you can get to all (or most) the nodes before time runs out, which means that on your first pass player 1 gets all but one of the nodes, leaving just one for the elephant, which isnt optimal

Jump in the discussion.

No email address required.

Oh, I see.

Jump in the discussion.

No email address required.

:#marseyembrace:

Jump in the discussion.

No email address required.

I saw something on 4chan that if you're lucky your input can be split in two like this. Then the first DFS goes right and the second left without interfering

![](/images/16712756079133458.webp)

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.