AOC

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

+/ 2 | #/.~ in

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

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

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

In 3d

+/,life^:6 ,:W

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

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

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

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

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

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

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
)

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

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

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

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

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

Count the differences and multiply.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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'

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