# AOC

## Table of Contents

- 2020
- Day 25: Combo Breaker
- Day 24: Lobby Layout
- Day 20: Jurassic Jigsaw
- Day 17: Conway Cubes
- Day 16: Ticket Translation
- Day 13: Shuttle Search
- Day 12: Rain Risk
- Day 11: Seating System
- Day 10: Adapter Array
- Day 9: Encoding Error
- Day 6: Custom Customs
- Day 5: Binary Boarding
- Day 3: Toboggan Trajectory
- Day 2: Pasword Philosophy
- Day 1: Report Repair

- 2019

Illiterate solutions to some advent of code puzzles.

See https://github.com/jitwit/aoc for more solutions that I haven't included here.

## 2020

### Day 25: Combo Breaker

https://adventofcode.com/2020/day/25

'a M b d' =: 7 20201227 , ".;._2 aoc 2020 25

After a horrible problem description, the task is just doing discrete logarithms. The following uses the baby-step giant-step algorithm to find the solution efficiently. It is also possible to brute force it.

d M&|@^m#.((a M&|@^i.m)(i.~,i.)M|b*a M&|@^(M-1+m)*i.m)-.m=.>.%:M

### Day 24: Lobby Layout

https://adventofcode.com/2020/day/24

V =: _2 ]\ 1 0 0 1 _1 1 _1 0 0 _1 1 _1 in =: +/@:(V{~(;:'e ne nw w sw se')i.(<;.2~ e.&'ew'));._2 aoc 2020 24

#### Part A

Most of the work was done in representing moves as 2d axial coordinates and parsing.

+/ 2 | #/.~ in

#### Part B

Another game of life, except with a hexagonal grid.

P =: (0&,@,&0)"1@:(0&,@,&0) G =: 1 (<"1 G)}(1+>./G=.(-"1<./)in#~2|+/-:"1/~in)$0 +/,{{2=z+y*1=z=.+/V|.!.0"1 _/y=.P y}}^:100 G

### Day 20: Jurassic Jigsaw

https://adventofcode.com/2020/day/20

in =: ([: <;._2 ,&LF) &.> (<;._2~ (2#LF)&E.) LF,aoc 2020 20

#### Part A

Find corner patches by finding those that connect to exactly two others.

I =: ([: {: 0 ". ':' -.~ 1&{::) &> in N =: %:#B =: ([: > 2&}.) &> in S =: [: (,|."1) {.,{:,({.,:{:)@:|: SYM =: (,|:"_1)@:(|:@:|.^:(i.4)) H =: {:"2 X =: SYM"_1 B G =: (-=@i.@#) +./"_1 ([: +./"1 (-:"1/~))/~ H */ I #~ 2 = +/ G

#### Part B

This part is not very nice, I will probably revisit at some point to
find something better. Find strips based on connections, starting with
corner. The `ST`

verb is necessary for making sure the strips line up
in agreement.

C0 =: {. I. 2 = +/ G M =: {{ , h #~ ({.y) ~: {."1 h =. 4 $. $. H -:"_2 _ {. X{~<y }} R =: {{ (#~ ((=&# ~.) {."1)"2) M^:(i.-N)"1 y,.i.8}} T =: {{ r #~ -. +./"1 {."_2 (x-.y) e.~ r =. R y }} ST =: {{ if.({:"1 x)-:{."1 y do. x,.y elseif. ({."1 x)-:{."1 y do. (|."1 x),.y elseif. ({."1 x)-:{:"1 y do. (|."1 x) ,. |."1 y else. x,.|."1 y end.}} SEA =: {{IMG=.ST/,/"_1 X{~<"1{."_1(F2&T)"0 F2=.{."1{.R y '#'=,./^:2(2 2$10)(}.@:}:"_1@:}.@:}:);._3 IMG}} SMC =: +/,SM =: '#'&=;._2 ] 0 : 0 # # ## ## ### # # # # # # ) MON =: (1 1,:$SM)&(SMC=+/@:,@:(SM&*);._3) (+/,IMG)-SMC*+/,MON"_1 SYM IMG =: SEA C0

DIM=: $IMG=: ,/(#~([:+./[:,MON)"_1) SYM SEA C0 monsters=: IMG++/(-4$.$.MON IMG)|."1 _/DIM$!.0,SM,"1(DIM-&{:$SM)$0 (0 30 255,130 30 255,:50 200 140) viewmat monsters

### Day 17: Conway Cubes

https://adventofcode.com/2020/day/17

Classic problem for APL languages, now in higher dimensions.

W =: '#'&=;._2 aoc 2020 17

A few tricks make this quite general and concise. The first is to get
an infinite representation by padding 0's at each step. The second is
to do that padding once for through each outer dimension. The third is
to generate arbitrary dimension neighborhoods by using base 3, as ```
_1+
#&3 #: i.@:(3&^)
```

does the trick. And the fourth, apparently first due
to Arthur Whitney is to encode the rules as `3=z-y*4=z`

, subtract one
if square is alive and the count is 4 then compare with 3.

life =: {{for_d.1+i.s=.#$y do.y=.0,"d y,"d,0 end. 3=z-y*4=z=.+/(<:(s#3)#:i.3^s)|.!.0"1 _/y}}

#### Part A

In 3d

+/,life^:6 ,:W

#### Part B

And in 4d. From discussions on advent's irc channel, this dense representation is surprisingly fast compared with what you get by using sparse trees holding bools at positions.

+/,life^:6 ,:^:2 W

### Day 16: Ticket Translation

https://adventofcode.com/2020/day/16

We get a list of rules, where ticket values must lie in one of two intervals. The task is to find necessarily invalid tickets and find which fields correspond to which rules.

n =: 1 + +/ ','={:];._2 in =: aoc 2020 16 'R T S' =: (<;._2~ (2#LF)&E.) in,LF vals =: {{ ". ' ' (I. -. y e. a09)} y }} T =: {: vals;._2 T,LF R =: _2 (_1 0&+)\ vals R S =: _2 +./\ R ([:+./1=I.)"1 0/ V =: (-n) ]\ vals S

`I.`

is used to check interval membership and \(S\) is a so called
brick, a 3d table, where first axis corresponds to rules, second to
tickets, and third to fields.

#### Part A

To find the fields that don't fit in to any rule, we or-reduce, flatten, then logically negate.

+/ (,V) #~ -. , +./ S

#### Part B

For this part, we build a graph by and reducing over the tickets to get a table of valid rules, ie for each rule 0 means some ticket had a field that didn't satisfy that rule. This is done after throwing out tickets with any invalid fields (or reduce after and reduce on fields).

For the puzzle input it's sufficient to find a rule with only 1 possible field, and remove that option from the other fields until a fixpoint is reached (the valid assignment). It is a simpleton's edge cover.

A =: {{1(<"1 r,"0 c)}0(<a:;c=.I.(r=.I.1=+/"1 y){y)}y}} */ T {~ 6{.,I.A^:_ *./"2 (+./ *./"1 S) #"2 S

### Day 13: Shuttle Search

https://adventofcode.com/2020/day/13

\(A\) are buses relevant in part a and \(B\) for part b; a doesn't care
about `x`

but b does.

D =: ". {. 'D A' =: ];._2 aoc 2020 13 A =: 0 -.~ B =: ,".;._1 ',',A

#### Part A

We find the bus id \(T\) for the bus leaving at the earliest time and and multiply

A *&(((i.<./)T)&{) T =. A (|-) D

#### Part B

Now we want to line up the bus ids and the depart times. This means solving a system of equations \(x \equiv a_i \mod b_i\), which we handle using the Chinese remainder theorem.

{. crt/ x: (* # ] ((|-),[)"0 i.@#) B

Here is the `crt`

implementation, which finds the \(s,t\) from the
extended euclid algorithm.

egcd =: 4 : 0 NB. extended euclid 'a b c d s t' =. 1 0 0 1,x,y while. r =. t - s*q =. <. t%s do. c =. t [ a =. c-q*a [ t =. a d =. t [ b =. d-q*b [ t =. b s =. r [ t =. s end. a,b,s assert. s = (a*x) + b*y ) crt =: 4 : 0 NB. chinese remainder theorem 's t g'=.m egcd n['b n'=.y['a m'=.x <.(<.m*n%g)(|,[)(a*t*<.n%g)+(b*m*<.s%g) assert. 0 = g | a-b )

### Day 12: Rain Risk

https://adventofcode.com/2020/day/12

in =: ];._2 aoc 2020 12

We can represent the state as a position and a waypoint. We can represent each of the required movements with 3x3 augmented matrices. These transformations can then be composed by multiplying the matrices. So, here's some long winded parsing:

S =: (".@:}.) * 1 _1 0j1 0j_1 {~ 'EWNS' i. {. NB. move T =: (0j_1 0j1 {~'RL'i.{.) ^ 1r90*".@:}. NB. turn M =: {{ (u y) (<v)} =i.3 }} NB. help parsing PA =: (".@}. M 0 1)`(T M 1 1)`(T M 1 1)`(S M 0 2)@.('FRL'i.{.)

#### Part A

NB. facing a direction is actually the same concept as the waypoint from part B.

+/ | +. {. (+/ . */ |. PA"1 in) +/ . * 0 1 1

#### Part B

Part B wants us to move the waypoint instead of the ship for `NESW`

directions. So,

PB =: (".@}. M 0 1)`(T M 1 1)`(T M 1 1)`(S M 1 2)@.('FRL'i.{.) +/ | +. {. (+/ . */ |. PB"1 in) +/ . * 0 10j1 1

### Day 11: Seating System

https://adventofcode.com/2020/day/11

in=: 'L'&= ;._2 aoc 2020 11

#### Part A

This is basically a game of life type thing, with a mask for cells that are can't be occupied (the floor of the plane).

S =: (*&(=&0)+[*4>]) [: +/ (<:3 3#:(i.9)-.4)|.!.0/ ] +/ , (in*S) ^: _ in

#### Part B

This gave me some difficulty at first. The rules update not based on immediate cells, but by next "visible" cell in any of the 8 directions. My first very slow solution scanned the whole matrix in each direction at each iteration. Only later did I see that we can represent the situation as a flat array with vertices at nonzero indices in the original matrix and edges between seats that are mutually visible.

Z =: [: < 2 <\ (#~ {&in) G =. (,|."1)>;(Z/.J),(Z/.|.J),Z"1 J,|:J=:{;~i.#in G =: (([: < {:"1)/.~{."1) (i.~ [: ~. {."1) G T =: (*&(=&0)+[*5>]) {{ ([: +/ {&y) &> G }} +/ T^:_ (#G)$0

### Day 10: Adapter Array

https://adventofcode.com/2020/day/10

We start off by sorting the chargers and adding 0 and one 3 above the end.

in =: 0,(,3+{:)/:~ ". ;._2 aoc 2020 10

#### Part A

Count the differences and multiply.

*/ #/.~ (}.-}:) in

#### Part B

This part is more fun. Being able to jump up 1,2,3 jolts (or whatever the puzzle terminology is supposed to be), we answer how many ways are there to go from 0 to end.

We can represent this as a graph with chargers for vertices and edges for valid jumps. The length 1 paths are the adjacency matrix \(G\). The length 2 paths are that matrix \(G^2\). And so on, so that \(G^n_{i,j}\) gives the count of the length \(n\) paths between chargers \(i\) and \(j\).

Basically, letting \(N\) be the number of chargers, we want to calculate \[\sum G^j_{0,N-1}\cdot[0\le j].\]

The steps are all positive and there are finitely many vertices, so this will converge to a matrix of all 0 after not too long. A more clever way to find the answer, however, is to note that we can instead calculate \[(I-G)^{-1}_{0,N-1}\] as we have a power series with coefficient 1 everywhere.

<. (<-i.2) { %. (-~ =@i.@#) (0&<*<&4) -~/~ in

### Day 9: Encoding Error

https://adventofcode.com/2020/day/9

in=: ". ;._2 aoc 2020 9

#### Part A

We want to find the first number that isn't a sum of a pair of the previous 25 numbers. So, pretty directly, we scan the length 26 infixes of the input and find the first tail that isn't in the sum table of the curtail.

]A =: {. (#~*) 26 ({:*{: -.@e. [: , +/~ @: }:)\ in

#### Part B

Now we want to find some window where the members sum to the number from part a. We can do that by calculating a subtraction table of the prefix sums of the input, finding where A occurs in the table and taking the sum of the minimum and maximum of the subarray of the input based on that location.

in (>./+<./);.0~ ({:,:-/) {. 4 $. $. A = -/~ +/\ in

### Day 6: Custom Customs

https://adventofcode.com/2020/day/6

Parsing is in fact the most interesting part of the solution. We want to group lines of the input based on double newlines. Otherwise we're just intersecting and unioning chars.

az=: a.{~97+i.26 in=: (<@:(az&e.;._1);._2~ (2#LF)&E.) LF,(aoc 2020 6),LF

#### Part A

+/ , +./ &> in

#### Part B

+/ , *./ &> in

### Day 5: Binary Boarding

https://adventofcode.com/2020/day/5

ids =: #. e.&'BR' ;._2 aoc 2020 5

The seats in the plane are basically binary numbers where back and right correspond to on bits.

#### Part A

>./ ids

#### Part B

We want to find the gap. Add 1 to input and delete the input from that. One of these numbers will be 1 + part a (the max) and the other will be the gap. So, we take the minimum of the set difference.

(1&+ <./@-. ]) ids

### Day 3: Toboggan Trajectory

https://adventofcode.com/2020/day/3

trees =: '#'&=;._2 aoc 2020 3

#### Part A

ski =: [: +/ ] {~ [: <"1 $@] |"1 i.@>.@(%~&{.$@]) */ [ 1 3 ski trees

#### Part B

*/ _2 ski&trees\ 1 1 1 3 1 5 1 7 2 1

### Day 2: Pasword Philosophy

https://adventofcode.com/2020/day/2

in =: |: ;: ;._2 aoc 2020 2 'a b' =: ". &> 0 2 { 'a d b c p' =: in

#### Part A

How many passowrds \(p\) have between \(a\) and \(b\) occurrences of char \(c\)?

+/ (a&<: *. <:&b) +/"1 p = {."1 c

#### Part B

And how many \(p\) have exactly one occurrence of char \(c\) at indices \(a\) and \(b\) (using 1-indexing, that is)?

+/ 1 = +/"1 (<:a,.b) {"1 p = {."1 c

### Day 1: Report Repair

https://adventofcode.com/2020/day/1

in =: ".;._2 aoc 2020 1

#### Part A

I've normally done problems like this by passing through sparse arrays
via `4 $. $. y`

to grab the nonzero indices. rnafiz pointed out a
nicer approach: finding the target elements by or-reducing (`+./`

)
then selecting (`#`

).

What's the product of the pair of expenses in the input that sums to 2020?

*/ in #~ (e. 2020&-) in

#### Part B

What's the product of the triplet of expenses in the input that sums to 2020?

*/ in #~ +./ (+/~ e. 2020&-) in

## 2019

### Day 22: Slam Shuffle

#### Part A

PC =: {{2 2 $ 1,(-".1{::y),0 1}} PI =: {{2 2 $ (".3{::y),0 0 1}} PN =: {{_1 _1,:0 1}} SEL =: ('';'increment';'new') I. 2&{ P =: PC`PI`PN@.SEL shuffles =: P"1 ([:<;._1' '&,);._2 aoc 2019 22

Inelegant parsing, but it does the trick. Given a deck of \(M\) cards, each of the shuffles is a permutation of \(\mathbb{Z}/M\mathbb{Z}\):

**increment**– distribute cards, evenly spaced. Like winding around the deck: \(x \mapsto n\cdot x \mod M\)**cut**– shift all cards by same amount: \(x \mapsto x-n \mod M\)**new stack**– reverse the deck \(x \mapsto -1-x \mod M\)

The trick is to write these shuffles as affine transformation matrices so that multiplying them is sequencing them.

'a b'=. {. +/ . */ x: |. shuffles 10007 | b + 2019 * a

#### Part B

`partB`

requires two extra tricks. We have to do the shuffle a bunch
of times, == (!), so brute forcing is
rather futile. Eureka #2 is that iterating goes like \[ax + b\]
\[a(ax+b)+b\] \[a(a(ax+b)+b)+b\] \[\vdots\] \[a^n\cdot x+b\cdot
\sum a^k \cdot [0 \le k < n ] = a^n\cdot x + b\cdot \frac{a^n-1}{a-1}.\]

Eureka #3 is that we can turn the division into multiplication and manage the huge powers because the deck size is prime.

\[a-1\equiv (a-1)^M \iff \frac{1}{a-1} \equiv (a-1)^{M-2} \mod M\]

In `J`

modular exponentiation is written by `m&|@^`

.

an=: a M&|@^ <:(M=:119315717514047x)-101741582076661x M|(an*2020)+b*(an-1)*(a-1)M&|@^M-2

### Day 16: Flawed Frequency Transmission

#### Part A

digits=: "."0}: aoc 2019 16 pat=: ([: }. >:@[ $ 0 1 0 _1#~])"_ 0 >:@i. ffta=: 10 #. 8 {. pat@# (10 | [: | (+/ . *))^:100 ] ffta digits

The trickiest part J implementation-wise was figuring out how to
generate the pattern matrix of cycled `0 1 0 _1`

. Verb copy is used to
repeat the values consecutively enough times.

palette=.3 3 $ 220 150 140 0 90 110 0 0 70 echo '../images/aoc/fft.png' linki palette {~ (- <./@,) pat 324

#### Part B

fftb=: 10 #. 7 {. [: (10|+/\.)^:100 (10#.7{.]) }. ($~10000*#) fftb digits

### Day 10: Monitoring Station

https://adventofcode.com/2019/day/10

grid =: ];.2 aoc 2019 10

#### Part A

Pass through a sparse grid to get the locations of the hashes, then
convert to complex numbers, which makes it easy to calculate angles
`*.`

and do arithmetic on locations.

A =: (j.~/"1) 4 $. $. '#' = grid >./ C =: (# @ ~. @: (1 {"1 *. @ -.&0))"1 -/~ A

#### Part B

We order the asteroids by angle after rotating clockwise by
\(\frac{\pi}{2}\) to match verb `*.`

to the problem
instructions. Grading first by magnitue away from station `S`

and then
by angle orders the asteroids appropriately. Once the asteroids are
keyed together, we zap by beheading each group of them having the same
angle until none remain, keeping intermediate states. Finally, we raze
the asteroids together after taking the head from each box.

S =: A {~ (i. >./) C phi =: 2p1 | 1p1 + {:@*.@*&0j_1 A0 =: (<@(/:|)/.~phi) (/:phi) (A - S) -. 0 Z =: S + {.&> ; (a: -.~ }.&.>) &.> ^: a: < A0 100 100 #. +. 199 { Z

Visualization where brighter squares are zapped before dimmer ones.

clrs =: ".(;._2) 0 : 0 0 0 0 54 85 134 109 171 255 163 255 255 ) A1 =: |: (80+i.-#Z) (<"1 +. Z)} (1 + >./ +. A) $ 0 clrs viewmat A1

### Day 8: Space Image Format

https://adventofcode.com/2019/day/8

We read the input and group so that the items of result are the pixels.

image =: (-6*25) "."0\ LF -.~ aoc 2019 8

#### Part A

We are to find the row with the fewest 0's, count the 1's and 2's and
multiply those counts. Rank `_1`

is used to count item-wise.

1 2 */@:(+/"_1)@(=/) ({~ (i.<./)@(+/ . =&0)) image

#### Part B

Here, we transpose the image to "stack" the pixels so the first non-2 entries at each item give the color.

viewmat _25 -.\ (|: {.@-."_1 2:) image

### Day 6: Universal Orbit Map

https://adventofcode.com/2019/day/6

Tree problem, ie an opportunity to apply some of Aaron Hsu's tree idioms. The main idea is to take our edge list and create a parent pointer vector. From that, it'll be easy to do queries like depth and build paths to central planet.

map =: ([:[;._1')',]);._2 aoc 2019;6 T =: ({."1@])`({:"1@])`(i.@>:@#@])}~ NB. edge list -> parent pointers O =: T map i.~ P =: ~. ,/ map NB. O for orbits, P for planets

#### Part A

The first part asks us to sum up all the depths, which is fairly straightforward.

D =: <: @ # @ ({&O^:a:) +/ D"0 i.#P

#### Part B

This part is more interesting. The distance between two planets is determined by a path that shoots up the tree and turns at their least common ancestor. The LCA is found by comparing paths from root, being the last member of their common prefix. We only care about depth to get the answer (ie the length of the common prefix) as the distance between the two planets is the depth of the planets minus twice the depth of their lca.

L =: +/ @ (=/) @ ,: & (|.@({&O^:a:)) 'SAN' (+&D - 2*L)&(P&i.) 'YOU'

### Day 1: Tyranny of the Rocket Equation

https://adventofcode.com/2019/day/1

masses =: ".;._2 aoc 2019 1

#### Part A

The fuel is the maximum of 0 and the floor of the input minus 2. I think this solution is in good APL spirit. We have a verb which operates on the whole of the input and solve by fixpoint without explicit loops or conditionals or pattern matching.

+/ 1 { (0 >. <.@%&3-2:)^:a: masses

#### Part B

+/ , }. (0 >. <.@%&3-2:)^:a: masses