2020/Day 14.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 14 - Bit masking operations\n",
    "\n",
    "- https://adventofcode.com/2020/day/14\n",
    "\n",
    "All we need to do is generate _two_ bitmasks per input mask:\n",
    "\n",
    "- A mask to _set_ bits, using bit-wise OR (`number | bitmask`); any `1` in the bitmask sets that bit in the output.\n",
    "- A mask to _clear_ bits, using bit-wise AND (`number & bitmask`); any `0` in the bitmask clears that bit.\n",
    "\n",
    "The masks can be generated trivially; just replace the `\"X\"`s with `\"0\"` or `\"1\"` respectively, then convert the string as a binary value to an integer; the example `XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X` input makes a set mask when transformed to `int(\"000000000000000000000000000001000000\", 2)`, and a clear mask when transformed to `int(\"111111111111111111111111111111111101\", 2)`.\n",
    "\n",
    "Memory is just a `defaultdict(int)` object.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "from collections import defaultdict\n",
    "from dataclasses import dataclass\n",
    "from typing import Any\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Mask:\n",
    "    set_mask: int = 0\n",
    "    clear_mask: int = (2**36) - 1\n",
    "\n",
    "    def __rand__(self, other: Any) -> int:\n",
    "        if not isinstance(other, int):\n",
    "            return NotImplemented\n",
    "        return other & self.clear_mask | self.set_mask\n",
    "\n",
    "    @classmethod\n",
    "    def from_mask(cls, mask: str) -> \"Mask\":\n",
    "        return cls(\n",
    "            int(mask.translate({88: 48}), 2),  # X -> 0\n",
    "            int(mask.translate({88: 49}), 2),  # X -> 1\n",
    "        )\n",
    "\n",
    "\n",
    "_instr = re.compile(\n",
    "    r\"\"\"\n",
    "  ^(?:\n",
    "    mem\\[(?P<addr>\\d+)\\]\\s*=\\s*(?P<val>\\d+)\n",
    "  | mask\\s*=\\s*(?P<mask>[01X]+)\n",
    "  )$\n",
    "\"\"\",\n",
    "    flags=re.VERBOSE,\n",
    ").search\n",
    "\n",
    "\n",
    "def initialize_program(lines: list[str], _parse=_instr) -> int:\n",
    "    mem = defaultdict(int)\n",
    "    mask = Mask()\n",
    "    for match in map(_parse, lines):\n",
    "        if mval := match[\"mask\"]:\n",
    "            mask = Mask.from_mask(mval)\n",
    "        else:\n",
    "            mem[int(match[\"addr\"])] = int(match[\"val\"]) & mask\n",
    "    return sum(mem.values())\n",
    "\n",
    "\n",
    "assert (\n",
    "    initialize_program(\n",
    "        \"\"\"\\\n",
    "mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X\n",
    "mem[8] = 11\n",
    "mem[7] = 101\n",
    "mem[8] = 0\n",
    "\"\"\".splitlines()\n",
    "    )\n",
    "    == 165\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "lines = aocd.get_data(day=14, year=2020).splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 11501064782628\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", initialize_program(lines))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2 - generating addresses\n",
    "\n",
    "At first I wondered if there might be a method of eliminating addresses from the input, as I was worried about the size of the address space. But looking at my input, the masks never have more than 9 Xs, so up to 512 potential addresses to generate per mask. That's easy enough to brute-force.\n",
    "\n",
    "To generate the floating masks, we need to _clear_ the bits at the `X` positions, then provide alternative values for these for all possible bit combinations. We can take the `X` positions to produce a series of `(0, 1 << bitpos)` tuples as input to `product()`, we can then use their combination as an additional OR mask.\n",
    "\n",
    "E.g. `000000000000000000000000000000X1001X` becomes a set mask (`000000000000000000000000000000010010`), and the Xs are mapped to `1 << 5` and `1 << 1` and each paired with `0`, so we can generate `(0, 0)`, `(0, 1 << 1)`, `(1 << 5, 0)` and `(1 << 5, 1 << 1)`, generating the 4 masks needed to produce the floating addresses.\n",
    "\n",
    "I opted to generate `Mask` instances; you can generate all possible addresses by applying the `Mask` instances that iteration over a `FloatingMask` produces:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections.abc import Iterable, Iterator\n",
    "from functools import reduce\n",
    "from itertools import product\n",
    "from operator import or_\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class FloatingMask:\n",
    "    set_mask: int = 0\n",
    "    clear_mask: int = (2**36) - 1\n",
    "    address_bits: Iterable[int] = ()\n",
    "\n",
    "    def __rand__(self, other: Any) -> int:\n",
    "        if not isinstance(other, int):\n",
    "            return NotImplemented\n",
    "        return other & self.clear_mask | self.set_mask\n",
    "\n",
    "    def __iter__(self) -> Iterator[Mask]:\n",
    "        for combo in product(*([0, a] for a in self.address_bits)):\n",
    "            yield Mask(reduce(or_, combo, self.set_mask), self.clear_mask)\n",
    "\n",
    "    @classmethod\n",
    "    def from_mask(cls, mask: str) -> \"Mask\":\n",
    "        return cls(\n",
    "            int(mask.translate({88: 48}), 2),  # X -> 0\n",
    "            int(mask.translate({48: 49, 88: 48}), 2),  # 0 -> 1, X -> 0\n",
    "            [1 << (35 - i) for i, c in enumerate(mask) if c == \"X\"],\n",
    "        )\n",
    "\n",
    "\n",
    "def apply_memory_address_decoder_program(lines: list[str], _parse=_instr) -> int:\n",
    "    mem = defaultdict(int)\n",
    "    fmask = FloatingMask()\n",
    "    for match in map(_parse, lines):\n",
    "        if mval := match[\"mask\"]:\n",
    "            fmask = FloatingMask.from_mask(mval)\n",
    "        else:\n",
    "            addr, val = map(int, (match[\"addr\"], match[\"val\"]))\n",
    "            mem |= {addr & mask: val for mask in fmask}\n",
    "    return sum(mem.values())\n",
    "\n",
    "\n",
    "assert (\n",
    "    apply_memory_address_decoder_program(\n",
    "        \"\"\"\\\n",
    "mask = 000000000000000000000000000000X1001X\n",
    "mem[42] = 100\n",
    "mask = 00000000000000000000000000000000X0XX\n",
    "mem[26] = 1\n",
    "\"\"\".splitlines()\n",
    "    )\n",
    "    == 208\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 5142195937660\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", apply_memory_address_decoder_program(lines))"
   ]
  }
 ],
 "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"
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}