15.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "import numpy as np\n",
    "from dataclasses import dataclass\n",
    "import re\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "@dataclass\n",
    "class point:\n",
    "    x : int\n",
    "    y : int\n",
    "\n",
    "    @property\n",
    "    def diagonal(self):\n",
    "        return self.x+self.y\n",
    "\n",
    "    @property\n",
    "    def offset(self):\n",
    "        return self.y-self.x\n",
    "\n",
    "    @classmethod\n",
    "    def from_do(cls, diagonal, offset):\n",
    "        x = ((diagonal - offset)/2)\n",
    "        y = ((diagonal + offset)/2)\n",
    "        pt = cls(x,y)\n",
    "        assert(pt.offset == offset) and (pt.diagonal == diagonal)\n",
    "        return pt\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash((self.x, self.y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "@dataclass\n",
    "class interval:\n",
    "    c1 : int\n",
    "    c2 : int\n",
    "\n",
    "    @property\n",
    "    def non_negative(self) -> bool :\n",
    "        return (self.c2 >= self.c1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_interval(s : point, b : point, y : int):\n",
    "    size = abs(s.x - b.x) + abs(s.y- b.y)\n",
    "    length = size - abs(s.y - y)\n",
    "    return interval(s.x-length, s.x+length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [],
   "source": [
    "allowed = '0123456789-'\n",
    "def parse_line(line):\n",
    "\n",
    "    sx,sy,bx,by = map(int,(''.join([l if l in allowed else ' ' for l in line])).split())\n",
    "    return point(sx,sy), point(bx,by)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read(prefix='data'):\n",
    "    lines = Path(f'{prefix}/15.txt').read_text().rstrip().split('\\n')\n",
    "    return [parse_line(line) for line in lines]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [],
   "source": [
    "def row_length(lines, y, display=False):\n",
    "    S = set()\n",
    "    for (s,b) in lines:\n",
    "        ivl = to_interval(s,b, y)\n",
    "        if ivl.non_negative:\n",
    "            for x in range(ivl.c1, ivl.c2+1, 1):\n",
    "                S.add(x)\n",
    "\n",
    "    for (_,b) in lines:\n",
    "        if b.y == y:\n",
    "            if b.x in S:\n",
    "                S.remove(b.x)\n",
    "\n",
    "    return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [],
   "source": [
    "def show(S):\n",
    "    return len(S), ''.join(['#' if i in S else '.' for i in range(min(S), len(S)-min(S))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(26, '####.######################...')"
      ]
     },
     "execution_count": 226,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test = read('test')\n",
    "show(row_length(test, y=10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5461729"
      ]
     },
     "execution_count": 227,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lines = read()\n",
    "len(row_length(lines, y=2000000))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {},
   "outputs": [],
   "source": [
    "@dataclass\n",
    "class Dline:\n",
    "    x : int\n",
    "    y : int\n",
    "    length : int\n",
    "\n",
    "    def __iter__(self):\n",
    "        for i in range(self.length):\n",
    "            yield point(self.x + i, self.y - i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[point(x=1, y=2), point(x=2, y=1), point(x=3, y=0)]"
      ]
     },
     "execution_count": 229,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x for x in Dline(1,2,3)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [],
   "source": [
    "@dataclass\n",
    "class Diamond:\n",
    "    x : int\n",
    "    y : int\n",
    "    size : int\n",
    "\n",
    "    @classmethod\n",
    "    def from_sensorbeacon(cls,s,b):\n",
    "        size = abs(s.x - b.x) + abs(s.y- b.y)\n",
    "        return cls(s.x,s.y, size)\n",
    "\n",
    "    @property\n",
    "    def top(self):\n",
    "        return point(self.x, self.y - self.size)\n",
    "\n",
    "    @property\n",
    "    def bottom(self):\n",
    "        return point(self.x, self.y + self.size)\n",
    "\n",
    "    @property\n",
    "    def left(self):\n",
    "        return point(self.x - self.size, self.y)\n",
    "\n",
    "    @property\n",
    "    def right(self):\n",
    "        return point(self.x + self.size, self.y)\n",
    "\n",
    "    @property\n",
    "    def corners(self):\n",
    "        return (self.top, self.bottom, self.left, self.right)\n",
    "\n",
    "    def contains(self, pt : point):\n",
    "        dist = abs(self.x - pt.x) + abs(self.y - pt.y)\n",
    "        return dist <= self.size\n",
    "\n",
    "    def line_on(self, diagonal):\n",
    "        if (self.bottom.diagonal < diagonal) or (self.left.diagonal > diagonal):\n",
    "            return Dline(0,0,0)\n",
    "        offset = diagonal - self.left.diagonal\n",
    "        x = self.left.x + math.ceil(offset/2)\n",
    "        y = self.left.y + math.floor(offset/2)\n",
    "        size = self.size if offset %2 else self.size + 1\n",
    "        return Dline(x, y, size)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw(d, size=(21,21)):\n",
    "    A = np.full(size, '.')\n",
    "    for l in range(A.shape[0] + A.shape[1]):\n",
    "        for p in d.line_on(l):\n",
    "            A[p.x, p.y] = str(l % 10)\n",
    "    A[d.x, d.y] = 'S'\n",
    "    A[d.left.x, d.left.y] = 'L'\n",
    "    A[d.top.x, d.top.y] = 'T'\n",
    "    A[d.bottom.x, d.bottom.y] = 'B'\n",
    "    A[d.right.x, d.right.y] = 'R'\n",
    "    print(*[''.join(r) for r in A.T], sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".....................\n",
      ".....................\n",
      "..........T..........\n",
      ".........234.........\n",
      "........23456........\n",
      ".......2345678.......\n",
      "......234567890......\n",
      ".....23456789012.....\n",
      "....2345678901234....\n",
      "...234567890123456...\n",
      "..L3456789S1234567R..\n",
      "...456789012345678...\n",
      "....6789012345678....\n",
      ".....89012345678.....\n",
      "......012345678......\n",
      ".......2345678.......\n",
      "........45678........\n",
      ".........678.........\n",
      "..........B..........\n",
      ".....................\n",
      ".....................\n"
     ]
    }
   ],
   "source": [
    "d = Diamond(10,10,8)\n",
    "draw(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_changepoints(diamonds):\n",
    "    return sorted({d.bottom.diagonal+1 for d in diamonds})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_in(lines, mx=1000):\n",
    "    diamonds = [Diamond.from_sensorbeacon(s,b) for (s,b) in lines]\n",
    "    changepoints = get_changepoints(diamonds)\n",
    "\n",
    "    holes = set()\n",
    "    for diag in changepoints:\n",
    "        sd = [diamond.line_on(diag) for diamond in diamonds]\n",
    "        sd = [d for d in sd if d.length > 0]\n",
    "        sd = sorted(sd, key=lambda d: d.x)\n",
    "\n",
    "        if len(sd) > 0:\n",
    "            xe = sd[0].x + sd[0].length\n",
    "            for dl in sd:\n",
    "                if dl.x > xe:\n",
    "                    holes.add((xe, diag -xe))\n",
    "                xe = max(dl.x + dl.length, xe)\n",
    "             \n",
    "    return holes.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14 11\n",
      "56000011\n"
     ]
    }
   ],
   "source": [
    "(x,y) = find_in(read('test'), mx=20)\n",
    "print(x,y)\n",
    "print(int(x*4000000 + y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2655411, 3166538)\n",
      "10621647166538\n"
     ]
    }
   ],
   "source": [
    "(x,y) = find_in(lines, mx=4000000)\n",
    "print((x,y))\n",
    "print(int(x*4000000 + y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def find_in_two(lines, mx=1000):\n",
    "    diamonds = [Diamond.from_sensorbeacon(s,b) for (s,b) in lines]\n",
    "    ch = {pt for d in diamonds for pt in d.corners}\n",
    "\n",
    "    for p1 in list(ch):\n",
    "        for p2 in list(ch): \n",
    "            ch.add(point.from_do(p1.diagonal, p2.offset))\n",
    "            ch.add(point.from_do(p2.diagonal, p1.offset))\n",
    "\n",
    "    for pt in list(ch):\n",
    "        for dx in [-1,0,1]:\n",
    "            for dy in [-1,0,1]:\n",
    "                ch.add(point(pt.x+dx, pt.y+dy))\n",
    "\n",
    "\n",
    "\n",
    "    for pt in ch:\n",
    "        if not any(dia.contains(pt) for dia in diamonds):\n",
    "            if pt.x >= 0 and pt.y >= 0 and pt.x <= mx and pt.y <= mx:\n",
    "                return pt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 265,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "point(x=14.0, y=11.0)\n",
      "56000011\n"
     ]
    }
   ],
   "source": [
    "pt = find_in_two(read('test'), mx=20)\n",
    "print(pt)\n",
    "print(int(pt.x*4000000 + pt.y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "point(x=2655411.0, y=3166538.0)\n",
      "10621647166538\n"
     ]
    }
   ],
   "source": [
    "pt = find_in_two(read(), mx=4000000)\n",
    "print(pt)\n",
    "print(int(pt.x*4000000 + pt.y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.11.0 64-bit",
   "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.0"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "949777d72b0d2535278d3dc13498b2535136f6dfe0678499012e853ee9abcab1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}