From 0a4fe70d367f0bf1a78602af600052f58a377c34 Mon Sep 17 00:00:00 2001 From: Brian Chu Date: Mon, 21 Feb 2022 00:11:06 -0800 Subject: solutions to day 25 --- day17.fsx | 27 ++++++++++++++++++++ day18.fsx | 86 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day18.py | 66 ++++++++++++++++++++++++++++++++++++++++++++++++ day19.py | 37 +++++++++++++++++++++++++++ day20.fsx | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++ day21.py | 47 ++++++++++++++++++++++++++++++++++ day22.jl | 25 +++++++++++++++++++ day23.c | 22 ++++++++++++++++ day23.fsx | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day24.fsx | 21 ++++++++++++++++ day25.fsx | 64 +++++++++++++++++++++++++++++++++++++++++++++++ 11 files changed, 550 insertions(+) create mode 100644 day17.fsx create mode 100644 day18.fsx create mode 100644 day18.py create mode 100644 day19.py create mode 100644 day20.fsx create mode 100644 day21.py create mode 100644 day22.jl create mode 100644 day23.c create mode 100644 day23.fsx create mode 100644 day24.fsx create mode 100644 day25.fsx 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 ) = + 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() + 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 +// 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 ) = + 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) (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() + 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() +// 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() +type State = A | B | C | D | E | F + +let getValue (tape: Dictionary) index = + if not (tape.ContainsKey index) then tape[index] <- 0 + tape[index] + +let rec turingStep (tape: Dictionary) 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 -- cgit 1.4.1-2-gfad0