2017/Day 20.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import re\n",
    "from collections import defaultdict\n",
    "from dataclasses import dataclass\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Vector:\n",
    "    x: int\n",
    "    y: int\n",
    "    z: int\n",
    "\n",
    "    @property\n",
    "    def distance(self):\n",
    "        return abs(self.x) + abs(self.y) + abs(self.z)\n",
    "\n",
    "\n",
    "def solve_quadratic(p1, p2, v1, v2, a1, a2):\n",
    "    a = (a1 - a2) / 2\n",
    "    b = (v1 - v2) + a\n",
    "    c = p1 - p2\n",
    "    discriminant = (b**2) - (4 * a * c)\n",
    "    if discriminant < 0:\n",
    "        # no solutions\n",
    "        return ()\n",
    "    if discriminant == 0:\n",
    "        return ((-b / (2 * a)),)\n",
    "    return (\n",
    "        (-b + math.sqrt(discriminant)) / (2 * a),\n",
    "        (-b - math.sqrt(discriminant)) / (2 * a),\n",
    "    )\n",
    "\n",
    "\n",
    "def solve_linear(p1, p2, v1, v2):\n",
    "    return (p2 - p1) / (v1 - v2)\n",
    "\n",
    "\n",
    "def solve(p1, p2, v1, v2, a1, a2):\n",
    "    \"\"\"Find the positive integer points in time where P1 and P2 intersect\n",
    "\n",
    "    Returns a set with points in time.\n",
    "\n",
    "    \"\"\"\n",
    "    if a1 == a2:\n",
    "        ts = (solve_linear(p1, p2, v1, v2),)\n",
    "    else:\n",
    "        ts = solve_quadratic(p1, p2, v1, v2, a1, a2)\n",
    "    return {int(round(t)) for t in ts if t > 0 and math.isclose(t, round(t))}\n",
    "\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Particle:\n",
    "    id: int\n",
    "    p: Vector\n",
    "    v: Vector\n",
    "    a: Vector\n",
    "\n",
    "    @classmethod\n",
    "    def from_line(cls, idx, line, _d=re.compile(r\"-?\\d+\")):\n",
    "        px, py, pz, vx, vy, vz, ax, ay, az = map(int, _d.findall(line))\n",
    "        return cls(idx, Vector(px, py, pz), Vector(vx, vy, vz), Vector(ax, ay, az))\n",
    "\n",
    "    def __and__(self, other):\n",
    "        # find if two particles will collide in a future point in time\n",
    "        solutions = None\n",
    "        for c in \"xyz\":\n",
    "            p1, p2, v1, v2, a1, a2 = (\n",
    "                getattr(getattr(ob, v), c) for v in \"pva\" for ob in (self, other)\n",
    "            )\n",
    "            if a1 == a2 and v1 == v2:\n",
    "                # parallel paths, always matching if starting position is equal\n",
    "                if p1 == p2:\n",
    "                    continue\n",
    "                # positions not equal, will never cross\n",
    "                return False, None\n",
    "            if solutions is None:\n",
    "                solutions = solve(p1, p2, v1, v2, a1, a2)\n",
    "            else:\n",
    "                solutions &= solve(p1, p2, v1, v2, a1, a2)\n",
    "            if not solutions:\n",
    "                return False, None\n",
    "        return True, min(solutions)\n",
    "\n",
    "\n",
    "def read_particles(lines):\n",
    "    return [Particle.from_line(i, line) for i, line in enumerate(lines)]\n",
    "\n",
    "\n",
    "def find_closest(particles):\n",
    "    # Assumption: the lowest absolute acceleration and velocity will win\n",
    "    return min(particles, key=lambda p: (p.a.distance, p.v.distance, p.p.distance))\n",
    "\n",
    "\n",
    "def eliminate_collisions(particles):\n",
    "    collisions = defaultdict(set)\n",
    "    for p1, p2 in combinations(particles, 2):\n",
    "        collide, time = p1 & p2\n",
    "        if not collide:\n",
    "            continue\n",
    "        collisions[time] |= {p1, p2}\n",
    "\n",
    "    eliminated = None\n",
    "    for _, collided in sorted(collisions.items()):\n",
    "        if not eliminated:\n",
    "            eliminated = set(collided)\n",
    "        else:\n",
    "            for p1, p2 in combinations(collided - eliminated, 2):\n",
    "                if (p1 & p2)[0]:\n",
    "                    eliminated |= {p1, p2}\n",
    "    return len(particles) - len(eliminated)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_particles = read_particles(\n",
    "    \"\"\"\\\n",
    "p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>\n",
    "p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>\n",
    "\"\"\".splitlines()\n",
    ")\n",
    "assert find_closest(test_particles).id == 0\n",
    "\n",
    "test_particles = read_particles(\n",
    "    \"\"\"\\\n",
    "p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>\n",
    "p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>\n",
    "p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>\n",
    "p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>\n",
    "\"\"\".splitlines()\n",
    ")\n",
    "assert eliminate_collisions(test_particles) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "data = aocd.get_data(day=20, year=2017)\n",
    "particles = read_particles(data.splitlines())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 170\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", find_closest(particles).id)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# underlying math\n",
    "\n",
    "For particles $P_1$ and $P_2$ (given position $p$, velocity $v$ and acceleration $a$, they will intersect when:\n",
    "\n",
    "$\\left( \\frac{a_1 - a_2}{2} \\right)t^2 + \\left( v_1 - v_2 + \\left( \\frac{a_1 - a_2}{2} \\right) \\right)t + \\left(p_1 - p_2\\right) = 0$\n",
    "\n",
    "So we can calculate the 0, 1 or 2 solutions using quadratic equations, but only for _positive values of_ $t$:\n",
    "\n",
    "$a = \\frac{a_1 - a_2}{2}$\n",
    "\n",
    "$b = v_1 - v_2 + \\left( \\frac{a_1 - a_2}{2} \\right)$\n",
    "\n",
    "$c = p_1 - p_2$\n",
    "\n",
    "and\n",
    "\n",
    "$t = \\frac{-b \\pm  \\sqrt{b^2 - 4ac} }{2a}$\n",
    "\n",
    "There are 0 solutions if $b^2 - 4ac$ is smaller than 0, 1 solution if equal to 0, and 2 solutions if greater than 0. We only care about the smallest whole positive number solution (as $t$ moves forward from 0 and moves in whole integer steps).\n",
    "\n",
    "We need to find $t$ for all 3 vector components, and only if they all match, will particles collide.\n",
    "\n",
    "If acceleration is 0 for both particles, then it's a linear equation:\n",
    "\n",
    "$t = (p_2 - p_1) / (v_1 - v_2)$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 571\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", eliminate_collisions(particles))"
   ]
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}