solutions to day 25 main

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