:date: 2023-12-14 12:00
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}'
109755That 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.
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 <<<$IOI'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)