summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--day17.fsx27
-rw-r--r--day18.fsx86
-rw-r--r--day18.py66
-rw-r--r--day19.py37
-rw-r--r--day20.fsx71
-rw-r--r--day21.py47
-rw-r--r--day22.jl25
-rw-r--r--day23.c22
-rw-r--r--day23.fsx84
-rw-r--r--day24.fsx21
-rw-r--r--day25.fsx64
11 files changed, 550 insertions, 0 deletions
diff --git a/day17.fsx b/day17.fsx
new file mode 100644
index 0000000..33bf215
--- /dev/null
+++ b/day17.fsx
@@ -0,0 +1,27 @@
+type CircularArray =
+ struct
+ val mutable arr: int array
+ val mutable position: int
+ val mutable stepNum: int
+ val increment: int
+ new(i) = {arr=[|0|]; position=0; stepNum=1; increment=i}
+
+ member this.step() =
+ this.position <- 1 + (this.position + this.increment) % (Array.length this.arr)
+ this.arr <- Array.insertAt this.position this.stepNum this.arr
+ this.stepNum <- this.stepNum + 1
+ end
+
+let () =
+ let mutable arr = new CircularArray(377)
+ for i = 1 to 2017 do
+ arr.step()
+
+ arr.arr[arr.position+1] |> printfn "%d"
+
+ let mutable p = 0
+ let mutable oneth = 1
+ for i = 1 to 50000000 do
+ p <- (p + (377 % i) + 1) % i
+ if p = 0 then oneth <- i
+ printfn "%d" oneth \ No newline at end of file
diff --git a/day18.fsx b/day18.fsx
new file mode 100644
index 0000000..383519f
--- /dev/null
+++ b/day18.fsx
@@ -0,0 +1,86 @@
+open System.IO
+open System.Collections.Generic
+open System.Text.RegularExpressions
+
+type Register = string
+type Value =
+ | Literal of int64
+ | Reg of Register
+
+let (|InstRegex|_|) pattern string =
+ let m = Regex(pattern).Match(string)
+ if m.Success then
+ Some(List.tail [for g in m.Groups -> g.Value])
+ else None
+
+type Instruction =
+ | Snd of x: Value
+ | Set of x: Register * y: Value
+ | Add of x: Register * y: Value
+ | Mul of x: Register * y: Value
+ | Mod of x: Register * y: Value
+ | Rcv of x: Value
+ | Jgz of x: Value * y: Value
+
+let resolveValue (value: Value) (registers: Dictionary<string, int64> ) =
+ let tryGetDefaultRegister key =
+ if not (registers.ContainsKey(key)) then registers.[key] <- 0L
+ registers.[key]
+
+ match value with
+ | Literal x -> x
+ | Reg x -> tryGetDefaultRegister x
+
+let parseValue line =
+ match line with
+ | InstRegex "snd ([a-p])" [x] -> Snd (Reg x)
+ | InstRegex "snd (-?\d+)" [x] -> Snd (Literal (int x))
+ | InstRegex "set ([a-p]) ([a-p])" [x; y] -> Set (x, Reg y)
+ | InstRegex "set ([a-p]) (-?\d+)" [x; y] -> Set (x, Literal (int y))
+ | InstRegex "add ([a-p]) ([a-p])" [x; y] -> Add (x, Reg y)
+ | InstRegex "add ([a-p]) (-?\d+)" [x; y] -> Add (x, Literal (int y))
+ | InstRegex "mul ([a-p]) ([a-p])" [x; y] -> Mul (x, Reg y)
+ | InstRegex "mul ([a-p]) (-?\d+)" [x; y] -> Mul (x, Literal (int y))
+ | InstRegex "mod ([a-p]) ([a-p])" [x; y] -> Mod (x, Reg y)
+ | InstRegex "mod ([a-p]) (-?\d+)" [x; y] -> Mod (x, Literal (int y))
+ | InstRegex "rcv ([a-p])" [x] -> Rcv (Reg x)
+ | InstRegex "rcv (-?\d+)" [x] -> Rcv (Literal (int x))
+ | InstRegex "jgz ([a-p]) ([a-p])" [x; y] -> Jgz (Reg x, Reg y)
+ | InstRegex "jgz ([a-p]) (-?\d+)" [x; y] -> Jgz (Reg x, Literal (int y))
+ | InstRegex "jgz (-?\d+) ([a-p])" [x; y] -> Jgz (Literal (int x), Reg y)
+ | InstRegex "jgz (-?\d+) (-?\d+)" [x; y] -> Jgz (Literal (int x), Literal (int y))
+ | x -> printfn "%A" x; failwith "invalid input"
+
+let rec executeInst (instructions: Instruction array) registers (index: int64) lastSound =
+ match instructions.[int index] with
+ | Snd x ->
+ executeInst instructions registers (index + 1L) (resolveValue x registers)
+ | Set(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- resolveValue y registers
+ executeInst instructions registers (index + 1L) lastSound
+ | Add(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- registers.[x] + resolveValue y registers
+ executeInst instructions registers (index + 1L) lastSound
+ | Mul(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- registers.[x] * resolveValue y registers
+ executeInst instructions registers (index + 1L) lastSound
+ | Mod(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- registers.[x] % resolveValue y registers
+ executeInst instructions registers (index + 1L) lastSound
+ | Rcv x ->
+ if (resolveValue x registers) > 0 then lastSound else executeInst instructions registers (index + 1L) lastSound
+ | Jgz(x, y) ->
+ if (resolveValue x registers) > 0 then
+ executeInst instructions registers (index + resolveValue y registers) lastSound
+ else
+ executeInst instructions registers (index + 1L) lastSound
+
+let () =
+ let registers = new Dictionary<string, int64>()
+ let input = File.ReadAllLines "day18.txt" |> Array.map parseValue
+ let recovered = executeInst input registers 0 0
+ printfn "%A" recovered \ No newline at end of file
diff --git a/day18.py b/day18.py
new file mode 100644
index 0000000..15a9545
--- /dev/null
+++ b/day18.py
@@ -0,0 +1,66 @@
+import queue
+import collections
+import multiprocessing.pool
+
+with open("day18.txt") as program:
+ PROGRAM = [line.strip() for line in program]
+
+
+def run(ident, inqueue, outqueue):
+ regs = collections.defaultdict(int)
+ regs['p'] = ident
+
+ def val(v):
+ try:
+ return int(v)
+ except ValueError:
+ return regs[v]
+
+ pc = 0
+ count = 0
+ played = None
+
+ while 0 <= pc < len(PROGRAM):
+ cmd = PROGRAM[pc].split()
+ if cmd[0] == 'snd':
+ played = val(cmd[1])
+ if outqueue:
+ outqueue.put(val(cmd[1]))
+ count += 1
+ elif cmd[0] == 'set':
+ regs[cmd[1]] = val(cmd[2])
+ elif cmd[0] == 'add':
+ regs[cmd[1]] += val(cmd[2])
+ elif cmd[0] == 'mul':
+ regs[cmd[1]] *= val(cmd[2])
+ elif cmd[0] == 'mod':
+ regs[cmd[1]] %= val(cmd[2])
+ elif cmd[0] == 'rcv':
+ if inqueue:
+ try:
+ regs[cmd[1]] = inqueue.get(timeout=5)
+ except queue.Empty:
+ return count
+ elif regs[cmd[1]] != 0:
+ return played
+ elif cmd[0] == 'jgz':
+ if val(cmd[1]) > 0:
+ pc += val(cmd[2])
+ continue
+ pc += 1
+
+ return count
+
+
+print('PART 1:', run(0, None, None))
+
+pool = multiprocessing.pool.ThreadPool(processes=2)
+
+q1 = multiprocessing.Queue()
+q2 = multiprocessing.Queue()
+
+res1 = pool.apply_async(run, (0, q1, q2))
+res2 = pool.apply_async(run, (1, q2, q1))
+
+res1.get()
+print('PART 2:', res2.get()) \ No newline at end of file
diff --git a/day19.py b/day19.py
new file mode 100644
index 0000000..eddbe77
--- /dev/null
+++ b/day19.py
@@ -0,0 +1,37 @@
+with open("day19.txt") as diagram:
+ l = [line.strip('\n') for line in diagram]
+
+lx, ly = 0, 0
+sx, sy = 0, 0
+while l[sx][sy] == ' ':
+ sy += 1
+dx, dy = 1, 0
+
+ddx = [1, -1, 0, 0]
+ddy = [0, 0, -1, 1]
+ans = 0
+ret = ""
+while True:
+ ans += 1
+ if l[sx][sy].isupper():
+ ret += l[sx][sy]
+ nx, ny = sx + dx, sy + dy
+ if nx >= 0 and nx < len(l) and ny >= 0 and ny < len(l[nx]) and l[nx][ny] != ' ':
+ lx, ly, sx, sy = sx, sy, nx, ny
+ else:
+ k = 0
+ good = False
+ while k < len(ddx):
+ dx, dy = ddx[k], ddy[k]
+ nx, ny = sx + dx, sy + dy
+ if nx == lx and ny == ly:
+ k += 1
+ continue
+ if nx >= 0 and nx < len(l) and ny >= 0 and ny < len(l[nx]) and l[nx][ny] != ' ':
+ lx, ly, sx, sy = sx, sy, nx, ny
+ good = True
+ break
+ k += 1
+ if not good:
+ print("trail ends at {} {} with string {} and length {}".format(sx, sy, ret, ans))
+ break \ No newline at end of file
diff --git a/day20.fsx b/day20.fsx
new file mode 100644
index 0000000..e357986
--- /dev/null
+++ b/day20.fsx
@@ -0,0 +1,71 @@
+open System.IO
+open System.Text.RegularExpressions
+
+type Vector =
+ struct
+ val mutable x: int
+ val mutable y: int
+ val mutable z: int
+ new(X, Y, Z) = {x=X; y=Y; z=Z}
+
+ member this.add(other: Vector) =
+ this.x <- this.x + other.x
+ this.y <- this.y + other.y
+ this.z <- this.z + other.z
+
+ member this.manhattan() =
+ abs this.x + abs this.y + abs this.z
+
+ override this.ToString() =
+ sprintf "(%d, %d, %d)" this.x this.y this.z
+ end
+
+type Projectile =
+ struct
+ val id: int
+ val mutable position: Vector
+ val mutable velocity: Vector
+ val acceleration: Vector
+ new(ID, pos, vel, acc) = {id=ID; position=pos; velocity=vel; acceleration=acc}
+
+ member this.update() =
+ this.velocity.add(this.acceleration)
+ this.position.add(this.velocity)
+ this
+
+ member this.distance() =
+ this.velocity.manhattan()
+
+ override this.ToString() =
+ sprintf "p=%A v=%A a=%A" this.position this.velocity this.acceleration
+ end
+
+let parseInput i str =
+ let m = Regex("(-?\d+)").Matches(str)
+ let values = [for g in m -> int g.Value]
+ if List.length values <> 9 then printfn "%A" values; failwith "invalid input"
+ Projectile(i, Vector(values[0], values[1], values[2]),
+ Vector(values[3], values[4], values[5]),
+ Vector(values[6], values[7], values[8]))
+
+let part1() =
+ let mutable projectiles = File.ReadAllLines "day20.txt" |> Array.mapi parseInput
+ // assume that 1000 simulations is good enough
+ for i = 1 to 1000 do
+ projectiles <- Array.map (fun (x: Projectile) -> x.update()) projectiles
+ Array.minBy (fun (x: Projectile) -> x.distance()) projectiles |> (fun x -> x.id) |> printfn "%d"
+
+let part2() =
+ let mutable projectiles = File.ReadAllLines "day20.txt" |> Array.mapi parseInput
+ for i = 1 to 1000 do
+ projectiles <- Array.map (fun (x: Projectile) -> x.update()) projectiles
+ let uncollided = Array.groupBy (fun (x: Projectile) -> x.position) projectiles
+ |> Array.filter (fun (pos, xs) -> Array.length xs = 1)
+ |> Array.map snd
+ |> Array.fold Array.append Array.empty
+ projectiles <- uncollided
+ Array.length projectiles |> printfn "%d"
+
+let () =
+ part1()
+ part2() \ No newline at end of file
diff --git a/day21.py b/day21.py
new file mode 100644
index 0000000..5904366
--- /dev/null
+++ b/day21.py
@@ -0,0 +1,47 @@
+import numpy as np
+
+
+with open('day21.txt') as f:
+ instructions = f.readlines()
+
+mappings = {}
+start = '.#./..#/###'
+
+
+def translate_to_np(s):
+ return np.array([[c == '#' for c in l]
+ for l in s.split('/')])
+
+for line in instructions:
+ k, v = map(translate_to_np, line.strip().split(' => '))
+ for a in (k, np.fliplr(k)):
+ for r in range(4):
+ mappings[np.rot90(a, r).tobytes()] = v
+
+
+def enhance(grid):
+ size = len(grid)
+ by = 2 if size % 2 == 0 else 3
+ resize = lambda x: x * (by+1) // by
+ new_size = resize(size)
+ solution = np.empty((new_size, new_size), dtype=bool)
+ squares = range(0, size, by)
+ new_squares = range(0, new_size, by+1)
+
+ for i, ni in zip(squares, new_squares):
+ for j, nj in zip(squares, new_squares):
+ square = grid[i:i+by, j:j+by]
+ enhanced = mappings[square.tobytes()]
+ solution[ni:ni+by+1, nj:nj+by+1] = enhanced
+ return solution
+
+def solve(part):
+ grid = translate_to_np(start)
+ iterations = 5 if part == 1 else 18
+ for _ in range(iterations):
+ grid = enhance(grid)
+ return int(grid.sum())
+
+
+print(solve(part=1))
+print(solve(part=2))
diff --git a/day22.jl b/day22.jl
new file mode 100644
index 0000000..6e13236
--- /dev/null
+++ b/day22.jl
@@ -0,0 +1,25 @@
+grid = Int.(hcat(collect.(readlines("day22.txt"))...).=='#')'
+testgrid = [0 0 1; 1 0 0; 0 0 0]
+
+rule1 = reshape([0 -1 1 0 0 1 -1 0], 2, 2, :)
+rule2 = reshape([0 -1 1 0 1 0 0 1 0 1 -1 0 -1 0 0 -1], 2, 2, :)
+
+function virus(grid, steps, dirs)
+ (i, j), n = div.(size(grid).+1, 2), size(dirs, 3)
+ di, dj, inf = -1, 0, 0
+ g = Dict((i,j)=>grid[i,j]*div(n,2) for i=1:size(grid,1), j=1:size(grid,2))
+ for _=1:steps
+ x = get(g, (i,j), 0)
+ g[i,j] = mod(x+1, n)
+ (di, dj) = [di dj] * dirs[:,:,x+1]
+ if x+1==n/2; inf+=1 end
+ i+=di; j+=dj
+ end
+ inf
+end
+
+part1 = virus(grid, 10^4, rule1)
+part2 = virus(grid, 10^7, rule2)
+
+println(part1)
+println(part2)
diff --git a/day23.c b/day23.c
new file mode 100644
index 0000000..9622fdc
--- /dev/null
+++ b/day23.c
@@ -0,0 +1,22 @@
+#include <stdio.h>
+// decompiled assembly from the original problem specification
+int main() {
+ int b = 81;
+ int c = b;
+ int h = 0;
+ b = 100 * b + 100000;
+ c = b + 17000;
+ for (; b<= c; b += 17) {
+ int d = 2;
+ while (d != b) {
+ if (b % d == 0) {
+ ++h;
+ d = b;
+ } else {
+ ++d;
+ }
+ }
+ }
+ printf("%d", h);
+ return 0;
+} \ No newline at end of file
diff --git a/day23.fsx b/day23.fsx
new file mode 100644
index 0000000..5714fad
--- /dev/null
+++ b/day23.fsx
@@ -0,0 +1,84 @@
+open System.IO
+open System.Collections.Generic
+open System.Text.RegularExpressions
+
+type Register = string
+type Value =
+ | Literal of int64
+ | Reg of Register
+
+let (|InstRegex|_|) pattern string =
+ let m = Regex(pattern).Match(string)
+ if m.Success then
+ Some(List.tail [for g in m.Groups -> g.Value])
+ else None
+
+type Instruction =
+ | Set of x: Register * y: Value
+ | Sub of x: Register * y: Value
+ | Mul of x: Register * y: Value
+ | Jnz of x: Value * y: Value
+
+let resolveValue (value: Value) (registers: Dictionary<string, int64> ) =
+ let tryGetDefaultRegister key =
+ if not (registers.ContainsKey(key)) then registers.[key] <- 0L
+ registers.[key]
+
+ match value with
+ | Literal x -> x
+ | Reg x -> tryGetDefaultRegister x
+
+let parseValue line =
+ match line with
+ | InstRegex "set ([a-p]) ([a-p])" [x; y] -> Set (x, Reg y)
+ | InstRegex "set ([a-p]) (-?\d+)" [x; y] -> Set (x, Literal (int y))
+ | InstRegex "sub ([a-p]) ([a-p])" [x; y] -> Sub (x, Reg y)
+ | InstRegex "sub ([a-p]) (-?\d+)" [x; y] -> Sub (x, Literal (int y))
+ | InstRegex "mul ([a-p]) ([a-p])" [x; y] -> Mul (x, Reg y)
+ | InstRegex "mul ([a-p]) (-?\d+)" [x; y] -> Mul (x, Literal (int y))
+ | InstRegex "jnz ([a-p]) ([a-p])" [x; y] -> Jnz (Reg x, Reg y)
+ | InstRegex "jnz ([a-p]) (-?\d+)" [x; y] -> Jnz (Reg x, Literal (int y))
+ | InstRegex "jnz (-?\d+) ([a-p])" [x; y] -> Jnz (Literal (int x), Reg y)
+ | InstRegex "jnz (-?\d+) (-?\d+)" [x; y] -> Jnz (Literal (int x), Literal (int y))
+ | x -> printfn "%A" x; failwith "invalid input"
+
+let rec executeInst (instructions: Instruction array) (registers: Dictionary<string, int64>) (index: int64) mulCount =
+ if (int index) >= Array.length instructions || (int index) < 0 then mulCount
+ else
+ match instructions.[int index] with
+ | Set(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- resolveValue y registers
+ executeInst instructions registers (index + 1L) mulCount
+ | Sub(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- registers.[x] - resolveValue y registers
+ executeInst instructions registers (index + 1L) mulCount
+ | Mul(x, y) ->
+ if not (registers.ContainsKey(x)) then registers.[x] <- 0
+ registers.[x] <- registers.[x] * resolveValue y registers
+ executeInst instructions registers (index + 1L) (mulCount + 1)
+ | Jnz(x, y) ->
+ if (resolveValue x registers) <> 0 then
+ executeInst instructions registers (index + resolveValue y registers) mulCount
+ else
+ executeInst instructions registers (index + 1L) mulCount
+
+let part1() =
+ let registers = new Dictionary<string, int64>()
+ let input = File.ReadAllLines "day23.txt" |> Array.map parseValue
+ let mulCount = executeInst input registers 0 0
+ printfn "%A" mulCount
+
+// i knew it couldn't be that easy :(
+// time to decompile the assembly and figure out what's happening
+
+// let part2() =
+// let registers = new Dictionary<string, int64>()
+// registers.["a"] <- 1
+// let input = File.ReadAllLines "day23.txt" |> Array.map parseValue
+// executeInst input registers 0 0 |> ignore
+// printfn "%A" registers.["h"]
+
+let () =
+ part1() \ No newline at end of file
diff --git a/day24.fsx b/day24.fsx
new file mode 100644
index 0000000..3acdd7b
--- /dev/null
+++ b/day24.fsx
@@ -0,0 +1,21 @@
+open System.IO
+
+let parseLine (str: string) = str.Split('/') |> Array.map int |> (fun x -> (x[0], x[1]))
+let strength = List.sumBy (fun c -> fst c + snd c)
+
+let edges = File.ReadAllLines "day24.txt" |> Array.map parseLine
+
+let rec build bridge next components =
+ seq {
+ yield bridge
+ if Set.contains (next, next) components then yield! build ((next, next) :: bridge) next (Set.remove (next, next) components)
+ else
+ let bridgeable = Set.filter (fun c -> fst c = next || snd c = next) components
+ for comp in bridgeable do
+ let next' = if snd comp = next then fst comp else snd comp
+ yield! build (comp :: bridge) next' (Set.remove comp components) }
+
+let solve maximiser = set >> build [] 0 >> Seq.maxBy maximiser >> strength
+
+solve strength edges |> printfn "%A"
+solve (fun c -> (List.length c, strength c)) edges |> printfn "%A" \ No newline at end of file
diff --git a/day25.fsx b/day25.fsx
new file mode 100644
index 0000000..bd44736
--- /dev/null
+++ b/day25.fsx
@@ -0,0 +1,64 @@
+open System.Collections.Generic
+
+let stepCount = 12172063
+let tape = Dictionary<int, int>()
+type State = A | B | C | D | E | F
+
+let getValue (tape: Dictionary<int, int>) index =
+ if not (tape.ContainsKey index) then tape[index] <- 0
+ tape[index]
+
+let rec turingStep (tape: Dictionary<int, int>) index state stepCount=
+ if stepCount = 0 then tape.Values |> Seq.groupBy id |> dict |> (fun x -> Seq.length x[1])
+ else
+ match state with
+ | A ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 1
+ turingStep tape (index + 1) B (stepCount - 1)
+ else
+ tape[index] <- 0
+ turingStep tape (index - 1) C (stepCount - 1)
+ | B ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 1
+ turingStep tape (index - 1) A (stepCount - 1)
+ else
+ tape[index] <- 1
+ turingStep tape (index - 1) D (stepCount - 1)
+ | C ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 1
+ turingStep tape (index + 1) D (stepCount - 1)
+ else
+ tape[index] <- 0
+ turingStep tape (index + 1) C (stepCount - 1)
+ | D ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 0
+ turingStep tape (index - 1) B (stepCount - 1)
+ else
+ tape[index] <- 0
+ turingStep tape (index + 1) E (stepCount - 1)
+ | E ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 1
+ turingStep tape (index + 1) C (stepCount - 1)
+ else
+ tape[index] <- 1
+ turingStep tape (index - 1) F (stepCount - 1)
+ | F ->
+ if (getValue tape index) = 0
+ then
+ tape[index] <- 1
+ turingStep tape (index - 1) E (stepCount - 1)
+ else
+ tape[index] <- 1
+ turingStep tape (index + 1) A (stepCount - 1)
+
+turingStep tape 0 A stepCount |> printfn "%d" \ No newline at end of file