Really appreciate the video! I'm hoping to see you climb the leaderboard once the puzzles are getting too hard for the LLM bro's to solve in 10 seconds.
Hi @jonathanpaulson, Thank you so much for sharing the code - I really appreciate your work! I noticed that there might be a missing test case: an obstruction should not be placed at the guard's starting position. I came across this scenario while testing with my input. Just wanted to bring this to your attention.
I confirmed this was a bug in my solution. Fortunately my input didn't have this case, so my answer was accepted anyway. Did your input have this case?
A real quick optimization: figure out the unobstructed path like in part one and then only place obstacles on those parts of the path, since otherwise the guard will not touch that spot. This speeds it up by about 5x on my input.
Another idea: maybe you could represent each (obstacle, direction) as a node in a graph and you can then model it as state transitions where you move directly from one obstacle to another. This may simplify/speed up the problem a bit...
Thats a good idea. Another idea I implemented was to precalculate the guard states for every obstacle, for every approaching direction. So we can just skip from obstacle to obstacle, or out of the map. EDIT: rather than precomputing the map all the time I tried doing partial updates (since 99% of the map state is always idendical). This speeds up my solution quite a bit. Running on the full map (130*130=16900 updates) takes 500ms and running only on the original path fields (4903 updates) runs in 140ms.
i also brute forced it, but my original idea was to check line of sight, and if the guard has seen the wall from the same position it. means it is stuck, but couldn't really implement it!
What's your opinion about all the LLM people on the leaderboard? As a sponsor and a long time member of the community, do you think something needs to be done about it?
It's pretty frustrating and has definitely marred the experience for me this year. OTOH, I sympathize with the idea that this is a fundamentally unsolvable problem and the organizers don't want to start an unwinnable fight. If it were up to me, I would take some low-effort steps like re-announcing more visibly that AI use is not allowed, maybe manually removing of the most egregious offenders from the leaderboard, and maybe making it harder to programmatically download the problem statements somehow (I don't really see a good use case for downloading the problem statements from a script other than feeding them to an LLM).
i feel so stupid, i wasted HOURS on part 2... while doing the initial simulation, counting the steps, i also simulated at each step if putting an obstruction on the next coordinate would cause a loop. i did not realize the obstruction has to be placed before the guard starts moving at all 🤦♂
II had corners in my input, where I had to turn twice at the same position to solve part 2 correctly. I cannot see that your code handles this case - did you not encounter that in your input data?
@@jonathanpaulson5053 I do the same in my cache, but the "if G[rr][cc]=="#" or rr==o_r and cc==o_c": line for my input only yields the correct result if i switch the "if" to a "while"?
Ah, now I get it. You do not update the position in the else - i do not have that. This means that I do not cache the intermediate turn state, but that does not make a difference here I follow your videos every year and always look for you on the leader board first thing - good luck this year :-).
Really appreciate the video! I'm hoping to see you climb the leaderboard once the puzzles are getting too hard for the LLM bro's to solve in 10 seconds.
Im super impressed how fast you can solve these!
The last samurai fighting the lllms 😅.
Hi @jonathanpaulson,
Thank you so much for sharing the code - I really appreciate your work! I noticed that there might be a missing test case: an obstruction should not be placed at the guard's starting position.
I came across this scenario while testing with my input. Just wanted to bring this to your attention.
good point I think this may be a bug in my solution
I confirmed this was a bug in my solution. Fortunately my input didn't have this case, so my answer was accepted anyway. Did your input have this case?
@@jonathanpaulson5053 Yes my input had this case
Damn we didn't hear "Day 6, what's going on.."
A real quick optimization: figure out the unobstructed path like in part one and then only place obstacles on those parts of the path, since otherwise the guard will not touch that spot. This speeds it up by about 5x on my input.
Good idea. I see the same ~5x speedup
Another idea: maybe you could represent each (obstacle, direction) as a node in a graph and you can then model it as state transitions where you move directly from one obstacle to another. This may simplify/speed up the problem a bit...
Hashing the tuples (r,c,d) before adding to the SEEN sets also helps with speed for part2.
this is exactly what i did and it took over 30 minutes for pypy to run lol
Thats a good idea. Another idea I implemented was to precalculate the guard states for every obstacle, for every approaching direction. So we can just skip from obstacle to obstacle, or out of the map.
EDIT: rather than precomputing the map all the time I tried doing partial updates (since 99% of the map state is always idendical). This speeds up my solution quite a bit. Running on the full map (130*130=16900 updates) takes 500ms and running only on the original path fields (4903 updates) runs in 140ms.
Came here to see what I'd done wrong when mine took 37s to run (in perl, I am old!). I don't feel so bad now.
i also brute forced it, but my original idea was to check line of sight, and if the guard has seen the wall from the same position it. means it is stuck, but couldn't really implement it!
What's your opinion about all the LLM people on the leaderboard? As a sponsor and a long time member of the community, do you think something needs to be done about it?
It's pretty frustrating and has definitely marred the experience for me this year. OTOH, I sympathize with the idea that this is a fundamentally unsolvable problem and the organizers don't want to start an unwinnable fight.
If it were up to me, I would take some low-effort steps like re-announcing more visibly that AI use is not allowed, maybe manually removing of the most egregious offenders from the leaderboard, and maybe making it harder to programmatically download the problem statements somehow (I don't really see a good use case for downloading the problem statements from a script other than feeding them to an LLM).
i feel so stupid, i wasted HOURS on part 2...
while doing the initial simulation, counting the steps, i also simulated at each step if putting an obstruction on the next coordinate would cause a loop.
i did not realize the obstruction has to be placed before the guard starts moving at all 🤦♂
Great solve, really impressive how quick you came up with this solution!
What cpu / setup are you running this on?
II had corners in my input, where I had to turn twice at the same position to solve part 2 correctly. I cannot see that your code handles this case - did you not encounter that in your input data?
It does handle it. That’s the point of including the current direction in the SEEN map.
@@jonathanpaulson5053 I do the same in my cache, but the "if G[rr][cc]=="#" or rr==o_r and cc==o_c": line for my input only yields the correct result if i switch the "if" to a "while"?
Ah, now I get it. You do not update the position in the else - i do not have that. This means that I do not cache the intermediate turn state, but that does not make a difference here
I follow your videos every year and always look for you on the leader board first thing - good luck this year :-).
im trying since 2h ago can you tell me answer please ?
"She"...