AoC - Day 14

:date: 2023-12-14 12:00

Part One

This was a fun and interesting problem. And I just couldn't shake the feeling that i could use unix tricks to solve it. And I was right. Here is the solution to Part One.

$ for J in $(seq $(head -n1 $I|tr -d '\n'|wc -c));do cut -c$J $I|awk '{C[NR]=$1}END{E=1;for(i=0;i<=NR;i++){if(C[i]=="#")E=i+1;else if(C[i]=="O"){if(E<i){C[i]=".";C[E]="O"}E=E+1}}for(i=1;i<=NR;i++)print(C[i]=="O")?NR-i+1:""}'|awk '{X+=$1}END{print X}';done|awk '{X+=$1}END{print X}'

That ran in 549ms for me. It may seem like opening all these processes and subshells will be a disaster but in reality, it helps to distribute the whole solution over multiple cores in parallel. That's why it's ok, for example, that there's a second Awk line just to sum up each column value, and a third to sum all the columns.

Part Two

I was originally not planning to touch Part Two. But its mechanics seemed like something that I'd already done. I'd already written a transposing program yesterday; shouldn't be too hard to make it rotate the whole grid. And then just apply Part One.

Sounds easy! But in reality it was quite a chore to put all this together. But I did it! It wasn't really feasible to run the 1e9 iterations asked for (I projected 2.8 years needed) but I got the idea that maybe the system would reach some kind of periodic equilibrium much quicker than that.

Finally I got the rotating working using a simple 2d array switching in Awk and rewrote Part One to now return the whole grid. I then wrote a specific scoring script. Then I put it all together in a very interesting circular pipe loop.

IO=$(cat $I);for N in $(seq 4001); do for NWSE in $(seq 4); do IO=$(./script14b.awk <<<$IO | ./rotateCW ); done; done; ./script14-sum.awk <<<$IO

I've never done  —  or seen!  —  anything like that before.

I couldn't quite wait for the final answer, but I have a correct program that can, in theory, find it. I also know the answer is around 90780.

Ok, letting that run in various ranges over night was illuminating. It also was strangely not especially taxing to my system; pipelines are generally quite effective at spreading the load to multiple cores in a transparent way. There's a reason the early unix guys came up with this approach just as they were exploring how to control a multi-process system.

Anyway, I noticed a period where the state would repeat after 26 iterations. I had one sequence running at 500 step intervals and it also had a period, of 13. Extrapolating out to the billion came up with the correct answer! (90928)