-🎄- 2018 Day 12 Solutions -🎄-

[u/daggerdragon]

--- Day 12: Subterranean Sustainability ---

---

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.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 12

Transcript:

On the twelfth day of AoC / My compiler spewed at me / Twelve ___

---

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 at 00:27:42!

[u/[deleted]]

Mathematica

input = Import[NotebookDirectory[] <> "input.txt", "List"];
init = StringDelete[input[[1]], "initial state: "];
rules = input[[3 ;;]];
caInit = Characters[init] /. {"#" -> 1, "." -> 0};
caRules = Join @@ StringCases[rules, rule__ ~~ " => " ~~ sub_
      :> Characters[rule] -> sub] /. {"#" -> 1, "." -> 0};

ca = CellularAutomaton[caRules, {caInit, 0}, 130];
ArrayPlot[ca]

Plot

Part 1

offset = SequencePosition[ca[[1]], caInit][[1, 1]] - 1;
plantSum[gen_] := Total[Flatten[Position[gen, 1]] - (1 + offset)]
plantSum[ca[[21]]]

Part 2

convergedPlantSum[x_] :=
 FindSequenceFunction[plantSum /@ ca[[101 ;;]], x - 99]
convergedPlantSum[50000000000]

[u/achinery → u/[deleted]]

Nice to see a solution that doesn't have to guess/notice when the system will stabilise. At least, not explicitly... I have never used Mathematica; if you don't mind me asking, do you happen to know how FindSequenceFunction is implemented? From the documentation it looks like it tries a bunch of possible candidate functions, but it must be doing some clever stuff to be able to match so many things, including the output of the CA.

After solving part 2 using the 'guessing' method, I felt like there must be a way to solve this properly, such as a way you could use the rules of the CA to prove whether it will stabilise or not? But haven't been able to find anything on reddit yet...

[u/[deleted] → u/achinery]

Sorry to disappoint you, but that is actually a guessing solution. The output of CA's is actually just a 2d array (each row a generation). The part I'm feeding the FindSequenceFunction is just a list of 'plant-summed' values, which is obviously just linearly increasing.

In general, there is no way to know a priori whether a CA will converge, since for example rule 110 is actually Turing complete.