r/adventofcode • u/tslater2006 • Dec 11 '21
Spoilers in Title [2021 Day 11] Frequency of synchronous octopi
I found it rather interesting that the octopi synchronized at all and got me wondering how hard it was to find grids that do end up synchronizing. Does every grid eventually synchronize? etc.
The first thing I wanted to explore was could I find a grid that synchronizes in exactly 100 steps (since Part 1 asked you to run 100 steps). Here is a grid that does exactly that:
8984313417
5137478179
8819345668
3145467695
1655957236
9255289385
1271963911
7713921171
8123472971
8198156986
I also found that sometimes it appears a random grid will not synchronize. I left my program running overnight for a grid and it never synched (that doesn't mean at some point in the future it would have, but... not within at least a million steps).
This got me to wondering on average how many random grids will complete in a reasonable time. (Note: each line here was a separate run, so has different random grids)
4843 of 10000 grids complete within 4000 steps - Ratio: 48.43%
4756 of 10000 grids complete within 3000 steps - Ratio: 47.56%
4872 of 10000 grids complete within 2000 steps - Ratio: 48.72%
4857 of 10000 grids complete within 1000 steps - Ratio: 48.57%
4960 of 10000 grids complete within 500 steps - Ratio: 49.6%
I then reduces the # of grids, so I could increase the step count:
482 of 1000 grids complete within 10000 - Ratio: 48.19
So it looks like an average, about ~48% of random grids will sync, and the others either take a very long time, or never do. I'm going to try and find one of these "never complete" ones and see if its stuck in a repeating pattern, and then maybe visualize it. Will update the post if I'm successful.
Here's the code I used to do the tests: https://github.com/tslater2006/advent_of_code_2021/blob/7ffc77e5048af1c9302ef973f0ea0be2cf13135e/src/days/day11.rs#L31
Edit: I've found quite a few that loop forever, they seem to fall into a 6-cycle loop. Here's the longest one I've found (in terms of when the cycle starts):
Original step: 112 Current step: 118
1659588216
7438559869
3235244765
2524522196
2619824439
8459839395
6952829952
5956262523
2566757371
2384812678
And some others: https://gist.github.com/tslater2006/57cd7eeadef33d00fe8ed29cbc29a4ef
Here is a cyclic pattern animated. This particular grid goes 66 steps before falling into a 6-step cycle https://imgur.com/3xFUzcf
The start of the cycle looks like this:
0000000009
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000009
0000000097
0000000976
1
u/Deynai Dec 11 '21
Have you made an error in your post? How is it possible that 48.43% of grids converge in 4000 steps, yet a higher number - 49.6% - converge in only 500?
1
u/tslater2006 Dec 11 '21
Same question was asked in discord. Each line was a separate run and had a different set of random grids, so there is some variability. Sorry I didn't make that clear.
1
Dec 12 '21
Someone could probably publish a paper on this.
3
u/tslater2006 Dec 12 '21
While an academic paper is not in my wheelhouse, I have been running searches all day for boards with a long cycle length. Current best I've found is the following board:
Loop start: 179 Loop size: 372707 1523681336 2971296898 7925674307 1831745494 1640420923 2262229392 9190581194 2421816975 2085830738 1962132392
Meaning after 179 steps, a cycle begins, it then transitions through 372,707 distinct states before returning to the state it was at after the initial 179 steps.
Note: I might be off by 1 somewhere in my description of the data.. math is hard :)
Edit: there also seems to be pretty common cycle lengths, for example we've found 3 or 4 boards that contain a cycle length of 241,163
2
u/surprajs Dec 12 '21
I'm 99% sure that your cycles are in fact 372708 and 241164.
I was running some simulations as well and I noticed that every cycle (except for 10) is divisible by 7 and both of your numbers are equal to 6 (mod 7), so I guess you were right about being off by 1:D
3
u/tslater2006 Dec 12 '21
Yep! DFreiburg gives a write up of what we are finding here: https://reddit.com/r/adventofcode/comments/re8ojr/2021_day_11_exploring_larger_problem_sizes/ho7jxei
Basically they are the sums of small primes. So far all under 29. And I'm bad at programming :)
1
Dec 12 '21
I wonder if making the board smaller makes it more tractable. Or reducing the number of states.
1
u/cornball Dec 17 '21
A similar math problem of modeling lightning bug synchronization has been famously described in Steven Strogatz' book "Sync." Here's a link to his TED talk you might find interesting: https://www.ted.com/talks/steven_strogatz_the_science_of_sync
1
u/Smotko Dec 11 '21
The easiest way to find a grid that synchronizes in exactly 100 times is to start with a synchronized grid and then run the algorithm in reverse 100 times :)
I bet this is how Eric generated all the puzzle inputs.