🌟 Advent of Code (AoC) 2023 🌟

lines = open('input14.txt', 'rt').read().split('\n')

pattern0 = tuple(tuple(l) for l in lines)

H = len(pattern0)
W = len(pattern0[0])

def tilt_north(pattern):
    mutable_pattern = [list(l) for l in pattern]
    for y in range(1, H):
        for x in range(W):
            if mutable_pattern[y][x] == 'O':
                new_y = y
                for y2 in range(y-1, -1, -1):
                    if mutable_pattern[y2][x] == '.':
                        new_y = y2
                    else:
                        break
                if new_y != y:
                    mutable_pattern[y][x] = '.'
                    mutable_pattern[new_y][x] = 'O'
    return tuple(tuple(l) for l in mutable_pattern)

def rotate_90(pattern):
    return tuple(tuple(pattern[H - 1 - x][y] for x in range(W)) for y in range(H))

period = 0
offset = 0
patterns = {}
pattern = pattern0

N = 1000000000

for spins in range(1, N):
    for _ in range(4):
        pattern = tilt_north(pattern)
        pattern = rotate_90(pattern)

    last_occurrence = patterns.get(pattern)
    if last_occurrence is not None:
        period = spins - last_occurrence
        offset = spins
        break
    patterns[pattern] = spins

patterns = ((i, t) for t, i in patterns.items())
patterns = [t for _, t in sorted(patterns)]
patterns = patterns[-period:]

def calculate_load(pattern):
    return sum(sum(c == 'O' for c in row) * (H - y) for y, row in enumerate(pattern))

pattern_index = (N - offset) % period
pattern = patterns[pattern_index]
print(calculate_load(pattern))

val input = Using.resource(Source.fromFile("15.txt"))(_.mkString.trim)

extension (s: String) def hash: Int = s.foldLeft(0)((acc, ch) => ((acc + ch) * 17) % 256)

// del 1
input.split(',').map(_.hash).sum

// del 2
input
   .split(',')
   .groupBy(_.takeWhile(_.isLetter).hash)
   .map: (box, ops) =>
      ops
         .foldLeft(mutable.LinkedHashMap.empty[String, Int]): (m, op) =>
            op match
               case s"$id=$value" => m += id -> value.toInt
               case s"$id-"       => m -= id
         .valuesIterator.zip(Iterator.from(1)).map(_ * _ * (box + 1)).sum
   .sum

lines = open('input16.txt', 'rt').read().split('\n')

H = len(lines)
W = len(lines[0])

L2R = 1
T2B = 2
R2L = 4
B2T = 8

TURN_SLASH = {L2R: B2T, T2B: R2L, R2L: T2B, B2T: L2R}
TURN_BACKSLASH = {L2R: T2B, T2B: L2R, R2L: B2T, B2T: R2L}

def follow_beam(y, x, dir):
    while True:
        if y < 0 or y >= H or x < 0 or x >= W:
            return

        if energized[y][x] & dir:
            return

        energized[y][x] |= dir

        c = lines[y][x]

        if c == '/':
            dir = TURN_SLASH[dir]
        elif c == '\\':
            dir = TURN_BACKSLASH[dir]
        elif c == '|' and dir in (L2R, R2L):
            stack.append((y-1, x, B2T))
            dir = T2B
        elif c == '-' and dir in (T2B, B2T):
            stack.append((y, x-1, R2L))
            dir = L2R

        if dir == L2R:
            x += 1
        elif dir == T2B:
            y += 1
        elif dir == R2L:
            x -= 1
        elif dir == B2T:
            y -= 1

energized = [[0] * W for _ in range(H)]
stack = []

max_tiles_energized = 0

for start_dir in [L2R, T2B, R2L, B2T]:
    n = H if start_dir in (L2R, R2L) else W
    for i in range(n):
        energized = [[0] * W for _ in range(H)]

        if start_dir == L2R:
            stack = [(i, 0, start_dir)]
        elif start_dir == T2B:
            stack = [(0, i, start_dir)]
        elif start_dir == R2L:
            stack = [(i, W-1, start_dir)]
        elif start_dir == B2T:
            stack = [(H-1, i, start_dir)]

        while stack:
            y, x, dir = stack.pop(0)
            follow_beam(y, x, dir)

        tiles_energized = sum(1 if x else 0 for row in energized for x in row)

        if max_tiles_energized < tiles_energized:
            max_tiles_energized = tiles_energized

print(max_tiles_energized)

val input = Using.resource(Source.fromFile("16.txt"))(_.getLines().toVector)

enum Dir:
   case L, R, U, D

   def direction: (Int, Int) = this match
      case L => (-1, 0)
      case R => (1, 0)
      case U => (0, -1)
      case D => (0, 1)
