21.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "from functools import cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 245,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LookUp:\n",
    "    def __init__(self, D : dict):\n",
    "        self._D = dict(D)\n",
    "\n",
    "    def __getitem__(self, k):\n",
    "        return self._D[k]\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash(tuple(self._D.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "metadata": {},
   "outputs": [],
   "source": [
    "@cache\n",
    "def apply(D : LookUp, l, op=None, r=None):\n",
    "    if op is None:\n",
    "        return int(l)\n",
    "\n",
    "    l = apply(D,*D[l])\n",
    "    r = apply(D,*D[r])\n",
    "    if op == '+':\n",
    "        return l + r\n",
    "    elif op == '-':\n",
    "        return l - r\n",
    "    elif op == '/':\n",
    "        return int(l / r)\n",
    "    elif op == '*':\n",
    "        return l * r\n",
    "    elif op == '=':\n",
    "        return l == r\n",
    "    else:\n",
    "        raise Exception(f'{op=} not known')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_line(l):\n",
    "    k, v = l.split(':')\n",
    "    v = tuple(v.split())\n",
    "    return (k,v)\n",
    "\n",
    "def read(prefix='data'):\n",
    "    data = Path(f'{prefix}/21.txt').read_text().rstrip().split('\\n')\n",
    "    return dict(parse_line(l) for l in data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 248,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "152"
      ]
     },
     "execution_count": 248,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = LookUp(read('test'))\n",
    "apply(D, *D['root'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 249,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "82225382988628"
      ]
     },
     "execution_count": 249,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = LookUp(read())\n",
    "apply(D, *D['root'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {},
   "outputs": [],
   "source": [
    "@cache\n",
    "def humncount(D : LookUp, l, op=None, r=None):\n",
    "    tot = 0\n",
    "    if op is None:\n",
    "        return 0 \n",
    "        \n",
    "    if l == 'humn':\n",
    "        tot += 1\n",
    "    else:\n",
    "        lc = humncount(D,*D[l])\n",
    "        if lc > 0:\n",
    "            tot +=1\n",
    "\n",
    "    if r == 'humn':\n",
    "        tot += 1\n",
    "    else:\n",
    "        rc = humncount(D,*D[r])\n",
    "        if rc > 0:\n",
    "            tot +=1\n",
    "\n",
    "    return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "metadata": {},
   "outputs": [],
   "source": [
    "@cache\n",
    "def simplify(D : LookUp, l, op=None, r=None):\n",
    "    tot = 0\n",
    "\n",
    "    if op is None:\n",
    "        return (l, op, r)\n",
    "        \n",
    "    if (l != 'humn') and humncount(D, *D[l]) == 0:\n",
    "        l = apply(D,*D[l])\n",
    "\n",
    "    if (r != 'humn') and humncount(D, *D[r]) == 0:\n",
    "        r = apply(D,*D[r])\n",
    "\n",
    "    return (l, op, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "metadata": {},
   "outputs": [],
   "source": [
    "def follow(D):\n",
    "    k = 'root'\n",
    "    (l, op, r) = D['root']\n",
    "    L = [(l,op, r)]\n",
    "    while l != None:\n",
    "        k = r if str(l).isdigit() else l\n",
    "        (l,op, r) = D[k]\n",
    "        L.append(D[k])\n",
    "\n",
    "    return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invert(L):\n",
    "    val = 0\n",
    "    assert L[-1] == (None, None, None)\n",
    "    for (l, op, r) in L[:-1]:\n",
    "        left_is_var = str(l).islower()\n",
    "        o = int(r if left_is_var else l)\n",
    "        if op == '+':\n",
    "            val -= o\n",
    "        elif op == '-':\n",
    "            if left_is_var:\n",
    "                val = val + o\n",
    "            else:\n",
    "                val = o - val\n",
    "        elif op == '/':\n",
    "            if left_is_var:\n",
    "                val = val * o\n",
    "            else:\n",
    "                val = o / val\n",
    "        elif op == '*':\n",
    "            val /= o\n",
    "        elif op == '=':\n",
    "            val = o\n",
    "        else:\n",
    "            raise Exception(f'{op=} not known')\n",
    "\n",
    "        val = int(val)\n",
    "\n",
    "    return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pt2(D):\n",
    "    D['root'] = (D['root'][0], '=', D['root'][2])\n",
    "    D['humn'] = (None, None, None)\n",
    "    DL = LookUp(D)\n",
    "    assert humncount(DL, *DL['root']) == 1\n",
    "    S= {k : simplify(DL, *DL[k]) for k in D}\n",
    "    humn = invert(follow(S))\n",
    "\n",
    "    D['humn'] = (humn, None, None)\n",
    "    DL = LookUp(D)\n",
    "    assert apply(LookUp(D), *D['root'])\n",
    "    return humn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "301"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pt2(read('test'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3429411069028"
      ]
     },
     "execution_count": 256,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pt2(read())"
   ]
  }
 ],
 "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.11.0 (main, Nov 15 2022, 19:58:01) [GCC 10.2.1 20210110]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "949777d72b0d2535278d3dc13498b2535136f6dfe0678499012e853ee9abcab1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}