I implemented this without the deque, so standard visit problem with cycle detection (stop when you end up in a tile that you alredy visited while going in a direction that is the same as the current direction). The fun thing is that it exceeded recursion limit at first. Then I increased the recursion limit with sys a little bit, and it worked also for part two. I laughed pretty hard at this one.
Recursive grid walking with visit detection got me into 48 levels of recursion max and it finishes calculating part 2 in ~0.98 seconds (TypeScript) P.S. to check max depth just add a 'depth' arg for recursive function and pass a "depth + 1" in this arg in recursive calls. Then save it to a global 'maxDepth' (when it exceeds prev max value) and print out in the end ^^
For your part 2: when you loop over columns, you should check for len(grid[0]), not len(grid). It works in this case because the grid is a perfect square. I'm sure it was just a typo tho. Loving these videos!
I'm pretty sure it's necessary to avoid getting stuck in loops. If you have a square of mirrors all pointing at each other and there's a beam splitter along the "edge" of the square, then you can get stuck in a loop if you don't check for (r, c, dr, dc) in seen.
@@ibraheemahmed1670yup, I spent an hour trying to figure out why I kept looping. Forgot to check to see if the beam was already seen before adding it to the deque
Unedited solve is available: ruclips.net/video/UkZiKyCdzdE/видео.html
I implemented this without the deque, so standard visit problem with cycle detection (stop when you end up in a tile that you alredy visited while going in a direction that is the same as the current direction). The fun thing is that it exceeded recursion limit at first. Then I increased the recursion limit with sys a little bit, and it worked also for part two. I laughed pretty hard at this one.
Recursive grid walking with visit detection got me into 48 levels of recursion max and it finishes calculating part 2 in ~0.98 seconds (TypeScript)
P.S. to check max depth just add a 'depth' arg for recursive function and pass a "depth + 1" in this arg in recursive calls. Then save it to a global 'maxDepth' (when it exceeds prev max value) and print out in the end ^^
For your part 2: when you loop over columns, you should check for len(grid[0]), not len(grid). It works in this case because the grid is a perfect square. I'm sure it was just a typo tho. Loving these videos!
Good catch! Yes, you're right, just a typo lol. Was lucky that it was a square grid
My solution was same, except for 1. it was in rust and 2. I ran the simulations in parallel, hence it completed in about 10ms
seen is a set. Is the check for (r, c, dr, dc) in seen not necessary?
I'm pretty sure it's necessary to avoid getting stuck in loops. If you have a square of mirrors all pointing at each other and there's a beam splitter along the "edge" of the square, then you can get stuck in a loop if you don't check for (r, c, dr, dc) in seen.
@@ibraheemahmed1670yup, I spent an hour trying to figure out why I kept looping. Forgot to check to see if the beam was already seen before adding it to the deque