Notebooks/day-15.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a2e8b6df-ab8f-4c85-a069-2a08db7b0917",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = open('../inputs/day-15').read().splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "497c7129-d753-44e0-996e-8d25a3f91e13",
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "399fca00-0554-4c6e-b761-105adab26a5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "loc = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "532b153d-2bda-4e08-a511-e2d4d14b8091",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dist(p1, p2):\n",
    "    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "3fd30d8a-8727-4d5d-ba4e-2d61ea35bf6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "for l in data:\n",
    "    sx, sy, bx, by = list(map(int, re.match(\".* x=(\\S+), y=(\\S+):.* x=(\\S+), y=(\\S+)\", l).groups([1,2,3,4])))\n",
    "    loc[(sx,sy)] = (bx,by)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "1baf1d1d-6524-4981-b84b-a09e0928fe71",
   "metadata": {},
   "outputs": [],
   "source": [
    "distances = {}\n",
    "for s, b in loc.items():\n",
    "    distances[s] = dist(s,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "da25b923-1030-4b53-ae4e-0bcd05d2c9ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "y_q = 2_000_000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "32d1ea25-3b4a-4e64-b2ea-2cd5f5ee755d",
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "f6908cbe-1438-4440-ba25-cb7188b2adf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_sensor(s, L):\n",
    "    val = L - abs(s[1] - y_q)\n",
    "    if val > 0:\n",
    "        ans.update(range(s[0] - val, s[0] + val + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "d8277a3a-bdc2-4270-9b80-e3a37bdf7322",
   "metadata": {},
   "outputs": [],
   "source": [
    "for s, L in distances.items():\n",
    "    solve_sensor(s, L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d55ddba-e030-4197-ade6-04b286a81c47",
   "metadata": {},
   "source": [
    "Need to remove the sensors and beacons locations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "a060ed74-a349-4889-a2e2-b7ad8921d982",
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = ans.difference([s[0] for s in loc.keys() if s[1] == y_q])\n",
    "ans = ans.difference([s[0] for s in loc.values() if s[1] == y_q])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "28d9bf9b-1fd2-4e34-8382-158e297ceb65",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5688618"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a9d3b98-ca90-4a0b-bfd5-a009ab48f11e",
   "metadata": {},
   "source": [
    "## Find the location"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e89d72c-604b-43bc-9f11-efa366365b3b",
   "metadata": {},
   "source": [
    "The idea is that the only empty location is at the immediate perimeter of the clusters, the L+1 shell, if you like. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "5ba9b6ea-bd67-4e1b-a1cb-ff2ad35c666d",
   "metadata": {},
   "outputs": [],
   "source": [
    "limit = 4_000_000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "9261e703-d2a4-4ce0-8e08-f38bd93e1157",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_perim(s, L):\n",
    "    ans = set()\n",
    "    sx, sy = s\n",
    "    py = sy + L + 1\n",
    "    px = sx\n",
    "    for _ in range(L + 1):\n",
    "        if 0 <= px <= limit and 0 <= py <= limit:\n",
    "            ans.add((px,py))\n",
    "        px += 1\n",
    "        py -= 1\n",
    "    for _ in range(L + 1):\n",
    "        if 0 <= px <= limit and 0 <= py <= limit:\n",
    "            ans.add((px,py))\n",
    "        px -= 1\n",
    "        py -= 1\n",
    "    for _ in range(L + 1):\n",
    "        if 0 <= px <= limit and 0 <= py <= limit:\n",
    "            ans.add((px,py))\n",
    "        px -= 1\n",
    "        py += 1\n",
    "    for _ in range(L + 1):\n",
    "        if 0 <= px <= limit and 0 <= py <= limit:\n",
    "            ans.add((px,py))\n",
    "        px += 1\n",
    "        py += 1\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9714151-8329-49cb-9e1e-c182992349a2",
   "metadata": {},
   "source": [
    "This empty location lies in the intersection of at least some of the other perimeters (or it's in the corner, which isn't interesting)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "3f389363-a784-4013-957e-46844af10071",
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = set()\n",
    "shared = set()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08c9fe9f-0825-43e8-80c0-342f56cd8199",
   "metadata": {},
   "source": [
    "This takes about 1 minute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "5fbb0232-26df-4052-a365-8784cf2eecaf",
   "metadata": {},
   "outputs": [],
   "source": [
    "for s,L in distances.items():\n",
    "    per = get_perim(s, L)\n",
    "    shared.update(per.intersection(ans))\n",
    "    ans.update(per)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "0ad5b0c5-4126-40bc-89e3-e22f68f82132",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1154346"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(shared)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c90504c9-f300-45c9-9fd9-7ec4909f9d64",
   "metadata": {},
   "source": [
    "There are 1M such points, so we need to check manually who is the only point which is not any cluster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "47f3d10e-5682-4902-9e8d-9b6434f4394c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_p(p):\n",
    "    for s, L in distances.items():\n",
    "        if dist(p, s) <= L:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "ba6c6192-893e-4e63-bcf2-833335660ef7",
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "a3e9e728-9862-4b5b-856d-eb2ddce4208e",
   "metadata": {},
   "outputs": [],
   "source": [
    "for p in shared:\n",
    "    if test_p(p):\n",
    "        ans = p\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "59e0556b-b6c9-4939-86cb-c82d8da3d388",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12625383204261"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4000000 * ans[0] + ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3895082-7c46-4e15-9b16-8aa5fb9e9349",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}