In this document, "cycle" means North-West-South-East move once, and "loop" means the repeating pattern after some amount of cycles are run. "Loop length" the number of cycles needed to obtain the loop, and call a pattern "length X loop" meaning it will repeat the end state after every X cycles.
So, here's my basic item. Call it Q0.
.##.
#.O#
#..#
.##.
Pretty straightforward length 1 loop in 4x4.
Take four of Q0 arrange in a square, break off two # to connect them into a big loop. Call this Q1, a length 3 loop in 7x7:
.##.##.
#.O#..#
#.....#
.#...#.
#.....#
#..#..#
.##.##.
Now take two of Q1, arrange together, break off two # to connect together. This is D1, length 3+3-1 = 5 loop in 13x7:
.##.##.##.##.
#.O#..#..#..#
#.....#.....#
.#...#.#...#.
#...........#
#..#.....#..#
.##.##.##.##.
So I can put two Q1 and one D1 together, produces this length 15 loop in 13x13, called X2:
.##.##.##.##.
#.O#..#.O#..#
#.....#.....#
.#...#.#...#.
#.....#.....#
#..#..#..#..#
.##.##.##.##.
#.O#..#..#..#
#.....#.....#
.#...#.#...#.
#...........#
#..#.....#..#
.##.##.##.##.
What if I connect 4 copies of Q1? We now have a length 3*4-1 = 11 loop in 13x13, this is Q2:
.##.##.##.##.
#.O#..#..#..#
#.....#.....#
.#...#.#...#.
#.....#.....#
#..#.....#..#
.##.#...#.##.
#..#.....#..#
#.....#.....#
.#...#.#...#.
#.....#.....#
#..#..#..#..#
.##.##.##.##.
Put X2 and Q2 together but don't break any bricks. A length 15*11 = 165 loop in 27x13, called Y2:
.##.##.##.##.##.##.##.##.
#.O#..#.O#..#.O#..#..#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#
#..#..#..#..#..#.....#..#
.##.##.##.##.##.#...#.##.
#.O#..#..#..#..#.....#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#...........#.....#.....#
#..#.....#..#..#..#..#..#
.##.##.##.##.##.##.##.##.
Connect two Q2, we have a length 11+11-1 = 21 loop in 27x13, called D2:
.##.##.##.##.##.##.##.##.
#.O#..#..#..#..#..#..#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#
#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#...........#.....#
#..#..#..#.....#..#..#..#
.##.##.##.##.##.##.##.##.
Put Y2 and D2 together. This is X3, length 1155 loop in 27x27:
.##.##.##.##.##.##.##.##.
#.O#..#.O#..#.O#..#..#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#
#..#..#..#..#..#.....#..#
.##.##.##.##.##.#...#.##.
#.O#..#..#..#..#.....#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#...........#.....#.....#
#..#.....#..#..#..#..#..#
.##.##.##.##.##.##.##.##.
#.O#..#..#..#..#..#..#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#
#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#
#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.
#.....#...........#.....#
#..#..#..#.....#..#..#..#
.##.##.##.##.##.##.##.##.
Now you see the pattern.
Here's a recap:
- Q0, length 1 loop in 4x4.
- Connect four Q0 => Q1, length 3 loop in 7x7
- Connect two Q1 => D1, length 5 loop in 13x7 (3+3-1)
- Two Q1 + D1 => X2, length 15 loop in 13x13 (LCM(5,3))
- Connect four Q1 => Q2, length 11 loop in 13x13 (3+3+3+3-1)
- X2 + Q2 => Y2, length 165 loop in 25x13 (LCM(15,11))
- Connect two Q2 => D2, length 21 loop in 25x13 (11+11-1)
- Y2 + D2 => X3, length 1155 loop in 25x25 (LCM(165,21))
This pattern can continue on:
- Connect four Q2 => Q3, length 43 loop in 25x25 (11+11+11+11-1)
- X3 + Q3 => Y3, length 49,665 loop in 49x25 (LCM(1155,43))
- Connect two Q3 => D3, length 85 loop in 49x25 (43+43-1)
- Y3 + D3 => X4, length 844,305 loop in 49x49 (LCM(844305,85))
- Connect four Q3 => Q4, length 171 loop in 49x49 (43+43+43+43-1)
- X4 + Q4 => Y4, length 48,125,385 loop in 97x49 (LCM(844305,171))
- Connect two Q4 => D4, length 341 loop in 97x49 (171+171-1)
- Y4 + D4 => X5, length 1,491,886,935 loop in 97x97 (LCM(48125385,341)) -- This won't even finish one loop when the 1 billion cycles specified in the problem are done!
I even have three rows and columns to spare!
My (pretty naive) solution is already struggling with Y3 (length 49,665 loop), mostly because I store full board to compare states.
Here's X5 in its full glory, 97x97:
.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
#.O#..#.O#..#.O#..#..#..#.O#..#..#..#..#..#..#..#.O#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.##.##.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#.O#..#..#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#...........#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
.##.##.##.##.##.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.
#.O#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#...........#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#.....#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#
.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.#...#.##.##.##.##.##.##.##.
#.O#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#...........#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#
.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.
#.O#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#
.##.##.##.##.##.##.##.#...#.##.##.##.##.##.##.##.##.##.##.##.##.##.##.#...#.##.##.##.##.##.##.##.
#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.##.##.##.#...#.##.##.##.
#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#..#..#..#.....#..#..#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.##.#...#.##.
#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#..#.....#..#
#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#.....#
.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.#...#.
#.....#.....#.....#.....#.....#.....#.....#...........#.....#.....#.....#.....#.....#.....#.....#
#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#.....#..#..#..#..#..#..#..#..#..#..#..#..#..#..#..#
.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.##.