AoC_2023.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Advent of Code 2023\n",
    "\n",
    "This notebook contains my solutions for the Advent of Code (https://adventofcode.com/2023) programming challenge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Init\n",
    "import numpy, re, itertools"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 1: Trebuchet?!\n",
    "https://adventofcode.com/2023/day/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input 1 ---\n",
    "\n",
    "input1 = \"\"\"1abc2\n",
    "pqr3stu8vwx\n",
    "a1b2c3d4e5f\n",
    "treb7uchet\"\"\"\n",
    "\n",
    "# --- Test Input 2 ---\n",
    "\n",
    "input2 = \"\"\"two1nine\n",
    "eightwothree\n",
    "abcone2threexyz\n",
    "xtwone3four\n",
    "4nineeightseven2\n",
    "zoneight234\n",
    "7pqrstsixteen\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "142"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- Part 1 ---\n",
    "\n",
    "rows = [list(filter(str.isnumeric, line)) for line in input1.splitlines()]\n",
    "sum(int(n[0]+n[-1]) for n in rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "281"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- Part 2 ---\n",
    "\n",
    "for i,n in enumerate(\"one two three four five six seven eight nine\".split()):\n",
    "    input2 = input2.replace(n, n[0]+str(i+1)+n[2:])\n",
    "rows = (list(filter(str.isnumeric, line)) for line in input2.splitlines())\n",
    "sum(int(n[0]+n[-1]) for n in rows)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 2: Cube Conundrum\n",
    "https://adventofcode.com/2023/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green\n",
    "Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue\n",
    "Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red\n",
    "Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red\n",
    "Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- Part 1 ---\n",
    "\n",
    "bag = {\"red\": 12 , \"green\": 13 , \"blue\": 14}\n",
    "idSum = 0\n",
    "for game in input.splitlines():\n",
    "    ID, _, S = game.partition(':')\n",
    "    possible = True\n",
    "    for s in S.split(';'):\n",
    "        for cs in s.split(','):\n",
    "            n, c = cs.split()\n",
    "            if int(n) > bag[c]:\n",
    "                possible = False\n",
    "    if possible:\n",
    "        idSum += int(ID.split()[1])\n",
    "idSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2286"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- Part 2 ---\n",
    "\n",
    "score = 0\n",
    "for game in input.splitlines():\n",
    "    bag = {\"red\": 0 , \"green\": 0 , \"blue\": 0}\n",
    "    ID, _, S = game.partition(':')\n",
    "    possible = True\n",
    "    for s in S.split(';'):\n",
    "        for cs in s.split(','):\n",
    "            n, c = cs.split()\n",
    "            if int(n) > bag[c]:\n",
    "                bag[c] = int(n)\n",
    "    p = 1\n",
    "    for v in bag.values(): p *= v\n",
    "    score += p\n",
    "score"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 3: Gear Ratios\n",
    "https://adventofcode.com/2023/day/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"467..114..\n",
    "...*......\n",
    "..35..633.\n",
    "......#...\n",
    "617*......\n",
    ".....+.58.\n",
    "..592.....\n",
    "......755.\n",
    "...$.*....\n",
    ".664.598..\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 4361\n",
      "Part 2: 467835\n"
     ]
    }
   ],
   "source": [
    "# --- Part 1 + 2 ---\n",
    "\n",
    "import numpy, re\n",
    "\n",
    "chars = numpy.array([list(l)+['.'] for l in input.split()])\n",
    "numbers = list(map(int, re.findall('\\d+', input)))\n",
    "numIndexMap = numpy.zeros(chars.shape, 'i') - 1\n",
    "for i,m in enumerate(re.finditer('\\d+', input)):\n",
    "    numIndexMap.flat[m.start(): m.end()] = i\n",
    "\n",
    "sPart1 = set()\n",
    "sPart2 = 0\n",
    "for x in range(chars.shape[0]):\n",
    "    for y in range(chars.shape[1]):\n",
    "        if chars[x,y] != '.' and numIndexMap[x,y] == -1:\n",
    "            sPart1.update(numIndexMap[x-1:x+2,y-1:y+2].ravel())\n",
    "        if chars[x,y] == '*':\n",
    "            ind = set(numIndexMap[x-1:x+2,y-1:y+2].ravel())\n",
    "            neigb = [i for i in ind if i>=0] # neighbors\n",
    "            if len(neigb) == 2:\n",
    "                sPart2 += numbers[neigb[0]] * numbers[neigb[1]]\n",
    "\n",
    "print('Part 1:', sum([numbers[i] for i in sPart1 if i>=0]))\n",
    "print('Part 2:', sPart2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 4: Scratchcards\n",
    "https://adventofcode.com/2023/day/4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53\n",
    "Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19\n",
    "Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1\n",
    "Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83\n",
    "Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36\n",
    "Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "part 1: 13\n",
      "part 2: 30\n"
     ]
    }
   ],
   "source": [
    "# --- Part 1 + 2 ---\n",
    "\n",
    "lines = input.splitlines()\n",
    "s = 0  # Part 1\n",
    "cardCount = [1] * len(lines)  # Part 2\n",
    "for i,line in enumerate(lines):\n",
    "    n1, n2 = line.split(':')[-1].split('|')\n",
    "    points = len(set(n1.split()).intersection(n2.split()))\n",
    "    s += int(2**(points-1))  # Part 1\n",
    "    for j in range(i+1,i+1+points): cardCount[j] += cardCount[i] # Part 2\n",
    "print('part 1:', s)\n",
    "print('part 2:', sum(cardCount))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 5: If You Give A Seed A Fertilizer\n",
    "https://adventofcode.com/2023/day/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"seeds: 79 14 55 13\n",
    "\n",
    "seed-to-soil map:\n",
    "50 98 2\n",
    "52 50 48\n",
    "\n",
    "soil-to-fertilizer map:\n",
    "0 15 37\n",
    "37 52 2\n",
    "39 0 15\n",
    "\n",
    "fertilizer-to-water map:\n",
    "49 53 8\n",
    "0 11 42\n",
    "42 0 7\n",
    "57 7 4\n",
    "\n",
    "water-to-light map:\n",
    "88 18 7\n",
    "18 25 70\n",
    "\n",
    "light-to-temperature map:\n",
    "45 77 23\n",
    "81 45 19\n",
    "68 64 13\n",
    "\n",
    "temperature-to-humidity map:\n",
    "0 69 1\n",
    "1 0 69\n",
    "\n",
    "humidity-to-location map:\n",
    "60 56 37\n",
    "56 93 4\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "46\n"
     ]
    }
   ],
   "source": [
    "blocks = input.split('\\n\\n')\n",
    "seeds = list(map(int,blocks[0].split(':')[1].split()))\n",
    "transforms = [[list(map(int, line.split()))\n",
    "               for line in b.split(':\\n')[-1].split('\\n')]\n",
    "               for b in blocks[1:]]\n",
    "\n",
    "intervals = set(((i,1) for i in seeds))        # -- part 1 --\n",
    "intervals = set(zip(seeds[::2], seeds[1::2]))  # -- part 2 --\n",
    "\n",
    "for transform in transforms:\n",
    "    shiftedInterv = set()\n",
    "    for yShifted, y, ny in transform:  # y: transformed interval\n",
    "        restIntervals = set()\n",
    "        for i,(x,nx) in enumerate(intervals): # x: original interval\n",
    "            edges = sorted([(x,'x'), (x+nx,'x'), (y,'y'), (y+ny,'y')])\n",
    "            order = ''.join(s for _,s in edges)\n",
    "            parts = [(e, edges[i+1][0]-e) for i,(e,_) in enumerate(edges[:-1])]\n",
    "            task = { # overlap cases\n",
    "                # case: what to do with the 3 parts (x:keep, +:transform)\n",
    "                \"xxyy\": \"x  \", # non-overlapping\n",
    "                \"yyxx\": \"  x\", # non-overlapping\n",
    "                \"xyxy\": \"x+ \", # x left overlap\n",
    "                \"yxyx\": \" +x\", # x right overlap\n",
    "                \"xyyx\": \"x+x\", # y inside x\n",
    "                \"yxxy\": \" + \", # x inside y\n",
    "            }[order]\n",
    "            for trans, (newX, newN) in zip(task, parts):\n",
    "                if newN > 0:\n",
    "                    if trans == 'x': restIntervals.add((newX, newN))\n",
    "                    if trans == '+': shiftedInterv.add((newX+yShifted-y, newN))\n",
    "        intervals = restIntervals\n",
    "    intervals = shiftedInterv.union(restIntervals)\n",
    "print(min(intervals)[0])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 6: Wait For It\n",
    "https://adventofcode.com/2023/day/6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"Time:      7  15   30\n",
    "Distance:  9  40  200\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "71503"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# inp = input                  # --- part 1 ---\n",
    "inp = input.replace(' ','')  # --- part 2 ---\n",
    "\n",
    "import numpy\n",
    "times = numpy.array(list(map(int, inp.splitlines()[0].split(':')[1].split())),'d')\n",
    "distances = numpy.array(list(map(int, inp.splitlines()[1].split(':')[1].split())),'d')\n",
    "tMin = numpy.ceil(times/2 - numpy.sqrt(times**2/4-distances) + 1E-12)\n",
    "tMax = numpy.floor(times/2 + numpy.sqrt(times**2/4-distances) - 1E-12)\n",
    "int(numpy.prod(tMax - tMin + 1))\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 7: Camel Cards\n",
    "https://adventofcode.com/2023/day/7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"32T3K 765\n",
    "T55J5 684\n",
    "KK677 28\n",
    "KTJJT 220\n",
    "QQQJA 483\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5905"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "values, joker = \"AKQJT98765432\"[::-1], '-'  # --- Part 1 ---\n",
    "values, joker = \"AKQT98765432J\"[::-1], 'J'  # --- Part 2 ---\n",
    "\n",
    "ranks = '11111 1112 122 113 23 14 5'.split()\n",
    "cardList = input.splitlines()\n",
    "for i,line in enumerate(cardList):\n",
    "    card, bid = line.split()\n",
    "    bestValues = sorted((card.count(c), values.index(c), c)\n",
    "                        for c in set(card) if c != joker)\n",
    "    bestCard = card.replace(joker, bestValues[-1][2]\n",
    "                            if bestValues else values[-1])\n",
    "    rank = ranks.index(''.join(sorted(str(bestCard.count(c))\n",
    "                                      for c in set(bestCard))))\n",
    "    card = ''.join([chr(ord('A')+values.index(v)) for v in card])\n",
    "    cardList[i] = rank, card, int(bid)\n",
    "sum([line[2]*(i+1) for i,line in enumerate(sorted(cardList))])\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 8: Haunted Wasteland\n",
    "https://adventofcode.com/2023/day/8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input1 = \"\"\"LLR\n",
    "\n",
    "AAA = (BBB, BBB)\n",
    "BBB = (AAA, ZZZ)\n",
    "ZZZ = (ZZZ, ZZZ)\"\"\"\n",
    "\n",
    "input2 = \"\"\"LR\n",
    "\n",
    "11A = (11B, XXX)\n",
    "11B = (XXX, 11Z)\n",
    "11Z = (11B, XXX)\n",
    "22A = (22B, XXX)\n",
    "22B = (22C, 22C)\n",
    "22C = (22Z, 22Z)\n",
    "22Z = (22B, 22B)\n",
    "XXX = (XXX, XXX)\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This final solution is assuming 3 properties of the data:\n",
    "1. The system enters the loop already at the second step.\n",
    "2. The loop has only one z-node\n",
    "3. The system enters the loop one step after the z-node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy\n",
    "\n",
    "# input = input1   # --- part 1 ---\n",
    "input = input2   # --- part 2 ---\n",
    "\n",
    "d, _, *net = input.split('\\n')\n",
    "net = {(a:=line.split(' = '))[0]: a[1][1:-1].split(', ') for line in net}\n",
    "nodes = [k for k in net.keys() if k[-1]=='A'] if input != input1 else ['AAA']\n",
    "solutions = []\n",
    "for node in nodes:\n",
    "    iStep = 0\n",
    "    while node[2] != 'Z':\n",
    "        node = net[node]['LR'.index(d[iStep%len(d)])]\n",
    "        iStep += 1\n",
    "    solutions.append(iStep)\n",
    "numpy.lcm.reduce(numpy.array(solutions, 'longlong'))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 9: Mirage Maintenance\n",
    "https://adventofcode.com/2023/day/9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"0 3 6 9 12 15\n",
    "1 3 6 10 15 21\n",
    "10 13 16 21 30 45\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy\n",
    "\n",
    "lines = input.split('\\n')\n",
    "inp = numpy.array([list(map(int,i.split())) for i in lines])\n",
    "\n",
    "inp = inp[:,::-1]  # reverse order --- part 2 ---\n",
    "\n",
    "s = 0\n",
    "for line in inp:\n",
    "    start = []\n",
    "    a = line\n",
    "    while not numpy.all(a==0):\n",
    "        start.append(a[0])\n",
    "        a = numpy.diff(a)\n",
    "    a = [*a, 0]\n",
    "    for i in range(len(start)):\n",
    "        a = numpy.cumsum([start.pop(), *a])\n",
    "    s += a[-1]\n",
    "s"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 10: Pipe Maze\n",
    "https://adventofcode.com/2023/day/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"FF7FSF7F7F7F7F7F---7\n",
    "L|LJ||||||||||||F--J\n",
    "FL-7LJLJ||||||LJL-77\n",
    "F--JF--7||LJLJ7F7FJ-\n",
    "L---JF-JLJ.||-FJLJJ7\n",
    "|F|F-JF---7F7-L7L|7|\n",
    "|FFJF7L7F-JF7|JL---7\n",
    "7-L-JL7||F7|L7F-7F7|\n",
    "L.L7LFJ|||||FJL7||LJ\n",
    "L7JLJL-JLJLJL--JLJ.L\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "80\n"
     ]
    }
   ],
   "source": [
    "# --- part 1 ---\n",
    "\n",
    "import numpy\n",
    "\n",
    "lines = input.split('\\n')\n",
    "a = numpy.array([list(l) for l in lines])\n",
    "ny, nx = a.shape\n",
    "(ys,), (xs,) = numpy.where(a == 'S')\n",
    "\n",
    "up = '|JLS'\n",
    "down = '|7FS'\n",
    "left = '-7JS'\n",
    "right = '-FLS'\n",
    "\n",
    "n = numpy.zeros((ny, nx), 'i')\n",
    "iCount = 0\n",
    "y, x = ys, xs\n",
    "n[y,x] = -1\n",
    "for i in range(a.size):\n",
    "    dx, dy = 0, 0\n",
    "    if y > 0 and n[y-1,x]==0 and \\\n",
    "         a[y,x] in up and a[y-1,x] in down: dy = -1\n",
    "    elif y+1 < ny and n[y+1,x]==0 and \\\n",
    "        a[y,x] in down and a[y+1,x] in up: dy = +1\n",
    "    elif x > 0 and n[y,x-1]==0 and \\\n",
    "        a[y,x] in left and a[y,x-1] in right: dx = -1\n",
    "    elif x+1 < nx and n[y,x+1]==0 and \\\n",
    "        a[y,x] in right and a[y,x+1] in left: dx = 1\n",
    "    else:\n",
    "        print(int(iCount//2+1)) # end of pipe\n",
    "        break\n",
    "    if dx or dy:\n",
    "        y += dy\n",
    "        x += dx\n",
    "        iCount += 1\n",
    "        n[y,x] = iCount\n",
    "        if iCount==1: y1, x1 = y, x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- part 2 ---\n",
    "\n",
    "sType = ''.join(sorted('d u'[y1-ys+1] + 'l r'[x1-xs+1] + \\\n",
    "                       'd u'[y-ys+1]  + 'l r'[x-xs+1])[-2:])\n",
    "# close loop (cases to be extended for other data)\n",
    "a[ys,xs] = {'lu': '7', 'du': '|'}[sType]\n",
    "\n",
    "nTiles = 0\n",
    "for y in range(ny):\n",
    "    crossingH1 = False # 1st half of vertical crossing\n",
    "    crossingH2 = False # 2nd half of vertical crossing\n",
    "    for x in range(nx):\n",
    "        if n[y,x]:\n",
    "            if a[y,x] in down: crossingH1 = not crossingH1\n",
    "            if a[y,x] in up: crossingH2 = not crossingH2\n",
    "        elif crossingH1 and crossingH2: # inside\n",
    "            nTiles += 1\n",
    "nTiles"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 11: Cosmic Expansion\n",
    "https://adventofcode.com/2023/day/11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"...#......\n",
    ".......#..\n",
    "#.........\n",
    "..........\n",
    "......#...\n",
    ".#........\n",
    ".........#\n",
    "..........\n",
    ".......#..\n",
    "#...#.....\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82000210"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# dextra = 2        # --- part 1 ---\n",
    "dextra = 1000000  # --- part 2 ---\n",
    "\n",
    "import numpy\n",
    "\n",
    "lines = input.split('\\n')\n",
    "a = numpy.array([list(l) for l in lines])\n",
    "ny, nx = a.shape\n",
    "g = numpy.stack(numpy.where(a == '#')).T # list of galaxy coordinates\n",
    "\n",
    "y = [] # true coordinate y\n",
    "x = [] # true coordinate x\n",
    "\n",
    "for coordinate, lines in (y, a), (x, a.T):\n",
    "    d = 0\n",
    "    for line in lines:\n",
    "        d += dextra if (line == '.').all() else 1\n",
    "        coordinate.append(d)\n",
    "\n",
    "sum(abs(x[x2]-x[x1]) + abs(y[y2]-y[y1])\n",
    "    for y1,x1 in g for y2,x2 in g) // 2"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 12: Hot Springs\n",
    "https://adventofcode.com/2023/day/12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "input = \"\"\"???.### 1,1,3\n",
    ".??..??...?##. 1,1,3\n",
    "?#?#?#?#?#?#?#? 1,3,1,6\n",
    "????.#...#... 4,1,1\n",
    "????.######..#####. 1,6,5\n",
    "?###???????? 3,2,1\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Items **(i,v)** in counter:\n",
    "*   **i**: arr is confirmed until arr[:i]\n",
    "*   **v**: current incomplete length\n",
    "*   **counter[(i,v)]**: count of solutions with same item\n",
    "\n",
    "cases for **v**:\n",
    "*   **v == 0**: waiting for new block to start\n",
    "*   **v > 0**: waiting for block to end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "525152"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# nParts = 1  # --- part 1 ---\n",
    "nParts = 5  # --- part 2 ---\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "csum = 0\n",
    "for line in input.split('\\n'):\n",
    "    row = '?'.join([line.split()[0]]*nParts)\n",
    "    arr = list(map(int,line.split()[1].split(',')))*nParts\n",
    "    counter = Counter([(0,0)])\n",
    "    for s in row+'.':\n",
    "        for i,v in list(counter.keys()):\n",
    "            n = counter.pop((i, v))\n",
    "            if s in '#?': counter[(i,v+1)] += n\n",
    "            if s in '.?':\n",
    "                if v == 0:\n",
    "                    counter[(i,0)] += n\n",
    "                elif i < len(arr) and arr[i] == v:\n",
    "                    counter[(i+1,0)] += n\n",
    "    csum += counter[(len(arr),0)]\n",
    "csum"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 13: Point of Incidence\n",
    "https://adventofcode.com/2023/day/13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"#.##..##.\n",
    "..#.##.#.\n",
    "##......#\n",
    "##......#\n",
    "..#.##.#.\n",
    "..##..##.\n",
    "#.#.##.#.\n",
    "\n",
    "#...##..#\n",
    "#....#..#\n",
    "..##..###\n",
    "#####.##.\n",
    "#####.##.\n",
    "..##..###\n",
    "#....#..#\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "400"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part = 2  # --- part 1 and 2 ---\n",
    "\n",
    "import numpy\n",
    "scoreSum = 0\n",
    "for block in input.split('\\n\\n'):\n",
    "    score = 0\n",
    "    b = (numpy.array([list(i) for i in block.split()])=='#').astype('i')\n",
    "    sides = b, b.T, b[::-1], b.T[::-1]\n",
    "    for iCut, bSides in enumerate(sides):\n",
    "        for nCut in range(1,len(bSides)-1,2):\n",
    "            bCut = bSides[nCut:]\n",
    "            match = bCut == bCut[::-1]\n",
    "            if (part == 1 and numpy.all(match)) or \\\n",
    "                    (part == 2 and numpy.sum(~match) == 2):\n",
    "                score = len(bCut)//2 + (nCut if iCut < 2 else 0)\n",
    "                break\n",
    "        if score: break\n",
    "    scoreSum += score * (100 if iCut%2 == 0 else 1)\n",
    "scoreSum"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 14: Parabolic Reflector Dish\n",
    "https://adventofcode.com/2023/day/14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"O....#....\n",
    "O.OO#....#\n",
    ".....##...\n",
    "OO.#O....O\n",
    ".O.....O#.\n",
    "O.#..O.#.#\n",
    "..O..#O..O\n",
    ".......O..\n",
    "#....###..\n",
    "#OO..#....\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "136"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- part 1 ---\n",
    "\n",
    "def transpose(a):\n",
    "    return '\\n'.join(''.join(i) for i in list(map(list, zip(*a.splitlines()))))\n",
    "\n",
    "def roll(a):\n",
    "    a = transpose(a)\n",
    "    while '.O' in a: a = a.replace('.O','O.')\n",
    "    return transpose(a)\n",
    "\n",
    "def score(a):\n",
    "    countO = [i.count('O') for i in a.split()]\n",
    "    return sum([(i+1)*n for i, n in enumerate(reversed(countO))])\n",
    "\n",
    "score(roll(input))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "periodicity found from step 3 to 10\n",
      "64\n"
     ]
    }
   ],
   "source": [
    "# --- part 2 ---\n",
    "\n",
    "def spin(a): # turn clock wise\n",
    "    return transpose('\\n'.join(a.splitlines()[::-1]))\n",
    "\n",
    "nCycles = 1000000000\n",
    "\n",
    "history = []\n",
    "a = input\n",
    "for i in range(nCycles):\n",
    "    if a in history:\n",
    "        iPeriodStart = history.index(a)\n",
    "        print(f'periodicity found from step {iPeriodStart} to {i}')\n",
    "        nRemaining = nCycles - iPeriodStart\n",
    "        iH = iPeriodStart + nRemaining % (i-iPeriodStart)\n",
    "        print(score(history[iH]))\n",
    "        break\n",
    "    history.append(a)\n",
    "    for i in range(4): # N,W,S,E\n",
    "        a = spin(roll(a))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 15: Lens Library\n",
    "https://adventofcode.com/2023/day/15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# --- Test Input ---\n",
    "\n",
    "input = \"\"\"rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1320"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- part 1 ---\n",
    "\n",
    "def HASH(s, h=0):\n",
    "    for l in s:\n",
    "        h = ((h+ord(l)) * 17) % 256\n",
    "    return h\n",
    "\n",
    "sum(map(HASH, input.split(',')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "145"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# --- part 2 ---\n",
    "\n",
    "boxes = [{} for i in range(256)]\n",
    "for item in input.split(','):\n",
    "    if '=' in item:\n",
    "        label, fLen = item.split('=')\n",
    "        boxes[HASH(label)][label] = int(fLen)\n",
    "    if '-' in item:\n",
    "        label = item[:-1]\n",
    "        box = boxes[HASH(label)]\n",
    "        if label in box:\n",
    "            del box[label]\n",
    "\n",
    "sum([(HASH(label)+1)*(i+1)*box[label] for box in boxes \\\n",
    "      for i, label in enumerate(box)])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 16: The Floor Will Be Lava\n",
    "https://adventofcode.com/2023/day/16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "input = r\"\"\".|...\\....\n",
    "|.-.\\.....\n",
    ".....|-...\n",
    "........|.\n",
    "..........\n",
    ".........\\\n",
    "..../.\\\\..\n",
    ".-.-/..|..\n",
    ".|....-|.\\\n",
    "..//.|....\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "51\n"
     ]
    }
   ],
   "source": [
    "import numpy\n",
    "chars = numpy.array([list(l) for l in input.split()])\n",
    "ny, nx = chars.shape\n",
    "\n",
    "# (x,y,d), d=0:right, d=1:left, d=2:down, d=3:up\n",
    "frontStart = [(0, y, 0) for y in range(ny)]\n",
    "frontStart += [(nx-1, y, 1) for y in range(ny)]\n",
    "frontStart += [(x, 0, 2) for x in range(nx)]\n",
    "frontStart += [(x, ny-1, 3) for x in range(nx)]\n",
    "\n",
    "# frontStart = frontStart[:1] # --- part 1 ---\n",
    "\n",
    "smax = 0\n",
    "for f in frontStart:\n",
    "    front = [f]\n",
    "    history = numpy.zeros((ny, nx, 4), 'bool')\n",
    "    while front:\n",
    "        x, y, d = front.pop(0)\n",
    "        if not ((0 <= x < nx) and (0 <= y < ny)): continue\n",
    "        if history[y, x, d]: continue\n",
    "        history[y, x, d] = 1\n",
    "        c = chars[y, x]\n",
    "        if c == '|' and d in (0,1):\n",
    "            front.append((x, y-1, 3))\n",
    "            front.append((x, y+1, 2))\n",
    "        elif c == '-' and d in (2,3):\n",
    "            front.append((x-1, y, 1))\n",
    "            front.append((x+1, y, 0))\n",
    "        else:\n",
    "            if c == '\\\\': d = [2,3,0,1][d]\n",
    "            if c == '/': d = [3,2,1,0][d]\n",
    "            dx = [1,-1,0,0][d]\n",
    "            dy = [0,0,1,-1][d]\n",
    "            front.append((x+dx, y+dy, d))\n",
    "    nEnergized = numpy.sum(numpy.sum(history, axis=2) > 0)\n",
    "    smax = max(smax, nEnergized)\n",
    "print(smax)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 17: Clumsy Crucible\n",
    "https://adventofcode.com/2023/day/17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "input = r\"\"\"2413432311323\n",
    "3215453535623\n",
    "3255245654254\n",
    "3446585845452\n",
    "4546657867536\n",
    "1438598798454\n",
    "4457876987766\n",
    "3637877979653\n",
    "4654967986887\n",
    "4564679986453\n",
    "1224686865563\n",
    "2546548887735\n",
    "4322674655533\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "94"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# minTurn, maxGo = 1, 3 # --- part 1 ---\n",
    "minTurn, maxGo = 4, 10  # --- part 2 ---\n",
    "\n",
    "import numpy\n",
    "H = numpy.array([list(map(int,list(l))) for l in input.split()])\n",
    "ny, nx = H.shape\n",
    "front = [(0,1,0,0,1), (0,0,1,1,1)] # score, x, y, d, nd\n",
    "history = numpy.zeros((ny, nx, 4, maxGo+1), 'i')\n",
    "scoreMax = 0\n",
    "\n",
    "while front:\n",
    "    front.sort(reverse=True)\n",
    "    score, x, y, d, nd = front.pop()\n",
    "    if not ((0 <= x < nx) and (0 <= y < ny)): continue\n",
    "    score += H[y, x]\n",
    "    sHist = history[y, x, d, nd]\n",
    "    if sHist > 0 and score >= sHist: continue\n",
    "    history[y, x, d, nd] = score\n",
    "    if (x,y) != (ny-1, nx-1):\n",
    "        dL, dR = (d-1)%4, (d+1)%4  # 0123 = RDLU\n",
    "        xNew, yNew = (x+1, x, x-1, x), (y, y+1, y, y-1)\n",
    "        if nd >= minTurn:\n",
    "            front.append((score, xNew[dL], yNew[dL], dL, 1))\n",
    "            front.append((score, xNew[dR], yNew[dR], dR, 1))\n",
    "        if nd < maxGo: front.append((score, xNew[d], yNew[d], d, nd+1))\n",
    "    else:\n",
    "        if scoreMax == 0 or score < scoreMax:\n",
    "            scoreMax = score\n",
    "scoreMax\n",
    "\n",
    "# Inefficient solution: Runtime for part 2 input took 27 Minutes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#### Day 18"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 18: Lavaduct Lagoon\n",
    "https://adventofcode.com/2023/day/18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Day 24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.10.5"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "181910aaa68cd38c7d7c014f0d8f9f2d166eaab60163d0065093fdfa4a43668d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}