2020/Day 05.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary by any other name\n",
    "\n",
    "- https://adventofcode.com/2020/day/5\n",
    "\n",
    "Today's task is to decode binary. The seat ID, with its row and column numbers, is a typical pack-two-values-into-one-binary number scheme, with the number here consisting of 10 digits; the 3 least significant are encoding the column, the other 7 the row. Eric Wastle's description is just reading out the binary number from the most significant bit to the least.\n",
    "\n",
    "In this scheme, the 0's and 1's have been replaced by letters. `F` and `B` for the row number, and `L` and `R` for the column number. If you use the [`str.translate()` function](https://docs.python.org/3/library/stdtypes.html#str.translate) this is trivially returned to base binary notation. Don't worry about separating out the two values again, that's just a [right-shift operation](https://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift) and a [bit mask](https://en.wikipedia.org/wiki/Bitwise_operation#AND).\n",
    "\n",
    "As so often with AoC puzzles, I've used a dataclass for this (I'm rather fond of the module) so I can easily inspect the puzzle results and have a nice representation. It also made it trivially easy to make the objects orderable, to find the max seat id. I've given the implementation a [`__slots__` attribute](https://docs.python.org/3/reference/datamodel.html#slots) almost out of habit, it is very simple immutable data object, and we don't _need_ to store arbitrary additional attributes, so why pay the memory price? And by making the class immutable (`frozen=True`) we get hashability for free, which came in helpful in part 2.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "from typing import Mapping, Tuple\n",
    "\n",
    "_from_pass = str.maketrans(\"FBLR\", \"0101\")\n",
    "_to_row = str.maketrans(\"01\", \"FB\")\n",
    "_to_col = str.maketrans(\"01\", \"LR\")\n",
    "\n",
    "\n",
    "@dataclass(order=True, frozen=True)\n",
    "class SeatId:\n",
    "    __slots__ = (\"id\",)\n",
    "    id: int\n",
    "\n",
    "    @property\n",
    "    def row(self) -> int:\n",
    "        return self.id >> 3\n",
    "\n",
    "    @property\n",
    "    def rowid(self, _tm=_to_row) -> str:\n",
    "        return format(self.row, \"07b\").translate(_tm)\n",
    "\n",
    "    @property\n",
    "    def col(self) -> int:\n",
    "        return self.id & 7\n",
    "\n",
    "    @property\n",
    "    def colid(self, _tm=_to_col) -> str:\n",
    "        return format(self.col, \"03b\").translate(_tm)\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"<SeatID {self.id} {self.rowid}-{self.colid}>\"\n",
    "\n",
    "    @classmethod\n",
    "    def from_boardingpass(cls, pass_: str, _tm=_from_pass) -> \"SeatId\":\n",
    "        return cls(int(pass_.translate(_tm), 2))\n",
    "\n",
    "\n",
    "tests: Mapping[str, Tuple[int, int, int]] = {\n",
    "    \"FBFBBFFRLR\": (44, 5, 357),\n",
    "    \"BFFFBBFRRR\": (70, 7, 567),\n",
    "    \"FFFBBBFRRR\": (14, 7, 119),\n",
    "    \"BBFFBBFRLL\": (102, 4, 820),\n",
    "}\n",
    "for pass_, (row, col, id_) in tests.items():\n",
    "    seatid = SeatId.from_boardingpass(pass_)\n",
    "    assert (seatid.row, seatid.col, seatid.id) == (row, col, id_)\n",
    "\n",
    "assert max(map(SeatId.from_boardingpass, tests)).id == 820"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Sequence\n",
    "\n",
    "import aocd\n",
    "\n",
    "seatids: Sequence[SeatId] = [\n",
    "    SeatId.from_boardingpass(pass_)\n",
    "    for pass_ in aocd.get_data(day=5, year=2020).splitlines()\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 866\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", max(seatids).id)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding your seat\n",
    "\n",
    "Now we get to apply a little logic. From the instructions we know that not all possible row numbers _exist_; the plane is missing row numbers at the front and back, but the plane is also _full_, so we can assume that there is someone sitting in every _existing_ row. So the possible row ids are simply the range from the minimum to the maximum existing row id in the input. We also know we are not sitting in the first nor last row.\n",
    "\n",
    "This is not a large problem; even if there were no seats missing, there are _at most_ 1008 possible candidate seats (8 columns times 126 rows). Since we are looking for a numeric seat id where the ids before and after do exist (and so are occupied), only need to generate all possible seat id numbers (from `min(rowids) << 3 & 7` through to `max(rowids) << 7`), iterate over these with a _sliding window_, and find the one case where a missing seat is flanked by two occupied seats.\n",
    "\n",
    "A sliding window is an iterator from an input iterable, gives you the first `n` elements as a tuple, as the first element it produces. Then the next element it gives you is a tuple with the first element dropped, and another element from the input iterable added to the end. E.g. if your iterator starts with `'foo'`, `'bar'`, `'baz'`, `'spam'`, `'ham'`, then a sliding window with `n` set to `3`, from those inputs would first produce `('foo', 'bar', 'baz')`, then `('bar', 'baz', 'spam')`, and then `('baz', 'spam', 'ham')`. To find our own seat, a sliding window with 3 elements gives us the preceding ID, our possible boarding pass, and the subsequent ID. I built my sliding window using [`itertools.tee()`](https://docs.python.org/3/library/itertools.html#itertools.tee) and [`itertools.islice()`](https://docs.python.org/3/library/itertools.html#itertools.islice); the `tee()` object handles the buffering for us, with only 3 elements the warnings in the documentation about _significant auxiliary storage_ don't apply.\n",
    "\n",
    "Note that we generate IDs for the seat just before the first possible seat, and for the one just after. Say, row 5 is the first possible row, then our seat would have, at minimum, id `(6 * 8) + 0 == 48`. But then the boarding pass with id 47 would have to exist (as well as boarding pass #49), so we generate all numbers starting at `(8 * 6) - 1`. Ditto for the last possible seat; we need not just `(max(rowids) - 1) * 8 + 7`, but want to generate `(max(rowids) * 8 + 0)` too, just so we can iterate with a sliding window that includes that those two ids at the start and end.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import islice, tee\n",
    "\n",
    "\n",
    "def find_empty(seatids: Sequence[SeatId]) -> SeatId:\n",
    "    occupied = set(seatids)\n",
    "    # not the first, and not the last row, but include the seat ids before and after\n",
    "    candidates = map(\n",
    "        SeatId,\n",
    "        range(min(s.row for s in occupied) << 3 & 7, max(s.row for s in occupied) << 3),\n",
    "    )\n",
    "    # sliding window, every 3 seatids, the one before, the candidate seat, and the one after.\n",
    "    windowed = zip(\n",
    "        *(islice(it, start, None) for start, it in enumerate(tee(candidates, 3)))\n",
    "    )\n",
    "    # b, s, a => before, seat, after. Yes, I fell for the lure of the single line expression.\n",
    "    return next(\n",
    "        s for b, s, a in windowed if s not in occupied and len({a, b} & occupied) == 2\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 583\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", find_empty(seatids).id)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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"
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}