aoc-all

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

day15.nim (4324B)

      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/math     import gcd
     16 from std/sequtils import map, mapIt, toSeq
     17 from std/strutils import find, join, replace
     18 
     19 # Read input file
     20 
     21 type
     22   Point = tuple
     23     x, y: int
     24   Input_Data = tuple
     25     map: seq[string]
     26     start: Point
     27     moves: string
     28 
     29 func `+`(a, b: Point): Point = (x: a.x + b.x, y: a.y + b.y)
     30 proc `+=`(a: var Point, b: Point): void = a = a + b
     31 func `-`(a, b: Point): Point = (x: a.x - b.x, y: a.y - b.y)
     32 func `[]`(m: seq[string], p: Point): char = m[p.y][p.x]
     33 proc `[]=`(m: var seq[string], p: Point, c: char): void = m[p.y][p.x] = c
     34 
     35 func process_data(data: seq[string]): Input_Data =
     36   var
     37     in_map = true
     38     has_start = false
     39     moves: seq[string]
     40   for s in data:
     41     if s == "":
     42       assert in_map
     43       in_map = false
     44     elif in_map:
     45       let sx = s.find('@')
     46       if sx >= 0:
     47         assert not has_start
     48         result.start = (x: sx, y: len(result.map))
     49         has_start = true
     50       result.map.add(s)
     51     else:
     52       moves.add(s)
     53   assert not in_map
     54   assert has_start
     55   result.moves = moves.join()
     56 
     57 let
     58   data = process_data(stdin.lines().toSeq())
     59 
     60 # Puzzle 1
     61 
     62 func find_robot(m: seq[string]): Point =
     63   for y in 0 ..< len(m):
     64     let sx = m[y].find('@')
     65     if sx > 0:
     66       return (x: sx, y: y)
     67   assert false
     68 
     69 func direction(c: char): Point =
     70   case c
     71   of '<':
     72     return (x: -1, y: 0)
     73   of '>':
     74     return (x: 1, y: 0)
     75   of 'v':
     76     return (x: 0, y: 1)
     77   of '^':
     78     return (x: 0, y: -1)
     79   else:
     80     assert false
     81 
     82 func valid(p: Point, m: seq[string]): bool =
     83   p.x >= 0 and p.y >= 0 and p.y < len(m) and p.x < len(m[p.y])
     84 
     85 func move1(m: seq[string], c: char): seq[string] =
     86   let
     87     d = direction(c)
     88     start = find_robot(m)
     89   result = m
     90   var dest = start + d
     91   while valid(dest, m) and m[dest] == 'O':
     92     dest += d
     93   if valid(dest, m) and m[dest] == '.':
     94     result[dest] = result[dest - d]
     95     result[start + d] = result[start]
     96     result[start] = '.'
     97   else:
     98     return m
     99 
    100 proc display(m: seq[string]): void =
    101   for s in m:
    102     echo s
    103 
    104 proc moves1(map: seq[string], moves: string): seq[string] =
    105   result = map
    106   for c in moves:
    107     result = move1(result, c)
    108 # display(result)
    109 
    110 func answer(m: seq[string]): int =
    111   result = 0
    112   for y in 0 ..< len(m):
    113     for x in 0 ..< len(m[y]):
    114       if m[y][x] == 'O' or m[y][x] == '[':
    115         result += 100 * y + x
    116 
    117 echo "Puzzle 1: ", answer(moves1(data.map, data.moves))
    118 
    119 # Puzzle 2
    120 
    121 let
    122   map2 = data.map.mapIt(it.replace("#", "##").replace("O", "[]").replace(".", "..").replace("@", "@."))
    123 
    124 func move2(m: seq[string], c: char): seq[string] =
    125   let
    126     d = direction(c)
    127     start = find_robot(m)
    128   result = m
    129   result[start] = '.'
    130 
    131   if d.y == 0:
    132     var pos = start + d
    133     while valid(pos, m) and (m[pos] == '[' or m[pos] == ']'):
    134       result[pos] = m[pos - d]
    135       pos += d
    136     if valid(pos, m) and m[pos] == '.':
    137       result[pos] = m[pos - d]
    138     else:
    139       return m
    140   else:
    141     var pos = @[start + d]
    142     while len(pos) > 0:
    143       var next: seq[Point]
    144       for p in pos:
    145         case m[p]
    146         of '[':
    147           next.add(p + d)
    148           next.add(p + d + (x: 1, y: 0))
    149         of ']':
    150           next.add(p + d)
    151           next.add(p + d + (x: -1, y: 0))
    152         of '.':
    153           discard nil
    154         else:
    155           return m
    156       for p in next:
    157         result[p - d] = '.'
    158       for p in pos:
    159         result[p] = m[p - d]
    160       pos = next
    161 
    162 proc moves2(map: seq[string], moves: string): seq[string] =
    163   result = map
    164   for c in moves:
    165     result = move2(result, c)
    166 #   echo c
    167 #   display(result)
    168 # display(result)
    169 
    170 echo "Puzzle 2: ", answer(moves2(map2, data.moves))