AoC_2022_Day_23.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPOFk3sr2Tq1yFeknAkWmad",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/mattmorganpdx/AdventOfCode2022/blob/main/AoC_2022_Day_23.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JZpq-hb7aN7J",
        "outputId": "e9259f88-3866-4914-da93-869feabee605"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            ".............................###.............#......................#...........\n",
            ".......#...........#...#.........###.#...........##..#.......#.#......#.........\n",
            "..........#..##.#.....#.....#............#..#..............#....#..#............\n",
            "........#.........#.#...#.#...#.#...#..##.....##.#..#..##..........#.#.#..##....\n",
            "....#.......##.......#...#............#...#.#......##.#.#.#....###.........#....\n",
            "...#.............#...#.#......##..##.#.#.#.#.....#.......#..#..#...#...#........\n",
            "......##..######...#..#.#..##.....#.#...#...#.##....#.....#..#.......#..##...#..\n",
            "....#....#.#...#..#..#....#..#..#..#...#.#.#..#.#..#.###.#.##.#.###.#..#.#.#....\n",
            ".....#..#...#.#..#.#...#.#.##.#...#.#.#.#.#.#..#.#..#...#.#..#.#...#.#..#.......\n",
            "...#...#.#...#.##.#.#.....#..#..##.#.#.#.#.#..#.##.#.#.#.##.#.#.#.#.#.#....###..\n",
            ".....#...#.#.##..#.#..##....#..#.#.##.#.#.#.#..#..#.#.#.##.#.#.#.#.#.#..##..#...\n",
            "...#...#.#..##.#..#.#....#.####.#.#..###....#.#.#..#.#.#.##.#.#.#.#...#......#..\n",
            ".....#.#...###..#..#.##.#.#.#..#.##.#..#.#.#.#...##.#.#...#....#.#..#...#.#.....\n",
            "........#.###.#..#..#..#.#.#.##.#..#.####.#.#.#...#.#...#..#.#...#.#..#..#..##..\n",
            "...#..#.#..#.#.##.###.#.#.#.####.##.#.##.#.#.#.#...#.##...#.#.#.#.#..#...#.#....\n",
            ".....#..#.#.#.#.##.#.#.#...##..##.####.##.#.#.#.#.#.#..#.#.#.#.#..#.#..#......#.\n",
            "...#...#.#.#.#.#.#.#..#.#.##.#.#...##.#.##.#.#.#.#.####.#.#.#.#.#..#..#...###...\n",
            "......#.##..#.#.#.#.##.#.#..#.#.#.#.#..#..#.#.#.#.##.#.#.#...#.#..#..#..#.#.#...\n",
            "....#.#...##.#.#.#...##.#..#..##.#.#.#...#.#.#.#.#..#...#.#.#.#..#.##..##..#....\n",
            ".....#..##..#.#.#.#.#..#..#..##.#.##.##.#.#.#.##.#.#.#.#.#.#.#..#.#...........#.\n",
            "....#..#.###.###.#.#.##.#..##.##.#..#..#.#.#.#..###.#...#.#.#.##.#..##....#..#..\n",
            ".....##..##.#.#.#.#.#.#####.##.#.##..#.#....#.##.#.#.#.#.#.#.#..#.#..#..........\n",
            "...#..##...#.#.#.#.#.#.##..#.###.#.##.#.##.#.#..#..#.##.###.#.#.#..#..####.#....\n",
            "...#.....##.#.#.#.#.#.#.#.#..#..#.#.##.##.#.##.#.##.#.#.#....#.#.##.#..#....#.#.\n",
            "......#.#..#.#.#.#.#.#.#.##.#.##.#.#.##..#.#.#..#..#.#.#.##...#.##.#.....#.#....\n",
            "....##.#.#.#..#.#.#.#.###..#.#.##.#..###..#.#.#.#.#..##.##.#.#.#.##.#.#.#.....#.\n",
            "......#.#..#####.#.#.#...#.#..#.##..###.##...#.#.#.##.##..#.#.#.#.....#...##....\n",
            "....#...#.#...#.###.#.###.#.####.#######..#.#.#.#.#.#.##.#.#.#.#.#.###.#..#..#..\n",
            "......#....#.#.#.##...#.#..####.#.#...#.#.#..#.#....#.#.#.#.#.#.#.#...#.#.......\n",
            ".........#..#.##..##.#.#.###.###.#..##.#.#.#...#.#.#.#.#.#.#.###.#.#.#.#.....##.\n",
            "...#.#.##..#.#..##..#...####.##.#.##.#..#.#.#####.#...#.#.#.###.#.#.#.##.###....\n",
            "..........#.#.##..##.#.#..#..#.#.#.#.##..#.#.####.#.#....#...#.#.#.#.#..#..#.#..\n",
            "......##...#.#..#.#.#.#..#..#.#.#.#.#..#..#.#..#.#.#.####...#.#...#.#..#.#.....#\n",
            "...#........#.##.#.#.#.##..#.#...##.##..##.#.####.#.....#.#..#.#.#.#..#...#..#..\n",
            "......#.##.#.##.#.#.#.#.#.#.#.#.###.#.#.#.#.###.##.#.#.#..#.#...#.#.##..#..#....\n",
            "....#..#..#.#..#.#....#..#.#.#.#.#.#.#.#..#..#.#..#.#.#.#.#..#.#.#.#.#.###......\n",
            ".......#.#.####.#..#.#.##...#...#.#.#.#..###.#..##.#.#...#..#.#.#.#.#.#.##..##..\n",
            "........#..###.#.##.#.##.#.#...#.#.#.#.##.##..#.#.#.#.#.#.#.#..#.#.#.#.#........\n",
            "....#.#.#.#.##..#.#.#.#.#.#.#.#.#.#.#.#..##.#.##.#.#.#.#.#.#.#..#.#.#..#.#.##.#.\n",
            "......#....#...#.#.#.#.#...#.#.#.###.#..###.#####.#.#.#.#.#..#.#.#.#..#.#..#....\n",
            "....#...#....##.###.#.#.#.#.#.#.#.#.#.##.#.#..#.##.##.#.#.#.#.#.#.#..##.........\n",
            "......#..#.##..#.#.#.#...#....#..#.#.#.##.#..#.#.#.#.#.#...#.#.#.#..#..#.##..##.\n",
            "..........#.#.#.#.#.#.#.#..#.#.##.#.#.#.##.#..#.#.#.#.#.#.#.#.#.#.##.##.#.#.....\n",
            "...#...###.#.#.#...#.#....#.#..##..#.#...##..#.#.#.#.#.#.#.#.#.#.#..#..#.#......\n",
            "............#.#.#.#.#.##.#.#..#####.#.#.#.###.#.#...#.#...#.#.#...##..#.#...##..\n",
            ".....#....##.#.#....#...#.#..#...###.#.#.#.#.#...#.#.##.##.#.#..#.#..#.#..#.....\n",
            ".......##...#....###.#.#.#.#..###.#.#.#.#.#.#.#...#.##.#....#..#.#..#.#.##....#.\n",
            "...#...#..#...#.#...#.#.#.#.##.#.#.#.#.#.#.#..#..#.#..###.#.#.#..#.#.##.........\n",
            ".........#.###.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#...#.#..#...#.#.##.#.#.#.....###..#\n",
            ".....###..#..#.##.#.#.#.#.##.#.#.#.#.#.#.##..#.#....#.##..#.####.#.#..#.#...#...\n",
            "...#.....#.##.#.##.#.#.###..#.#.#.#.#...#.##.##..#.#.##....#...##.#.##.#.#...#..\n",
            ".....#.#..##.#.##.#.#.#..#.#.#.#.#.#.....#..#..##.#.#.#.#.#.####.#.#...#.#......\n",
            ".........#..#.#....#.#..#.#.#.#.#.##.##.#.##..#.#.##.#.#.#.#.###..#.####.#.##...\n",
            "...#..#.#.#.#####.#....#.#.......#.##..####..#.#.#..#.#.#.#.#.####.#..#........#\n",
            "...#..#..#.##.##.#.#.##.#.#.#..#..#.###.#..##.#.##.#.#.#...#..##.#.###.#..#.....\n",
            "........#.#.##..#.#.##.....#.#.#.#.#.#.#.#...#.#.##..##...#..#..#.#...#..#..##..\n",
            "....###..#..###..#.#..#.#.#.#...#...#.#.#.#.#.#...###..#.#..#.##.#.##.##........\n",
            "...#.#..#.##.#.##.#..#.#.#.#..#..#.#.#.#.#.#.#.#.#.#.#..#.##.#..#.#..#..#.##....\n",
            "......#..#..#..#.#..#.#.#.#.##.#..#.#.#.#.###.#.#.#.#.#..#..##.#.#.#.#.#..#.....\n",
            "...#....#.#.###.#.##.#...#....#.#....#.#..#..#.#.#.#...#..##..#.#.#.#.#.#...##..\n",
            "....#..#.#.##..#.#..#.#.#..#.#.#.#.#..##.#..#.#....##.#.#.#.##.#..#.#..#..#.....\n",
            "..#.#...#...#.##.#.##.#.#.#.#.#......#.#.##.#...#.#..#.#.#.####..#.#.#..#.#...#.\n",
            "....#.#..#..##.##.#..#.#.#.#..#.#.#.#.#.#..#..#..#.##.#.#.#...#.#.#.#.##..#.#...\n",
            "...#....#.....###..##.###.###.#..#.#...#..#.##.##..###.#.##.##.#.#.#.#..#.....#.\n",
            "#....#.#.#.#..#..#..#.#..#.#.#..#.#.#.#.#.#...#..#..#.#..#.##.#.#..##....#..#...\n",
            "....#...#.#.#...#.##.#.##.#.#.#.#.#..#.#.#..#.###.#..#.#...##.#.###.#.#.#.#.....\n",
            ".#....#..#.#..#..#..#.##.#.#.##..#.#.#....#..#...#.##.#.###..#.#.#...#....#..##.\n",
            ".#........#..#.#...#.#..#.#..#.##.#.#.#.##..#.#.#.#.##.#.#.#..#.#.#.#.#.#.......\n",
            "......###.....#..##.#.#..#..#.#....#.#.#..#..#.#.#.#..#.#.#.#.##.#.##.#.#..##...\n",
            "..##.....#.####.#..#.#.#.#.#.#.#.#....#.#.#.#.#.#.#.#..####.##.##.#...#...#...#.\n",
            "........#.##...#.#..#...#...#.#.#..##..#.#.#.#.#.#.#.#..##.##.##.#.#...#...#....\n",
            ".....##......#..#..#.#.#..#..#...#.#..#.#.#.........#.#...##.#..#.#.#..#.....#..\n",
            "........#.#.#.#..#.#..#..#.#..#.#...........##..#.#..#.#.#..#....#.......#......\n",
            ".......#..........#.....#...........#..#.#.........#......#..##.....###.#....#..\n",
            ".....#...#.##..#...#.#.....##..#..#...#.#.#.#.##.#...##.#.#.....#.........##....\n",
            "..............#..#.....#.#......#.##......................#...#...#.#..#.#......\n",
            ".......#.#.#.....##.#...#.#.#.#.........#..........##..#....#..#...#........#...\n",
            ".............#........#..............#....#.#.##...#..#....#..#......#..........\n",
            "...............#..................##....................#.......#...............\n",
            "found 3925 empty dots\n",
            "903\n"
          ]
        }
      ],
      "source": [
        "from collections import deque\n",
        "\n",
        "def draw_locations(elf_locations):\n",
        "  min_y = min(elf_locations)[0]\n",
        "  max_y = max(elf_locations)[0]\n",
        "  min_x = min(l[1] for l in elf_locations)\n",
        "  max_x = max(l[1] for l in elf_locations)\n",
        "  count = 0\n",
        "  for y in range(min_y, max_y + 1):\n",
        "    for x in range(min_x, max_x + 1):\n",
        "      print('#' if (y,x) in elf_locations else '.', end=\"\")\n",
        "      count += 0 if (y,x) in elf_locations else 1\n",
        "    print()\n",
        "  print(f\"found {count} empty dots\")\n",
        "\n",
        "elf_locations = []\n",
        "\n",
        "for idx, line in enumerate(pi.splitlines()):\n",
        "  for jdx, space in enumerate(line):\n",
        "    if space == '#':\n",
        "      elf_locations.append((idx, jdx))\n",
        "\n",
        "def check_empty(elf, f):\n",
        "  for i in [-1, 0, 1]:\n",
        "    if f(elf, i) in elf_locations:\n",
        "      return False\n",
        "  return True\n",
        "\n",
        "direction_check_functions = {\n",
        "    'n': lambda elf, i: (elf[0] - 1, elf[1] + i),\n",
        "    's': lambda elf, i: (elf[0] + 1, elf[1] + i),\n",
        "    'e': lambda elf, i: (elf[0] + i, elf[1] + 1),\n",
        "    'w': lambda elf, i: (elf[0] + i, elf[1] - 1),\n",
        "}\n",
        "move_functions = {\n",
        "    'n': lambda elf: (elf[0] - 1, elf[1]),\n",
        "    's': lambda elf: (elf[0] + 1, elf[1]),\n",
        "    'e': lambda elf: (elf[0], elf[1] + 1),\n",
        "    'w': lambda elf: (elf[0], elf[1] - 1)\n",
        "}\n",
        "\n",
        "directions = deque(['n', 's', 'w', 'e'])\n",
        "\n",
        "def round_part_1(directions):\n",
        "  suggested_moves = {}\n",
        "  for i, elf in enumerate(elf_locations):\n",
        "    if not all(check_empty(elf, direction_check_functions.get(d)) for d in directions):\n",
        "      for d in directions:\n",
        "        if check_empty(elf, direction_check_functions.get(d)):\n",
        "          if not suggested_moves.get(elf):\n",
        "            suggested_moves[elf] = move_functions.get(d)(elf)\n",
        "  return suggested_moves\n",
        "\n",
        "def round_part_2(suggested_moves):\n",
        "  move_count = 0\n",
        "  for i, elf in enumerate(elf_locations):\n",
        "    suggestion = suggested_moves.get(elf)\n",
        "    if list(suggested_moves.values()).count(suggestion) == 1:\n",
        "      elf_locations[i] = suggestion\n",
        "      move_count += 1\n",
        "  return move_count\n",
        "    \n",
        "\n",
        "for _ in range(10):\n",
        "  round_part_2(round_part_1(directions))\n",
        "  directions.rotate(-1)\n",
        "\n",
        "# Part 1\n",
        "draw_locations(elf_locations)\n",
        "round = 11\n",
        "\n",
        "while round_part_2(round_part_1(directions)):\n",
        "  directions.rotate(-1)\n",
        "  round += 1\n",
        "  \n",
        "print(round)\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "test_input = '''....#..\n",
        "..###.#\n",
        "#...#.#\n",
        ".#...##\n",
        "#.###..\n",
        "##.#.##\n",
        ".#..#..'''"
      ],
      "metadata": {
        "id": "5YbeOOSnaUNI"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "pi = '''###.#.#.#...###.#.#...#######.#.#...###.#.###.#.#......#.###.###.###..\n",
        ".#..#..#..#####...#.##..##...#..########.#........#.#.#..#..####..###.\n",
        ".####.....#.#.#.#..#..........#..##...#.##.....##..####..##.#..##....#\n",
        "##.#.#.#....#.#..#....#....##.##.#.##..##...#..#.##..##..#...##.##..##\n",
        ".#....#...##.#....#.#.#.###.#.##....#.##.#####.#.####..#.#.#.....#.###\n",
        "#####..##.#.#..#...#..##.####..#..##...#.####..#..###.#....#.#####....\n",
        "...#...##.#..#.#####..#.#..##..#####.#.#.#.###...###.#.###.#..#.#.#...\n",
        ".###.###.##..##....######.#.#..###..#.#..#.#.#.#.#.##..##.###..#.##..#\n",
        ".###.###..#...#.#.....#....####..#.........###...#..##.#..#........#.#\n",
        "#.#.###.####.##..#..#.#####....#####..#........#....#...##..#...#.....\n",
        ".##.##.#..#.####......####.##.#.##...#..#.....##...#....#..##.##.###.#\n",
        ".#..#.#.....###..##.####.##.####.##..#.##....##..#.#.....#..#..#.##.#.\n",
        "##.#.#.##..###.#...###...#...##...###.####..#####.#.##.##.#..#...####.\n",
        "..#.#..##..##.##..#.#..##.#...#....#.#..##.###.#..##..#.##.##..#..#.#.\n",
        "###.##...#.##..##.#.....##.###.#####..##.###.#..#.#.####.##..###.#....\n",
        ".###..###.#..#.....###.###..##.##.##..#.##.#.##....##....##...#..#.#.#\n",
        ".#########.#.#.##.#..##.##.#..#..#.#......###.#..#...##....#.#.#.#..#.\n",
        "..####..#...###.#####.##.#.##.#.##...#######.#.#...#..###.#...#.###...\n",
        "##.#.#...###..##.##.#.####.#.##...###..#....##.######......#.#......#.\n",
        "..##.#.###.###.####....#.#..####.##.#.##.##..#.####....###.##.......#.\n",
        ".###.##...##.#.##..##.#.##....###.#.##.##.#..#.....##..##.##..#...##.#\n",
        "..#.##..#...............###.#..####...#.#.##.##.#.##.....#####.##.##.#\n",
        "##.#######.#.#...####.#.#.##..###..#.#.#.....##.##..###.#..#....#...##\n",
        "#...##.######..#####..####.########.....#.#.#.#.##..##.#...##.#...##.#\n",
        "..##...##.###.#.#.#..####.#.#...#...##..##....#######...##.#...#.###..\n",
        ".##..#..###.##.#.#.###.###..#.##....#.#..##.....#..#.#######...####.#.\n",
        "#.....#........#..####.##.#.#.##....#.######.####....####...##..##.##.\n",
        "#####...#..###.#.#.##..##.#.#..#####.#######.##....#.#.##...####.#.###\n",
        ".....#.##.#.#.#..##..##..#.##.#....#.....#.#.......#..#.##..#....#...#\n",
        "#......#####...###.#.##..#.##.#######..####..#..#...#..#..##..##...#..\n",
        "##...#.##...#..#...#.##...###.#..##.#.###.#.##.#...##..#.....###.#####\n",
        "#.#.#.#..##..#.#.#.....#.#.#####....#..#....##.##..#.#.#...#..###.#...\n",
        "..#######..#...#.##...#.#..#..#...####.#.###.##......####.#..##.#.###.\n",
        "..#..####.##...###.#.#......##....#.##..#.#..#...##..##.....##.#.##.#.\n",
        "..#..###.#.#...##..###...#.###.#..###.#.##.#.###...#.##..###.#.#.#####\n",
        "..#..#.###.#....##.#...##.######..#########.#...#.#.#.#....#..#.#..###\n",
        "#...#.....####.###..###.#...#...##.#...##.###..###.##.#####..#####....\n",
        ".#.#.#..#..#..##.#.......#..##...###....#..##..#...#.##.#.............\n",
        ".#....###...####..#....#.##.##..#####..#..###.#.#...#..##.###..##.###.\n",
        "#..##....###.#.....##...###.#....####.#..##...##.#.##....#...#..##.#..\n",
        "#.##...#.#.......####...#######.....#####.#....###.##..#.###....#....#\n",
        "#....####.#......##...##...####.##...#.#...#...##.........##..#..###.#\n",
        "...####..####..#.####.#.##.##..##..###....#...##.#.##.##.#...##.###..#\n",
        "..#.#...#.#.#..#..##.#####.#..#..##..#..###.##.#.##....##....##.#.#.##\n",
        "...#.###.#......##.....###.#..##.####.#..#.....####...###.##.##...#.#.\n",
        "####...#.##.#.#..##...#.#.##.##.#.###..#...#..#...#..#####.#.#.##.....\n",
        "##...#.#.###.###.####.##..........#.##.##..#.##.#....#...####....#.###\n",
        ".#####.#.##.#.#....##......###..#.....##....#.#.###.#.####...##..##...\n",
        "#..#..#.#...#...####..#...####....#####....###.##......###..#.#####..#\n",
        ".##.#.#####.......#...##...####..#####..#.##.#...##..#.#####.#..###...\n",
        "...#.##.##......##....##....#.###.###....####..#...##...##.#.###....#.\n",
        "#.###.##..####.#.#.#.##....#####.#.....#.#.##..##...#.#####.#...#..##.\n",
        ".###..###..#.####.#.###...#.......#.#..#.#.####..##.....##..###.####..\n",
        "##.###.#.##..#.###...#.#.##..#.##.##.#.#.#...#.#..#..##......#.#..##.#\n",
        ".##.#.#..##..#....#.#..#.###.....#..####......#.#..#.#.#....##.##.#.#.\n",
        "#..##.###...##.#.....#...#......###.#.#..#.#..#.#...##.#.#.###.##.##..\n",
        "##.#.##..###..#.#.#...##........###..######...###..##.##.#.##....#.#..\n",
        "##..#.#.##.#.###..##..#.....#######..#......#.#..#..#####..#.##...#..#\n",
        ".##.#.##.##...#..#...#.##.##...#..#..#.#.##.###..#..#...#.....##..##.#\n",
        ".####.##.######.#######......#.##..#..#..#.#.####.###.##.#.###.#####.#\n",
        "#.#...#.##.##.#.#..###...##..#....#.#.#.....#.#....#.###..#..##.#.#..#\n",
        "#.##..##......#..##..#.###.##.#..#...#.#....#....##..###..###.##...##.\n",
        "###.#....#...##.####.#.######..##.#....#.#.#####.####..#.###......#.#.\n",
        "###.#.....#.#...###.#..#........#.##..#...........##..#.#...#.#.#.....\n",
        "##......#.#...##.#.#..#.##.####..##..###...#####.##.#.#.##.#.###..##..\n",
        ".#.###.###..###..#..##.###.#....####..#.###.#.##.####.##.##.##.#####..\n",
        ".....##...#..#.#.......#.#..#.#.##.#.#..###..##..###.#####.##..#....##\n",
        "..#.####.##....###...##....##.#..######.#.####....##.#...###....#..#.#\n",
        "####...#######.#####..###.###.#...##.#....#..#..#.########.###...#.#.#\n",
        "..###.#..#####..##..#.###....##.#...#..##.#.######.#####.##..####...##'''"
      ],
      "metadata": {
        "id": "bu6v292EaUQC"
      },
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "ZfejiQr3ojVM"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}