AoC2020 Days 8 to 12

2020-12-12

Unfortunately I did not have much time to report on the last batch of puzzles. In part, because they became somewhat harder and thus needed more of my free time to be resovled :)

Day 8 required building an interpreter for a simple, 3-operations code (and finding the one instruction that needed to be modified for it not to loop indefinitely: interesting!); day 9 was fairly simple, as it was purely integer manipulation, though I did need to use package bit64 as the integers were too large for base R which thus relied on floating-point integer (which is not precise enough naturally).

Day 10 was the first one I wasn't able to "brute-force" and thus was a bit more interesting! Basically we had a chain of integer were each integer could only be separated by 1, 2 or 3; and we needed to figure out the number of possible paths between the smaller and the bigger one. At first i tried to solve that using igraph by turning the problem into a graph and calculating the number of possible paths but it crashed my laptop! As it turned out, it was solvable algebraically. None of the integer were separated by 2 meaning we had a serie of numbers separated by 1 or 3. The ones separated by 3 are not skippable given we can't connect to number separated by more than 3, so the problem in the hand was subsettable into figuring out the number of paths that was possible in each serie of numbers separated by only a single unit. There were no series longer than 5, as it turned out. So the number of possibilities were 7 for a series of 5 consecutive integers:

0 - 3 - 4 - 5 - 6 - 7 - 10
0 - 3 - 4 - 5 - 7 - 10
0 - 3 - 4 - 6 - 7 - 10
0 - 3 - 5 - 6 - 7 - 10
0 - 3 - 4 - 7 - 10
0 - 3 - 5 - 7 - 10
0 - 3 - 6 - 7 - 10

4 for a series of 4 integers:

0 - 3 - 4 - 5 - 6 - 9
0 - 3 - 4 - 6 - 9
0 - 3 - 5 - 6 - 9
0 - 3 - 6 - 9

2 for a series of 3:

0 - 3 - 4 - 5 - 8
0 - 3 - 5 - 8

And that's all! Meaning the number of paths was 7^(# of series of 5)*4^(# of series of 4)*2^(# of series of 3). Or in R:

options(digits=22) #Prevents R from displaying integers in scientific notation.
input <- scan("input10.txt")
chain <- c(0,sort(input),max(input)+3) #Minimum was 0 and Max was the max of the list plus 3
r <- rle(diff(chain)) #Run Length Encoding: returns a list of lengths and values, i. e. 1 1 1 1 becomes l=4, v=1
7^sum(r$l==4&r$v==1)*4^sum(r$l==3&r$v==1)*2^sum(r$l==2&r$v==1) #r$l==4 as we are working on differences, so 4 means 5 consecutive numbers

The option to display a large amount of digits was necessary as the result (in my case) was a staggerring 193 434 623 148 032. No wonder the graph solution crashed!

Day 11 was frankly the hardest: a form of game of life mixed with "line-of-sight" computations on a 2D map. It took me quite a while (I had to refactor entirely the code of part 1 to be able to process part 2), but transforming the "line-of-sight" (a row, a column or a matrix diagonal in that case) into a character string and then using regex to analyse it turned out to be the easiest solution. The solution is a bit too tedious to share here however, but feel free to have a look in my repository. Day 12 (i. e. today) finally was simpler: just take a series of instructions and translates that into coordinates. Not especially hard though the instructions on part 2 were not super clear (the rotation was ill defined I think).