aoc-all

My solutions to all Advent of Code
git clone https://git.instinctive.eu/aoc-all.git
Log | Files | Refs | README | LICENSE

day17.nim (4012B)

      1 # Copyright (c) 2024, Natacha Porté
      2 #
      3 # Permission to use, copy, modify, and distribute this software for any
      4 # purpose with or without fee is hereby granted, provided that the above
      5 # copyright notice and this permission notice appear in all copies.
      6 #
      7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
      8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
      9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
     10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
     11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
     12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
     13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
     14 
     15 from std/random   import randomize, rand
     16 from std/sequtils import map, toSeq
     17 from std/strutils import join, parseInt, split
     18 
     19 # Read input file
     20 
     21 let data = stdin.lines().toSeq()
     22 
     23 assert len(data) == 5
     24 assert data[0][0 .. 11] == "Register A: "
     25 assert data[1][0 .. 11] == "Register B: "
     26 assert data[2][0 .. 11] == "Register C: "
     27 assert data[3] == ""
     28 assert data[4][0 .. 8] == "Program: "
     29 
     30 type
     31   Machine = tuple
     32     A, B, C, ip: int
     33     res: seq[int]
     34 
     35 let
     36   init: Machine = (A: parseInt(data[0][12 .. ^1]), B: parseInt(data[1][12 .. ^1]), C: parseInt(data[2][12 .. ^1]), ip: 0, res: @[])
     37   program = data[4][9 .. ^1].split(",").map(parseInt)
     38 
     39 # Puzzle 1
     40 
     41 func combo(m: Machine, op: int): int =
     42   case op
     43   of 0 .. 3:
     44     result = op
     45   of 4:
     46     result = m.A
     47   of 5:
     48     result = m.B
     49   of 6:
     50     result = m.C
     51   else:
     52     assert false
     53 
     54 func adv(m: Machine, op: int): Machine =
     55   result = m
     56   result.A = result.A shr combo(m, op)
     57   result.ip += 2
     58 
     59 func bxl(m: Machine, op: int): Machine =
     60   result = m
     61   result.B = result.B xor op
     62   result.ip += 2
     63 
     64 func bst(m: Machine, op: int): Machine =
     65   result = m
     66   result.B = combo(m, op) mod 8
     67   result.ip += 2
     68 
     69 func jnz(m: Machine, op: int): Machine =
     70   result = m
     71   if result.A == 0:
     72     result.ip += 2
     73   else:
     74     result.ip = op
     75 
     76 func op_out(m: Machine, op: int): Machine =
     77   result = m
     78   result.res.add(combo(m, op) mod 8)
     79   result.ip += 2
     80 
     81 func bxc(m: Machine, op: int): Machine =
     82   result = m
     83   result.B = result.B xor result.C
     84   result.ip += 2
     85 
     86 func bdv(m: Machine, op: int): Machine =
     87   result = m
     88   result.B = result.A shr combo(m, op)
     89   result.ip += 2
     90 
     91 func cdv(m: Machine, op: int): Machine =
     92   result = m
     93   result.C = result.A shr combo(m, op)
     94   result.ip += 2
     95 
     96 let
     97   opcodes = [adv, bxl, bst, jnz, bxc, op_out, bdv, cdv]
     98 
     99 proc step(m: Machine, prg: seq[int]): Machine =
    100   result = opcodes[prg[m.ip]](m, prg[m.ip + 1])
    101 
    102 proc run(m: Machine, prg: seq[int]): Machine =
    103   result = m
    104   while result.ip + 1 < len(prg):
    105     result = step(result, prg)
    106 
    107 assert run((A: rand(9999), B: rand(9999), C: 9, ip: 0, res: @[]), @[2, 6]).B == 1
    108 assert run((A: 10, B: rand(9999), C: rand(9999), ip: 0, res: @[]), @[5,0,5,1,5,4]).res == @[0,1,2]
    109 assert run((A: 2024, B: rand(9999), C: rand(9999), ip: 0, res: @[]), @[0,1,5,4,3,0]).res == @[4,2,5,6,7,7,7,7,3,1,0]
    110 assert run((A: 2024, B: rand(9999), C: rand(9999), ip: 0, res: @[]), @[0,1,5,4,3,0]).A == 0
    111 assert run((A: rand(9999), B: 29, C: rand(9999), ip: 0, res: @[]), @[1,7]).B == 26
    112 assert run((A: rand(9999), B: 2024, C: 43690, ip: 0, res: @[]), @[4,0]).B == 44354
    113 
    114 echo "Puzzle 1: ", run(init, program).res.join(",")
    115 
    116 # Puzzle 2
    117 # 164515378771682 is too low
    118 
    119 let op_names = ["adv", "bxl", "bst", "jnz", "bxc", "op_out", "bdv", "cdv"]
    120 
    121 for i in 0 .. (len(program)-2) div 2:
    122   echo 2*i, ": ", op_names[program[2*i]], " ", program[2*i+1]
    123 
    124 proc answer2(im: Machine, prg: seq[int]): int =
    125   var
    126     m = im
    127     q = @[0]
    128   while len(q) > 0:
    129     let h = q[0]
    130     q = q[1 .. ^1]
    131     for i in 0 .. 7:
    132       m.A = h * 8 + i
    133       let s = run(m, prg).res
    134 
    135       if s == prg:
    136         return m.A
    137       elif s == prg[^len(s) .. ^1]:
    138         q.add(m.A)
    139       else:
    140         assert len(s) == 1 or s[1..^1] == prg[^(len(s)-1) .. ^1]
    141   assert false
    142 
    143 echo "Puzzle 2: ", answer2(init, program)