2023/2023.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict, Counter, deque, OrderedDict\n",
    "import decimal\n",
    "from intervaltree import Interval, IntervalTree\n",
    "import itertools\n",
    "import functools\n",
    "import heapq\n",
    "import math\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import re\n",
    "from typing import Callable, TypeVar\n",
    "import z3\n",
    "\n",
    "np.set_printoptions(edgeitems=30, linewidth=100000, \n",
    "    formatter=dict(float=lambda x: \"%.3g\" % x))\n",
    "\n",
    "T = TypeVar('T')\n",
    "\n",
    "def data(day: int, parser: Callable[[str], T] = str) -> list[T]:\n",
    "  with open(f\"./data/day{day}.txt\") as f:\n",
    "    return [parser(line.strip()) for line in f.readlines()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs(nodes, start, get_neighbors, end_condition=lambda _: False):\n",
    "    q, visited = deque([(start, 0)]), {}\n",
    "    while q:\n",
    "        current, distance = q.popleft()\n",
    "        if end_condition(current):\n",
    "            return visited, current\n",
    "        if current in visited:\n",
    "            continue\n",
    "        for node in get_neighbors(nodes, current):\n",
    "            q.append((node, distance+1))\n",
    "        visited[current] = distance\n",
    "    return visited, None\n",
    "\n",
    "def visualize(arr, vmap):\n",
    "    visual = arr.copy()\n",
    "    for x, y in vmap:\n",
    "        visual[y, x] = vmap[(x, y)]\n",
    "    print(visual)\n",
    "\n",
    "\n",
    "def dijkstra(\n",
    "    nodes, \n",
    "    start, \n",
    "    get_neighbors, \n",
    "    end_condition=lambda _: False, \n",
    "):\n",
    "    q, visited = start, {}\n",
    "    while q:\n",
    "        distance, current = heapq.heappop(q)\n",
    "        if str(current) in visited:\n",
    "            continue\n",
    "        visited[str(current)] = distance\n",
    "        if end_condition(current):\n",
    "            return visited, current\n",
    "        for node in get_neighbors(nodes, current, distance):\n",
    "            heapq.heappush(q, node)\n",
    "    return visited, None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(55816, 54980)"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data1 = data(1)\n",
    "\n",
    "def day1(match):\n",
    "    sum = 0\n",
    "    for line in data1:\n",
    "        matched = match(line)\n",
    "        first, last = matched[0], matched[-1]\n",
    "        # print(first, last, sum)\n",
    "        sum += int(first + last)\n",
    "    return sum\n",
    "\n",
    "def part2match(x):\n",
    "    change = {\n",
    "        'one': '1',\n",
    "        'two': '2',\n",
    "        'three': '3',\n",
    "        'four': '4',\n",
    "        'five': '5',\n",
    "        'six': '6',\n",
    "        'seven': '7',\n",
    "        'eight': '8',\n",
    "        'nine': '9',\n",
    "    }\n",
    "    matched = re.findall(r'(?=(\\d|one|two|three|four|five|six|seven|eight|nine))', x)\n",
    "    return [change[match] if match in change else match for match in matched]\n",
    "\n",
    "day1(lambda x: re.findall(r'\\d', x)), day1(part2match)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2377, 71220)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def format2(line):\n",
    "    def tuplefy(round):\n",
    "        result = [0,0,0]\n",
    "        for i in round:\n",
    "            result[0 if 'blue' in i else 1 if 'green' in i else 2] += int(i.split(' ')[0])\n",
    "        return result\n",
    "\n",
    "    line = line.split(': ')[-1]\n",
    "    rounds = line.split('; ' )\n",
    "    return np.array([tuplefy(x.split(', ')) for x in rounds])\n",
    "\n",
    "data2 = data(2, format2)\n",
    "\n",
    "def day2_1(start):\n",
    "    result = 0\n",
    "    for i, game in enumerate(data2):\n",
    "        possible = np.subtract(start, game)\n",
    "        if np.any(possible < 0):\n",
    "            continue\n",
    "        result += i+1\n",
    "    return result\n",
    "\n",
    "def day2_2():\n",
    "    result = 0\n",
    "    for game in data2:\n",
    "        requirements = np.amax(game, axis=0)\n",
    "        result += functools.reduce(lambda x, y: x*y, requirements, 1)\n",
    "    return result\n",
    "\n",
    "day2_1((14, 13, 12)), day2_2()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(521515, 69527306)"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data3 = data(3)\n",
    "\n",
    "def day3():\n",
    "    numbers = []\n",
    "    for i, line in enumerate(data3):\n",
    "        numbers += [(m.group(), (i, m.start())) for m in re.finditer(r'\\d+', line)]\n",
    "\n",
    "    array3 = np.pad(np.array([list(line) for line in data3]), ((1, 1), (1, 1)), constant_values='.')\n",
    "    gears = defaultdict(lambda: [])\n",
    "\n",
    "    part1 = 0\n",
    "    for n, (i, j) in numbers:\n",
    "        sliced = array3[i:i+3, j:j+2+len(n)]\n",
    "        stringified =  ''.join(''.join(x) for x in sliced)\n",
    "        if re.search(r'[^\\d.]', stringified):\n",
    "            part1 += int(n)\n",
    "        if stars := np.where(sliced == '*'):\n",
    "            for x, _ in enumerate(stars[0]):\n",
    "                gears[(i+stars[0][x], j+stars[1][x])].append(int(n))\n",
    "\n",
    "    part2 = 0\n",
    "    for g in gears:\n",
    "        if len(gears[g]) == 2:\n",
    "            part2 += gears[g][0] * gears[g][1]\n",
    "\n",
    "    return part1, part2\n",
    "\n",
    "day3()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25651, 19499881)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse4(line):\n",
    "    winning, have = map(\n",
    "        lambda numbers: {int(x) for x in numbers.split()},\n",
    "        line.split(':')[-1].split('|')\n",
    "    )\n",
    "    return winning, have\n",
    "\n",
    "data4 = data(4, parse4)\n",
    "\n",
    "def day4(data):\n",
    "    result, cards = 0, Counter()\n",
    "    for i, line in enumerate(data):\n",
    "        matches = line[0].intersection(line[1])\n",
    "        if matches:\n",
    "            result += 2**(len(matches)-1)\n",
    "        for n in range(len(matches)):\n",
    "            cards[i+1+n] += cards[i]+1\n",
    "    return result, cards.total() + len(data)\n",
    "\n",
    "day4(data4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1181555926, 37806486)"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "debug=False\n",
    "\n",
    "def day5_maps(data):\n",
    "    names, maps = [], []\n",
    "\n",
    "    def create_map(lines):\n",
    "        ranges = IntervalTree([Interval(0, math.inf)])\n",
    "        name = lines[0].split()[0]\n",
    "        for i, line in enumerate(lines[1:]):\n",
    "            if not line:\n",
    "                break\n",
    "            dest, source, size = map(int, line.split())\n",
    "            ranges.chop(source, source+size)\n",
    "            ranges[source:source+size] = dest\n",
    "        return name, ranges, lines[i+2:]\n",
    "\n",
    "    seeds, data = map(int, data[0].split(': ')[-1].split()), data[2:]\n",
    "\n",
    "    while len(data):\n",
    "        name, intervals, data = create_map(data)\n",
    "        names.append(name)\n",
    "        maps.append(intervals)\n",
    "\n",
    "    return list(seeds), maps, names\n",
    "\n",
    "seeds, intervals, names = day5_maps(data(5))\n",
    "\n",
    "def day5_1(seeds, data):\n",
    "    lowest = math.inf\n",
    "    for seed in seeds:\n",
    "        for interval in data:\n",
    "            start, end, dest = next(iter(interval.at(seed)))\n",
    "            seed = seed if dest is None else (seed-start)+dest\n",
    "        lowest = min(lowest, seed)\n",
    "    return lowest\n",
    "\n",
    "def day5_2(seeds, data):\n",
    "    seedrange = IntervalTree([Interval(start, start+size) for start, size in zip(seeds[::2], seeds[1::2])])\n",
    "    seedrange.merge_overlaps()\n",
    "\n",
    "    for i, interval in enumerate(data):\n",
    "        newrange = IntervalTree()\n",
    "        if debug:\n",
    "            print(names[i], seedrange, interval)\n",
    "        for (seedstart, seedend, _) in seedrange:\n",
    "            intersections = interval[seedstart:seedend]\n",
    "            for (start, end, dest) in intersections:\n",
    "                newstart = (dest + max(seedstart, start)-start) if dest is not None else seedstart\n",
    "                newend = (dest + min(seedend, end)-start) if dest is not None else seedend\n",
    "                newrange.addi(newstart, newend)\n",
    "        newrange.merge_overlaps()\n",
    "        seedrange = newrange\n",
    "        \n",
    "    lowest = min([loc[0] for loc in seedrange])\n",
    "    return lowest\n",
    "\n",
    "day5_1(seeds, intervals), day5_2(seeds, intervals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(252000, 36992486)"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data6 = data(6, lambda x: list(map(int, x.split(':')[-1].split())))\n",
    "\n",
    "def day6(times, distances):\n",
    "    result = []\n",
    "    for t, d in zip(times, distances):\n",
    "        # (t-x)*x = d+1\n",
    "        # -x**2 +xt -d-1 = 0\n",
    "        a, b, c = -1, t, -d-1\n",
    "        det = math.sqrt(b**2 - 4*a*c)\n",
    "        if det < 0:\n",
    "            continue\n",
    "        zeros = (-b+det)/(2*a), (-b-det)/(2*a)\n",
    "        floor, ceil = math.ceil(min(zeros)), math.floor(max(zeros))\n",
    "        result.append(ceil-floor+1)\n",
    "    return functools.reduce(lambda x, y: x*y, result, 1)\n",
    "\n",
    "day6(*data6), day6(*[[int(''.join(map(str, x)))] for x in data6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(248812215, 250057090)"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data7 = data(7, lambda x: x.split())\n",
    "\n",
    "def card_ord(card, flag=False):\n",
    "    match card:\n",
    "        case 'T': return 10\n",
    "        case 'J': return 1 if flag else 11\n",
    "        case 'Q': return 12\n",
    "        case 'K': return 13\n",
    "        case 'A': return 14\n",
    "    return int(card)\n",
    "\n",
    "def score_hand(hand, flag=False):\n",
    "    cards = [card_ord(card, flag) for card in hand]\n",
    "    if flag:\n",
    "        filtered = Counter(hand.replace('J', ''))\n",
    "        hand = hand.replace('J', filtered.most_common(1)[0][0] if filtered else 'A')\n",
    "\n",
    "    counts = Counter(hand)\n",
    "    score = sum([counts[x]**2 for x in counts])\n",
    "    return [score]+cards\n",
    "\n",
    "def day7(data, flag=False):\n",
    "    key = lambda x: score_hand(x[0], flag)\n",
    "    ordered = sorted(data, key=key)\n",
    "    return sum((i+1)*int(score) for i, (_, score) in enumerate(ordered))\n",
    "\n",
    "day7(data7), day7(data7, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(18673, 17972669116327)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse8(data):\n",
    "    instructions, nodes = data[0], {}\n",
    "    for line in data[2:]:\n",
    "        start, l, r = re.findall(r'(.{3}) = \\((.{3}), (.{3})\\)', line)[0] \n",
    "        nodes[start] = (l, r)\n",
    "    return instructions, nodes\n",
    "\n",
    "data8 = parse8(data(8))\n",
    "\n",
    "def day8(instructions, nodes, start, ends):\n",
    "    count, node = 0, start\n",
    "    for i in itertools.cycle(instructions):\n",
    "        node = nodes[node][0 if i == 'L' else 1]\n",
    "        count +=1\n",
    "        if ends(node):\n",
    "            break\n",
    "    return count\n",
    "\n",
    "def day8_2(instructions, nodes):\n",
    "    results = []\n",
    "    for start in filter(lambda x: re.match(r'..A', x), nodes):\n",
    "        results.append(day8(instructions, nodes, start, lambda x: re.match(r'..Z', x)))\n",
    "    return math.lcm(*results)\n",
    "\n",
    "day8(*data8, 'AAA', lambda x: x == 'ZZZ'), day8_2(*data8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2008960228, 1097)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data9 = data(9, lambda line: [int(x) for x in line.split()])\n",
    "\n",
    "def determine_steps(arr, i=-1):\n",
    "    steps = [arr[i]]\n",
    "    while len(np.unique(arr)) > 1:\n",
    "        arr = np.diff(arr)\n",
    "        steps.append(arr[i])\n",
    "    return steps\n",
    "\n",
    "def day9(data, part2=False):\n",
    "    part1, part2 = 0, 0\n",
    "    for history in data:\n",
    "        steps = determine_steps(np.array(history)), determine_steps(np.array(history), 0)\n",
    "        part1 += sum(steps[0])\n",
    "        part2 += sum(steps[1][::2]) - sum(steps[1][1::2])\n",
    "    return part1, part2\n",
    "\n",
    "day9(data9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6882, 491)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data10 = np.array(data(10, list))\n",
    "\n",
    "pipe_map = {\n",
    "    '|': [(0, -1), (0, 1)],\n",
    "    '-': [(-1, 0), (1, 0)],\n",
    "    'L': [(0, -1), (1, 0)],\n",
    "    'J': [(0, -1), (-1, 0)],\n",
    "    '7': [(0, 1), (-1, 0)],\n",
    "    'F': [(0, 1), (1, 0)],\n",
    "}\n",
    "\n",
    "def pipe_neighbors(pipe, x, y):\n",
    "    if pipe not in pipe_map:\n",
    "        return\n",
    "    for i in pipe_map[pipe]:\n",
    "        yield (x+i[0], y+i[1])\n",
    "\n",
    "def get_neighbors(x, y):\n",
    "    return [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]\n",
    "\n",
    "def fix_pipe_start(arr):    \n",
    "    start_coords = np.where(arr == 'S')\n",
    "    y, x = start_coords[0][0], start_coords[1][0]\n",
    "\n",
    "    neighbors = []\n",
    "    for i, j in get_neighbors(x, y):\n",
    "        if (x, y) in pipe_neighbors(data10[j, i], i, j):\n",
    "            neighbors.append((i-x, j-y))\n",
    "    for pipe in pipe_map.keys():\n",
    "        if frozenset(pipe_map[pipe]) == frozenset(neighbors):\n",
    "            arr[y, x] = pipe\n",
    "    return x, y\n",
    "\n",
    "def day10_1(data):\n",
    "    arr = data.copy()\n",
    "    start = fix_pipe_start(arr)\n",
    "    visited, _ = dfs(data, start, lambda _, coords: pipe_neighbors(arr[coords[1], coords[0]], *coords))\n",
    "    # visualize(arr, visited)\n",
    "    return visited\n",
    "\n",
    "def day10(data):\n",
    "    visited = day10_1(data)\n",
    "\n",
    "    claimed = {}\n",
    "    for y, row in enumerate(data):\n",
    "        inside = False\n",
    "        for x, pipe in enumerate(row):\n",
    "            if (x, y) in visited:\n",
    "                if pipe in 'LJ|':\n",
    "                    # If pipe is part of path and is north: taken from https://old.reddit.com/r/adventofcode/comments/18fgddy/2023_day_10_part_2_using_a_rendering_algorithm_to/\n",
    "                    inside ^= True \n",
    "            elif inside:\n",
    "                claimed[(x, y)] = 'I'\n",
    "    # visualize(data, claimed)\n",
    "\n",
    "    return max(visited.values()), len(claimed)\n",
    "\n",
    "day10(data10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1000000: 742305960572, 2: 9445168})"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data11 = np.array(data(11, list))\n",
    "\n",
    "def day11(data, expansions):\n",
    "    cols, rows = [IntervalTree([Interval(x, x+1) for x in np.where(np.all(data == '.', axis=i))[0]]) for i in range(2)]\n",
    "\n",
    "    galaxies = np.where(data == '#')\n",
    "\n",
    "    results = Counter()\n",
    "    for a, b in itertools.combinations(range(len(galaxies[0])), 2):\n",
    "        xs, ys = Interval(galaxies[0][a], galaxies[0][b]), Interval(*sorted([galaxies[1][a], galaxies[1][b]]))\n",
    "        empties = len(cols[ys[0]:ys[1]]) + len(rows[xs[0]:xs[1]])\n",
    "        distance = ys[1]-ys[0] + xs[1]-xs[0]\n",
    "        for expansion in expansions:\n",
    "            results[expansion] += distance + empties * (expansion-1)\n",
    "    return results\n",
    "\n",
    "day11(data11, [2, 1000000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7857, 28606137449920)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse12(line):\n",
    "    springs, conditions = line.split(' ')\n",
    "    return springs, tuple(map(int, conditions.split(',')))\n",
    "\n",
    "data12 = data(12, parse12)\n",
    "\n",
    "@functools.lru_cache()\n",
    "def fix_records(line, numbers, active=0):\n",
    "    if not numbers:\n",
    "        return 0 if '#' in line else 1\n",
    "    if not line:\n",
    "        return 0\n",
    "    n, nt = numbers[0], numbers[1:]\n",
    "    head, tail = line[0], line[1:]\n",
    "    if head == '.':\n",
    "        if active:\n",
    "            if n > 0:\n",
    "                return 0\n",
    "            return fix_records(tail, nt)\n",
    "        return fix_records(tail, numbers)\n",
    "    elif head == '#':\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        return fix_records(tail, (n-1, *nt), active+1)\n",
    "    else:\n",
    "        return fix_records('.'+tail, numbers, active) + fix_records('#'+tail, numbers, active)\n",
    "\n",
    "def sum_records(data, n=1):\n",
    "    result = 0\n",
    "    for spring, numbers in data:\n",
    "        result += fix_records('?'.join([spring]*n) + '.', numbers*n)\n",
    "        # print(spring*n, numbers*n, result)\n",
    "    return result\n",
    "\n",
    "def day12(data):\n",
    "    return sum_records(data), sum_records(data, 5)\n",
    "\n",
    "day12(data12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(31739, 31539)"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse13(lines):\n",
    "    result = []\n",
    "    for i, line in enumerate(lines):\n",
    "        line = line.strip()\n",
    "        if not line:\n",
    "            return result, lines[i+1:]\n",
    "        else:\n",
    "            result.append(list(map(int, line.replace('.', '0').replace('#', '1'))))\n",
    "    return result, []\n",
    "\n",
    "def get13():\n",
    "    patterns = []\n",
    "    with open(f\"./data/day13.txt\") as f:\n",
    "        lines = f.readlines()\n",
    "        while lines:\n",
    "            pattern, lines = parse13(lines)\n",
    "            patterns.append(np.array(pattern))\n",
    "    return patterns\n",
    "\n",
    "data13 = get13()\n",
    "\n",
    "def get_matches(pattern):\n",
    "    matches = defaultdict(lambda: set())\n",
    "    for i in range(len(pattern)):\n",
    "        for j in range(i+1, len(pattern)):\n",
    "            if np.all(pattern[i]==pattern[j]):\n",
    "                matches[i].add(j)\n",
    "                matches[j].add(i)\n",
    "    return matches\n",
    "\n",
    "def get_close_matches(pattern):\n",
    "    for i in range(len(pattern)):\n",
    "        for j in range(i+1, len(pattern)):\n",
    "            diffs = np.count_nonzero(pattern[i] != pattern[j])\n",
    "            if diffs == 1:\n",
    "                p = pattern.copy()\n",
    "                saved, p[i] = p[i], p[j]\n",
    "                yield p, get_matches(p)\n",
    "                p[i], p[j] = saved, saved\n",
    "                yield p, get_matches(p)\n",
    "\n",
    "def check_reflections(pattern, matches):\n",
    "    length = len(pattern)\n",
    "\n",
    "    def check_reflection(i):\n",
    "        distance = min(length, 2*(i+1)) - (i+1)\n",
    "        if not distance:\n",
    "            return\n",
    "        for j in range(distance):\n",
    "            if (i-j) not in matches[i+1+j]:\n",
    "                return False\n",
    "        return distance\n",
    "\n",
    "    for i in range(length):\n",
    "        if check_reflection(i):\n",
    "            yield i+1\n",
    "\n",
    "def find_reflection(pattern):\n",
    "    match = get_matches(pattern)\n",
    "    for h in check_reflections(pattern, match):\n",
    "        yield h*1j\n",
    "    t = np.transpose(pattern)\n",
    "    match = get_matches(t)\n",
    "    yield from check_reflections(t, match)\n",
    "\n",
    "def find_smudged_reflection(pattern, disallowed):\n",
    "    for p, match in get_close_matches(pattern):\n",
    "        for h in check_reflections(p, match):\n",
    "            if h != disallowed.imag:\n",
    "                return h*1j\n",
    "    for p, match in get_close_matches(np.transpose(pattern)):\n",
    "        for v in check_reflections(p, match):\n",
    "            if v != disallowed.real:\n",
    "                return v\n",
    "\n",
    "def day13(data):\n",
    "    def summarize(n):\n",
    "        return int(n.imag*100+n.real)\n",
    "\n",
    "    part1, part2 = 0, 0\n",
    "    for pattern in data:\n",
    "        disallowed = next(find_reflection(pattern))\n",
    "        part1 += disallowed\n",
    "        part2 += find_smudged_reflection(pattern, disallowed)\n",
    "\n",
    "    return summarize(part1), summarize(part2)\n",
    "\n",
    "day13(data13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(112773, 98894)"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data14 = np.array(data(14, list))\n",
    "\n",
    "def tilt(col, direction):\n",
    "    rock_groups = ''.join(col).split('#')\n",
    "    tilted = '#'.join(map(lambda x: ''.join(sorted(x, reverse=direction)), rock_groups))\n",
    "    return list(tilted)\n",
    "tiltup, tiltdown = lambda x: tilt(x, True), lambda x: tilt(x, False)\n",
    "\n",
    "def rotate(dish, direction):\n",
    "    match direction:\n",
    "        case 0: return np.apply_along_axis(tiltup, 0, dish)\n",
    "        case 1: return np.apply_along_axis(tiltup, 1, dish)\n",
    "        case 2: return np.apply_along_axis(tiltdown, 0, dish)\n",
    "    return np.apply_along_axis(tiltdown, 1, dish)\n",
    "\n",
    "def calculate_weight(arr):\n",
    "    weight = 0\n",
    "    stones = list(reversed(np.count_nonzero(arr == 'O', 1)))\n",
    "    for i in range(len(arr)):\n",
    "        weight += (i+1)*stones[i]\n",
    "    return weight\n",
    "\n",
    "def day14_1(data):\n",
    "    return calculate_weight(rotate(data, 0))\n",
    "\n",
    "def cycle(dish):\n",
    "    for j in range(4):\n",
    "        dish = rotate(dish, j)\n",
    "    return dish\n",
    "\n",
    "def day14_2(arr, target=1000000000):\n",
    "    repeated = {}\n",
    "    for i in range(target):\n",
    "        arr = cycle(arr)\n",
    "        if (rs := repeated.setdefault(arr.data.tobytes(), i)) != i:\n",
    "            i = ((target-rs)//(i-rs))*(i-rs) + rs +1 # potential bug here where before the +1 i is exactly at the target\n",
    "            break\n",
    "    for i in range(i, target): # should just figure out the number directly by pulling from repeated\n",
    "        arr = cycle(arr)\n",
    "\n",
    "    return calculate_weight(arr)\n",
    "\n",
    "day14_1(data14), day14_2(data14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(501680, 241094)"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data15 = list(itertools.chain.from_iterable(data(15, lambda x: x.split(','))))\n",
    "\n",
    "def advent_hash(input):\n",
    "    value = 0\n",
    "    for i in input:\n",
    "        value += ord(i)\n",
    "        value *= 17\n",
    "        value %= 256\n",
    "    return value\n",
    "\n",
    "def day15(data):\n",
    "    boxes = defaultdict(lambda: OrderedDict())\n",
    "\n",
    "    def advent_hash_map(input):\n",
    "        if input[-1] == '-':     \n",
    "            label = input[:-1]\n",
    "            box = advent_hash(label)\n",
    "            if label in boxes[box]:\n",
    "                del boxes[box][label]   \n",
    "        else:\n",
    "            label, value = input.split('=')\n",
    "            box = advent_hash(label)\n",
    "            boxes[box][label] = int(value)\n",
    "\n",
    "    for input in data:\n",
    "        advent_hash_map(input)\n",
    "\n",
    "    result = 0\n",
    "    for box in boxes:\n",
    "        for i, label in enumerate(boxes[box]):\n",
    "            # print(box, i, label)\n",
    "            result += (box+1) * (i+1) * boxes[box][label]\n",
    "\n",
    "    return sum([advent_hash(i) for i in data]), result\n",
    "        \n",
    "day15(data15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6883, 7228)"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data16 = np.array(data(16, list))\n",
    "\n",
    "def day16(data):\n",
    "    ymax, xmax = data.shape\n",
    "\n",
    "    def beam(pos, dir):\n",
    "        space = data[int(pos.imag)][int(pos.real)]\n",
    "        match space:\n",
    "            case '-':\n",
    "                if dir.imag:\n",
    "                    return [(pos+1, 1), (pos-1, -1)]\n",
    "            case '|':\n",
    "                if dir.real:\n",
    "                    return [(pos+1j, 1j), (pos-1j, -1j)]\n",
    "            case '/':\n",
    "                dir = (-1 if dir.real else 1) * 1j*dir\n",
    "            case '\\\\':\n",
    "                dir = (-1 if dir.imag else 1) * 1j*dir\n",
    "        return [(pos+dir, dir)]\n",
    "\n",
    "    def shoot(start=(0, 1)):\n",
    "        visited, q = set([start]), deque([start])\n",
    "        while q:\n",
    "            pos, dir = q.popleft()\n",
    "            for p, d in beam(pos, dir):\n",
    "                if p.real < 0 or p.real >= xmax or p.imag < 0 or p.imag >= ymax:\n",
    "                    continue\n",
    "                if (p, d) in visited:\n",
    "                    continue\n",
    "                visited.add((p, d))\n",
    "                q.append((p, d))\n",
    "\n",
    "        return len(set([p for p, _ in visited]))\n",
    "    \n",
    "    part1 = shoot()\n",
    "    maxlr = max([max(shoot((i*1j, 1)), shoot((xmax-1+i*1j, -1))) for i in range(ymax)])\n",
    "    maxud = max([max(shoot((i, -1j)), shoot((i+(ymax-1)*1j, 1j))) for i in range(ymax)])\n",
    "    return part1, max(maxlr, maxud)\n",
    "\n",
    "day16(data16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1039, 1201)"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "debug=False\n",
    "data17 = np.array(data(17, lambda x: list(map(int, x))))\n",
    "\n",
    "class Crucible:\n",
    "    # position, velocity, step\n",
    "    def __init__(self, p, v, s):\n",
    "        self.p = p\n",
    "        self.v = v\n",
    "        self.s = s\n",
    "    def __lt__(self, other):\n",
    "        return self.s < other.s\n",
    "    def __repr__(self) -> str:\n",
    "        return f'{self.p}, {self.v}, {self.s}'\n",
    "\n",
    "def heat_map(distances):\n",
    "    arr = data17.copy()\n",
    "    y, x = arr.shape\n",
    "    for i in range(y):\n",
    "        for j in range(x):\n",
    "            key = i*1j + j\n",
    "            arr[i, j] = distances.get(key, x*y)\n",
    "    return arr\n",
    "\n",
    "def day17(data, smax=3, smin=1):\n",
    "    ymax, xmax = data.shape\n",
    "    start = [(0, Crucible(0, 1, 1)), (0, Crucible(0, 1j, 1))]\n",
    "\n",
    "    def end_condition(node):\n",
    "        y, x = int(node.p.imag), int(node.p.real)\n",
    "        if y == ymax-1 and x == xmax-1:\n",
    "            return True\n",
    "\n",
    "    def get_neighbors(arr, current, distance):\n",
    "        new = current.p + current.v\n",
    "        y, x = int(new.imag), int(new.real)\n",
    "        if not (y >= 0 and x >= 0 and y < ymax and x < xmax):\n",
    "            return []\n",
    "\n",
    "        nodes = []\n",
    "        for v in [1, -1, 1j, -1j]:\n",
    "            node = Crucible(new, v, 1 if v != current.v else current.s+1)\n",
    "            if node.v == -current.v:\n",
    "                continue\n",
    "            if node.s > smax:\n",
    "                continue\n",
    "            if current.s < smin and v != current.v:\n",
    "                continue\n",
    "            nodes.append((distance + arr[y, x], node))\n",
    "        return nodes\n",
    "    \n",
    "    visited, _ = dijkstra(data, start, get_neighbors, end_condition)\n",
    "\n",
    "    distances = {}\n",
    "    for i in visited:\n",
    "        pos = complex(i.split(',')[0])\n",
    "        distances[pos] = min(distances.get(pos, math.inf), visited[i])\n",
    "    if debug:\n",
    "        heat_map(distances)\n",
    "    return distances[1j*(ymax-1)+xmax-1]\n",
    "\n",
    "day17(data17), day17(data17, 10, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(40131, 104454050898331)"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data18 = data(18, lambda x: x.split())\n",
    "\n",
    "def decode(data):\n",
    "    diffs = {\n",
    "        'R': 1,\n",
    "        'D': -1j,\n",
    "        'L': -1,\n",
    "        'U': 1j\n",
    "    }\n",
    "    for dir, length, _ in data:\n",
    "        yield diffs[dir], int(length)\n",
    "\n",
    "def decode_2(data):\n",
    "    diffs = {\n",
    "        '0': 1,\n",
    "        '1': -1j,\n",
    "        '2': -1,\n",
    "        '3': 1j\n",
    "    }\n",
    "    for _, _, hex  in data:\n",
    "        match = re.match(r'\\(#(.*)\\)', hex)[1]\n",
    "        n, dir = match[:-1], match[-1]\n",
    "        yield diffs[dir], int(n, 16)\n",
    "\n",
    "def day18(data, decode=decode):\n",
    "    current, ymin = 0, 0\n",
    "    for diff, length in decode(data):\n",
    "        if diff.imag:\n",
    "            current -= diff.imag*length\n",
    "            ymin = max(current, ymin)\n",
    "    current = ymin*1j\n",
    "\n",
    "    # taken from https://www.mathsisfun.com/geometry/area-irregular-polygons.html from https://old.reddit.com/r/adventofcode/comments/18l0qtr/2023_day_18_solutions/kdvs7m3/\n",
    "    surface, area = 1, 0\n",
    "    for diff, length in decode(data):\n",
    "        current = current + length*diff\n",
    "        surface += length\n",
    "        if not diff.imag:\n",
    "            area += (-1 if diff < 0 else 1)*(length)*(current.imag)*2\n",
    "\n",
    "    return math.ceil((surface + abs(area))/2)\n",
    "        \n",
    "day18(data18), day18(data18, decode_2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(331208, 121464316215623)"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get19():\n",
    "    rules = defaultdict(lambda: [])\n",
    "    parts = []\n",
    "    with open(f\"./data/day19.txt\") as f:\n",
    "        lines = f.readlines()\n",
    "        for i in range(len(lines)):\n",
    "            line = lines[i].strip()\n",
    "            if not line:\n",
    "                break\n",
    "            start, checks, terminus = re.findall(r'([a-zA-Z]+){((?:[a-zA-Z]+[<>]\\d+:[a-zA-Z]+,)+)([a-zA-Z]+)}', line)[0]\n",
    "            rules[start] = [check.split(':') for check in checks.split(',')[:-1]] + [['True', terminus]]\n",
    "        for i in range(i+1, len(lines)):\n",
    "            vars = [var.split('=') for var in re.findall(r'{(.+)}', lines[i].strip())[0].split(',')]\n",
    "            parts.append({k:int(v) for k,v in vars})\n",
    "    return rules, parts\n",
    "\n",
    "data19 = get19()\n",
    "\n",
    "def day19_1(rules, parts):\n",
    "    accepted = []\n",
    "\n",
    "    def check_part(part):\n",
    "        x, m, a, s = part['x'], part['m'], part['a'], part['s']\n",
    "        workflow = 'in'\n",
    "        while workflow:\n",
    "            for check, accept in rules[workflow]:\n",
    "                if eval(check):\n",
    "                    if accept == 'A':\n",
    "                        return accepted.append(part)\n",
    "                    elif accept == 'R':\n",
    "                        return\n",
    "                    workflow = accept\n",
    "                    break\n",
    "\n",
    "    for part in parts:\n",
    "        check_part(part)\n",
    "    return sum([sum(x.values()) for x in accepted])\n",
    "\n",
    "def day19_2(rules):\n",
    "    def rule_bounds(workflow, vars):\n",
    "        count = 0\n",
    "        if workflow == 'R':\n",
    "            return count\n",
    "        if workflow == 'A':\n",
    "            return functools.reduce(lambda acc, v: acc*(vars[v][1]-vars[v][0]+1), vars.keys(), 1)\n",
    "        for check, result in rules[workflow]:\n",
    "            if not (matched := re.match(r'([a-zA-z]+)(<|>)(\\d+)', check)):\n",
    "                return count + rule_bounds(result, vars)\n",
    "            var, sign, num = matched[1], matched[2], int(matched[3])\n",
    "            vrange, varss, varsl, lt = vars[var], vars.copy(), vars.copy(), sign=='<'\n",
    "            varss[var], varsl[var] = (vrange[0], num-(1 if lt else 0)), (num+(0 if lt else 1), vrange[1])\n",
    "            conds = {'<': varss, '>': varsl}\n",
    "            count += 0 if conds[sign][var][0] > conds[sign][var][1] else rule_bounds(result, conds[sign])\n",
    "            vars = conds['<' if sign == '>' else '>']\n",
    "            if vars[var][0] > vars[var][1]:\n",
    "                break\n",
    "        return count\n",
    "    return rule_bounds('in', {v: (1, 4000) for v in ['x', 'm', 'a', 's']})\n",
    "    \n",
    "day19_1(*data19), day19_2(data19[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(873301506, 241823802412393)"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "debug=False\n",
    "\n",
    "def parse20():\n",
    "    cons, flips, sources = {}, {}, defaultdict(lambda: [])\n",
    "    for line in data(20):\n",
    "        i, o = line.split(' -> ')\n",
    "        outputs = o.split(', ')\n",
    "        if i[0] == 'b':\n",
    "            broadcaster = outputs\n",
    "            i = f' broadcaster'\n",
    "        else:\n",
    "            (flips if i[0] == '%' else cons)[i[1:]] = [False, outputs]\n",
    "        for out in outputs:\n",
    "            sources[out].append(i[1:])\n",
    "    for con in cons:\n",
    "        cons[con][0] = {x: False for x in sources[con]}\n",
    "    return broadcaster, flips, cons, sources['rx'][0]\n",
    "\n",
    "data20 = parse20()\n",
    "\n",
    "def day20(broadcaster, flips, cons, target):\n",
    "    q, pulses, period = deque(), Counter(), {}    \n",
    "\n",
    "    def run():\n",
    "        while q:\n",
    "            source, mod, high = q.popleft()\n",
    "            pulses[high] += 1\n",
    "            if debug:\n",
    "                print(f'{source} -{'high' if high else 'low'} -> {mod}')\n",
    "            if (flip := flips.get(mod)) and not high:\n",
    "                status = not flip[0]\n",
    "                flip[0] = status\n",
    "                for dest in flip[1]:\n",
    "                    q.append((mod, dest, status))\n",
    "            elif con := cons.get(mod):\n",
    "                con[0][source] = high\n",
    "                output = False if np.all(list(con[0].values())) else True\n",
    "                for dest in con[1]:\n",
    "                    q.append((mod, dest, output))\n",
    "                    if output and dest == target:\n",
    "                        if mod not in period: # tested, this is perfectly periodic\n",
    "                            period[mod] = i+1 # because dd is the next step\n",
    "\n",
    "    def push():\n",
    "        pulses[False]+=1\n",
    "        for i in broadcaster:\n",
    "            q.append(('broadcaster', i, 0))\n",
    "        run()\n",
    "\n",
    "    for i in range(1000):\n",
    "        if debug:\n",
    "            print(i, pulses)\n",
    "        push()\n",
    "    part1 = functools.reduce(lambda x, y: x*y, pulses.values(), 1)\n",
    "\n",
    "    while len(period) < 4:\n",
    "        i+=1\n",
    "        push()\n",
    "\n",
    "    return part1, math.lcm(*period.values())\n",
    "\n",
    "day20(*data20)             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3617, 596857397104703)"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data21 = np.array(data(21, list))\n",
    "\n",
    "def possibles(visited):\n",
    "    results = Counter(visited.values())\n",
    "    for i in results:\n",
    "        results[i] = results[i] + results.get(i-2, 0)\n",
    "    return results\n",
    "\n",
    "def _day21(data, start):\n",
    "    ymax, xmax = data.shape\n",
    "    def get_neighbors(data, current):\n",
    "        for i in [1, -1, 1j, -1j]:\n",
    "            candidate = current + i\n",
    "            y, x = int(candidate.imag), int(candidate.real)\n",
    "            if y < 0 or y >= ymax or x < 0 or x >=xmax:\n",
    "                continue\n",
    "            if data[y, x] == '#':\n",
    "                continue\n",
    "            yield candidate\n",
    "    visited, _ = dfs(data, start, get_neighbors)\n",
    "    return possibles(visited)\n",
    "\n",
    "def day21(data):\n",
    "    ymax, xmax = data.shape\n",
    "    start = np.where(data == 'S')\n",
    "    start = start[0][0]*1j + start[1][0]\n",
    "    part1 = _day21(data, start)[64]\n",
    "    \n",
    "    n = 5\n",
    "    start += ((n-1)/2)*(ymax*1j + xmax)\n",
    "    temp = np.concatenate([data]*n, axis=0)\n",
    "    arr = np.concatenate([temp]*n, axis=1)\n",
    "    visited = _day21(arr, start)\n",
    "\n",
    "    first_edge = int((ymax-1)/2)\n",
    "    edges = [visited[i] for i in range(first_edge, first_edge+int(start.real)+1, ymax)]\n",
    "    steps = determine_steps(edges, 0)\n",
    "\n",
    "    # no idea why this works: taken from https://topaz.github.io/paste/#XQAAAQC3BQAAAAAAAAAzHUn/qWH7EwabIo363rcY5+qgXmPV7N++kDKUNVqpdxLx5ALztLD8JbsxWQoqaYoWk1LQqJD1GWoSR8s9L3mNyO4gQ+t7GGicv79QkOenjs8SXabqxDbJZfEK73BVbwVYC+U/bGiOMz/6gPG42VOzBCfXIq5KbNLvswJPg7mSDG8Iv1U32F8CByXfymd2qYs6yOa0gbwcCJp/3d7nHb59Hu2vBBKqX1b7klR+9QAc2k9lmDSt6qtT5qHQm3Aa9IysWwjGgB9m22b2UlfKuKFkjajLecDrcKLGtKexhN4TMbfzc0ISGfhprT9WazI6U+0gj2MLVdtbytewnt+vAZ3eJB9lbJrBCq6pWVawGnCPi7phPObHuhAYw9P7x1IPUYQ7+c/R6fH59v7MCIVTee/vqAjUvq2wDt9YSrQE1bWcbTOfQdbf8dB3Vw5v33VBdiuCF8QkugnnKAnpgr84ZfKuVsv2Z5IujhD4FIDuy7qKagMqwKg1oWmeeK7eRUTQXm4AGIWatAN9GAO8s9xyZXkoJkDxL2FjMUNnubETNoOmrXo1h3vpsDzafk2obzqZ8/NWlAcWFiYgbTRN8y7KfGPr/D5ilGDVzQtOH+FDBeWtoJJUuGm0oxK2BhMOEvlc4EYh8MLWFGfmyrPHc1ZTRGD3cWjjgdfiYxC/IF+13M0vPNFF5g0kddUzGuSy0YzIlJka8t5wz3OXN4tkjI5zVs165kXJv9kQBx29By8MlR0ad+LO1Ngc+3dQLJ3kXxl+PMXzSMbplD3HF+Z5wmAqA4KKL5QUNdIDUsFIfog+3+jmhIi2ZpAfD2/HvDfDvW+W+0AMJffu4M+WuoQmoOr2IpaZrxPa8C9Fn/2K+BI=\n",
    "    f = lambda x: int(steps[0] + steps[1]*x + x*(x-1)*steps[2]/2)\n",
    "    part2 = f(202300) # 131*202300+65 = 26501365\n",
    "\n",
    "    return part1, part2\n",
    "\n",
    "day21(data21)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(405, 61297)"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse22():\n",
    "    lines = data(22)\n",
    "    maxx, maxy, maxz = 0, 0, 0\n",
    "    blocks = []\n",
    "    for line in lines:\n",
    "        start, end = line.split('~')\n",
    "        split = lambda x: map(int, x.split(','))\n",
    "        (x0, y0, z0), (x1, y1, z1) = list(split(start)), list(split(end))\n",
    "        maxx, maxy, maxz = max(x1, maxx+1), max(y1, maxy+1), max(z1, maxz)\n",
    "        blocks.append([(z0, z1+1), (x0, x1+1), (y0, y1+1)])       \n",
    "    arr = np.zeros((maxz+1, maxx+1, maxy+1))\n",
    "    for i, (z, x, y) in enumerate(blocks):\n",
    "        arr[z[0], x[0], y[0]] = i+1\n",
    "    return arr, sorted(blocks)\n",
    "\n",
    "data22 = parse22()\n",
    "\n",
    "def day22(arr, blocks):\n",
    "    arr, supported = arr.copy(), {}\n",
    "\n",
    "    def drop(arr, i):\n",
    "        (z0, z1), (x0, x1), (y0, y1) = blocks[i]\n",
    "        z = z0\n",
    "        while z > 0:\n",
    "            z -= 1 \n",
    "            if len((supps := np.nonzero(arr[z, x0:x1, y0:y1]))[0]):\n",
    "                supported[i+1] = set(arr[z, x0:x1, y0:y1][supps])\n",
    "                break\n",
    "        arr[z0, x0, y0] = 0\n",
    "        arr[z+1:(z+1)+(z1-z0), x0:x1, y0:y1] = i+1\n",
    "\n",
    "    for i in range(len(blocks)):\n",
    "        drop(arr, i)\n",
    "\n",
    "    safe, supports = set(range(1, len(blocks)+1)), defaultdict(lambda: set())\n",
    "    for block in supported:\n",
    "        if len(supported[block]) == 1:\n",
    "            safe.discard(next(iter(supported[block])))\n",
    "        for support in supported[block]:\n",
    "            supports[support].add(block)\n",
    "\n",
    "    def chain_reaction(i, acc):\n",
    "        for candidate in supports.get(i, []):\n",
    "            if not supported[candidate].difference(acc):\n",
    "                acc.add(candidate)\n",
    "                chain_reaction(candidate, acc)\n",
    "        return len(acc)-1\n",
    "        \n",
    "    return len(safe), sum([chain_reaction(i, set([i]))  for i in supports])\n",
    "\n",
    "day22(*data22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2314, 6874)"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data23 = np.array(data(23, list))\n",
    "\n",
    "# more or less directly copied from solutions in https://old.reddit.com/r/adventofcode/comments/18oy4pc/2023_day_23_solutions/\n",
    "def gen_graph(data, slope_flag=True):\n",
    "    ymax, xmax = data.shape\n",
    "    graph = nx.DiGraph(nx.grid_graph((xmax, ymax)))\n",
    "    slopes = {'^': (0, -1), '>': (1, 0), 'v': (0, 1), '<': (-1, 0)}\n",
    "\n",
    "    for j, row in enumerate(data):\n",
    "        for i, v in enumerate(row):\n",
    "            if v == '#':\n",
    "                graph.remove_node((i, j))\n",
    "            elif slope_flag and (slope := slopes.get(v)):\n",
    "                graph.remove_edge((i, j), (i-slope[0], j-slope[1]))\n",
    "\n",
    "    nx.set_edge_attributes(graph, 1, 'weight')\n",
    "\n",
    "    for node in list(graph):\n",
    "        neighbors = list(graph.neighbors(node))\n",
    "        if len(neighbors) == 2:\n",
    "            new_weight = sum(graph.edges[node, neigh].get('weight', 1) for neigh in neighbors)\n",
    "            graph.add_edge(*neighbors, weight=new_weight)\n",
    "            graph.add_edge(neighbors[1], neighbors[0], weight=new_weight)\n",
    "            graph.remove_node(node)\n",
    "    return graph\n",
    "\n",
    "\n",
    "def day23(data, slope_flag=True):\n",
    "    graph = gen_graph(data, slope_flag)\n",
    "    # nx.draw(graph)    \n",
    "    return max(nx.path_weight(graph, path, 'weight') for path in nx.all_simple_paths(graph,  (np.where(data[0] == '.')[0][0], 0), (np.where(data[-1] == '.')[0][0], len(data)-1)))\n",
    "\n",
    "# 1-2 minute runtime\n",
    "day23(data23), day23(data23, False) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(14046, 808107741406756)"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse24(line):\n",
    "    pos, vel = line.split(' @ ')\n",
    "    f = lambda x: list(map(lambda x: decimal.Decimal(x), x.split(', ')))\n",
    "    return f(pos), f(vel)\n",
    "\n",
    "data24 = data(24, parse24)\n",
    "\n",
    "def day24_1(data, minb, maxb):\n",
    "    count = 0\n",
    "    for i, (a1, velA) in enumerate(data[:-1]):\n",
    "        a2 = np.add(a1, velA)\n",
    "        # https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line\n",
    "        for (b1, velB) in data[i+1:]:\n",
    "            b2 = np.add(b1, velB)\n",
    "            (x1, y1, _), (x2, y2, _), (x3, y3, _), (x4, y4, _) = a1, a2, b1, b2\n",
    "            if ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)) == 0:\n",
    "                continue\n",
    "            intx = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))\n",
    "            inty = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))\n",
    "            \n",
    "            minx = max(minb, x1 if velA[0] > 0 else minb, x3 if velB[0] > 0 else minb)\n",
    "            maxx = min(maxb, x1 if velA[0] < 0 else maxb, x3 if velB[0] < 0 else maxb)\n",
    "            miny = max(minb, y1 if velA[1] > 0 else minb, y3 if velB[1] > 0 else minb)\n",
    "            maxy = min(maxb, y1 if velA[1] < 0 else maxb, y3 if velB[1] < 0 else maxb)\n",
    "            if minx <= intx <= maxx and miny <= inty <= maxy:\n",
    "                count += 1\n",
    "    return count\n",
    "\n",
    "def day24_2(data):\n",
    "    # using z3 as suggested in https://old.reddit.com/r/adventofcode/comments/18pnycy/2023_day_24_solutions/\n",
    "    solver = z3.Solver()\n",
    "    x = z3.Int('x')\n",
    "    y = z3.Int('y')\n",
    "    z = z3.Int('z')\n",
    "    vx = z3.Int('vx')\n",
    "    vy = z3.Int('vy')\n",
    "    vz = z3.Int('vz')\n",
    "\n",
    "    for hail in data:\n",
    "        (a, b, c), (va, vb, vc) = hail\n",
    "        # x + vx*t = a + va*t\n",
    "        # x-a = t(va-vx)\n",
    "        # (x-a)/(va-vx) = t = (y-b)/(vb-vy)\n",
    "        # (x-a)*(vb-vy) = (y-b)*(va-vx)\n",
    "        solver.add((x-a)*(vb-vy) == (y-b)*(va-vx))\n",
    "        solver.add((x-a)*(vc-vz) == (z-c)*(va-vx))\n",
    "\n",
    "    solver.check()\n",
    "    result = solver.model()\n",
    "    return result[x].as_long() + result[y].as_long() + result[z].as_long()\n",
    "\n",
    "day24_1(data24, 200000000000000, 400000000000000), day24_2(data24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "531437"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def parse25(data):\n",
    "    g = nx.Graph()\n",
    "    for line in data:\n",
    "        start, ends = line.split(': ')\n",
    "        for end in ends.split(' '):\n",
    "            g.add_edge(start, end)\n",
    "    return g\n",
    "\n",
    "data25 = parse25(data(25))\n",
    "\n",
    "def day25(g):\n",
    "    n, groups = nx.stoer_wagner(g)\n",
    "    assert n == 3\n",
    "    return functools.reduce(lambda x, y: x*len(y), groups, 1)\n",
    "\n",
    "day25(data25)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}