To see a correct render of this notebook, check it out on nbviewer.
Annotated solutions in Dyalog APL.
Note that part of the charm of AoC is that every user (or at least groups of users) gets their own unique data set. Some of the solutions below exploit quirks in my particular data set, and so may conceivably not work for the general case.
⎕IO←1
]box on -style=max -trains=tree -fns=on
]rows on
DAY1←⊃⊃⎕NGET'data/2017/01.txt'1
Tack on the first item to the end, as per the problem statement.
DATA←DAY1,1⌷DAY1
We use a length-2 windowed reduction using equality to find all location where item n is equal to item n+1 as a binary map. We convert this to position (⍸
) and pick the corresponding items. As we're still dealing with characters, we need to convert to integers (⍎¨
) and then just sum them up.
+/⍎¨DATA[⍸2=/DATA] ⍝ Part 1: 1341
For part 2, we create a matrix where column 1 is the input and column 2 is the data rotated by half its length. Then compare the elements of each row to produce the binary map, and the rest is as per part 1.
+/⍎¨DAY1[⍸=/⍉↑(DAY1)(DAY1⊖⍨2÷⍨≢DAY1)] ⍝ Part 2: 1348
DAY2←16 16⍴⍎¨'\d+'⎕S'&'⊢⊃⎕NGET'data/2017/02.txt'1
Part 1 -- sum max-min for every row
+/(⌈/-⌊/)DAY2 ⍝ Part 1: 39126
In part 2 we're looking for the single pair of items per row that divides cleanly. For each row we generate all combinations, and try both ways of modular division, looking for a zero (not two) using
{≠/0=⍺(|,|⍨)⍵}
Finally, return the larger÷smaller and sum up everything.
Day2←{target←1↑⍸{≠/0=⍺(|,|⍨)⍵}/¨cmb←,⍵∘.,⍵⋄÷/pair[⍒pair←target⊃cmb]}
+/Day2¨↓DAY2 ⍝ Part 2: 258
https://adventofcode.com/2017/day/3
This spiral has a number of interesting properties. See http://oeis.org/A080335
We can exploit that we have perfect squares on the SE diagonal, which allows us to identify the size of the square which has the target number along one of its edges. We can then identify which edge, and count backwards from the next corner of the square (anti-clockwise).
⎕IO←0
DAY3←325489
Square←{r←⍵*0.5⋄⍵=2*⍨⌊r:r⋄0≠2|⌈r:⌈r⋄1+⌈r} ⍝ Smallest odd number < the square root, unless perfect square
]dinput
Day3p1←{
val←⍵
width←Square ⍵ ⍝ The width of the square in which the value is found
edge←⌊((width*2)-val)÷(width-1) ⍝ The side of the square: S E N W ← 0 1 2 3
pos←edge⊃,size,-size∘.,-size,size←⌊width÷2 ⍝ Grid coords of corner
_←(edge⊃,¯1 0∘.,0 ¯1)∘{pos+←⍺⋄⍵-1}⍣{⍺=val} (width*2)-edge×width-1 ⍝ Sequence at the nearest corner, acw
+/|¨pos ⍝ Manhattan distance to centre
}
Day3p1 DAY3 ⍝ 552
For part 2, we work our way outwards following the same spiral pattern, but this time the value of each point is the sum of the values of its 8-connected neighbours at the time of visit. The APL solution isn't pretty.
]dinput
Coords←{
⍝ Generate all coordinate pairs for the circumference of a square ⍵
pos←(⌊⍵÷2),(-⌊⍵÷2)+1
E←(⊂pos)+0,¨⍳⍵-1
N←(¯1↑E)+(-⍳⍵),¨0
W←(¯1↑N)+0,¨-⍳⍵
S←(¯1↑W)+(⍳⍵),¨0
∪E, N, W, S
}
Neighbours←{(⊂⍵)+(0 1)(1 1)(1 0)(1 ¯1)(0 ¯1)(¯1 ¯1)(¯1 0)(¯1 1)} ⍝ 8-neighbours
]dinput
Day3p2←{
target←⍵
seen←,⊂0 0 ⋄ vals←,1
{ ⍝ Move outwards one square at a time (i.e. odd numbers)
found←{ ⍝ Walk circumference, adding up values from visible neighbours
0=≢⍵:0
pos←⊃1↑⍵
old←seen⍳Neighbours pos
newVal←+/vals[((≢seen)>old)/old]
newVal>target:newVal
vals,←newVal
seen,←⊂pos
∇1↓⍵
} Coords ⍵
found>0:found
∇⍵+2
} 3
}
Day3p2 325489 ⍝ 330785
⎕IO←1
DAY4←' '(≠⊆⊢)¨⊃⎕NGET'data/2017/04.txt'1
Find phrases which don't match themselves with dupes removed.
+/(∪≡⊢)¨DAY4 ⍝ Part 1: 325
Part 2: apply the same process, but sort all words first.
+/(∪≡⊢)¨{⍵[⍋⍵]}¨¨DAY4 ⍝ Part 2: 119
⎕IO←1
DAY5←⍎¨⊃⎕NGET'data/2017/05.txt'1
]dinput
Day5←{
instr←⍵
modifier←⍺⍺
1 {
ip←1↑⍵
jmp←ip⌷instr
(ip+jmp)>≢instr:⍺
instr[ip]+←modifier jmp
(⍺+1)∇ip+jmp
} 1
}
{1} Day5 DAY5 ⍝ Part 1: 372671
{⍵≥3:¯1⋄1} Day5 DAY5 ⍝ Part 2: 25608480 (takes a minute or so)
https://adventofcode.com/2017/day/6
Part 1 and 2 differs only in the end condition and the start value.
⎕IO←0
DAY6←2 8 8 5 4 2 3 1 5 5 1 2 15 13 5 14
]dinput
Redist←{
(0@m⊢⍵) { ⍝ Zero out the current bin
0=⊃⍵:⍺ ⍝ Return end state
(1∘+@n⊢⍺)∇(⊃⍵-1),n←16|1+⊢/⍵ ⍝ Move one index on, mod size and add 1. Decrease value to distribute.
} ⍵[m],m←(⊢⍳⌈/)⍵ ⍝ Value and index of the largest element
}
Day6p1←{seen←⊂⍵⋄e←Redist⍣{seen∊⍨⊂⍺:1⋄0⊣seen,←⊂⍺} ⍵⋄(⊂e),≢seen} ⍝ Stop if we've seen a state before.
(elem seen)←Day6p1 DAY6
seen ⍝ 3156
Day6p2←{count←0⋄target←⍵⋄_←Redist⍣{count+←1⋄⍺≡target} ⍵⋄count} ⍝ Stop when we revisit end state of part 1.
Day6p2 elem ⍝ Part 2: 1610
⎕IO←1
'segs'⎕CY'dfns'
DAY7←⊃⎕NGET'data/2017/07.txt'1
We need to create a tree structure from the data. We'll create three vectors, the first being a list of the nodes themselves, the second holding their corresponding weights, and the third a nested vector containing any child-nodes. The 'dfns' workspace contains a handy function 'segs' that can slice up strings on a set of separators.
]dinput
Parse←{
⍺←⍬ ⍬ ⍬
0=≢⍵:⍺
items←'() ,->' segs ⊃1↑⍵
(⍺,¨(⊂1⊃items)(⍎2⊃items)(⊂2↓items))∇1↓⍵
}
(nodes weights children)←Parse DAY7
⊃nodes~{⊃,/,⊆¨⍵}⍣≡children ⍝ Part 1: xegshds
For part 2 we are to identify a single weight tweak to make the tree balanced in the sense that every child tree of any given node has equal weights. The first part of that is to be able to calculate the weight of the tree from a specific start node:
]dinput
SubTreeWeight←{ ⍝ (nodes weights children) SubTreeWeight 'node'
idx←(1⊃⍺)⍳⊂⍵ ⍝ Find the node's index
0=≢idx⊃3⊃⍺:idx⊃2⊃⍺ ⍝ If node has no children -- return the weight
(idx⊃2⊃⍺)++/⍺∘∇¨idx⊃3⊃⍺ ⍝ Add own weight to sum of child tree weights recursively
}
We can now drill down from the root, looking for the first node that is balanced. The tweak needs to happen at the parent level of this node. We descend recursively following the odd one out of the child nodes until all child nodes have the same weight.
]dinput
FindAnomaly←{ ⍝ Find first key where its child trees all have the same weight
idx←(1⊃⍺)⍳⊂⍵
ch←idx⊃3⊃⍺
0=≢ch:⍬
chw←⍺∘SubTreeWeight¨ch
(1≥≢∘∪)chw:⍵ (idx) ⍝ Child tree weights all equal - we're done
⍺∇⊃ch[∊{∩/⍵}⌸chw] ⍝ Intersect-reduce over unique indexes only returns non-empty for singles.
}
⊢ANOMALY←(nodes weights children) FindAnomaly 'xegshds'
The size of the tweak we need to make to the anomaly is the difference of its parent's child weights.
PARENT←⍸{ANOMALY[1]∊⍵}¨children
TWEAK←|-/∪(nodes weights children)∘SubTreeWeight¨⊃children[PARENT]
weights[2⊃ANOMALY]-TWEAK ⍝ Part 2: 299
⎕IO←1
'segs'⎕CY'dfns'
DAY8←⊃⎕NGET'data/2017/08.txt'1
DATA←' ' segs¨DAY8
]dinput
Day8←{
regs←∪{⊃,/,⊆¨⍵}⍣≡(↑⍵)[;1 5]
R←regs∘⍳ ⍝ By binding an operator, the static 'regs' vector is hashed
vals←0⍴⍨≢regs
Reg←{vals[R ⊂,⍵]}
Set←{vals[R ⊂,⍺]←⍵⋄⍬}
inc←{⍺ Set (Reg ⍺)+⍎⍵}
dec←{⍺ Set (Reg ⍺)-⍎⍵}
0 {
0=≢⍵:(⌈/vals) ⍺
max←⌈/vals,⍺
instr←1⊃⍵
rv←Reg 5⊃instr
f←⍎2⊃instr
((,'>')≡6⊃instr)∧rv>⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
((,'<')≡6⊃instr)∧rv<⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
('=='≡6⊃instr)∧rv=⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
('>='≡6⊃instr)∧rv≥⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
('<='≡6⊃instr)∧rv≤⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
('!='≡6⊃instr)∧rv≠⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr
max∇1↓⍵
} ⍵
}
Day8 DATA ⍝ Part 1: 3745 Part2: 4644
⎕IO←1
DAY9←⊃⊃⎕NGET'data/2017/09.txt'1
]dinput
Day9←{
pos←0
str←⍵
Yield←{pos+←1⋄pos⊃str}
Skip←{⍺←0⋄c←Yield⍬⋄c='>':⍺⋄c='!':⍺∇⍬⊣Yield⍬⋄(⍺+1)∇⍬}
(0 0 0) {
3::1↓⍺ ⍝ Catch index error at end of input
(depth total skipped)←⍺
c←Yield⍬
c='{':((1+depth),total,skipped)∇⍬
c='}':((¯1+depth),(total+depth),skipped)∇⍬
c='<':(depth,total,skipped+Skip⍬)∇⍬
c='!':⍺∇⍬⊣Yield⍬
⍺∇⍬
}⍬
}
Day9 DAY9 ⍝ Part 1: 10050 Part 2: 4482
⎕IO←0
'iotag'⎕CY'dfns'
DAY10←147 37 249 1 31 2 226 0 161 71 254 243 183 255 30 70
]dinput
Rot←{
(skip pos len)←⍵
0=len:(skip+1) (256|pos+len+skip) ⍺
(skip+1) (256|pos+len+skip) (⊖@(256|pos iotag pos+len-1)⊢⍺)
}
Round←{0=≢⍵:⍺⋄((2⊃⍺) Rot (0⊃⍺) (1⊃⍺) (0⊃⍵))∇1↓⍵}
Part 1 is a single round of the knot hash algorithm, with the answer sought is the product of the two first numbers.
×/2↑2⊃(0 0,⊂⍳256)Round DAY10 ⍝ Part 1: 37230
For part 2, we apply the knot hash round 64 times. The lengths are now a byte array derived from a string representation of the data (including commas!) and 5 additional bytes added at the end.
After the 64 rounds, we partition the result into blocks of 16:
↓16 16 ⍴ sparse
and XOR-reduce each block:
{2⊥⊃≠/(8⍴2)∘⊤¨⍵}¨
and finally convert to hexadecimal:
↓⍉{(⎕D,⎕A)[16⊥⍣¯1⊢⍵]}
]dinput
Knot←{
lengths←(⎕UCS¨' '⎕R','⍕⍵),17 31 73 47 23
sparse←(0 0,⊂⍳256) {
0=⍵:2⊃⍺
(⍺ Round lengths)∇⍵-1
} 64
↓⍉{(⎕D,⎕A)[16⊥⍣¯1⊢⍵]} {2⊥⊃≠/(8⍴2)∘⊤¨⍵}¨↓16 16 ⍴ sparse
}
Knot DAY10 ⍝ 70b856a24d586194331398c7fcfa0aaf
https://adventofcode.com/2017/day/11
Cube coordinates for hex grids; see https://www.redblobgames.com/grids/hexagons/#coordinates
Map N-S axis to y, NE-SW to z and NW-SE to x
Manhattan distance on the hex grid is half that on the cube grid.
We start with splitting the input on comma, and then converting strings to the index of their first occurrance. Note that this ordering needs to be mirrored in the DELTA variable of offsets -- it's not general for all inputs.
⎕IO←1
DAY11←(∪⍳⊢)','(≠⊆⊢)⊃⊃⎕NGET'data/2017/11.txt'1
HexMHD←{⌊2÷⍨+/|⍵} ⍝ Manhattan distance on a hex grid
DELTA←(¯1 0 1)(0 ¯1 1)(1 ¯1 0)(¯1 1 0)(1 0 ¯1)(0 1 ¯1) ⍝ SW S SE NW NE N -- order of index of first occurrance
All we need to do is sum it up - but as Dyalog's reduce goes R-L we need to reverse.
HexMHD ⊃+/⊖DELTA[DAY11] ⍝ Part 1: 643
For part 2, find the max MHD attained whilst walking the path. Dyalog's scan reduction operator goes left to right and maintains the running total.
⌈/HexMHD¨+\DELTA[DAY11] ⍝ Part 2: 1471
⎕IO←0
'segs'⎕CY'dfns'
DAY12←1↓¨⍎¨¨' <->,'∘segs¨⊃⎕NGET'data/2017/12.txt'1
Discover all nodes reachable from the root by means of a classic breadth-first search.
]dinput
BFS←{ ⍝ nodes BFS node
graph←⍺
⍬{
0=≢⍵:⍺
node←1↑⍵ ⋄ queue←1↓⍵
ch←node⊃graph
(⍺,node)∇(queue∪ch)~⍺
}⍵
}
≢DAY12 BFS 0 ⍝ Part 1: 175
Part 2: find the number of connected components. We repeatedly apply the BFS routine above and mark visited nodes.
]dinput
ConnectedComponents←{
graph←⍵
seen←⍬
0 {
root←⍵
root≥≢graph:⍺
root∊seen:⍺∇⍵+1
seen,←graph BFS root
(⍺+1)∇⍵+1
} 0
}
ConnectedComponents DAY12 ⍝ 213
⎕IO←0
'segs'⎕CY'dfns'
DAY13←⍎¨¨' :'∘segs¨⊃⎕NGET'data/2017/13.txt'1
MAX←⊃⊃1↑¯1↑DAY13
IDX←⊣/↑DAY13
LEN←⊢/↑DAY13
The Pos
function returns the location of the scanner for a given picosecond and layer depth.
Pos←{cycle←⍺-1⋄1=2|⌊⍵÷cycle:cycle-cycle|⍵⋄cycle|⍵} ⍝ depth Pos pico - the index at pico, for given depth
For part 1 we traverse through once, keeping track of each layer where we got caught. The cost of getting caught is the layer index times its depth.
Day13p1←{fw←⍵⋄0{⍵≥≢fw:⍺⋄0=fw[⍵] Pos ⍵:(⍺+fw[⍵]×⍵)∇⍵+1⋄⍺∇⍵+1}0}
+/Day13p1 LEN@IDX⊢(1+MAX)⍴0 ⍝ Part 1: 2384
In part 2, we need to find a delay that would enable us to traverse through all the layers without getting caught at all.
]dinput
Day13p2←{
fw←⍵
0 { ⍝ Current delay is ⍺
⍵≥≢fw:⍺
0=fw[⍵]:⍺∇⍵+1 ⍝ Skip gaps
0=fw[⍵] Pos ⍵+⍺:(⍺+1)∇0 ⍝ Caught! Increase delay and re-start from layer 0
⍺∇⍵+1 ⍝ Still going: try the next layer
} 0 ⍝ Current layer
}
Day13p2 LEN@IDX⊢(1+MAX)⍴0 ⍝ Part 2: 3921270
https://adventofcode.com/2017/day/14
This makes use of the 'Knot' function, defined in Day 10.
⎕IO←0
'dec'⎕CY'dfns' ⍝ Hex to dec helper function
DAY14←'jzgqcdpd'
ADJ←↑{∊{(8⍴2)⊤⍵}¨dec¨Knot DAY14,'-',⍕⍵}¨⍳128
+/∊ADJ ⍝ Part 1: 8074
For part 2 we need to find connected components, just like we did in Day 12. With a bit of tweaking we could have re-used the same functions for days 12 and 14, but here are specific versions again:
Bfs←{⍺←⍬⋄0=≢⍵:⍺⋄(⍺,1↑⍵)∇((1↓⍵)∪⍺⍺ 1↑⍵)~⍺}
Components←{⍺←0⋄0=≢⍵:⍺⋄(⍺+1)∇(1↓⍵)~⍺⍺ Bfs⊢1↑⍵}
]dinput
Connected←{
valid←({(⍵[0]≥0)∧(⍵[1]≥0)∧(⍵[0]<128)∧(⍵[1]<128)}¨n)/n←⍵+(¯1 0)(1 0)(0 1)(0 ¯1)
(1=⍺[valid])/valid
}
ADJ∘Connected Components ⊢ ⍸ADJ ⍝ Part 2: 1212
https://adventofcode.com/2017/day/15
A "generator" in this case is a function that remembers a bit of state between invocations. We achieve this by making an operator that takes a namespace as the operand.
Part1←{⊢⍺⍺.prev←2147483647|⍺⍺.prev×⍺⍺.fact}
GA←({⍵⊣⍵.(prev fact)←679 16807}⎕NS'') Part1
GB←({⍵⊣⍵.(prev fact)←771 48271}⎕NS'') Part1
{⍺←0⋄0=⍵:⍺⋄(⍺+≡/{(16⍴2)⊤⍵}¨(GA⍬) (GB⍬))∇⍵-1} 40000000 ⍝ Part 1: 626 -- takes a good few mins to run
For part 2, the generator functions need to spin until they find a value that's divisible by 4 or 8 respectively. Mercifully, we only need to consider 5M iterations.
Part2←{0=⍺⍺.multiple|⍺⍺.prev←2147483647|⍺⍺.prev×⍺⍺.fact:⍺⍺.prev⋄∇⍬}
GA2←({⍵⊣⍵.(prev fact multiple)←679 16807 4}⎕NS'') Part2
GB2←({⍵⊣⍵.(prev fact multiple)←771 48271 8}⎕NS'') Part2
{⍺←0⋄0=⍵:⍺⋄(⍺+≡/{(16⍴2)⊤⍵}¨(GA2⍬) (GB2⍬))∇⍵-1} 5000000 ⍝ Part 2: 306 -- also takes a good few mins to run
⎕IO←0
'segs'⎕CY'dfns'
DAY16←',' segs⊢⊃⊃⎕NGET'data/2017/16.txt'1
Spin←{(-⍺)⊖⍵}
Exchange←{(a b)←⍺⋄⍵[b a]@a b⊢⍵}
Pair←{(⍵⍳⍺)Exchange ⍵}
]dinput
Day16←{
⍺←'abcdefghijklmnop'
0=≢⍵:⍺
cmd←⊃1↑⍵
's'=cmd[0]:((⍎1↓cmd) Spin ⍺)∇1↓⍵
'x'=cmd[0]:((⊃1↓'/'⎕VFI 1↓cmd) Exchange ⍺)∇1↓⍵
((∊'/'(≠⊆⊢)1↓cmd) Pair ⍺)∇1↓⍵
}
Day16 DAY16 ⍝ Part 1: kbednhopmfcjilag
For part 2, a beeeellion iterations is obviously too much to brute, so we look for recurring patterns instead. End-of-dance state quickly recurs. The value at 100 is the value at 1,000 is the value at 1,000,000,000...
'abcdefghijklmnop' {0=⍵:⍺⋄(⍺ Day16 DAY16)∇⍵-1} 100 ⍝ Part 2: fbmcgdnjakpioelh
⎕IO←0
DAY17←356
Insert←{(v cur st)←⍵⋄c←1+(≢⍺)|cur+st⋄c≥≢⍺:c (⍺,v)⋄c ((c↑⍺),v,c↓⍺)}
Day17p1←{2018=⍵:⍺⋄(cur buf)←⍺⋄(buf Insert ⍵ cur DAY17)∇⍵+1}
(cur buf)←0 (,0)Day17p1 1
buf⌷⍨cur+1 ⍝ Part 1: 808
For part 2 we're looking for a value at a given index rather than a particular value. This means we don't need to actually maintain the circular buffer at all.
Day17p2←{(cur target st)←⍵⋄cur←1+st|cur+DAY17⋄1=cur:cur,st,st+1⋄cur,target,st+1}
1⊃Day17p2⍣50000000⊢0 ¯1 1 ⍝ Part 2: 47465686 -- takes a minute or so to run
⎕IO←1
DAY18←{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2017/18.txt'1
]dinput
Day18←{
mem←⍵
ri←{'abfips'⍳⍵}
val←{(1=2|⎕DR)⍵:⍵⋄⍺[ri ⍵]}
set←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)@(ri x)⊢⍺}
mul←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘×@(ri x)⊢⍺}
add←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘+@(ri x)⊢⍺}
mod←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘|@(ri x)⊢⍺}
rcv←{0≠⍺ val ⊃⍵:99∘+@7⊢⍺⋄1∘+@7⊢⍺}
snd←{⍺ set 's' (⊃⍵)}
jgz←{(x y)←⍵⋄(⍺ val x)>0:(⍺ val y)∘+@7⊢⍺⋄1∘+@7⊢⍺}
{
ip←¯1↑⍵
instr←ip⊃mem⋄op←⊃instr
⍵ (⍎op) 1↓instr
}⍣{(¯1↑⍺)>≢mem}⍺
}
6⊃0 0 0 0 0 0 1 Day18 DAY18 ⍝ Part 1: 3423
For part 2, it turns out the snd
and rcv
have nothing to do with audio, but are an IPC mechanism! We'll need two separate "processes" and message queues. We expand the registers a bit:
1 2 3 4 5 6 7 8
a b f i p blocked send-count ip
MSG←{⍵⊣⍵.Queue←⍬ ⍬}⎕NS''
]dinput
Step←{
pid←⍺
mem←DAY18
ri←{'abfip'⍳⍵}
val←{(1=2|⎕DR)⍵:⍵⋄⍺[ri ⍵]}
set←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)@(ri x)⊢⍺}
mul←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘×@(ri x)⊢⍺}
add←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘+@(ri x)⊢⍺}
mod←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘|@(ri x)⊢⍺}
jgz←{(x y)←⍵⋄(⍺ val x)>0:(⍺ val y)∘+@8⊢⍺⋄1∘+@8⊢⍺}
snd←{MSG.Queue[1+~pid],←⍺ val ⊃⍵⋄1∘+@7 8⊢⍺} ⍝ Add item to other's queue, and 1 to send-count and ip
rcv←{ ⍝ Pull item from message queue
data←⊃MSG.Queue[1+pid]
0=≢data:1@6⊢⍺ ⍝ Blocked! Ip stays unchanged.
val←1⊃data
MSG.Queue[1+pid]←⊂1↓data ⍝ Pop queue
0@6⊢⍺ set (⊃⍵) val ⍝ Set reg with value from queue, and make note that we're not blocked
}
ip←¯1↑⍵
ip>≢mem:⍵ ⍝ Already terminated
instr←ip⊃mem⋄op←⊃instr
⍵ (⍎⊃instr) 1↓instr
}
Deadlocked←{(p0 p1)←⍵⋄(p0[6]=1)∧p1[6]=1}
Terminated←{(p0 p1)←⍵⋄(p0[8]≥≢DAY18)∧p1[8]≥≢DAY18}
Done←{(Deadlocked ⍵)∨Terminated ⍵}
7⊃2⊃{⊃↓Step/0 1,⍪⍵}⍣{Done ⍺} (0 0 0 0 0 0 0 1)(0 0 0 0 1 0 0 1) ⍝ 'p' reg holds process id -- Part 2: 7493
https://adventofcode.com/2017/day/19
After eyeballing the data we make the following data-dependent assumptions:
⎕IO←1
DAY19←↑⊃⎕NGET'data/2017/19.txt'1
]rows on
]dinput
Turn←{
graph←⍺
(prev cur)←⍵
Valid←{({(⍵[1]>0)∧(⍵[2]>0)∧(⍵[1]≤≢graph)∧⍵[2]≤≢graph}¨⍵)/⍵}
⊃(' '≠graph[coords])/coords←Valid (⊂prev)~⍨{cur+⍵}¨(¯1 0)(1 0)(0 ¯1)(0 1)
}
]dinput
Next←{
(prev cur)←⍵
dir←v÷(2*∘÷⍨+.×⍨)v←cur-prev ⍝ Unit-vector in the direction of travel
next←cur+dir
⍺[⊂cur]='+':cur (⍺ Turn prev cur) 1 ⍝ On a jct
⍺[⊂next]∊⎕A,⍺[⊂cur],'+':cur (next) 1 ⍝ Straight or coming to jct
⍺[⊂next]=' ':cur (cur) 0 ⍝ End of the track
cur (next+dir) 2 ⍝ Underpass
}
]dinput
Day19←{
graph←⍺
(⍬ 1) {
(letters count)←⍺
(prev cur delta)←graph Next ⍵
graph[⊂cur]='Y':(letters,'Y') (count+delta)
graph[⊂cur]∊⎕A:((letters,graph[⊂cur]) (count+delta))∇prev (cur)
(letters (count+delta))∇prev (cur)
} ⍵
}
⊢START←DAY19[1;]⍳'|'
DAY19 Day19 (0 START) (1 START) ⍝ Part 1: GPALMJSOY Part 2: 16204
https://adventofcode.com/2017/day/20
Convergence for some number of itereations -- not converged at 300, but converged at 500. Part 1 is simply a sum-scan: acc vel pos → acc (acc+vel) (acc+vel+pos). We can do the whole lot as just:
+⍀⍣500
Gotta love APL. We create a matrix with the shape 3 × 1000 × 3 holding acceleration, velocity and position in that order -- the use of dyadic ⍉
is explained in depth here: https://stackoverflow.com/questions/62634746/how-do-i-convert-a-vector-of-triplets-to-a-3xnx3-matrix-in-dyalog-apl
⎕IO←0
DAY20←⊖1 0 2⍉(9÷⍨≢DATA)3 3⍴DATA←⍎¨'-?\d+'⎕S'&'⊢⊃⎕NGET'data/2017/20.txt'1 ⍝ 3 x 1000 x 3: acc vel pos
We can get the state after 500 iterations simply by +⍀⍣500
. What remains is to find the index of the point which has the smallest (⊃⍋
) Manhattan distance (+/|
) from the origin.
⊃⍋+/|2⌷+⍀⍣500⊢DAY20 ⍝ Part 1: 170
Part 2, remove all collisions. We can make good use of key ⌸
here.
Day20p2←{state←+⍀⍵⋄hist←{⍵ (2>≢⍵)}⌸2⌷state⋄state[;∊(hist[;1])/hist[;0];]}
≢2⌷Day20p2⍣500⊢DAY20 ⍝ Part 2: 571
https://adventofcode.com/2017/day/21
Most of the work here is setting up the lookup table. We expand all possible rotations and flips of each pattern key, and stay in the "matrix domain" rather than the unfolded strings.
The Tile
dfn divides up its argument matrix into a set of either 2×2 or 3×3 sub-matrices using key ⌸
. The curious expression (⍴×⍴∘⊃)⍴0 2 1 3⍉↑
in Day21
uses a dyadic transpose to merge the sub-matrices.
⎕IO←0
'segs'⎕CY'dfns'
DAY21←⍉↑'/'⎕R''¨↓⍉↑' =>'∘segs¨⊃⎕NGET'data/2017/21.txt'1
Rot←{(⍵)(⌽⍉⍵)(⌽⊖⍵)(⊖⍉⍵)}
Fold←{s←.5*⍨≢⍵⋄s s⍴⍵}
Trn←{m←Fold ⍵⋄∪(Rot m),(Rot⌽m),(Rot⊖m)}
Expand←{⍺←⍬⋄0=≢⍵:⍺⋄(k v)←⊃⍵⋄fv←Fold v⋄(⍺,{⍵ fv}¨Trn k)∇ 1↓⍵}
Tile←{2=⍺:,⊢∘⊂⌺(2 2⍴2 2)⊢⍵⋄1 1↓⊢∘⊂⌺(2 2⍴3 3)⊢0⍪0⍪0,0,⍵}
Day21←{s←2+2|≢⍵⋄tiles←,s Tile ⍵⋄dim←s÷⍨≢⍵⋄((⍴×⍴∘⊃)⍴0 2 1 3⍉↑)dim dim⍴{Find ⊂⍵}¨tiles}
TABLE←Expand ↓DAY21
Find←(⊣/↑TABLE)∘{⊃⊢/⊃TABLE[⍺⍳⍵]}
+/∊'#'=Day21⍣5⊢3 3⍴'.#...####' ⍝ Part 1: 162
+/∊'#'=Day21⍣18⊢3 3⍴'.#...####' ⍝ Part 2: 2264586
https://adventofcode.com/2017/day/22
We don't know our data size up-front, as the grid extends 'infinitely' in all directions. Trial and error soon lets us pick a finite size. This is arguably a bit wasteful as the grid will be pretty sparse.
⎕IO←0
Make←{s←(2÷⍨⍺)-2÷⍨≢⍵⋄ctr←⊂s s⋄1@(ctr+⍸⍵)⊢⍺ ⍺⍴0} ⍝ Center data in larger array of shape ⍺ ⍺
DAY22←429 Make 25 25⍴(∪⍳⊢)∊⊃⎕NGET'data/2017/22.txt'1
]dinput
Day22p1←{
m←⍺
start←⌊2÷⍨≢m
{
(row col infected count dir)←⍵
cur←m[row;col]
m[row;col]←~cur
newDir←cur {1=⍺:¯1∘⌽ ⍵⋄1∘⌽ ⍵} dir
newPos←(⊃newDir)⌷(⊂row col)(-,+)(1 0)(0 1)
(⊃newPos),(infected+~cur) (count-1) (newDir)
}⍣⍵⊢start start 0 ⍵ (⍳4)
}
2⊃DAY22 Day22p1 10000 ⍝ Part 1: 5261
For part 2 we're doing a hundred million iterations and have more states to deal with, but code-wise there are not a lot of changes.
The new state transitions are: clean, weakened, infected, flagged for 0 1 2 3, so we need to set the initial state to 2 for all infected cells.
]dinput
Day22p2←{
m←0 2[⍺] ⍝ Infected cells should have value 2
start←⌊2÷⍨≢m
{
(row col infected count dir)←⍵
cur←m[row;col]
m[row;col]←cur⊃1 2 3 0
newDir←cur {0=⍺:1⌽⍵⋄1=⍺:⍵⋄2=⍺:¯1⌽⍵⋄¯2⌽⍵} dir
newPos←(⊃newDir)⌷(⊂row col)(-,+)(1 0)(0 1)
(⊃newPos),(infected+2=m[row;col]) (count-1) (newDir)
}⍣⍵⊢start start 0 ⍵ (⍳4)
}
2⊃DAY22 Day22p2 10000000 ⍝ Part 2: 2511927 -- takes around 90s to run
https://adventofcode.com/2017/day/23
Moar messy ASM to un-mess. Same-ish as Day 18 above.
⎕IO←1
DAY23←{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2017/23.txt'1
]dinput
Day23←{
mem←⍵
ri←{'abcdefgh'⍳⍵}
val←{(1=2|⎕DR)⍵:⍵⋄⊃⍺[ri ⍵]}
set←{(x y)←⍵⋄1∘+@10⊢(⍺ val y)@(ri x)⊢⍺}
mul←{(x y)←⍵⋄1∘+@9⊢⍺ set x,(⍺ val x)×⍺ val y}
sub←{(x y)←⍵⋄⍺ set x,(⍺ val x)-⍺ val y}
jnz←{(x y)←⍵⋄(⍺ val x)≠0:(⍺ val y)∘+@10⊢⍺⋄1∘+@10⊢⍺}
{
ip←¯1↑⍵
instr←ip⊃mem⋄op←⊃instr
⍵ (⍎op) 1↓instr
}⍣{(¯1↑⍺)>≢mem}⍺
}
9⊃0 0 0 0 0 0 0 0 0 1 Day23 DAY23 ⍝ Part 1: 5929
Part 2 - set 'a' to 1 and run again, right? No, sadly.
The ASM code contains a multitude of nested loops that means that the program will not complete before the heat death of the universe. So let's look at the actual code.
{{ init a = 1 }}
1: set b 79
2: set c b
3: jnz a 2 IF a != 0: GOTO L1
4: jnz 1 5 GOTO L2
5: mul b 100 L1
6: sub b -100000
7: set c b
8: sub c -17000
9: set f 1 L2
10: set d 2
11: set e 2 L5
12: set g d L4
13: mul g e
14: sub g b
15: jnz g 2 IF g != 0: GOTO L3
16: set f 0
17: sub e -1 L3
18: set g e
19: sub g b
20: jnz g -8 IF g != 0: GOTO L4
21: sub d -1
22: set g d
23: sub g b L6
24: jnz g -13 IF g != 0: GOTO L5
25: jnz f 2 IF f != 0: GOTO L6
26: sub h -1
27: set g b L7
28: sub g c
29: jnz g 2 IF g != 0: GOTO L8
30: jnz 1 3 GOTO END
31: sub b -17 L8
32: jnz 1 -23 GOTO L2
END
The innermost (L4) loop (addresses 12-20) can be directly
translated to pseudo code as:
def L4(regs):
while True:
regs["g"] = regs["d"]
regs["g"] *= regs["e"]
regs["g"] -= regs["b"]
if regs["g"] == 0:
regs["f"] = 0
regs["e"] += 1
regs["g"] = regs["e"]
regs["g"] -= regs["b"]
if regs["g"] == 0:
break
where only g, f and e changes. The g value is always 0
after the loop terminates. The value of e is always b.
The f value is either unchanged, or set to 0.
If we refactor the code a bit further, we get to
def L4(regs):
while True:
regs["g"] = regs["d"] * regs["e"] - regs["b"]
if regs["g"] == 0:
regs["f"] = 0
regs["e"] += 1
regs["g"] = regs["e"] - regs["b"]
if regs["g"] == 0:
break
which means that f is 0 if and only if d*e = b, or in other
words if b/d is an integer in the range [1, b). The whole L4
loop can be removed and replaced with:
def L4(regs):
if regs["b"] % regs["d"] == 0:
v = regs["b"] // regs["d"]
if v >= regs["e"] and v < regs["b"]:
regs["f"] = 0
regs["e"] = regs["b"]
regs["g"] = 0
We could optimise out the L5 loop the same way, but with L4
removed the program runs in a few minutes.
Hideous, crude, ugly - pick any three. Direct tradfn translation of the ASM code, with the L4 hack described above.
]dinput
r←Day23p2 ;b;c;h;d;f;e;g;v
(b c d e f g h)←107900 124900 0 0 0 0 0
:While 1
(f d)←1 2
:While 1
e←2
:If 0=d|b ⍝ L4 hack
v←⌊b÷d
:If (v≥e)∧v<b
f←0
:EndIf
:EndIf
e←b
d+←1
g←d-b
:If g=0
:Leave
:EndIf
:EndWhile
:If f=0
h+←1
:EndIf
g←b-c
:If g=0
:Leave
:EndIf
b-←¯17
:EndWhile
r←h
Day23p2 ⍝ Part 2: 907
https://adventofcode.com/2017/day/24
Recursicve descent. Reasonably quick (~6s for part 1), despite not being tail-recursive. Part 2 is very similar, and we could probably have combined both parts at a loss of some clarity.
⎕IO←0
DAY24←⍎¨'/'⎕R','¨⊃⎕NGET'data/2017/24.txt'1
Find←{(a b)←↓⍉↑↑⍺⋄⍺[(⍸⍵=a)∪⍸⍵=b]}
]dinput
r←components Day24p1 args;path;pins;strongest;c;bridge
(path pins)←args
strongest←path
:For c :In (components~path) Find pins
bridge←(components~c)Day24p1 (⊂(path,⊂c)),c {r←⍺~⍵⋄0=≢r:⊃⍺⋄⊃r} pins ⍝ Handle when both pins are equal
:If (+/∊bridge)>+/∊strongest
strongest←bridge
:EndIf
:EndFor
r←strongest
+/∊DAY24 Day24p1 (⊂0 0) 0 ⍝ Part 1: 1511
]dinput
r←components Day24p2 args;path;pins;longest;c;bridge
(path pins)←args
longest←path
:For c :In (components~path) Find pins
bridge←(components~c)Day24p2 (⊂(path,⊂c)),c {r←⍺~⍵⋄0=≢r:⊃⍺⋄⊃r} pins ⍝ Handle when both pins are equal
:If (≢bridge)>≢longest
longest←bridge
:ElseIf ((≢bridge)=≢longest)∧(+/∊bridge)>+/∊longest
longest←bridge
:EndIf
:EndFor
r←longest
+/∊DAY24 Day24p2 (⊂0 0) 0 ⍝ Part 2: 1471
After some discussion on the APL Orchard forum, @ngn offered up the follwing version for part 1, which is significantly faster, shorter and no tradfn:
s←+/↑DAY24⋄n←1+⌈/∊DAY24⋄g←(⍳n)∘.∊DAY24⋄u←∘.≠⍨⍳≢DAY24
0{∨/c←⍵∧⍺⌷g:⌈/t+(-⍺-t←c/s)∇¨↓⍵∧⍤1⊢c⌿u⋄0}≡¨DAY24
If we un-golf it a bit, it's a bit easier to see how that works:
STRENGTHS←+/↑DAY24
COUNT←1+⌈/∊DAY24
GRAPH←(⍳COUNT)∘.∊DAY24
INVIDM←∘.≠⍨⍳≢DAY24 ⍝ Inverted identity matrix used to exclude the current item
]dinput
D24p1←{
candidates←⍵∧⍺⌷GRAPH
t←candidates/STRENGTHS
∨/candidates:⌈/t+(-⍺-t)∇¨↓⍵∧⍤1⊢candidates⌿INVIDM
0
}
0 D24p1 ≡¨DAY24
https://adventofcode.com/2017/day/25
All I want for Christmas is a Turing Machine.
Our given state machine looks like so:
+---+-------+-------+
| | 0 | 1 |
+---+-------+-------+
| A | 1 R B | 0 L C |
| B | 1 L A | 1 R D |
| C | 1 R A | 0 L E |
| D | 1 R A | 0 R B |
| E | 1 L F | 1 L C |
| F | 1 R D | 1 R A |
+---+-------+-------+
⎕IO←0
STATE←6 6⍴1 1 1 0 ¯1 2 1 ¯1 0 1 1 3 1 1 0 0 ¯1 4 1 1 0 0 1 1 1 ¯1 5 1 ¯1 2 1 1 3 1 1 0
]dinput
Day25←{
(pos state)←⍵
args←(0 3[pos⊃TAPE])+⍳3
(nv m ns)←STATE[state;args]
TAPE[pos]←nv
(pos+m) ns
}
TAPE←12919244⍴0⋄_←Day25⍣12919244⊢6459622 0⋄+/TAPE ⍝ 4287