import Dir.*

case class Beam(x: Int, y: Int, dir: Dir)

def move(beam: Beam, grid: Vector[String]): Set[Beam] =
   val (dx, dy) = beam.dir.direction
   val x        = beam.x + dx
   val y        = beam.y + dy
   if y < 0 || y >= grid.length || x < 0 || x >= grid.head.length then Set()
   else
      (grid(y)(x), beam.dir) match
         case ('.', dir)          => Set(Beam(x, y, dir))
         case ('|', L) | ('|', R) => Set(Beam(x, y, U), Beam(x, y, D))
         case ('|', dir)          => Set(Beam(x, y, dir))
         case ('-', U) | ('-', D) => Set(Beam(x, y, L), Beam(x, y, R))
         case ('-', dir)          => Set(Beam(x, y, dir))
         case ('/', L)            => Set(Beam(x, y, D))
         case ('/', R)            => Set(Beam(x, y, U))
         case ('/', U)            => Set(Beam(x, y, R))
         case ('/', D)            => Set(Beam(x, y, L))
         case ('\\', L)           => Set(Beam(x, y, U))
         case ('\\', R)           => Set(Beam(x, y, D))
         case ('\\', U)           => Set(Beam(x, y, L))
         case ('\\', D)           => Set(Beam(x, y, R))
         case default             => throw Exception(s"wtf!  $default")

def energize(start: Beam, grid: Vector[String]) =
   def recur(frontier: Set[Beam], visited: Set[Beam], energized: Set[(Int, Int)]): Int =
      if frontier.isEmpty then energized.size
      else
         val visited0  = visited.union(frontier)
         val frontier0 = frontier.flatMap(move(_, grid)).diff(visited0)
         recur(frontier0, visited0, energized.union(frontier0.map(b => (b.x, b.y))))
   recur(Set(start), Set.empty, Set.empty)

// del1
energize(Beam(-1, 0, R), input)

// del2
(input.indices.map(y => Beam(-1, y, R))
   ++ input.indices.map(y => Beam(input.head.length, y, L))
   ++ input.head.indices.map(x => Beam(x, -1, D))
   ++ input.head.indices.map(x => Beam(x, input.length, U))).par.map(energize(_, input)).max

lines = open('input17.txt', 'rt').read().split('\n')

H = len(lines)
W = len(lines[0])

RIGHT = 0
DOWN = 1
LEFT = 2
UP = 3

x_offs = [1, 0, -1, 0]
y_offs = [0, 1, 0, -1]

start = (0, 0, RIGHT, 0)

import heapq

dist_heap = [(0, start)]
dist_dict = {start: 0}

found = {}

part_no = 2

def allowed_dir(dir, dir_count, next_dir):
    if part_no == 1:
        if next_dir == dir:
            if dir_count == 3:
                return False
        elif next_dir == ((dir + 2) & 3):
            return False
        return True
    else:
        if next_dir == dir:
            if dir_count == 10:
                return False
        elif next_dir == ((dir + 2) & 3):
            return False
        elif dir_count < 4:
            return False
        return True

while dist_heap:
    d, state = heapq.heappop(dist_heap)
    del dist_dict[state]

    found[state] = d

    y, x, dir, dir_count = state
    if y == H-1 and x == W-1:
        if part_no == 1 or dir_count >= 4:
            print(d)
            break

    for next_dir in range(4):
        next_y = y + y_offs[next_dir]
        next_x = x + x_offs[next_dir]
        if next_y < 0 or next_y >= H or next_x < 0 or next_x >= W:
            continue

        if not allowed_dir(dir, dir_count, next_dir):
            continue

        next_dir_count = 1 + (dir_count if next_dir == dir else 0)

        next_state = (next_y, next_x, next_dir, next_dir_count)
        if next_state in found:
            continue

        cost = int(lines[next_y][next_x])
        next_d = d + cost

        prev_d = dist_dict.get(next_state)

        add_state = prev_d is None or next_d < prev_d

        if prev_d is not None and add_state:
            dist_heap.remove((prev_d, next_state))
            heapq.heapify(dist_heap)

        if add_state:
            heapq.heappush(dist_heap, (next_d, next_state))
            dist_dict[next_state] = next_d

val input = Using.resource(Source.fromFile("17.txt"))(_.getLines().to(ArraySeq))
val grid = input.map(_.map(_.asDigit).to(ArraySeq))

enum Dir:
   case L, R, U, D
import Dir.*

