gistfile1.txt

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from numpy import *\n",
    "import matplotlib\n",
    "from matplotlib import pyplot as plt\n",
    "from tqdm.auto import tqdm\n",
    "import requests\n",
    "import pickle\n",
    "import re\n",
    "import itertools\n",
    "import functools\n",
    "import collections\n",
    "import string\n",
    "import time\n",
    "from bs4 import BeautifulSoup\n",
    "from sortedcontainers import SortedList # http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedlist\n",
    "\n",
    "import multiprocess\n",
    "# with multiprocess.Pool(processes=8) as pool:\n",
    "#   for i in pool.imap_unordered(f, a):\n",
    "#     print(i)\n",
    "\n",
    "from adventlib.common import *\n",
    "# n, m, a = lines_as_matrix_nm(lines)\n",
    "# a = lines_as_matrix(lines)\n",
    "# a = lines_as_digit_matrix(lines)\n",
    "# chunks = split_iter_by_start_indices(a, indices)\n",
    "# chunks = split_iter_by_bools(a, bools)\n",
    "\n",
    "from adventlib.point_2d import *\n",
    "# from adventlib.point_3d import *\n",
    "\n",
    "YEAR = 2023\n",
    "DAY = int('18')\n",
    "\n",
    "submit1, submit2 = generate_submits(YEAR, DAY)\n",
    "\n",
    "while True:\n",
    "  try:\n",
    "    raw_input = get_input(YEAR, DAY)\n",
    "    break\n",
    "  except Exception as e:\n",
    "    print(e)\n",
    "    time.sleep(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines, groups = linesplit(\"\"\"\n",
    "R 6 (#70c710)\n",
    "D 5 (#0dc571)\n",
    "L 2 (#5713f0)\n",
    "D 2 (#d2c081)\n",
    "R 2 (#59c680)\n",
    "D 2 (#411b91)\n",
    "L 5 (#8ceee2)\n",
    "U 2 (#caa173)\n",
    "L 1 (#1b58a2)\n",
    "U 2 (#caa171)\n",
    "R 2 (#7807d2)\n",
    "U 3 (#a77fa3)\n",
    "L 2 (#015232)\n",
    "U 2 (#7a21e3)\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "678 lines\n",
      "1 groups\n",
      ">>>\n",
      "R 6 (#0e4c90)\n",
      "U 2 (#5b83a3)\n",
      "R 7 (#1a3a90)\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "lines, groups = linesplit(raw_input, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "a = []\n",
    "s = set()\n",
    "d = collections.defaultdict()\n",
    "\n",
    "dirs = [\n",
    "  Point(0, 1),\n",
    "  Point(1, 0),\n",
    "  Point(0, -1),\n",
    "  Point(-1, 0),\n",
    "]\n",
    "\n",
    "letter_to_dir_i = {\n",
    "  'R': 1,\n",
    "  'D': 2,\n",
    "  'L': 3,\n",
    "  'U': 0,\n",
    "}\n",
    "\n",
    "points = set()\n",
    "loc = Point(0, 0)\n",
    "\n",
    "for line in lines:\n",
    "  if m := re.findall(r'^(\\w) (\\d+) \\(#(.*)\\)', line):\n",
    "    letter, steps_s, color_s = m[0]\n",
    "    dir_i = letter_to_dir_i[letter]\n",
    "    steps = int(steps_s)\n",
    "    color = (\n",
    "      int(color_s[0:2], 16),\n",
    "      int(color_s[2:4], 16),\n",
    "      int(color_s[4:6], 16),\n",
    "    )\n",
    "    \n",
    "    points.add(loc)\n",
    "    for i in range(steps):\n",
    "      loc += dirs[dir_i]\n",
    "      points.add(loc)\n",
    "  else:\n",
    "    raise Exception()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "pmin, pmax = amap(Point.t, points).min(axis=0), amap(Point.t, points).max(axis=0)\n",
    "pmin, pmax = amap(lambda x: Point(*x), [pmin, pmax])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "pmin -= Point(1, 1)\n",
    "pmax += Point(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = pmax.x - pmin.x + 1\n",
    "m = pmax.y - pmin.y + 1\n",
    "\n",
    "a = np.zeros((n, m), dtype='<U1')\n",
    "a.fill(' ')\n",
    "\n",
    "for i in points:\n",
    "  a[i.x - pmin.x, i.y - pmin.y] = '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "            \n",
      "   ###  ### \n",
      " ### #  # # \n",
      " #   #### # \n",
      " #        # \n",
      " # ###    # \n",
      " # # #    # \n",
      " ### ###### \n",
      "            \n"
     ]
    }
   ],
   "source": [
    "for i in range(n):\n",
    "  for j in range(m):\n",
    "    print(a[i, j], end='')\n",
    "  print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "visited = set([pmin])\n",
    "q = collections.deque([pmin])\n",
    "\n",
    "while q:\n",
    "  p = q.popleft()\n",
    "  \n",
    "  for i in dirs:\n",
    "    pp = p + i\n",
    "    if pp in visited or pp in points:\n",
    "      continue\n",
    "    if pp.within_bounds_incl(pmin, pmax):\n",
    "      visited.add(pp)\n",
    "      q.append(pp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36807"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n * m - len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Submitting 36807...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "submit1(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "a = []\n",
    "s = set()\n",
    "d = collections.defaultdict()\n",
    "\n",
    "dirs = [\n",
    "  Point(0, 1),\n",
    "  Point(1, 0),\n",
    "  Point(0, -1),\n",
    "  Point(-1, 0),\n",
    "]\n",
    "\n",
    "letter_to_dir_i = {\n",
    "  'R': 1,\n",
    "  'D': 2,\n",
    "  'L': 3,\n",
    "  'U': 0,\n",
    "}\n",
    "\n",
    "cruxes = set()\n",
    "loc = Point(0, 0)\n",
    "instructions = []\n",
    "\n",
    "for line in lines:\n",
    "  if m := re.findall(r'^(\\w) (\\d+) \\(#(.*)\\)', line):\n",
    "    letter, steps_s, color_s = m[0]\n",
    "    dir_i = letter_to_dir_i[letter]\n",
    "    steps = int(steps_s)\n",
    "    color = (\n",
    "      int(color_s[0:2], 16),\n",
    "      int(color_s[2:4], 16),\n",
    "      int(color_s[4:6], 16),\n",
    "    )\n",
    "    \n",
    "    steps = int(color_s[0:5], 16)\n",
    "    letter = {\n",
    "      '0': 'R',\n",
    "      '1': 'D',\n",
    "      '2': 'L',\n",
    "      '3': 'U',\n",
    "    }[color_s[5]]\n",
    "    dir_i = letter_to_dir_i[letter]\n",
    "    \n",
    "    cruxes.add(loc)\n",
    "    instructions.append((\n",
    "      loc,\n",
    "      dirs[dir_i],\n",
    "      steps,\n",
    "    ))\n",
    "    loc += dirs[dir_i] * steps\n",
    "    cruxes.add(loc)\n",
    "  else:\n",
    "    raise Exception()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "unique_xs = sorted(list(set(amap(Point.a, cruxes)[:, 0])))\n",
    "unique_ys = sorted(list(set(amap(Point.a, cruxes)[:, 1])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = len(unique_xs) * 2 + 1\n",
    "m = len(unique_ys) * 2 + 1\n",
    "\n",
    "base_x = np.zeros(n, dtype=int)\n",
    "base_x[1:n:2] = unique_xs\n",
    "base_x[2:n:2] = base_x[1:n:2] + 1\n",
    "base_x[0] = base_x[1] - 1\n",
    "\n",
    "len_x = np.zeros(n, dtype=int)\n",
    "len_x[0:n-1] = base_x[1:] - base_x[:n-1]\n",
    "len_x[-1] = 1\n",
    "\n",
    "\n",
    "base_y = np.zeros(m, dtype=int)\n",
    "base_y[1:m:2] = unique_ys\n",
    "base_y[2:m:2] = base_y[1:m:2] + 1\n",
    "base_y[0] = base_y[1] - 1\n",
    "\n",
    "len_y = np.zeros(m, dtype=int)\n",
    "len_y[0:m-1] = base_y[1:] - base_y[:m-1]\n",
    "len_y[-1] = 1\n",
    "\n",
    "x_to_i = {j: i for i, j in enumerate(base_x)}\n",
    "y_to_i = {j: i for i, j in enumerate(base_y)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_points = set()\n",
    "\n",
    "for i in range(n):\n",
    "  for j in range(m):\n",
    "    all_points.add(Point(i, j))\n",
    "    \n",
    "border = set()\n",
    "visited = set()\n",
    "\n",
    "for start, direction, steps in instructions:\n",
    "  end = start + direction * steps\n",
    "  \n",
    "  x1 = x_to_i[start.x]\n",
    "  y1 = y_to_i[start.y]\n",
    "  x2 = x_to_i[end.x]\n",
    "  y2 = y_to_i[end.y]\n",
    "  \n",
    "  # print(x1, y1, x2, y2)\n",
    "  \n",
    "  # print(start, '->', end)\n",
    "  \n",
    "  x1, x2 = sorted([x1, x2])\n",
    "  y1, y2 = sorted([y1, y2])\n",
    "  \n",
    "  for i in range(x1, x2 + 1):\n",
    "    for j in range(y1, y2 + 1):\n",
    "      border.add(Point(i, j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[+0, +0]"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pmin = min(all_points)\n",
    "pmin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "visited = set([pmin])\n",
    "q = collections.deque([pmin])\n",
    "\n",
    "while q:\n",
    "  p = q.popleft()\n",
    "  \n",
    "  for i in dirs:\n",
    "    pp = p + i\n",
    "    if pp in visited or pp in border or pp not in all_points:\n",
    "      continue\n",
    "    visited.add(pp)\n",
    "    q.append(pp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [],
   "source": [
    "interesting = all_points - visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48797603984357"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = 0\n",
    "for i in sorted(interesting):\n",
    "  area = len_x[i.x] * len_y[i.y]\n",
    "  # print(f'{base_x[i.x]:20d}, {base_y[i.y]:20d}, {area:20d}')\n",
    "  result += area\n",
    "result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Submitting 48797603984357...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "submit2(_)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}