The idea of just rotating the grid is clever. I wrote two functions for tilting east/west and north/south, respectively, as it seemed less like a hassle than trying to combine both into one function. For the timeskip, instead of storing the times in a dict, I just stored all grids in an array. Since I've already computed the final grid at the point the repetition is discovered, I can just index the array at the index computed via modulo. The dict approach is probably faster, though, because of the O(1) average complexity of membership testing.
Yet another approach I used was to only implement roll_up and roll_down and then transpose the grid accordingly, this way you only have to implement 2 instead of 4 functions. Like this: ```python3 def cycle(grid) -> list[list[str]]: roll_up(grid) # north grid = transpose(grid) roll_up(grid) # west grid = transpose(grid) roll_down(grid) # south grid = transpose(grid) roll_down(grid) # east grid = transpose(grid) return grid ```
I wanted to do the rotate as that would have been easier, but thought it would be too processing intensive. I decided to try at doing what you did but used only one function. Although its a short function the conditionals are brutal x 1000000000. I was surprised it even worked. If I look back at it a day from now I know for a fact I would not recognize it was me that wrote that or what in the world it was doing.
After solving it the kinda confusing (for me) mathematical way, someone told me they got it working just trying the bruteforce method with dynamic programming. I had tried that earlier but did something wrong and it didn't work. Tried it again and it took 5 minutes. Then I realised I could "loop unroll" it and do e.g. 100 cycles, store the result in the DP table, then increase the cycle count by 1000. Because it enters a loop of already-seen states very quickly, you end up looping and just looking up the DP table 1 million times, which takes like 3 seconds.
I was maybe too anxious that the score wasn't a suitable way to determine if a cycle was occuring so hashed the grid after every rotation and looked for a repeated hash. I probably find the cycle in fewer iterations, but each iteration takes longer.
I just did the outputs of each iteration and then manually checked the repetition. For me it started to repeat after 100 iteration with a period of 9. So 109 cycles it is because (1_000_000_000 % 9) is 0, so no extra cycles would be added.
By the nature of this problem, I think that if you use the grid layout to detect the cycle you can derive the numbers after the first repetition. Since you are always doing the same operations on the same order, if you do them on the same grid it will give you the same result. (a lot of same, I know)
Yes; I added each grid to a map, along with the step where it was first seen. When a collision is found, we know the current step number, the offset where the loop began and the length of the loop, which is enough to calculate a point in time to jump forward to. Then I just continued the loop until reaching the target step count, although it might have been smarter to also store the reverse map of step number -> grid and use that to get the final state in one step.
crazy fast my cycle period was 22 so I had trouble spotting it in the output I used a hash { sequence => cycle_number } where sequence = [score_N, score_W, score_S, score_E]. Once I got a sequence that was already in the hash, it meant it had started repeating
Mine was 36, lol. I didn't even realize it looped before submitting. I just saw that 1000 and 10,000 iterations returned the same load, so I submitted that
If anything I need to learn to submit the answer ( even if do stuff manually ) rather than have working code outputting both numbers xD Btw, for rolling north efficiently, process column top to bottom, keep count of Os seen and last wall index, when you see a wall (#), place the count of Os starting from last hash index. ( Somewhat like computing runs of array, so the additional detail is to be careful for the last set of runs, so need to imagine walls at index -1 and n )
"How is this even working?" Yeah, that's a familiar feeling.
The idea of just rotating the grid is clever. I wrote two functions for tilting east/west and north/south, respectively, as it seemed less like a hassle than trying to combine both into one function. For the timeskip, instead of storing the times in a dict, I just stored all grids in an array. Since I've already computed the final grid at the point the repetition is discovered, I can just index the array at the index computed via modulo. The dict approach is probably faster, though, because of the O(1) average complexity of membership testing.
Yet another approach I used was to only implement roll_up and roll_down and then transpose the grid accordingly, this way you only have to implement 2 instead of 4 functions. Like this:
```python3
def cycle(grid) -> list[list[str]]:
roll_up(grid) # north
grid = transpose(grid)
roll_up(grid) # west
grid = transpose(grid)
roll_down(grid) # south
grid = transpose(grid)
roll_down(grid) # east
grid = transpose(grid)
return grid
```
I wanted to do the rotate as that would have been easier, but thought it would be too processing intensive. I decided to try at doing what you did but used only one function. Although its a short function the conditionals are brutal x 1000000000. I was surprised it even worked. If I look back at it a day from now I know for a fact I would not recognize it was me that wrote that or what in the world it was doing.
After solving it the kinda confusing (for me) mathematical way, someone told me they got it working just trying the bruteforce method with dynamic programming. I had tried that earlier but did something wrong and it didn't work. Tried it again and it took 5 minutes. Then I realised I could "loop unroll" it and do e.g. 100 cycles, store the result in the DP table, then increase the cycle count by 1000. Because it enters a loop of already-seen states very quickly, you end up looping and just looking up the DP table 1 million times, which takes like 3 seconds.
I was maybe too anxious that the score wasn't a suitable way to determine if a cycle was occuring so hashed the grid after every rotation and looked for a repeated hash. I probably find the cycle in fewer iterations, but each iteration takes longer.
I did the same - hashing the grid state, and looking for a repeat.
I just did the outputs of each iteration and then manually checked the repetition.
For me it started to repeat after 100 iteration with a period of 9. So 109 cycles it is because (1_000_000_000 % 9) is 0, so no extra cycles would be added.
On the other hand, I like that grid problems greatly simplify parsing :P
By the nature of this problem, I think that if you use the grid layout to detect the cycle you can derive the numbers after the first repetition. Since you are always doing the same operations on the same order, if you do them on the same grid it will give you the same result. (a lot of same, I know)
Yes; I added each grid to a map, along with the step where it was first seen. When a collision is found, we know the current step number, the offset where the loop began and the length of the loop, which is enough to calculate a point in time to jump forward to. Then I just continued the loop until reaching the target step count, although it might have been smarter to also store the reverse map of step number -> grid and use that to get the final state in one step.
crazy fast
my cycle period was 22 so I had trouble spotting it in the output
I used a hash { sequence => cycle_number } where sequence = [score_N, score_W, score_S, score_E]. Once I got a sequence that was already in the hash, it meant it had started repeating
Mine was 36, lol.
I didn't even realize it looped before submitting. I just saw that 1000 and 10,000 iterations returned the same load, so I submitted that
@@chjabr0010 Why are everyone getting different periods? Mine was 34.
If anything I need to learn to submit the answer ( even if do stuff manually ) rather than have working code outputting both numbers xD
Btw, for rolling north efficiently, process column top to bottom, keep count of Os seen and last wall index, when you see a wall (#), place the count of Os starting from last hash index. ( Somewhat like computing runs of array, so the additional detail is to be careful for the last set of runs, so need to imagine walls at index -1 and n )
ohhhhh you can just rotate!! i wrote 4 shifts and it took ages but i have a grid util which could have just rotated for me
3:10 is there no way in python to walk backwards through a range? And damn you are lucky with a 9 cycle, my cycle is 70.
I think you can do `reversed(range(limit)):`
range(len(arr), -1, -1) range(start, excluded_end, step)
I think that the problem converges after about 1000 iterations. At least for my input doing 1k was enough
Mine started repeating after about 140 iterations. I break when I see a grid repeated.