final case class Crucible(x: Int, y: Int, dir: Dir, fwd: Int, loss: Int):
   def compact: Int = (fwd << 18) | (dir.ordinal << 16) | (x << 8) | y

   def left = dir match
      case L => copy(y = y + 1, dir = D, fwd = 1)
      case R => copy(y = y - 1, dir = U, fwd = 1)
      case U => copy(x = x - 1, dir = L, fwd = 1)
      case D => copy(x = x + 1, dir = R, fwd = 1)

   def right = dir match
      case L => copy(y = y - 1, dir = U, fwd = 1)
      case R => copy(y = y + 1, dir = D, fwd = 1)
      case U => copy(x = x + 1, dir = R, fwd = 1)
      case D => copy(x = x - 1, dir = L, fwd = 1)

   def forward = dir match
      case L => copy(x = x - 1, fwd = fwd + 1)
      case R => copy(x = x + 1, fwd = fwd + 1)
      case U => copy(y = y - 1, fwd = fwd + 1)
      case D => copy(y = y + 1, fwd = fwd + 1)

object Crucible:
   given Ordering[Crucible] = Ordering.by[Crucible, Int](_.loss).reverse

def search(grid: ArraySeq[ArraySeq[Int]], start: List[Crucible], minFwd: Int, maxFwd: Int): Option[Int] =
   val visited = mutable.HashMap.empty[Int, Int]
   val pq      = mutable.PriorityQueue(start*)
   val ySize   = grid.size
   val xSize   = grid.head.size

   def neighbours(crusible: Crucible) =
      if crusible.fwd < minFwd then Iterator(crusible.forward)
      else if crusible.fwd < maxFwd then Iterator(crusible.left, crusible.forward, crusible.right)
      else Iterator(crusible.left, crusible.right)

   boundary:
      while pq.nonEmpty do
         val c = pq.dequeue()
         if c.x == xSize - 1 && c.y == ySize - 1 then boundary.break(Some(c.loss))
         if !visited.contains(c.compact) then
            visited += c.compact -> c.loss
            neighbours(c)
               .filter(c => c.x >= 0 && c.x < xSize && c.y >= 0 && c.y < ySize)
               .foreach(c => if !visited.contains(c.compact) then pq.enqueue(c.copy(loss = c.loss + grid(c.y)(c.x))))
      None

val start = List(Crucible(0, 0, R, 0, 0), Crucible(0, 0, D, 0, 0))

search(grid, start, 0, 3)
search(grid, start, 4, 10)

lines = open('input18.txt', 'rt').read().split('\n')

def get_instructions_part1(lines):
    directions = {'R': 0, 'D': 1, 'L': 2, 'U': 3}
    instructions = []
    for l in lines:
        dir, length, _ = l.split()
        dir = directions[dir]
        length = int(length)
        instructions.append((dir, length))
    return instructions

def get_instructions_part2(lines):
    instructions = []
    for l in lines:
        _, _, instr = l.split()
        length = int(instr[2:-2], 16)
        dir = int(instr[-2])
        instructions.append((dir, length))
    return instructions

def generate_vectors(instructions):
    offsets = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    vectors = []

    x, y = 0, 0
    prev_dir_outline = (instructions[-1][0] + 3) & 3

    for dir, length in instructions:
        dir_outline = (dir + 3) & 3

        dx1, dy1 = offsets[prev_dir_outline]
        dx2, dy2 = offsets[dir_outline]
        outline_x = x + (dx1 + dx2) * 0.5
        outline_y = y + (dy1 + dy2) * 0.5

        vectors.append((outline_x, outline_y))

        dx, dy = offsets[dir]
        x += dx * length
        y += dy * length

        prev_dir_outline = dir_outline

    return vectors

def inside_triangle(v0, v1, v2, v):
    tr = [v0, v1, v2]
    for i in range(3):
        vo = tr[i]
        vn = tr[(i + 1) % 3]
        e = (vn[0] - vo[0], vn[1] - vo[1])
        w = (v[0] - vo[0], v[1] - vo[1])
        cross = e[0] * w[1] - e[1] * w[0]
        if cross < 0:
            return False
    return True

def correctly_winded_triangle(v0, v1, v2):
    e1 = (v1[0] - v0[0], v1[1] - v0[1])
    e2 = (v2[0] - v1[0], v2[1] - v1[1])
    cross = e1[0] * e2[1] - e1[1] * e2[0]
    return cross >= 0

def triangulize(vectors):
    triangles = []

    while len(vectors) > 3:
        n = len(vectors)
        for i in range(n):
            vm1 = vectors[(i - 1) % n]
            v0 = vectors[i]
            v1 = vectors[(i + 1) % n]

            if not correctly_winded_triangle(vm1, v0, v1):
                continue

            is_ear = True
            for j in range(n - 3):
                v = vectors[(i + 2 + j) % n]
                if inside_triangle(vm1, v0, v1, v):
                    is_ear = False
                    break

            if is_ear:
                triangles.append((vm1, v0, v1))
                del vectors[i]
                break

    triangles.append(tuple(vectors))
    return triangles

