Different from @popa.bogdanp I mean
Before reading others, my solution was to create (essentially) a 3D array of pair x step x char counts as a giant lookup/hash table.
For example, “CB” after 3 steps would produce 2 new B’s, 4 H’s and 1 new C. This is constant and will never change. So - at parse time - I simply build a tree where each pair links to the 2 new pairs (left/right) it creates at runtime. Then for the initial string, I just walk all the pairs and add what it creates to the original counts in the template.
https://github.com/massung/advent2021/blob/main/day14/day14.lisp
Part 2 runs in ~10 ms.
I think @popa.bogdanp and I came pretty close in our solutions.
I ended up porting mine towards Bogdans, since my initial version was too slow. I was surprised that memoizing the pair->new-pairs transition (with rules mapping pair->insertion) was vastly slower than just having rules map pair->new-pairs. I expect some slowdown, but it was infeasibly slow
<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day14/day14.rkt|Day 14> - all sorts of interruptions today, but I enjoyed it once I was able to get into it.
50,000 iterations is 28 seconds and produces <https://gist.githubusercontent.com/lojic/4340219df3f56145c06390f7f5c31be7/raw/8c52b367ef4200c1413327eb4969bcd2831e63ad/big%2520number|this number> :) Part 2 is ~ 12 ms
Day 15 spoilers
Gonna clean code in the morning, but anyone who’s coded A* before pretty much had this in the bag from the get-go. The wording of the tiling on part 2 tripped me up due to skimming.
I also did A*, but I had to take a break before part 2 so I lost some points there. I’ll also post mine after some cleanup :smile:
Edit: <https://github.com/Bogdanp/aoc2021/blob/master/day15.rkt|here’s >mine.