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 off
DAY1←⊃⊃⎕NGET'data/2015/01.txt'1
Day1p1←{+/+⌿-@2⌷'()'∘.=⍵} ⍝ Binary mask with positions for '(' in row 1 and ')' in row 2,
⍝ and then row 2 negated. Sum down, then across.
Day1p1 DAY1 ⍝ 138
Day1p2←{1⊃⍸{⍵<0}¨+\+⌿-@2⌷'()'∘.=⍵} ⍝ As before, but scan-sum across and create mask of negatives and pick first.
Day1p2 DAY1 ⍝ 1771
DAY2←2⊃¨'x'⎕VFI¨⊃⎕NGET 'data/2015/02.txt' 1 ⍝ Many lines. Pick out three ints from each, separated by 'x'
Day2p1←{(l w h)←⍵ ⋄ s[⊃⍋s]++/2×s←(l×w) (w×h) (h×l)}
+/Day2p1¨DAY2 ⍝ 1606483
Day2p2←{(ll ww hh)←2×⍵⋄c[⊃⍋c←(hh+ww) (ww+ll) (ll+hh)]+×/⍵}
+/Day2p2¨DAY2 ⍝ 3842356
DAY3←⊃⊃⎕NGET'data/2015/03.txt'1
]dinput
Day3p1←{
points←-@1 3⌷'^v<>'∘.=⍵ ⍝ Matrix with 4 rows -y, y, -x, x
⍉(+\+⌿points[3 4;]),[0.5]+\+⌿points[1 2;] ⍝ Sum first along axis 1, then sum-scan along axis 2
} ⍝ separately for x and y. Laminate x and y parts, transpose
1+≢∪ Day3p1 DAY3 ⍝ 2081
Day3p2←{(1⊃p)⍪2⊃p←Day3p1¨{⍵⊢∘⊂⌸⍨2|⍳≢⍵}⍵} ⍝ Unzip ⍵ so we can treat santa and robo's paths separately
≢∪ Day3p2 DAY3 ⍝ 2341
Md5←{⎕SH 'md5 -q -s "',⍵,'"'} ⍝ No Dyalog built-in MD5 function, sadly
Day4p1←{⍺←0⋄'00000'≡5↑Md5 ⍵,⍕⍺:⍺⋄(⍺+1)∇⍵} ⍝ NOTE: WORKS, BUT INTRACTABLE WITHOUT NATIVE MD5
DAY5←⊃⎕NGET'data/2015/05.txt'1
]dinput
Day5p1←{
3>+/+⌿'aeiou'∘.=⍵:0 ⍝ Three or more vowels
0≠+/'ab' 'cd' 'pq' 'xy'∊↓{⍵}⌺2⊢⍵:0 ⍝ Illegal pairs
1≤+/=⌿⍵,[0.5](≢⍵)↑1↓⍵ ⍝ Repeated letters
}
+/Day5p1¨DAY5 ⍝ 238
]dinput
Day5p2←{
0=≢'(..).*\1'⎕S'\1'⊢⍵:0 ⍝ Regexery feels like a defeat
0≠+/(⊣/=⊢/){⍵}⌺3⊢⍵ ⍝ Overlapping triplets, compare first and last columns
}
+/Day5p2¨DAY5 ⍝ 69
https://adventofcode.com/2015/day/6
This time we'll go old-skool with a tradfn.
⎕IO←0 ⍝ The problem's coordinates are 0-based.
'iotag'⎕CY'dfns' ⍝ iotag -- generalised iota -- alows us to create ranges from a to b
DAY6←⊃⎕NGET 'data/2015/06.txt' 1
RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⊢ ⍵}
]dinput
res←Day6p1 data;state;parsed;row;spec;points
state←1000 1000⍴0
parsed←'(on|off|toggle)\s(\d+),(\d+)[^\d]+(\d+),(\d+)' RegexGroups data
:For row :In parsed
spec←⍎¨1↓row
points←(spec[0] iotag spec[2]) ∘., (spec[1] iotag spec[3])
:If (0⊃row)≡'on'
state[points]←1
:ElseIf (0⊃row)≡'off'
state[points]←0
:Else
state[points]←~state[points]
:EndIf
:EndFor
res←+/+⌿state
Day6p1 DAY6 ⍝ 569999
Part 2 is more of the same, just with different updates: turn on means add 1, turn off means subtract 1, capped at 0, and toggle means add 2.
]dinput
res←Day6p2 data;state;parsed;row;op;spec;points
state←1000 1000⍴0
parsed←'(on|off|toggle)\s(\d+),(\d+)[^\d]+(\d+),(\d+)' RegexGroups data
:For row :In parsed
spec←⍎¨1↓row
points←(spec[0] iotag spec[2]) ∘., (spec[1] iotag spec[3])
:If (0⊃row)≡'on'
state[points]+←1
:Elseif (0⊃row)≡'off'
state[points]-←1
state[points]⌈←0
:Else
state[points]+←2
:EndIf
:EndFor
res←+/+⌿state
Day6p2 DAY6 ⍝ 17836115
https://adventofcode.com/2015/day/7
A very interesting question. We have a set of "gates", specified like so:
af AND ah -> ai
NOT lk -> ll
hz RSHIFT 1 -> is
NOT go -> gp
du OR dt -> dv
So, for example, the gate "ai" has the value of the bitwise AND of the values of gates "af" and "ah". In other words, the gates are functions with inputs and outputs, and the input data is already a full program. We can exploit this in our solution. Take
af AND ah -> ai
and turn this into an APL function
ai←{(af ⍬) AND (ah ⍬)}
assuming that we have the AND function defined. If we convert the input specifications to such APL functions, all we need to do is to run the "a" function to get our result. Elegant, but with a small problem: it doesn't work.
The reason for this is that the functions can be expensive to compute, as may require many, many calls. However, as they never change, we can cache the values after the first invocation, and with this in place the solution is found very quickly. Instead of the above expression, we make
ai←({⍵⊣⍵.c←¯1}⎕NS'') Cache {(af ⍬) AND (ah ⍬)}
with the Cache operator defined as
Cache←{¯1=⍺⍺.c:⍺⍺.c⊣⍺⍺.c←⍵⍵ ⍵⋄⍺⍺.c}
which takes a namespace holding the cached int value.
Health warning: there is no macro facility in APL, so instead we're abusing the hydrant (⍎) function to evaluate APL code represented as strings. In lisp lingo, this is 100% unhygenic and rather unsafe.
)clear
⎕IO←1
DAY7←⊃⎕NGET'data/2015/07.txt'1
⍝ Some helper functions
Bin←{(16⍴2)⊤⍵}
Dec←{2⊥⍵}
RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)}⊢⍵}
Cache←{¯1=⍺⍺.c:⍺⍺.c⊣⍺⍺.c←⍵⍵ ⍵⋄⍺⍺.c}
⍝ Gate functions as defined in the problem statement
AND←{Dec (Bin ⍺)∧(Bin ⍵)}
OR←{Dec (Bin ⍺)∨(Bin ⍵)}
NOT←{Dec ~(Bin ⍵)}
RSHIFT←{ba←Bin ⍺⋄Dec (-≢ba)↑(-⍵)↓ba}
LSHIFT←{ba←Bin ⍺⋄Dec (≢ba)↑⍵↓ba}
Arg←{1=1⊃⎕VFI ⍵:⍵⋄∊'(',⍵,' ⍬)'}
Parse←{'(\w*)\s*(AND|NOT|OR|RSHIFT|LSHIFT|)\s*(\w*)\s->\s(\w+)' RegexGroups ⍵}
]dinput
Compile←{ ⍝ Turn the parsed input to strings representing APL functions.
(⊃⍵[1])≡'NOT':∊⍵[4],'←({⍵⊣⍵.c←¯1}⎕NS'''') Cache {NOT ',(Arg ⊃⍵[3]),'}'
0=≢⊃⍵[2]:∊⍵[4],'←({⍵⊣⍵.c←¯1}⎕NS'''') Cache {',(Arg ⊃⍵[1]),'}'
∊⍵[4],'←({⍵⊣⍵.c←¯1}⎕NS'''') Cache {',(Arg ⊃⍵[1]),' ',⍵[2],' ',(Arg ⊃⍵[3]),'}'
}
⍎¨Compile¨Parse DAY7
a ⍬ ⍝ Part1: what's the value of "a"? => 956
Part2: Reset, and then override "b" to the final value of "a" in Part 1. What's the value of "a" now?
⍎¨Compile¨Parse DAY7 ⍝ Reset by recompiling
b←{956} ⍝ Override "b" -- no need for the Cache.
a ⍬ ⍝ Part2: what's the value of "a"? =>40149
)clear
⎕IO←1
DAY8TEXT←⊃⎕NGET 'data/2015/08.txt' 1
DAY8BYTES←⊃{⍺⎕UCS¨⍨⊂'-\w+$'⎕R''⊢⍵}/2↑⎕NGET 'data/2015/08.txt' 1 ⍝ Raw bytes, split on line endings
Day8p1←{(≢⍵)-¯2+≢'\\\\'⎕R'\\'⊢s←'(\\x[a-f0-9]{2}|\\[\''"])'⎕R'⎕'⊢⍵}
+/Day8p1¨DAY8TEXT ⍝ 1350
Day8p2←{(≢⍵)-⍨(2+2×+/bq)++/~bq←3≠34 92⍳⍵} ⍝ +2 for surrounding brackets, +2 for every " and \
+/Day8p2¨DAY8BYTES ⍝ 2085
⎕IO←1
'pmat'⎕CY'dfns'
DAY9←' '(≠⊆⊢)¨'( to | = )'⎕R' '⊃⎕NGET'data/2015/09.txt'1
]dinput
Day9←{
weights←w,w←⍎¨⊢/↑⍵ ⍝ Two copies of the weights, as A->B == B->A
edges←(⊢⍪⌽)28 2⍴(∪⍳⊢),(↑⍵)[;1 2] ⍝ Swap strings for numeric index, and add reverse direction
adj←weights@(↓edges)⊢0⍴⍨2⍴8 ⍝ Build adjacency matrix
(⌊/,⌈/)+/adj[↓{∊⍵}⌺1 2⊢pmat 8] ⍝ Generate length 8 permuations, grab the path length, then min-max.
}
Day9 DAY9 ⍝ p1: 251 p2: 898
Day10←{∊(⍕∘≢,1∘↑)¨⍵⊂⍨1,2≠/⍵} ⍝ For each group of equal elements, generate count+element
≢Day10⍣40⊢'3113322113' ⍝ 329356
≢Day10⍣50⊢'3113322113' ⍝ 4666278
⎕IO←0 ⍝ NOTE: zero-based indexing!
AB←↓⍉↑(⊂,⊂)⎕A ⍝ Repeated pairs: aa bb cc ...
ABC←¯1↓1↓↓{⍵}⌺3⊢⎕A ⍝ Length-3 straights: abc bcd cde ...
]dinput
Valid←{
∨/'OIL'∊⍵:0 ⍝ Rule 2
0=+/ABC∊¯1↓1↓↓{⍵}⌺3⊢⍵:0 ⍝ Rule 1
(+/AB∊{⊂⍵}⌺2⊢⍵)≥2 ⍝ Rule 3
}
We need to generate the next password from a string of uppercase letters. This corresponds to adding 1 in base 26 (if ⎕IO←0
), which is conveniently expressable in APL using the encode and decode primitives. Here is an illustration:
⎕←b26←1+26⊥⎕A⍸'HELLO' ⍝ Convert string to base 26, and add 1
⎕←d←(5⍴26)⊤b26 ⍝ Convert back to decimal
⎕A[d] ⍝ Turn back into character vector
Day11←{({⎕A[(8⍴26)⊤1+26⊥⎕A⍸⍵]}⍣{Valid ⍺})⍵}
⎕←part1←Day11 'HEPXCRRQ' ⍝ HEPXXYZZ
Day11 part1 ⍝ HEQAABCC
⎕IO←1
]dinput
ValidItems←{
values←{0=≢⍵.(⎕NL ¯2):⍬⋄⍵.(⍎¨⎕NL ¯2)} ⍵
(⊂'red')∊values:,0
0=≢⍵.(⎕NL ¯9):values
values,∊∇¨⍵.(⍎¨⎕NL ¯9)
}
]dinput
Day12p2←{
{(1=2|⎕DR)⍵}⍵:⍵ ⍝ Are we a number?
(⍕≡⊢)⍵:0 ⍝ Are we a string?
{(326=⎕DR⍵)∧(0=≡)⍵} ⍵:+/∇ValidItems ⍵ ⍝ Are we an object?
+/∊∇¨⍵ ⍝ We're a list
}
{+/(3=⊢/⍵)/⍵[;3]} (⎕JSON⍠'M')⊃⊃⎕NGET'data/2015/12.txt'1 ⍝ Part 1: just sum all values...156366
Day12p2 ⎕JSON⊃⊃⎕NGET'data/2015/12.txt'1 ⍝ Part 2: 96852
https://adventofcode.com/2015/day/13
This is very similar to day 9, and we can broadly use the same technique.
⎕IO←1
RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⊢ ⍵}
DAY13← ↑'(.+) would (gain|lose) (\d+).+to ([^.]+)' RegexGroups ⊃⎕NGET'data/2015/13.txt'1
EDGES←⍉(⊣/DAY13),[0.5]⊢/DAY13
WEIGHTS←-@(((⊂'lose')≡¨DAY13[;2])/⍳≢DAY13[;2]) ⊢ ⍎¨DAY13[;3]
e←(⍴EDGES)⍴(∪⍳⊢),EDGES ⍝ Convert strings to indexes
adj←WEIGHTS@(↓e)⊢0⍴⍨2⍴8 ⍝ Happiness matrix
adj ⍝ Note: asymmetric!
Unlike Day 9, this graph is directional, so the weight from A to B is not the same as the weight from B to A. So we need to generate all permutations of length 8, but then ensure that we also have the reverse directions -- and also ensure that the end is tied back to the beginning.
The expression p,⊣/p←pmat 8
copies the first column to the end to ensure the circle is connected, and m,1↓[2]⌽m
means that we add in all the reverse connections.
⌈/+/adj[↓{∊⍵}⌺1 2⊢m,1↓[2]⌽m←p,⊣/p←pmat 8] ⍝ Part 1: 733
For part 2 we simply don't connect the circle -- this has the same effect as inserting a weight-0 node.
⌈/+/adj[↓{∊⍵}⌺1 2⊢m,1↓[2]⌽m←pmat 8] ⍝ Part 2: 725
⎕IO←1
DAY14←⍎¨'\d+'⎕S'&'⊃⎕NGET'data/2015/14.txt'1
DATA←(≢DAY14)3⍴DAY14
⍝ Speed, Travel-time, Rest-time, State, Counter, Distance travelled, Score
LB←(((DATA,1),(DATA[;2])),0),0
]dinput
Day14←{
lb←⍵
lb[;5]-←1 ⍝ Decrease the counter
lb[;6]+←lb[;1]×1=lb[;4] ⍝ Move any movers; resters unchanged
lb[;7]+←(⌈/a)=a←lb[;6] ⍝ Add 1 to the leaders col for part 2.
↑{0≠⍵[5]:⍵⋄⍵[3-s[4]]@5⊢s←~@4⊢⍵}¨↓lb ⍝ Perform state transitions where counter is 0
}
RACE←Day14⍣2503⊢LB ⍝ Run for 2503 iterations
⌈/RACE[;6] ⍝ Part 1 is max distance: 2655
⌈/RACE[;7] ⍝ Part 2 is max score: 1059
⎕IO←1
DAY15←(5÷⍨≢d)5⍴d←⍎¨'-?\d+'⎕S'&'⊃⎕NGET'data/2015/15.txt'1 ⍝ The numbers, wrestled into matrix of 5-element rows
CAL←⊢/DAY15 ⍝ Keep calorie data in a vector
INGR←¯1↓[2]DAY15 ⍝ Just the ingredients
Cmb←{(n t)←⍵⋄A←⊃∘.+/(n-1)⍴⊂⍳t⋄⊃,/{⍵,¨⍸(t-⍵)=A}¨⍳t} ⍝ Cmb N M -- All N-length vectors summing to M, N[i]∊⍳M
Day15p1←{ingr←⍵⋄⌈/{×/0∘⌈¨⍵+.×ingr}¨Cmb 4 100} ⍝ Multiply with cost matrix, multiply again, removing negatives
Day15p2←{ingr←⍵⋄cal←⍺⋄⌈/{500=+/cal×⍵:×/0∘⌈¨⍵+.×ingr⋄0}¨Cmb 4 100} ⍝ As above, but exactly 500 cals.
Day15p1 INGR ⍝ 222870
CAL Day15p2 INGR ⍝ 117936
⎕IO←1
DAY16←⊃⎕NGET'data/2015/16.txt'1
TARGET←0 2 7 3 5 1 3 2 3 0
ITEMS←'aki' 'car' 'cat' 'chi' 'gol' 'per' 'pom' 'sam' 'tre' 'viz'
]dinput
ToRow←{
m←↑{(⊂3↑1↓1⊃⍵),⊂⍎1↓2⊃⍵}¨':'(≠⊆⊢)¨⍵ ⍝ Split on ':', pick first 3 letters and convert the numbers
r←10⍴0
r[ITEMS⍳⊣/m]←⊢/m ⍝ Fill in the known quantities
r
}
Parse←{ToRow¨','(≠⊆⊢)¨'Sue \d+:'⎕R''⊢⍵}
]dinput
Day16p1←{
where←⍸0≠⍵
⍺[where]≡⍵[where]
}
]dinput
Day16p2←{
target←⍺
sue←⍵
∧/{
(⍵=3)∨⍵=9:sue[⍵]>target[⍵]
(⍵=5)∨⍵=7:sue[⍵]<target[⍵]
sue[⍵]=target[⍵]
}¨⍸0≠⍵
}
⍸TARGET∘Day16p1¨Parse DAY16 ⍝ Part 1: 40
⍸TARGET∘Day16p2¨Parse DAY16 ⍝ Part 2: 241 TODO: should not also return 225...
https://adventofcode.com/2015/day/17
Count the number of subsets of buckets that can hold exactly 150 units. This can be cast as a count-up from 1 to a "bucket-count"-bit binary number of all 1s. A 1 in a given place means that the corresponding bucket is picked. For example, if we have the following five buckets:
50 44 11 49 42
we need to count from 1 to 31 (11111). If we take for example the seventh (00111) selection we get
50 44 11 49 42
0 0 1 1 1 => 11 + 49 + 42 = 102
We can translate this approach directly to APL.
DAY17←50 44 11 49 42 46 18 32 26 40 21 7 18 43 10 47 36 24 22 40 ⍝ Container volumes
Bin←{(20⍴2)⊤⍵}
Dec←{2⊥⍵}
+/{150=+/DAY17/⍨Bin ⍵}¨⍳Dec 20⍴1 ⍝ Part 1: 654
For part 2 we need to find the fewest number of buckets that can hold 150 units, and then count the number of distinct such combinations. We know there are 654 solutions in total -- let's capture them, rather than just counting them:
VALID←(0≠v)/v←{150=+/DAY17/⍨Bin ⍵:⍵⋄0}¨⍳Dec 20⍴1 ⍝ Return the sequence number if sum is 150, otherwise 0
Next step is to find the fewest number of buckets:
⎕←MIN←⌊/≢¨BUCKETS←{DAY17/⍨Bin ⍵}¨VALID
and then count the solutions using the minimum number of buckets, which is our answer:
+/MIN=≢¨BUCKETS ⍝ 57
https://adventofcode.com/2015/day/18
This is an implementation of Conway's Game of Life. It's a bit of an APL party trick. An excellent walk-through of the technique applied here is provided in a Dyalog webinar.
DAY18←↑'#'=¨⊃⎕NGET'data/2015/18.txt'1
GoL←{≢⍸⍵}⌺3 3∊¨3+0,¨,¨ ⍝ Wait, what kind of witchcraft is this...?
Day18p1←{+/∊GoL⍣100⊢⍵}
Day18p1 DAY18 ⍝ 1061
For part 2, the 4 corner cells are immortal. We can simply ensure those are reset at the end of each iteration:
GoL2←{1@(,1 100∘.,1 100)⊢GoL ⍵}
Day18p2←{+/∊GoL2⍣100⊢⍵}
Day18p2 DAY18 ⍝ 1006
DAY19←⊃⎕NGET'data/2015/19.txt'1
TARGET←⊃¯1↑DAY19
RULES←↓(↑' '(≠⊆⊢)¨¯2↓DAY19)[;1 3]
]dinput
ApplyRule←{ ⍝ Apply a transformation rule, returning all resulting strings
(key val)←⍵
⍺∘{
(idx len)←⍵
(idx↑⍺),val,⍺↓⍨idx+len ⍝ Separate the string on the match, and re-join on replacement
}¨key ⎕S{⍵.((1↑Offsets),1↑Lengths)}⊢⍺ ⍝ Each match location
}
≢∪{⊃,/⊆¨⍵}⍣≡TARGET∘ApplyRule¨RULES ⍝ 509 - count uniques in the flattened vector of produced strings
For part 2, we seek the smallest number of transformations to reach the target molecule starting from a single "electron": "e". To solve this we work backwards from the target molecule applying the rules in reverse until we either get to "e", or we reach a point where there is no change.
If there is no change, we shuffle the rules order to break out of the local minimum reached in the search space. This will only result in the shortest path if there is only a single path from "e" to target, which fortunately is the case, and the convergence is super-quick.
Obviously not the most array-based solution, and most natural as a tradfn.
]dinput
res←molecule Day19p2 rules;current;count;prev;val;key
current←molecule
count←0
:While current≢,'e'
prev←current
:For val key :In rules ⍝ Note: we apply rules 'backwards'
:If ~key(1∊⍷)current ⍝ Check if rule matches
:Continue
:EndIf
current←(key ⎕R val⍠'ML'1)current ⍝ Apply single step -- as _unwinding_ transformations
count+←1
:If prev≡current ⍝ No change after applying all rules: local minimum
current←molecule
count←0
rules←(⊢⌷⍨∘⊂?⍨∘≢)rules ⍝ Shuffle the rules ordering to break out of local minimum
:EndIf
:EndFor
:EndWhile
res←count
TARGET Day19p2 RULES ⍝ 195
https://adventofcode.com/2015/day/20
The obvious observation is that the number of elf-visits at a given house (part 1) is the sum of the divisors of the house number. There is no handy built-in for this -- the APL Cart suggestion of (+/∘∪⊢∨⍳)
is too inefficient here. We can roll our own using the handy pco
prime sieve from the dfns workspace.
⎕IO←1
'pco'⎕CY'dfns' ⍝ Pull in 'pco' -- a fast prime sieve
DAY20←29000000
DivSum←{×/{(¯1+⍺*⍵+1)÷⍺-1}⌿2 pco ⍵} ⍝ Sum of positive divisors, aka σ(n)
Divisors←{⍵=1:,1⋄∊∘.×/{⍺∘.*0,⍳⍵}⌿2 pco ⍵}
1+⍣{(DivSum ⍺)≥DAY20÷10}1 ⍝ Part 1: 665280 -- note: takes around 15s or so to run
1+⍣{({11×+/(⍵{⍺≤⍵×50}¨d)/d←Divisors ⍵} ⍺)≥DAY20}1 ⍝ Part 2: 705600 -- note: takes around 30s or so to run
https://adventofcode.com/2015/day/21
Fight-rules:
DAY21←103 9 2 ⍝ The boss-spec: Hitpoints Damage Armor
We're given the characteristics of weaponry and armor etc. Turn this into a matrix, adding an extra row of three zeros for armor, signifying that it's optional, and two such rows for the same reason in the rings section.
ITEMS←8 4 0 10 5 0 25 6 0 40 7 0 74 8 0 0 0 0 13 0 1 31 0 2 53 0 3 75 0 4 102 0 5 0 0 0 0 0 0 25 1 0 50 2 0 100 3 0 20 0 1 40 0 2 80 0 3
(COSTS DAMAGE ARMOR)←↓⍉(3÷⍨≢ITEMS) 3⍴ITEMS
We can now construct a set of vectors representing the possible choices of 1 weapon, 0 or 1 armour, and 0, 1 or 2 rings (which must be unique).
⍝ <-weapon> <---armor---> <--------ring 1-------> <--------ring 2------->
CHOICES←,1 2 3 4 5∘.,6 7 8 9 10 11∘.,12 13 14 15 16 17 18 19∘.,12 13 14 15 16 17 18 19
VALID←~{(⍵[3]>14)∧(⍵[3]=⍵[4])}¨CHOICES
OPTIONS←VALID/CHOICES
]dinput
Winner←{ ⍝ boss Winner selection
⍺ {
bhp←⍺[1]-1⌈⍵[2]-⍺[3] ⋄ bhp≤0:1
php←⍵[1]-1⌈⍺[2]-⍵[3] ⋄ php≤0:0
(bhp@1⊢⍺)∇php@1⊢⍵
} 100,(+/DAMAGE[⍵]),+/ARMOR[⍵]
}
CHARGE←{+/COSTS[⍵]}¨OPTIONS ⍝ Total costs per kit-out in the store
⌊/CHARGE[⍸DAY21∘Winner¨OPTIONS] ⍝ Part 1: 121 -- least spend for a win
⌈/CHARGE[⍸~DAY21∘Winner¨OPTIONS] ⍝ Part 2: 201 -- most spend for a loss
https://adventofcode.com/2015/day/22
As in the previous question, we're given a table of data, this time describing "spells" and "effects". We massage these into a nice matrix with the following columns:
mana-change player-hp boss-hp total-cost shield poison recharge
⍝ State vector fields: mana-change player-hp boss-hp total-spend shield poison recharge
⍝
⍝ <-magic missile-> <-----drain-----> <-----shield-----> <-----poison-----> <----recharge---->
⎕←MAGIC←5 7⍴¯53 0 ¯4 53 0 0 0 ¯73 2 ¯2 73 0 0 0 ¯113 0 0 113 6 0 0 ¯173 0 0 173 0 6 0 ¯229 0 0 229 0 0 5
This time, at each turn we must choose a spell to cast from the above five. This turns the search space into a graph, and the solution one of costed path finding.
At each point we have a state, consisting of the player and the boss with their respective "stats", plus the player's stash of "mana" and any lingering spell effects. A state transition is the casting of a spell, the application of any multi-turn spells already cast, plus the response from the boss.
START←500 50 71 0 0 0 0 ⍝ State vector: mana player-hp boss-hp total-spend shield poison recharge
⍝ Effects
Shield←{⍵[5]>0:¯1∘+@5⊢⍵⋄⍵} ⍝ No need to do anything apart from decrease counter
Poison←{⍵[6]>0:¯3∘+@3⊢¯1∘+@6⊢⍵⋄⍵} ⍝ Boss: hp-←3, if active
Recharge←{⍵[7]>0:101∘+@1⊢¯1∘+@7⊢⍵⋄⍵} ⍝ Mana+←101, if active
ApplyEffects←{Finished ⍵:⍵⋄Shield Poison Recharge ⍵}
BossTurn←{Finished ⍵:⍵⋄dp←10-7×⍵[5]>0⋄{⍵-dp}@2⊢⍵}
PlayerTurn←{⍵∘Cast¨↓MAGIC}
Finished←{(⍵[2]≤0)∨⍵[3]≤0}
StateTransition←{Finished ⍵:⍬ ⋄ ApplyEffects∘BossTurn¨PlayerTurn ApplyEffects ⍵}
]dinput
Cast←{ ⍝ Cast a spell: state Cast spell
⍺[1]<-⍵[1]:⍺ ⍝ Too expensive!
⍵[3]<0:⍺+⍵ ⍝ Non-time limited spell; just cast it
idx←⍸0≠¯3↑⍵
0≠idx⌷¯3↑⍺:⍺ ⍝ Time-limited spell already in effect!
⍺+⍵ ⍝ Ok, we can cast spell.
}
We now crudely brute out the whole graph and ask questions later. This could be done much faster with a full Dijkstra or A* implementation instead.
]dinput
BFS←{ ⍝ Naive breadth-first search, to the bottom. Accumulate visited states as ⍺
⍺←⍬⋄0=≢⍵:⍺
current←⊃1↑⍵ ⋄ queue←1↓⍵
neighbours←StateTransition current
(⍺,⊂current)∇queue∪neighbours~⍺
}
]dinput
Day22p1←{
data←BFS ⍵
bhp←(↑data)[;3] ⍝ Boss hitpoints
⌊/(↑(0>bhp)/data)[;4] ⍝ Pick winning rows, and find smallest total cost
}
Day22p1 ⊂START ⍝ 1824 -- note, takes a minute or two to run.
DAY23←⊃⎕NGET'data/2015/23.txt'1
RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⊢ ⍵}
Parse←{0<≢'^[+-]?\d+$'⎕S'&'⊢⍵:⍎⍵⋄⍵≡,'a':1⋄⍵≡,'b':2⋄⍵}
data←{⊃,/⊆¨⍵}⍣≡'([a-z]{3}) ([+ab0-9-]+),?\s*([+0-9]*)'∘RegexGroups¨DAY23
MEM←(3÷⍨≢data) 3⍴Parse¨data
]dinput
Day23←{
ip←3⌷⍺
ip>≢⍵:⍺
instr←ip⌷⍵⋄op←⊃instr ⍝ Fetch instruction at ip, opcode is first element
op≡'hlf':(⍺ {r←⊃⍵⋄1∘+@3⊢(2÷⍨r⌷⍺)@r⊢⍺} 1↓instr)∇⍵ ⍝ Halve reg content, add 1 to ip
op≡'jio':(⍺ {(r d)←⍵⋄1=r⌷⍺:d∘+@3⊢⍺⋄1∘+@3⊢⍺} 1↓instr)∇⍵ ⍝ If reg content is 1, add delta to ip, else add 1
op≡'inc':(⍺ {r←⊃⍵⋄1∘+@3⊢(1+⍨r⌷⍺)@r⊢⍺} 1↓instr)∇⍵ ⍝ Add 1 to reg content, add 1 to ip
op≡'tpl':(⍺ {r←⊃⍵⋄1∘+@3⊢(3×⍨r⌷⍺)@r⊢⍺} 1↓instr)∇⍵ ⍝ 3 × reg content, add 1 to ip
op≡'jmp':(⍺ {d←⊃⍵⋄d∘+@3⊢⍺} 1↓instr)∇⍵ ⍝ Add delta to ip
op≡'jie':(⍺ {(r d)←⍵⋄0=2|r⌷⍺:d∘+@3⊢⍺⋄1∘+@3⊢⍺} 1↓instr)∇⍵ ⍝ If reg content is even, add delta to ip, else add 1
}
2⌷0 0 1 Day23 MEM ⍝ 255
2⌷1 0 1 Day23 MEM ⍝ 334
https://adventofcode.com/2015/day/24
Data is a list of very prime-looking numbers. Task is to create three groups, summing to the same number, with the extra constraint that the first group should minimise the number of items.
'cmat' 'big'⎕CY'dfns'
DAY24←1 3 5 11 13 17 19 23 29 31 37 41 43 47 53 59 67 71 73 79 83 89 97 101 103 107 109 113
3÷⍨+/DAY24
By applying part guesswork and part brute force, we will start at the minimum number of items required, try all combinations, and if none is found, add another item such that the sum is 508 (data sum divided by 3). In other words, we only search for the first group, and "hope" that the rest works out. The lower bound of the number of items is 5, as 103 + 107 + 109 + 113 < 508, but adding the fifth largest item takes us above.
]dinput
TrySelection←{
numbers←⍺
(elements val)←⍵
Best←{⍺≡⍬:⍵⋄(×/⍺)<×/⍵:⍺⋄⍵} ⍝ Compare products of elements
⍬{
0=≢⍵:⍺
weights←numbers[1↑⍵] ⍝ Selected elements
val=+/weights:(⍺ Best weights)∇1↓⍵ ⍝ Correct sum? If so, any better than previous best?
⍺∇1↓⍵ ⍝ Keep going
}↑elements cmat ≢numbers ⍝ All possible selection of 'elements' numbers
}
Day24←{n←⍵⋄val←⍺÷⍨+/⍵⋄⍵ {v←n TrySelection ⍵ val⋄v≢⍬:v⋄∇⍵+1} 5} ⍝ Starting from 5 elements, increase until solution
⊃×big/3 Day24 DAY24 ⍝ Part 1: 10439961859 -- need to use big-number × from dfns
⊃×big/4 Day24 DAY24 ⍝ Part 2: 72050269
https://adventofcode.com/2015/day/25
Christmas day! We celebrate by brute-forcing our way, zig-zagging exactly as described in the most naively possible way.
DAY25←2947 3029
]dinput
Day25←{
⍺←2 1
n←33554393|252533×⍵
⍺≡2947 3029:n
1=1⌷⍺:n∇⍨1,⍨1+2⌷⍺
n∇⍨¯1 1+⍺
}
Day25 20151125 ⍝ 19980801