def calculate_total_area(triangles):
    total_area = 0
    for v0, v1, v2 in triangles:
        x0, y0 = v0
        x1, y1 = v1
        x2, y2 = v2
        area = abs(x0 * (y1 - y2) + x1 * (y2 - y0) + x2 * (y0 - y1)) / 2
        total_area += area
    return total_area

instructions = get_instructions_part2(lines)
vectors = generate_vectors(instructions)
triangles = triangulize(vectors)
total_area = calculate_total_area(triangles)
print(total_area)

lines = open('input19.txt', 'rt').read().split('\n')

def parse_rules_parts(lines):
    LETTER_TO_INDEX = {'x': 0, 'm': 1, 'a': 2, 's': 3}
    rules = {}
    parts = []
    for line in lines:
        if line == '':
            pass
        elif line[0] != '{':
            pos = line.find('{')
            name = line[:pos]
            xs = line[pos+1:-1].split(',')
            rule = []
            for x in xs:
                pos = x.find(':')
                if pos != -1:
                    clause = (LETTER_TO_INDEX[x[0]], x[1], int(x[2:pos]), x[pos+1:])
                else:
                    clause = (0, '', 0, x)
                rule.append(clause)
            rules[name] = rule
        else:
            xs = line[1:-1].split(',')
            xs = tuple(int(x.split('=')[1]) for x in xs)
            parts.append(xs)
    return rules, parts

def evaluate(rule, limits, queues_to_evaluate, accepted):
    for clause in rule:
        index, comparison, value, target = clause
        limit_min, limit_max = limits[index]
        if comparison == '<':
            match_min, match_max = limit_min, value-1
            keep_min, keep_max = value, limit_max
        elif comparison == '>':
            match_min, match_max = value+1, limit_max
            keep_min, keep_max = limit_min, value
        else:
            match_min, match_max = limit_min, limit_max
            keep_min, keep_max = 1, 0

        if match_min <= match_max:
            match_limits = tuple(((match_min, match_max) if i == index else p for i, p in enumerate(limits)))
            if target == 'A':
                accepted.append(match_limits)
            elif target != 'R':
                queues_to_evaluate.append((target, match_limits))

        if keep_min <= keep_max:
            limits = tuple(((keep_min, keep_max) if i == index else p for i, p in enumerate(limits)))
        else:
            break

rules, _ = parse_rules_parts(lines)
queues_to_evaluate = [('in', ((1, 4000), (1, 4000), (1, 4000), (1, 4000)))]
accepted = []

while queues_to_evaluate:
    queue_name, limits = queues_to_evaluate.pop()
    rule = rules[queue_name]
    evaluate(rule, limits, queues_to_evaluate, accepted)

res = 0
for limits in accepted:
    elements = 1
    for limit_min, limit_max in limits:
        elements *= limit_max - limit_min + 1
    res += elements
print(res)

lines = open('input20.txt', 'rt').read().split('\n')

module_kind = {}
module_targets = {}

for l in lines:
    a, b = l.split(' -> ')
    targets = b.split(', ')
    if a == 'broadcaster':
        kind, name = 'b', a
    else:
        kind, name = a[0], a[1:]
    module_kind[name] = kind
    module_targets[name] = targets

def get_initial_memory():
    memory = {}

    for name, kind in module_kind.items():
        if kind == '%':
            memory[name] = 0
        elif kind == '&':
            memory[name] = {}

    for name, targets in module_targets.items():
        for target in targets:
            kind = module_kind.get(target)
            if kind == '&':
                memory[target][name] = 0

    return memory

def process_pulses(pulses, memory):
    while pulses:
        sender, level, name = pulses.pop(0)
        kind = module_kind.get(name)
        targets = module_targets.get(name)
        if kind == 'b':
            for target in targets:
                pulses.append((name, level, target))
        elif kind == '%':
            if level == 0:
                level = memory.get(name, 0) ^ 1
                memory[name] = level
                for target in targets:
                    pulses.append((name, level, target))
        elif kind == '&':
            if level == 1 and 'rx' in targets:
                return True
            mem = memory.get(name, {})
            mem[sender] = level
            level = 0 if all(x == 1 for x in mem.values()) else 1
            for target in targets:
                pulses.append((name, level, target))
    return False

prod = 1

for n in module_targets['broadcaster']:
    memory = get_initial_memory()
    steps = 0
    while True:
        steps += 1
        pulses = [('broadcaster', 0, n)]
        if process_pulses(pulses, memory):
            prod *= steps
            break

print(prod)