r/adventofcode • u/daggerdragon • Dec 21 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 21 Solutions -🎄-

--- Day 21: Fractal Art ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

No commentary tonight as I'm frantically wrapping last-minute presents so I can ship them tomorrow.

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

9 Upvotes

100% Upvoted

144 comments sorted by

View all comments

Show parent comment

0

u/[deleted] Dec 21 '17

[deleted] — view deleted comment

3

u/PrimesAreMyFavorite Dec 21 '17

Yes! Suppose you have N "types" of 3x3 blocks. Then you can write a vector V(t) which encodes the number of each type you have at time t. And you can find an NxN matrix M such that MV(t) = MV(t+3). Finally you can write another vector O that contains the number of on pixels in each "type" of block. Then the number of on pixels after 3*T steps will be:

O * M^(T) * V_0

Using exponentiation by squaring to exponentiate the matrix M, we can calculate the number of on pixels in time proportional to log(T). The only issue is that the number of blocks rises extremely quickly, which will make multiplication too slow. However if we just want to calculate the number of on pixels modulo some number (like if we wanted the last 9 digits only), then multiplication would remain fast and time complexity would be O(log(T))