scratch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iteration 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "from inspect import signature\n",
    "from typing import Callable\n",
    "\n",
    "from collections import defaultdict\n",
    "from dataclasses import dataclass\n",
    "from typing import Any, Callable, Tuple, Union\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class FunctionCall:\n",
    "    func_name: str\n",
    "    args: tuple\n",
    "    kwargs: frozenset\n",
    "\n",
    "    def __repr__(self):\n",
    "        if len(self.kwargs) == 0:\n",
    "            if len(self.args) == 1:\n",
    "                return f\"{self.func_name}({self.args[0]})\"\n",
    "            return f\"{self.func_name}{self.args}\"\n",
    "        return f\"{self.func_name}({self.args}, {self.kwargs})\"\n",
    "\n",
    "ArgsHash = Tuple[Tuple, frozenset]\n",
    "\n",
    "class CacheGraph:\n",
    "    def __init__(self):\n",
    "        self.reset()\n",
    "\n",
    "    def reset(self):\n",
    "        self.stack: list[FunctionCall] = [] # what function is currently being called\n",
    "        self.caches: defaultdict[str, dict[ArgsHash, Any]] = defaultdict(dict) # Results of function calls\n",
    "        self.graph: defaultdict[FunctionCall, set[FunctionCall]] = defaultdict(set) # Call graph, graph[caller] = [callee1, callee2, ...]\n",
    "        # Typically aggregated results for a function at a timestep.\n",
    "        self.stored_results: defaultdict[str, dict[int, Any]] = defaultdict(dict)\n",
    "        # What is the last function that needs the result of a function? Used to help in clearing the cache\n",
    "        self.last_needed_by: dict[FunctionCall, FunctionCall] = {}\n",
    "        # can_clear[caller] = [callee1, callee2, ...] means that caller can clear the cache of callee1 and callee2\n",
    "        self.can_clear: dict[FunctionCall, list[FunctionCall]] = defaultdict(list)\n",
    "\n",
    "    def check_if_cached(self, function_call: FunctionCall):\n",
    "        name_in_cache = function_call.func_name in self.caches\n",
    "        return name_in_cache and (function_call.args, function_call.kwargs) in self.caches[function_call.func_name]\n",
    "    \n",
    "    def optimize(self):\n",
    "        self.can_clear = defaultdict(list)\n",
    "        for callee, caller in self.last_needed_by.items():\n",
    "            self.can_clear[caller].append(callee)\n",
    "\n",
    "    def __call__(self, storage_func: Union[Callable, None] = None):\n",
    "        def decorator_factory(func):\n",
    "            def wrapper(*args, **kwargs):\n",
    "                frozen_kwargs = frozenset(kwargs.items())\n",
    "                function_call = FunctionCall(func.__name__, args, frozen_kwargs)\n",
    "                if self.stack:\n",
    "                    self.graph[self.stack[-1]].add(function_call)\n",
    "                    self.last_needed_by[function_call] = self.stack[-1]\n",
    "                if not self.check_if_cached(function_call):\n",
    "                    self.stack.append(function_call)\n",
    "                    result = func(*args, **kwargs)\n",
    "                    for clearable_call in self.can_clear[function_call]:\n",
    "                        del self.caches[clearable_call.func_name][(clearable_call.args, clearable_call.kwargs)]\n",
    "                    self.caches[func.__name__][(args, frozen_kwargs)] = result\n",
    "                    self._store_result(storage_func, func, args, kwargs, result)\n",
    "                    self.stack.pop()\n",
    "                return self.caches[func.__name__][(args, frozen_kwargs)]\n",
    "            decorator = _Cache(self, wrapper)\n",
    "            return decorator\n",
    "        return decorator_factory\n",
    "    \n",
    "    def _store_result(self, storage_func: Union[Callable, None], func: Callable, args: tuple, kwargs: dict, raw_result: Any):\n",
    "        \"\"\"We might want to store an intermediate result\"\"\"\n",
    "        if storage_func is None:\n",
    "            return\n",
    "        # These conditions should not trigger, why we assert and not throw an exception\n",
    "        assert len(args) == 1 and isinstance(args[0], int)\n",
    "        assert len(kwargs) == 0\n",
    "        # store the processed result\n",
    "        timestep = args[0]\n",
    "        stored_result = storage_func(raw_result)\n",
    "        self.stored_results[func.__name__][timestep] = stored_result\n",
    "\n",
    "    def size(self):\n",
    "        return sum(len(cache) for cache in self.caches.values())\n",
    "\n",
    "class _Cache:\n",
    "    def __init__(self, cache_graph: CacheGraph, func: Callable):\n",
    "        self.cache = cache_graph.caches[func.__name__]\n",
    "        self._func = func\n",
    "\n",
    "    def __setitem__(self, key, value):\n",
    "        if isinstance(key, int):\n",
    "            self.cache[((key,), frozenset())] = value\n",
    "        else:\n",
    "            self.cache[(key, frozenset())] = value\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"<Cache Function: {self._func.__name__} Size: {len(self.cache)}>\"\n",
    "    \n",
    "    def __call__(self, *args: Any, **kwds: Any) -> Any:\n",
    "        return self._func(*args, **kwds)\n",
    "    \n",
    "    \n",
    "def check_if_single_parameter_t(func: Callable):\n",
    "    sig = signature(func)\n",
    "    return 't' in sig.parameters and len(sig.parameters) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cg.can_clear=defaultdict(<class 'list'>, {fib(300): [fib(299), fib(298)], fib(299): [fib(297)], fib(298): [fib(296)], fib(297): [fib(295)], fib(296): [fib(294)], fib(295): [fib(293)], fib(294): [fib(292)], fib(293): [fib(291)], fib(292): [fib(290)], fib(291): [fib(289)], fib(290): [fib(288)], fib(289): [fib(287)], fib(288): [fib(286)], fib(287): [fib(285)], fib(286): [fib(284)], fib(285): [fib(283)], fib(284): [fib(282)], fib(283): [fib(281)], fib(282): [fib(280)], fib(281): [fib(279)], fib(280): [fib(278)], fib(279): [fib(277)], fib(278): [fib(276)], fib(277): [fib(275)], fib(276): [fib(274)], fib(275): [fib(273)], fib(274): [fib(272)], fib(273): [fib(271)], fib(272): [fib(270)], fib(271): [fib(269)], fib(270): [fib(268)], fib(269): [fib(267)], fib(268): [fib(266)], fib(267): [fib(265)], fib(266): [fib(264)], fib(265): [fib(263)], fib(264): [fib(262)], fib(263): [fib(261)], fib(262): [fib(260)], fib(261): [fib(259)], fib(260): [fib(258)], fib(259): [fib(257)], fib(258): [fib(256)], fib(257): [fib(255)], fib(256): [fib(254)], fib(255): [fib(253)], fib(254): [fib(252)], fib(253): [fib(251)], fib(252): [fib(250)], fib(251): [fib(249)], fib(250): [fib(248)], fib(249): [fib(247)], fib(248): [fib(246)], fib(247): [fib(245)], fib(246): [fib(244)], fib(245): [fib(243)], fib(244): [fib(242)], fib(243): [fib(241)], fib(242): [fib(240)], fib(241): [fib(239)], fib(240): [fib(238)], fib(239): [fib(237)], fib(238): [fib(236)], fib(237): [fib(235)], fib(236): [fib(234)], fib(235): [fib(233)], fib(234): [fib(232)], fib(233): [fib(231)], fib(232): [fib(230)], fib(231): [fib(229)], fib(230): [fib(228)], fib(229): [fib(227)], fib(228): [fib(226)], fib(227): [fib(225)], fib(226): [fib(224)], fib(225): [fib(223)], fib(224): [fib(222)], fib(223): [fib(221)], fib(222): [fib(220)], fib(221): [fib(219)], fib(220): [fib(218)], fib(219): [fib(217)], fib(218): [fib(216)], fib(217): [fib(215)], fib(216): [fib(214)], fib(215): [fib(213)], fib(214): [fib(212)], fib(213): [fib(211)], fib(212): [fib(210)], fib(211): [fib(209)], fib(210): [fib(208)], fib(209): [fib(207)], fib(208): [fib(206)], fib(207): [fib(205)], fib(206): [fib(204)], fib(205): [fib(203)], fib(204): [fib(202)], fib(203): [fib(201)], fib(202): [fib(200)], fib(201): [fib(199)], fib(200): [fib(198)], fib(199): [fib(197)], fib(198): [fib(196)], fib(197): [fib(195)], fib(196): [fib(194)], fib(195): [fib(193)], fib(194): [fib(192)], fib(193): [fib(191)], fib(192): [fib(190)], fib(191): [fib(189)], fib(190): [fib(188)], fib(189): [fib(187)], fib(188): [fib(186)], fib(187): [fib(185)], fib(186): [fib(184)], fib(185): [fib(183)], fib(184): [fib(182)], fib(183): [fib(181)], fib(182): [fib(180)], fib(181): [fib(179)], fib(180): [fib(178)], fib(179): [fib(177)], fib(178): [fib(176)], fib(177): [fib(175)], fib(176): [fib(174)], fib(175): [fib(173)], fib(174): [fib(172)], fib(173): [fib(171)], fib(172): [fib(170)], fib(171): [fib(169)], fib(170): [fib(168)], fib(169): [fib(167)], fib(168): [fib(166)], fib(167): [fib(165)], fib(166): [fib(164)], fib(165): [fib(163)], fib(164): [fib(162)], fib(163): [fib(161)], fib(162): [fib(160)], fib(161): [fib(159)], fib(160): [fib(158)], fib(159): [fib(157)], fib(158): [fib(156)], fib(157): [fib(155)], fib(156): [fib(154)], fib(155): [fib(153)], fib(154): [fib(152)], fib(153): [fib(151)], fib(152): [fib(150)], fib(151): [fib(149)], fib(150): [fib(148)], fib(149): [fib(147)], fib(148): [fib(146)], fib(147): [fib(145)], fib(146): [fib(144)], fib(145): [fib(143)], fib(144): [fib(142)], fib(143): [fib(141)], fib(142): [fib(140)], fib(141): [fib(139)], fib(140): [fib(138)], fib(139): [fib(137)], fib(138): [fib(136)], fib(137): [fib(135)], fib(136): [fib(134)], fib(135): [fib(133)], fib(134): [fib(132)], fib(133): [fib(131)], fib(132): [fib(130)], fib(131): [fib(129)], fib(130): [fib(128)], fib(129): [fib(127)], fib(128): [fib(126)], fib(127): [fib(125)], fib(126): [fib(124)], fib(125): [fib(123)], fib(124): [fib(122)], fib(123): [fib(121)], fib(122): [fib(120)], fib(121): [fib(119)], fib(120): [fib(118)], fib(119): [fib(117)], fib(118): [fib(116)], fib(117): [fib(115)], fib(116): [fib(114)], fib(115): [fib(113)], fib(114): [fib(112)], fib(113): [fib(111)], fib(112): [fib(110)], fib(111): [fib(109)], fib(110): [fib(108)], fib(109): [fib(107)], fib(108): [fib(106)], fib(107): [fib(105)], fib(106): [fib(104)], fib(105): [fib(103)], fib(104): [fib(102)], fib(103): [fib(101)], fib(102): [fib(100)], fib(101): [fib(99)], fib(100): [fib(98)], fib(99): [fib(97)], fib(98): [fib(96)], fib(97): [fib(95)], fib(96): [fib(94)], fib(95): [fib(93)], fib(94): [fib(92)], fib(93): [fib(91)], fib(92): [fib(90)], fib(91): [fib(89)], fib(90): [fib(88)], fib(89): [fib(87)], fib(88): [fib(86)], fib(87): [fib(85)], fib(86): [fib(84)], fib(85): [fib(83)], fib(84): [fib(82)], fib(83): [fib(81)], fib(82): [fib(80)], fib(81): [fib(79)], fib(80): [fib(78)], fib(79): [fib(77)], fib(78): [fib(76)], fib(77): [fib(75)], fib(76): [fib(74)], fib(75): [fib(73)], fib(74): [fib(72)], fib(73): [fib(71)], fib(72): [fib(70)], fib(71): [fib(69)], fib(70): [fib(68)], fib(69): [fib(67)], fib(68): [fib(66)], fib(67): [fib(65)], fib(66): [fib(64)], fib(65): [fib(63)], fib(64): [fib(62)], fib(63): [fib(61)], fib(62): [fib(60)], fib(61): [fib(59)], fib(60): [fib(58)], fib(59): [fib(57)], fib(58): [fib(56)], fib(57): [fib(55)], fib(56): [fib(54)], fib(55): [fib(53)], fib(54): [fib(52)], fib(53): [fib(51)], fib(52): [fib(50)], fib(51): [fib(49)], fib(50): [fib(48)], fib(49): [fib(47)], fib(48): [fib(46)], fib(47): [fib(45)], fib(46): [fib(44)], fib(45): [fib(43)], fib(44): [fib(42)], fib(43): [fib(41)], fib(42): [fib(40)], fib(41): [fib(39)], fib(40): [fib(38)], fib(39): [fib(37)], fib(38): [fib(36)], fib(37): [fib(35)], fib(36): [fib(34)], fib(35): [fib(33)], fib(34): [fib(32)], fib(33): [fib(31)], fib(32): [fib(30)], fib(31): [fib(29)], fib(30): [fib(28)], fib(29): [fib(27)], fib(28): [fib(26)], fib(27): [fib(25)], fib(26): [fib(24)], fib(25): [fib(23)], fib(24): [fib(22)], fib(23): [fib(21)], fib(22): [fib(20)], fib(21): [fib(19)], fib(20): [fib(18)], fib(19): [fib(17)], fib(18): [fib(16)], fib(17): [fib(15)], fib(16): [fib(14)], fib(15): [fib(13)], fib(14): [fib(12)], fib(13): [fib(11)], fib(12): [fib(10)], fib(11): [fib(9)], fib(10): [fib(8)], fib(9): [fib(7)], fib(8): [fib(6)], fib(7): [fib(5)], fib(6): [fib(4)], fib(5): [fib(3)], fib(4): [fib(2)], fib(3): [fib(1)], fib(2): [fib(0)]})\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "cg = CacheGraph()\n",
    "@cg()\n",
    "def fib(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    return fib(n-1) + fib(n-2)\n",
    "fib(300)\n",
    "cg.optimize()\n",
    "print(f\"{cg.can_clear=}\")\n",
    "can_clear = cg.can_clear\n",
    "cg.reset()\n",
    "cg.can_clear = can_clear\n",
    "fib(300)\n",
    "print(cg.size())\n",
    "# cg.caches\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(dict,\n",
       "            {'fib': {((1,), frozenset()): 1,\n",
       "              ((0,), frozenset()): 0,\n",
       "              ((2,), frozenset()): 1,\n",
       "              ((3,), frozenset()): 2,\n",
       "              ((4,), frozenset()): 3,\n",
       "              ((5,), frozenset()): 5,\n",
       "              ((6,), frozenset()): 8,\n",
       "              ((7,), frozenset()): 13,\n",
       "              ((8,), frozenset()): 21,\n",
       "              ((9,), frozenset()): 34,\n",
       "              ((10,), frozenset()): 55,\n",
       "              ((11,), frozenset()): 89,\n",
       "              ((12,), frozenset()): 144,\n",
       "              ((13,), frozenset()): 233,\n",
       "              ((14,), frozenset()): 377,\n",
       "              ((15,), frozenset()): 610,\n",
       "              ((16,), frozenset()): 987,\n",
       "              ((17,), frozenset()): 1597,\n",
       "              ((18,), frozenset()): 2584,\n",
       "              ((19,), frozenset()): 4181,\n",
       "              ((20,), frozenset()): 6765,\n",
       "              ((21,), frozenset()): 10946,\n",
       "              ((22,), frozenset()): 17711,\n",
       "              ((23,), frozenset()): 28657,\n",
       "              ((24,), frozenset()): 46368,\n",
       "              ((25,), frozenset()): 75025,\n",
       "              ((26,), frozenset()): 121393,\n",
       "              ((27,), frozenset()): 196418,\n",
       "              ((28,), frozenset()): 317811,\n",
       "              ((29,), frozenset()): 514229,\n",
       "              ((30,), frozenset()): 832040,\n",
       "              ((31,), frozenset()): 1346269,\n",
       "              ((32,), frozenset()): 2178309,\n",
       "              ((33,), frozenset()): 3524578,\n",
       "              ((34,), frozenset()): 5702887,\n",
       "              ((35,), frozenset()): 9227465,\n",
       "              ((36,), frozenset()): 14930352,\n",
       "              ((37,), frozenset()): 24157817,\n",
       "              ((38,), frozenset()): 39088169,\n",
       "              ((39,), frozenset()): 63245986,\n",
       "              ((40,), frozenset()): 102334155,\n",
       "              ((41,), frozenset()): 165580141,\n",
       "              ((42,), frozenset()): 267914296,\n",
       "              ((43,), frozenset()): 433494437,\n",
       "              ((44,), frozenset()): 701408733,\n",
       "              ((45,), frozenset()): 1134903170,\n",
       "              ((46,), frozenset()): 1836311903,\n",
       "              ((47,), frozenset()): 2971215073,\n",
       "              ((48,), frozenset()): 4807526976,\n",
       "              ((49,), frozenset()): 7778742049,\n",
       "              ((50,), frozenset()): 12586269025,\n",
       "              ((51,), frozenset()): 20365011074,\n",
       "              ((52,), frozenset()): 32951280099,\n",
       "              ((53,), frozenset()): 53316291173,\n",
       "              ((54,), frozenset()): 86267571272,\n",
       "              ((55,), frozenset()): 139583862445,\n",
       "              ((56,), frozenset()): 225851433717,\n",
       "              ((57,), frozenset()): 365435296162,\n",
       "              ((58,), frozenset()): 591286729879,\n",
       "              ((59,), frozenset()): 956722026041,\n",
       "              ((60,), frozenset()): 1548008755920,\n",
       "              ((61,), frozenset()): 2504730781961,\n",
       "              ((62,), frozenset()): 4052739537881,\n",
       "              ((63,), frozenset()): 6557470319842,\n",
       "              ((64,), frozenset()): 10610209857723,\n",
       "              ((65,), frozenset()): 17167680177565,\n",
       "              ((66,), frozenset()): 27777890035288,\n",
       "              ((67,), frozenset()): 44945570212853,\n",
       "              ((68,), frozenset()): 72723460248141,\n",
       "              ((69,), frozenset()): 117669030460994,\n",
       "              ((70,), frozenset()): 190392490709135,\n",
       "              ((71,), frozenset()): 308061521170129,\n",
       "              ((72,), frozenset()): 498454011879264,\n",
       "              ((73,), frozenset()): 806515533049393,\n",
       "              ((74,), frozenset()): 1304969544928657,\n",
       "              ((75,), frozenset()): 2111485077978050,\n",
       "              ((76,), frozenset()): 3416454622906707,\n",
       "              ((77,), frozenset()): 5527939700884757,\n",
       "              ((78,), frozenset()): 8944394323791464,\n",
       "              ((79,), frozenset()): 14472334024676221,\n",
       "              ((80,), frozenset()): 23416728348467685,\n",
       "              ((81,), frozenset()): 37889062373143906,\n",
       "              ((82,), frozenset()): 61305790721611591,\n",
       "              ((83,), frozenset()): 99194853094755497,\n",
       "              ((84,), frozenset()): 160500643816367088,\n",
       "              ((85,), frozenset()): 259695496911122585,\n",
       "              ((86,), frozenset()): 420196140727489673,\n",
       "              ((87,), frozenset()): 679891637638612258,\n",
       "              ((88,), frozenset()): 1100087778366101931,\n",
       "              ((89,), frozenset()): 1779979416004714189,\n",
       "              ((90,), frozenset()): 2880067194370816120,\n",
       "              ((91,), frozenset()): 4660046610375530309,\n",
       "              ((92,), frozenset()): 7540113804746346429,\n",
       "              ((93,), frozenset()): 12200160415121876738,\n",
       "              ((94,), frozenset()): 19740274219868223167,\n",
       "              ((95,), frozenset()): 31940434634990099905,\n",
       "              ((96,), frozenset()): 51680708854858323072,\n",
       "              ((97,), frozenset()): 83621143489848422977,\n",
       "              ((98,), frozenset()): 135301852344706746049,\n",
       "              ((99,), frozenset()): 218922995834555169026,\n",
       "              ((100,), frozenset()): 354224848179261915075,\n",
       "              ((101,), frozenset()): 573147844013817084101,\n",
       "              ((102,), frozenset()): 927372692193078999176,\n",
       "              ((103,), frozenset()): 1500520536206896083277,\n",
       "              ((104,), frozenset()): 2427893228399975082453,\n",
       "              ((105,), frozenset()): 3928413764606871165730,\n",
       "              ((106,), frozenset()): 6356306993006846248183,\n",
       "              ((107,), frozenset()): 10284720757613717413913,\n",
       "              ((108,), frozenset()): 16641027750620563662096,\n",
       "              ((109,), frozenset()): 26925748508234281076009,\n",
       "              ((110,), frozenset()): 43566776258854844738105,\n",
       "              ((111,), frozenset()): 70492524767089125814114,\n",
       "              ((112,), frozenset()): 114059301025943970552219,\n",
       "              ((113,), frozenset()): 184551825793033096366333,\n",
       "              ((114,), frozenset()): 298611126818977066918552,\n",
       "              ((115,), frozenset()): 483162952612010163284885,\n",
       "              ((116,), frozenset()): 781774079430987230203437,\n",
       "              ((117,), frozenset()): 1264937032042997393488322,\n",
       "              ((118,), frozenset()): 2046711111473984623691759,\n",
       "              ((119,), frozenset()): 3311648143516982017180081,\n",
       "              ((120,), frozenset()): 5358359254990966640871840,\n",
       "              ((121,), frozenset()): 8670007398507948658051921,\n",
       "              ((122,), frozenset()): 14028366653498915298923761,\n",
       "              ((123,), frozenset()): 22698374052006863956975682,\n",
       "              ((124,), frozenset()): 36726740705505779255899443,\n",
       "              ((125,), frozenset()): 59425114757512643212875125,\n",
       "              ((126,), frozenset()): 96151855463018422468774568,\n",
       "              ((127,), frozenset()): 155576970220531065681649693,\n",
       "              ((128,), frozenset()): 251728825683549488150424261,\n",
       "              ((129,), frozenset()): 407305795904080553832073954,\n",
       "              ((130,), frozenset()): 659034621587630041982498215,\n",
       "              ((131,), frozenset()): 1066340417491710595814572169,\n",
       "              ((132,), frozenset()): 1725375039079340637797070384,\n",
       "              ((133,), frozenset()): 2791715456571051233611642553,\n",
       "              ((134,), frozenset()): 4517090495650391871408712937,\n",
       "              ((135,), frozenset()): 7308805952221443105020355490,\n",
       "              ((136,), frozenset()): 11825896447871834976429068427,\n",
       "              ((137,), frozenset()): 19134702400093278081449423917,\n",
       "              ((138,), frozenset()): 30960598847965113057878492344,\n",
       "              ((139,), frozenset()): 50095301248058391139327916261,\n",
       "              ((140,), frozenset()): 81055900096023504197206408605,\n",
       "              ((141,), frozenset()): 131151201344081895336534324866,\n",
       "              ((142,), frozenset()): 212207101440105399533740733471,\n",
       "              ((143,), frozenset()): 343358302784187294870275058337,\n",
       "              ((144,), frozenset()): 555565404224292694404015791808,\n",
       "              ((145,), frozenset()): 898923707008479989274290850145,\n",
       "              ((146,), frozenset()): 1454489111232772683678306641953,\n",
       "              ((147,), frozenset()): 2353412818241252672952597492098,\n",
       "              ((148,), frozenset()): 3807901929474025356630904134051,\n",
       "              ((149,), frozenset()): 6161314747715278029583501626149,\n",
       "              ((150,), frozenset()): 9969216677189303386214405760200,\n",
       "              ((151,), frozenset()): 16130531424904581415797907386349,\n",
       "              ((152,), frozenset()): 26099748102093884802012313146549,\n",
       "              ((153,), frozenset()): 42230279526998466217810220532898,\n",
       "              ((154,), frozenset()): 68330027629092351019822533679447,\n",
       "              ((155,), frozenset()): 110560307156090817237632754212345,\n",
       "              ((156,), frozenset()): 178890334785183168257455287891792,\n",
       "              ((157,), frozenset()): 289450641941273985495088042104137,\n",
       "              ((158,), frozenset()): 468340976726457153752543329995929,\n",
       "              ((159,), frozenset()): 757791618667731139247631372100066,\n",
       "              ((160,), frozenset()): 1226132595394188293000174702095995,\n",
       "              ((161,), frozenset()): 1983924214061919432247806074196061,\n",
       "              ((162,), frozenset()): 3210056809456107725247980776292056,\n",
       "              ((163,), frozenset()): 5193981023518027157495786850488117,\n",
       "              ((164,), frozenset()): 8404037832974134882743767626780173,\n",
       "              ((165,), frozenset()): 13598018856492162040239554477268290,\n",
       "              ((166,), frozenset()): 22002056689466296922983322104048463,\n",
       "              ((167,), frozenset()): 35600075545958458963222876581316753,\n",
       "              ((168,), frozenset()): 57602132235424755886206198685365216,\n",
       "              ((169,), frozenset()): 93202207781383214849429075266681969,\n",
       "              ((170,), frozenset()): 150804340016807970735635273952047185,\n",
       "              ((171,), frozenset()): 244006547798191185585064349218729154,\n",
       "              ((172,), frozenset()): 394810887814999156320699623170776339,\n",
       "              ((173,), frozenset()): 638817435613190341905763972389505493,\n",
       "              ((174,), frozenset()): 1033628323428189498226463595560281832,\n",
       "              ((175,), frozenset()): 1672445759041379840132227567949787325,\n",
       "              ((176,), frozenset()): 2706074082469569338358691163510069157,\n",
       "              ((177,), frozenset()): 4378519841510949178490918731459856482,\n",
       "              ((178,), frozenset()): 7084593923980518516849609894969925639,\n",
       "              ((179,), frozenset()): 11463113765491467695340528626429782121,\n",
       "              ((180,), frozenset()): 18547707689471986212190138521399707760,\n",
       "              ((181,), frozenset()): 30010821454963453907530667147829489881,\n",
       "              ((182,), frozenset()): 48558529144435440119720805669229197641,\n",
       "              ((183,), frozenset()): 78569350599398894027251472817058687522,\n",
       "              ((184,), frozenset()): 127127879743834334146972278486287885163,\n",
       "              ((185,), frozenset()): 205697230343233228174223751303346572685,\n",
       "              ((186,), frozenset()): 332825110087067562321196029789634457848,\n",
       "              ((187,), frozenset()): 538522340430300790495419781092981030533,\n",
       "              ((188,), frozenset()): 871347450517368352816615810882615488381,\n",
       "              ((189,), frozenset()): 1409869790947669143312035591975596518914,\n",
       "              ((190,), frozenset()): 2281217241465037496128651402858212007295,\n",
       "              ((191,), frozenset()): 3691087032412706639440686994833808526209,\n",
       "              ((192,), frozenset()): 5972304273877744135569338397692020533504,\n",
       "              ((193,), frozenset()): 9663391306290450775010025392525829059713,\n",
       "              ((194,), frozenset()): 15635695580168194910579363790217849593217,\n",
       "              ((195,), frozenset()): 25299086886458645685589389182743678652930,\n",
       "              ((196,), frozenset()): 40934782466626840596168752972961528246147,\n",
       "              ((197,), frozenset()): 66233869353085486281758142155705206899077,\n",
       "              ((198,),\n",
       "               frozenset()): 107168651819712326877926895128666735145224,\n",
       "              ((199,),\n",
       "               frozenset()): 173402521172797813159685037284371942044301,\n",
       "              ((200,),\n",
       "               frozenset()): 280571172992510140037611932413038677189525,\n",
       "              ((201,),\n",
       "               frozenset()): 453973694165307953197296969697410619233826,\n",
       "              ((202,),\n",
       "               frozenset()): 734544867157818093234908902110449296423351,\n",
       "              ((203,),\n",
       "               frozenset()): 1188518561323126046432205871807859915657177,\n",
       "              ((204,),\n",
       "               frozenset()): 1923063428480944139667114773918309212080528,\n",
       "              ((205,),\n",
       "               frozenset()): 3111581989804070186099320645726169127737705,\n",
       "              ((206,),\n",
       "               frozenset()): 5034645418285014325766435419644478339818233,\n",
       "              ((207,),\n",
       "               frozenset()): 8146227408089084511865756065370647467555938,\n",
       "              ((208,),\n",
       "               frozenset()): 13180872826374098837632191485015125807374171,\n",
       "              ((209,),\n",
       "               frozenset()): 21327100234463183349497947550385773274930109,\n",
       "              ((210,),\n",
       "               frozenset()): 34507973060837282187130139035400899082304280,\n",
       "              ((211,),\n",
       "               frozenset()): 55835073295300465536628086585786672357234389,\n",
       "              ((212,),\n",
       "               frozenset()): 90343046356137747723758225621187571439538669,\n",
       "              ((213,),\n",
       "               frozenset()): 146178119651438213260386312206974243796773058,\n",
       "              ((214,),\n",
       "               frozenset()): 236521166007575960984144537828161815236311727,\n",
       "              ((215,),\n",
       "               frozenset()): 382699285659014174244530850035136059033084785,\n",
       "              ((216,),\n",
       "               frozenset()): 619220451666590135228675387863297874269396512,\n",
       "              ((217,),\n",
       "               frozenset()): 1001919737325604309473206237898433933302481297,\n",
       "              ((218,),\n",
       "               frozenset()): 1621140188992194444701881625761731807571877809,\n",
       "              ((219,),\n",
       "               frozenset()): 2623059926317798754175087863660165740874359106,\n",
       "              ((220,),\n",
       "               frozenset()): 4244200115309993198876969489421897548446236915,\n",
       "              ((221,),\n",
       "               frozenset()): 6867260041627791953052057353082063289320596021,\n",
       "              ((222,),\n",
       "               frozenset()): 11111460156937785151929026842503960837766832936,\n",
       "              ((223,),\n",
       "               frozenset()): 17978720198565577104981084195586024127087428957,\n",
       "              ((224,),\n",
       "               frozenset()): 29090180355503362256910111038089984964854261893,\n",
       "              ((225,),\n",
       "               frozenset()): 47068900554068939361891195233676009091941690850,\n",
       "              ((226,),\n",
       "               frozenset()): 76159080909572301618801306271765994056795952743,\n",
       "              ((227,),\n",
       "               frozenset()): 123227981463641240980692501505442003148737643593,\n",
       "              ((228,),\n",
       "               frozenset()): 199387062373213542599493807777207997205533596336,\n",
       "              ((229,),\n",
       "               frozenset()): 322615043836854783580186309282650000354271239929,\n",
       "              ((230,),\n",
       "               frozenset()): 522002106210068326179680117059857997559804836265,\n",
       "              ((231,),\n",
       "               frozenset()): 844617150046923109759866426342507997914076076194,\n",
       "              ((232,),\n",
       "               frozenset()): 1366619256256991435939546543402365995473880912459,\n",
       "              ((233,),\n",
       "               frozenset()): 2211236406303914545699412969744873993387956988653,\n",
       "              ((234,),\n",
       "               frozenset()): 3577855662560905981638959513147239988861837901112,\n",
       "              ((235,),\n",
       "               frozenset()): 5789092068864820527338372482892113982249794889765,\n",
       "              ((236,),\n",
       "               frozenset()): 9366947731425726508977331996039353971111632790877,\n",
       "              ((237,),\n",
       "               frozenset()): 15156039800290547036315704478931467953361427680642,\n",
       "              ((238,),\n",
       "               frozenset()): 24522987531716273545293036474970821924473060471519,\n",
       "              ((239,),\n",
       "               frozenset()): 39679027332006820581608740953902289877834488152161,\n",
       "              ((240,),\n",
       "               frozenset()): 64202014863723094126901777428873111802307548623680,\n",
       "              ((241,),\n",
       "               frozenset()): 103881042195729914708510518382775401680142036775841,\n",
       "              ((242,),\n",
       "               frozenset()): 168083057059453008835412295811648513482449585399521,\n",
       "              ((243,),\n",
       "               frozenset()): 271964099255182923543922814194423915162591622175362,\n",
       "              ((244,),\n",
       "               frozenset()): 440047156314635932379335110006072428645041207574883,\n",
       "              ((245,),\n",
       "               frozenset()): 712011255569818855923257924200496343807632829750245,\n",
       "              ((246,),\n",
       "               frozenset()): 1152058411884454788302593034206568772452674037325128,\n",
       "              ((247,),\n",
       "               frozenset()): 1864069667454273644225850958407065116260306867075373,\n",
       "              ((248,),\n",
       "               frozenset()): 3016128079338728432528443992613633888712980904400501,\n",
       "              ((249,),\n",
       "               frozenset()): 4880197746793002076754294951020699004973287771475874,\n",
       "              ((250,),\n",
       "               frozenset()): 7896325826131730509282738943634332893686268675876375,\n",
       "              ((251,),\n",
       "               frozenset()): 12776523572924732586037033894655031898659556447352249,\n",
       "              ((252,),\n",
       "               frozenset()): 20672849399056463095319772838289364792345825123228624,\n",
       "              ((253,),\n",
       "               frozenset()): 33449372971981195681356806732944396691005381570580873,\n",
       "              ((254,),\n",
       "               frozenset()): 54122222371037658776676579571233761483351206693809497,\n",
       "              ((255,),\n",
       "               frozenset()): 87571595343018854458033386304178158174356588264390370,\n",
       "              ((256,),\n",
       "               frozenset()): 141693817714056513234709965875411919657707794958199867,\n",
       "              ((257,),\n",
       "               frozenset()): 229265413057075367692743352179590077832064383222590237,\n",
       "              ((258,),\n",
       "               frozenset()): 370959230771131880927453318055001997489772178180790104,\n",
       "              ((259,),\n",
       "               frozenset()): 600224643828207248620196670234592075321836561403380341,\n",
       "              ((260,),\n",
       "               frozenset()): 971183874599339129547649988289594072811608739584170445,\n",
       "              ((261,),\n",
       "               frozenset()): 1571408518427546378167846658524186148133445300987550786,\n",
       "              ((262,),\n",
       "               frozenset()): 2542592393026885507715496646813780220945054040571721231,\n",
       "              ((263,),\n",
       "               frozenset()): 4114000911454431885883343305337966369078499341559272017,\n",
       "              ((264,),\n",
       "               frozenset()): 6656593304481317393598839952151746590023553382130993248,\n",
       "              ((265,),\n",
       "               frozenset()): 10770594215935749279482183257489712959102052723690265265,\n",
       "              ((266,),\n",
       "               frozenset()): 17427187520417066673081023209641459549125606105821258513,\n",
       "              ((267,),\n",
       "               frozenset()): 28197781736352815952563206467131172508227658829511523778,\n",
       "              ((268,),\n",
       "               frozenset()): 45624969256769882625644229676772632057353264935332782291,\n",
       "              ((269,),\n",
       "               frozenset()): 73822750993122698578207436143903804565580923764844306069,\n",
       "              ((270,),\n",
       "               frozenset()): 119447720249892581203851665820676436622934188700177088360,\n",
       "              ((271,),\n",
       "               frozenset()): 193270471243015279782059101964580241188515112465021394429,\n",
       "              ((272,),\n",
       "               frozenset()): 312718191492907860985910767785256677811449301165198482789,\n",
       "              ((273,),\n",
       "               frozenset()): 505988662735923140767969869749836918999964413630219877218,\n",
       "              ((274,),\n",
       "               frozenset()): 818706854228831001753880637535093596811413714795418360007,\n",
       "              ((275,),\n",
       "               frozenset()): 1324695516964754142521850507284930515811378128425638237225,\n",
       "              ((276,),\n",
       "               frozenset()): 2143402371193585144275731144820024112622791843221056597232,\n",
       "              ((277,),\n",
       "               frozenset()): 3468097888158339286797581652104954628434169971646694834457,\n",
       "              ((278,),\n",
       "               frozenset()): 5611500259351924431073312796924978741056961814867751431689,\n",
       "              ((279,),\n",
       "               frozenset()): 9079598147510263717870894449029933369491131786514446266146,\n",
       "              ((280,),\n",
       "               frozenset()): 14691098406862188148944207245954912110548093601382197697835,\n",
       "              ((281,),\n",
       "               frozenset()): 23770696554372451866815101694984845480039225387896643963981,\n",
       "              ((282,),\n",
       "               frozenset()): 38461794961234640015759308940939757590587318989278841661816,\n",
       "              ((283,),\n",
       "               frozenset()): 62232491515607091882574410635924603070626544377175485625797,\n",
       "              ((284,),\n",
       "               frozenset()): 100694286476841731898333719576864360661213863366454327287613,\n",
       "              ((285,),\n",
       "               frozenset()): 162926777992448823780908130212788963731840407743629812913410,\n",
       "              ((286,),\n",
       "               frozenset()): 263621064469290555679241849789653324393054271110084140201023,\n",
       "              ((287,),\n",
       "               frozenset()): 426547842461739379460149980002442288124894678853713953114433,\n",
       "              ((288,),\n",
       "               frozenset()): 690168906931029935139391829792095612517948949963798093315456,\n",
       "              ((289,),\n",
       "               frozenset()): 1116716749392769314599541809794537900642843628817512046429889,\n",
       "              ((290,),\n",
       "               frozenset()): 1806885656323799249738933639586633513160792578781310139745345,\n",
       "              ((291,),\n",
       "               frozenset()): 2923602405716568564338475449381171413803636207598822186175234,\n",
       "              ((292,),\n",
       "               frozenset()): 4730488062040367814077409088967804926964428786380132325920579,\n",
       "              ((293,),\n",
       "               frozenset()): 7654090467756936378415884538348976340768064993978954512095813,\n",
       "              ((294,),\n",
       "               frozenset()): 12384578529797304192493293627316781267732493780359086838016392,\n",
       "              ((295,),\n",
       "               frozenset()): 20038668997554240570909178165665757608500558774338041350112205,\n",
       "              ((296,),\n",
       "               frozenset()): 32423247527351544763402471792982538876233052554697128188128597,\n",
       "              ((297,),\n",
       "               frozenset()): 52461916524905785334311649958648296484733611329035169538240802,\n",
       "              ((298,),\n",
       "               frozenset()): 84885164052257330097714121751630835360966663883732297726369399,\n",
       "              ((299,),\n",
       "               frozenset()): 137347080577163115432025771710279131845700275212767467264610201,\n",
       "              ((300,),\n",
       "               frozenset()): 222232244629420445529739893461909967206666939096499764990979600,\n",
       "              ((301,),\n",
       "               frozenset()): 359579325206583560961765665172189099052367214309267232255589801,\n",
       "              ((302,),\n",
       "               frozenset()): 581811569836004006491505558634099066259034153405766997246569401,\n",
       "              ((303,),\n",
       "               frozenset()): 941390895042587567453271223806288165311401367715034229502159202,\n",
       "              ((304,),\n",
       "               frozenset()): 1523202464878591573944776782440387231570435521120801226748728603,\n",
       "              ((305,),\n",
       "               frozenset()): 2464593359921179141398048006246675396881836888835835456250887805,\n",
       "              ((306,),\n",
       "               frozenset()): 3987795824799770715342824788687062628452272409956636682999616408,\n",
       "              ((307,),\n",
       "               frozenset()): 6452389184720949856740872794933738025334109298792472139250504213,\n",
       "              ((308,),\n",
       "               frozenset()): 10440185009520720572083697583620800653786381708749108822250120621,\n",
       "              ((309,),\n",
       "               frozenset()): 16892574194241670428824570378554538679120491007541580961500624834,\n",
       "              ((310,),\n",
       "               frozenset()): 27332759203762391000908267962175339332906872716290689783750745455,\n",
       "              ((311,),\n",
       "               frozenset()): 44225333398004061429732838340729878012027363723832270745251370289,\n",
       "              ((312,),\n",
       "               frozenset()): 71558092601766452430641106302905217344934236440122960529002115744,\n",
       "              ((313,),\n",
       "               frozenset()): 115783425999770513860373944643635095356961600163955231274253486033,\n",
       "              ((314,),\n",
       "               frozenset()): 187341518601536966291015050946540312701895836604078191803255601777,\n",
       "              ((315,),\n",
       "               frozenset()): 303124944601307480151388995590175408058857436768033423077509087810,\n",
       "              ((316,),\n",
       "               frozenset()): 490466463202844446442404046536715720760753273372111614880764689587,\n",
       "              ((317,),\n",
       "               frozenset()): 793591407804151926593793042126891128819610710140145037958273777397,\n",
       "              ((318,),\n",
       "               frozenset()): 1284057871006996373036197088663606849580363983512256652839038466984,\n",
       "              ((319,),\n",
       "               frozenset()): 2077649278811148299629990130790497978399974693652401690797312244381,\n",
       "              ((320,),\n",
       "               frozenset()): 3361707149818144672666187219454104827980338677164658343636350711365,\n",
       "              ((321,),\n",
       "               frozenset()): 5439356428629292972296177350244602806380313370817060034433662955746,\n",
       "              ((322,),\n",
       "               frozenset()): 8801063578447437644962364569698707634360652047981718378070013667111,\n",
       "              ((323,),\n",
       "               frozenset()): 14240420007076730617258541919943310440740965418798778412503676622857,\n",
       "              ((324,),\n",
       "               frozenset()): 23041483585524168262220906489642018075101617466780496790573690289968,\n",
       "              ((325,),\n",
       "               frozenset()): 37281903592600898879479448409585328515842582885579275203077366912825,\n",
       "              ((326,),\n",
       "               frozenset()): 60323387178125067141700354899227346590944200352359771993651057202793,\n",
       "              ((327,),\n",
       "               frozenset()): 97605290770725966021179803308812675106786783237939047196728424115618,\n",
       "              ((328,),\n",
       "               frozenset()): 157928677948851033162880158208040021697730983590298819190379481318411,\n",
       "              ((329,),\n",
       "               frozenset()): 255533968719576999184059961516852696804517766828237866387107905434029,\n",
       "              ((330,),\n",
       "               frozenset()): 413462646668428032346940119724892718502248750418536685577487386752440,\n",
       "              ((331,),\n",
       "               frozenset()): 668996615388005031531000081241745415306766517246774551964595292186469,\n",
       "              ((332,),\n",
       "               frozenset()): 1082459262056433063877940200966638133809015267665311237542082678938909,\n",
       "              ((333,),\n",
       "               frozenset()): 1751455877444438095408940282208383549115781784912085789506677971125378,\n",
       "              ((334,),\n",
       "               frozenset()): 2833915139500871159286880483175021682924797052577397027048760650064287,\n",
       "              ((335,),\n",
       "               frozenset()): 4585371016945309254695820765383405232040578837489482816555438621189665,\n",
       "              ((336,),\n",
       "               frozenset()): 7419286156446180413982701248558426914965375890066879843604199271253952,\n",
       "              ((337,),\n",
       "               frozenset()): 12004657173391489668678522013941832147005954727556362660159637892443617,\n",
       "              ((338,),\n",
       "               frozenset()): 19423943329837670082661223262500259061971330617623242503763837163697569,\n",
       "              ((339,),\n",
       "               frozenset()): 31428600503229159751339745276442091208977285345179605163923475056141186,\n",
       "              ((340,),\n",
       "               frozenset()): 50852543833066829834000968538942350270948615962802847667687312219838755,\n",
       "              ((341,),\n",
       "               frozenset()): 82281144336295989585340713815384441479925901307982452831610787275979941,\n",
       "              ((342,),\n",
       "               frozenset()): 133133688169362819419341682354326791750874517270785300499298099495818696,\n",
       "              ((343,),\n",
       "               frozenset()): 215414832505658809004682396169711233230800418578767753330908886771798637,\n",
       "              ((344,),\n",
       "               frozenset()): 348548520675021628424024078524038024981674935849553053830206986267617333,\n",
       "              ((345,),\n",
       "               frozenset()): 563963353180680437428706474693749258212475354428320807161115873039415970,\n",
       "              ((346,),\n",
       "               frozenset()): 912511873855702065852730553217787283194150290277873860991322859307033303,\n",
       "              ((347,),\n",
       "               frozenset()): 1476475227036382503281437027911536541406625644706194668152438732346449273,\n",
       "              ((348,),\n",
       "               frozenset()): 2388987100892084569134167581129323824600775934984068529143761591653482576,\n",
       "              ((349,),\n",
       "               frozenset()): 3865462327928467072415604609040860366007401579690263197296200323999931849,\n",
       "              ((350,),\n",
       "               frozenset()): 6254449428820551641549772190170184190608177514674331726439961915653414425,\n",
       "              ((351,),\n",
       "               frozenset()): 10119911756749018713965376799211044556615579094364594923736162239653346274,\n",
       "              ((352,),\n",
       "               frozenset()): 16374361185569570355515148989381228747223756609038926650176124155306760699,\n",
       "              ((353,),\n",
       "               frozenset()): 26494272942318589069480525788592273303839335703403521573912286394960106973,\n",
       "              ((354,),\n",
       "               frozenset()): 42868634127888159424995674777973502051063092312442448224088410550266867672,\n",
       "              ((355,),\n",
       "               frozenset()): 69362907070206748494476200566565775354902428015845969798000696945226974645,\n",
       "              ((356,),\n",
       "               frozenset()): 112231541198094907919471875344539277405965520328288418022089107495493842317,\n",
       "              ((357,),\n",
       "               frozenset()): 181594448268301656413948075911105052760867948344134387820089804440720816962,\n",
       "              ((358,),\n",
       "               frozenset()): 293825989466396564333419951255644330166833468672422805842178911936214659279,\n",
       "              ((359,),\n",
       "               frozenset()): 475420437734698220747368027166749382927701417016557193662268716376935476241,\n",
       "              ((360,),\n",
       "               frozenset()): 769246427201094785080787978422393713094534885688979999504447628313150135520,\n",
       "              ((361,),\n",
       "               frozenset()): 1244666864935793005828156005589143096022236302705537193166716344690085611761,\n",
       "              ((362,),\n",
       "               frozenset()): 2013913292136887790908943984011536809116771188394517192671163973003235747281,\n",
       "              ((363,),\n",
       "               frozenset()): 3258580157072680796737099989600679905139007491100054385837880317693321359042,\n",
       "              ((364,),\n",
       "               frozenset()): 5272493449209568587646043973612216714255778679494571578509044290696557106323,\n",
       "              ((365,),\n",
       "               frozenset()): 8531073606282249384383143963212896619394786170594625964346924608389878465365,\n",
       "              ((366,),\n",
       "               frozenset()): 13803567055491817972029187936825113333650564850089197542855968899086435571688,\n",
       "              ((367,),\n",
       "               frozenset()): 22334640661774067356412331900038009953045351020683823507202893507476314037053,\n",
       "              ((368,),\n",
       "               frozenset()): 36138207717265885328441519836863123286695915870773021050058862406562749608741,\n",
       "              ((369,),\n",
       "               frozenset()): 58472848379039952684853851736901133239741266891456844557261755914039063645794,\n",
       "              ((370,),\n",
       "               frozenset()): 94611056096305838013295371573764256526437182762229865607320618320601813254535,\n",
       "              ((371,),\n",
       "               frozenset()): 153083904475345790698149223310665389766178449653686710164582374234640876900329,\n",
       "              ((372,),\n",
       "               frozenset()): 247694960571651628711444594884429646292615632415916575771902992555242690154864,\n",
       "              ((373,),\n",
       "               frozenset()): 400778865046997419409593818195095036058794082069603285936485366789883567055193,\n",
       "              ((374,),\n",
       "               frozenset()): 648473825618649048121038413079524682351409714485519861708388359345126257210057,\n",
       "              ((375,),\n",
       "               frozenset()): 1049252690665646467530632231274619718410203796555123147644873726135009824265250,\n",
       "              ((376,),\n",
       "               frozenset()): 1697726516284295515651670644354144400761613511040643009353262085480136081475307,\n",
       "              ((377,),\n",
       "               frozenset()): 2746979206949941983182302875628764119171817307595766156998135811615145905740557,\n",
       "              ((378,),\n",
       "               frozenset()): 4444705723234237498833973519982908519933430818636409166351397897095281987215864,\n",
       "              ((379,),\n",
       "               frozenset()): 7191684930184179482016276395611672639105248126232175323349533708710427892956421,\n",
       "              ((380,),\n",
       "               frozenset()): 11636390653418416980850249915594581159038678944868584489700931605805709880172285,\n",
       "              ((381,),\n",
       "               frozenset()): 18828075583602596462866526311206253798143927071100759813050465314516137773128706,\n",
       "              ((382,),\n",
       "               frozenset()): 30464466237021013443716776226800834957182606015969344302751396920321847653300991,\n",
       "              ((383,),\n",
       "               frozenset()): 49292541820623609906583302538007088755326533087070104115801862234837985426429697,\n",
       "              ((384,),\n",
       "               frozenset()): 79757008057644623350300078764807923712509139103039448418553259155159833079730688,\n",
       "              ((385,),\n",
       "               frozenset()): 129049549878268233256883381302815012467835672190109552534355121389997818506160385,\n",
       "              ((386,),\n",
       "               frozenset()): 208806557935912856607183460067622936180344811293149000952908380545157651585891073,\n",
       "              ((387,),\n",
       "               frozenset()): 337856107814181089864066841370437948648180483483258553487263501935155470092051458,\n",
       "              ((388,),\n",
       "               frozenset()): 546662665750093946471250301438060884828525294776407554440171882480313121677942531,\n",
       "              ((389,),\n",
       "               frozenset()): 884518773564275036335317142808498833476705778259666107927435384415468591769993989,\n",
       "              ((390,),\n",
       "               frozenset()): 1431181439314368982806567444246559718305231073036073662367607266895781713447936520,\n",
       "              ((391,),\n",
       "               frozenset()): 2315700212878644019141884587055058551781936851295739770295042651311250305217930509,\n",
       "              ((392,),\n",
       "               frozenset()): 3746881652193013001948452031301618270087167924331813432662649918207032018665867029,\n",
       "              ((393,),\n",
       "               frozenset()): 6062581865071657021090336618356676821869104775627553202957692569518282323883797538,\n",
       "              ((394,),\n",
       "               frozenset()): 9809463517264670023038788649658295091956272699959366635620342487725314342549664567,\n",
       "              ((395,),\n",
       "               frozenset()): 15872045382336327044129125268014971913825377475586919838578035057243596666433462105,\n",
       "              ((396,),\n",
       "               frozenset()): 25681508899600997067167913917673267005781650175546286474198377544968911008983126672,\n",
       "              ((397,),\n",
       "               frozenset()): 41553554281937324111297039185688238919607027651133206312776412602212507675416588777,\n",
       "              ((398,),\n",
       "               frozenset()): 67235063181538321178464953103361505925388677826679492786974790147181418684399715449,\n",
       "              ((399,),\n",
       "               frozenset()): 108788617463475645289761992289049744844995705477812699099751202749393926359816304226,\n",
       "              ((400,),\n",
       "               frozenset()): 176023680645013966468226945392411250770384383304492191886725992896575345044216019675,\n",
       "              ((401,),\n",
       "               frozenset()): 284812298108489611757988937681460995615380088782304890986477195645969271404032323901,\n",
       "              ((402,),\n",
       "               frozenset()): 460835978753503578226215883073872246385764472086797082873203188542544616448248343576,\n",
       "              ((403,),\n",
       "               frozenset()): 745648276861993189984204820755333242001144560869101973859680384188513887852280667477,\n",
       "              ((404,),\n",
       "               frozenset()): 1206484255615496768210420703829205488386909032955899056732883572731058504300529011053,\n",
       "              ((405,),\n",
       "               frozenset()): 1952132532477489958194625524584538730388053593825001030592563956919572392152809678530,\n",
       "              ((406,),\n",
       "               frozenset()): 3158616788092986726405046228413744218774962626780900087325447529650630896453338689583,\n",
       "              ((407,),\n",
       "               frozenset()): 5110749320570476684599671752998282949163016220605901117918011486570203288606148368113,\n",
       "              ((408,),\n",
       "               frozenset()): 8269366108663463411004717981412027167937978847386801205243459016220834185059487057696,\n",
       "              ((409,),\n",
       "               frozenset()): 13380115429233940095604389734410310117100995067992702323161470502791037473665635425809,\n",
       "              ((410,),\n",
       "               frozenset()): 21649481537897403506609107715822337285038973915379503528404929519011871658725122483505,\n",
       "              ((411,),\n",
       "               frozenset()): 35029596967131343602213497450232647402139968983372205851566400021802909132390757909314,\n",
       "              ((412,),\n",
       "               frozenset()): 56679078505028747108822605166054984687178942898751709379971329540814780791115880392819,\n",
       "              ((413,),\n",
       "               frozenset()): 91708675472160090711036102616287632089318911882123915231537729562617689923506638302133,\n",
       "              ((414,),\n",
       "               frozenset()): 148387753977188837819858707782342616776497854780875624611509059103432470714622518694952,\n",
       "              ((415,),\n",
       "               frozenset()): 240096429449348928530894810398630248865816766662999539843046788666050160638129156997085,\n",
       "              ((416,),\n",
       "               frozenset()): 388484183426537766350753518180972865642314621443875164454555847769482631352751675692037,\n",
       "              ((417,),\n",
       "               frozenset()): 628580612875886694881648328579603114508131388106874704297602636435532791990880832689122,\n",
       "              ((418,),\n",
       "               frozenset()): 1017064796302424461232401846760575980150446009550749868752158484205015423343632508381159,\n",
       "              ((419,),\n",
       "               frozenset()): 1645645409178311156114050175340179094658577397657624573049761120640548215334513341070281,\n",
       "              ((420,),\n",
       "               frozenset()): 2662710205480735617346452022100755074809023407208374441801919604845563638678145849451440,\n",
       "              ((421,),\n",
       "               frozenset()): 4308355614659046773460502197440934169467600804865999014851680725486111854012659190521721,\n",
       "              ((422,),\n",
       "               frozenset()): 6971065820139782390806954219541689244276624212074373456653600330331675492690805039973161,\n",
       "              ((423,),\n",
       "               frozenset()): 11279421434798829164267456416982623413744225016940372471505281055817787346703464230494882,\n",
       "              ((424,),\n",
       "               frozenset()): 18250487254938611555074410636524312658020849229014745928158881386149462839394269270468043,\n",
       "              ((425,),\n",
       "               frozenset()): 29529908689737440719341867053506936071765074245955118399664162441967250186097733500962925,\n",
       "              ((426,),\n",
       "               frozenset()): 47780395944676052274416277690031248729785923474969864327823043828116713025492002771430968,\n",
       "              ((427,),\n",
       "               frozenset()): 77310304634413492993758144743538184801550997720924982727487206270083963211589736272393893,\n",
       "              ((428,),\n",
       "               frozenset()): 125090700579089545268174422433569433531336921195894847055310250098200676237081739043824861,\n",
       "              ((429,),\n",
       "               frozenset()): 202401005213503038261932567177107618332887918916819829782797456368284639448671475316218754,\n",
       "              ((430,),\n",
       "               frozenset()): 327491705792592583530106989610677051864224840112714676838107706466485315685753214360043615,\n",
       "              ((431,),\n",
       "               frozenset()): 529892711006095621792039556787784670197112759029534506620905162834769955134424689676262369,\n",
       "              ((432,),\n",
       "               frozenset()): 857384416798688205322146546398461722061337599142249183459012869301255270820177904036305984,\n",
       "              ((433,),\n",
       "               frozenset()): 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353,\n",
       "              ((434,),\n",
       "               frozenset()): 2244661544603472032436332649584708114319787957314032873538930901437280496774780497748874337,\n",
       "              ((435,),\n",
       "               frozenset()): 3631938672408255859550518752770954506578238315485816563618848933573305722729383091461442690,\n",
       "              ((436,),\n",
       "               frozenset()): 5876600217011727891986851402355662620898026272799849437157779835010586219504163589210317027,\n",
       "              ((437,),\n",
       "               frozenset()): 9508538889419983751537370155126617127476264588285666000776628768583891942233546680671759717,\n",
       "              ((438,),\n",
       "               frozenset()): 15385139106431711643524221557482279748374290861085515437934408603594478161737710269882076744,\n",
       "              ((439,),\n",
       "               frozenset()): 24893677995851695395061591712608896875850555449371181438711037372178370103971256950553836461,\n",
       "              ((440,),\n",
       "               frozenset()): 40278817102283407038585813270091176624224846310456696876645445975772848265708967220435913205,\n",
       "              ((441,),\n",
       "               frozenset()): 65172495098135102433647404982700073500075401759827878315356483347951218369680224170989749666,\n",
       "              ((442,),\n",
       "               frozenset()): 105451312200418509472233218252791250124300248070284575192001929323724066635389191391425662871,\n",
       "              ((443,),\n",
       "               frozenset()): 170623807298553611905880623235491323624375649830112453507358412671675285005069415562415412537,\n",
       "              ((444,),\n",
       "               frozenset()): 276075119498972121378113841488282573748675897900397028699360341995399351640458606953841075408,\n",
       "              ((445,),\n",
       "               frozenset()): 446698926797525733283994464723773897373051547730509482206718754667074636645528022516256487945,\n",
       "              ((446,),\n",
       "               frozenset()): 722774046296497854662108306212056471121727445630906510906079096662473988285986629470097563353,\n",
       "              ((447,),\n",
       "               frozenset()): 1169472973094023587946102770935830368494778993361415993112797851329548624931514651986354051298,\n",
       "              ((448,),\n",
       "               frozenset()): 1892247019390521442608211077147886839616506438992322504018876947992022613217501281456451614651,\n",
       "              ((449,),\n",
       "               frozenset()): 3061719992484545030554313848083717208111285432353738497131674799321571238149015933442805665949,\n",
       "              ((450,),\n",
       "               frozenset()): 4953967011875066473162524925231604047727791871346061001150551747313593851366517214899257280600,\n",
       "              ((451,),\n",
       "               frozenset()): 8015687004359611503716838773315321255839077303699799498282226546635165089515533148342062946549,\n",
       "              ((452,),\n",
       "               frozenset()): 12969654016234677976879363698546925303566869175045860499432778293948758940882050363241320227149,\n",
       "              ((453,),\n",
       "               frozenset()): 20985341020594289480596202471862246559405946478745659997715004840583924030397583511583383173698,\n",
       "              ((454,),\n",
       "               frozenset()): 33954995036828967457475566170409171862972815653791520497147783134532682971279633874824703400847,\n",
       "              ((455,),\n",
       "               frozenset()): 54940336057423256938071768642271418422378762132537180494862787975116607001677217386408086574545,\n",
       "              ((456,),\n",
       "               frozenset()): 88895331094252224395547334812680590285351577786328700992010571109649289972956851261232789975392,\n",
       "              ((457,),\n",
       "               frozenset()): 143835667151675481333619103454952008707730339918865881486873359084765896974634068647640876549937,\n",
       "              ((458,),\n",
       "               frozenset()): 232730998245927705729166438267632598993081917705194582478883930194415186947590919908873666525329,\n",
       "              ((459,),\n",
       "               frozenset()): 376566665397603187062785541722584607700812257624060463965757289279181083922224988556514543075266,\n",
       "              ((460,),\n",
       "               frozenset()): 609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595,\n",
       "              ((461,),\n",
       "               frozenset()): 985864329041134079854737521712801814394706432953315510410398508752777354792040897021902752675861,\n",
       "              ((462,),\n",
       "               frozenset()): 1595161992684664972646689501703019021088600608282570556855039728226373625661856805487290962276456,\n",
       "              ((463,),\n",
       "               frozenset()): 2581026321725799052501427023415820835483307041235886067265438236979150980453897702509193714952317,\n",
       "              ((464,),\n",
       "               frozenset()): 4176188314410464025148116525118839856571907649518456624120477965205524606115754507996484677228773,\n",
       "              ((465,),\n",
       "               frozenset()): 6757214636136263077649543548534660692055214690754342691385916202184675586569652210505678392181090,\n",
       "              ((466,),\n",
       "               frozenset()): 10933402950546727102797660073653500548627122340272799315506394167390200192685406718502163069409863,\n",
       "              ((467,),\n",
       "               frozenset()): 17690617586682990180447203622188161240682337031027142006892310369574875779255058929007841461590953,\n",
       "              ((468,),\n",
       "               frozenset()): 28624020537229717283244863695841661789309459371299941322398704536965075971940465647510004531000816,\n",
       "              ((469,),\n",
       "               frozenset()): 46314638123912707463692067318029823029991796402327083329291014906539951751195524576517845992591769,\n",
       "              ((470,),\n",
       "               frozenset()): 74938658661142424746936931013871484819301255773627024651689719443505027723135990224027850523592585,\n",
       "              ((471,),\n",
       "               frozenset()): 121253296785055132210628998331901307849293052175954107980980734350044979474331514800545696516184354,\n",
       "              ((472,),\n",
       "               frozenset()): 196191955446197556957565929345772792668594307949581132632670453793550007197467505024573547039776939,\n",
       "              ((473,),\n",
       "               frozenset()): 317445252231252689168194927677674100517887360125535240613651188143594986671799019825119243555961293,\n",
       "              ((474,),\n",
       "               frozenset()): 513637207677450246125760857023446893186481668075116373246321641937144993869266524849692790595738232,\n",
       "              ((475,),\n",
       "               frozenset()): 831082459908702935293955784701120993704369028200651613859972830080739980541065544674812034151699525,\n",
       "              ((476,),\n",
       "               frozenset()): 1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757,\n",
       "              ((477,),\n",
       "               frozenset()): 2175802127494856116713672426425688880595219724476419600966267302098624954951397614199316858899137282,\n",
       "              ((478,),\n",
       "               frozenset()): 3520521795081009298133389068150256767486070420752187588072561774116509929361729683723821683646575039,\n",
       "              ((479,),\n",
       "               frozenset()): 5696323922575865414847061494575945648081290145228607189038829076215134884313127297923138542545712321,\n",
       "              ((480,),\n",
       "               frozenset()): 9216845717656874712980450562726202415567360565980794777111390850331644813674856981646960226192287360,\n",
       "              ((481,),\n",
       "               frozenset()): 14913169640232740127827512057302148063648650711209401966150219926546779697987984279570098768737999681,\n",
       "              ((482,),\n",
       "               frozenset()): 24130015357889614840807962620028350479216011277190196743261610776878424511662841261217058994930287041,\n",
       "              ((483,),\n",
       "               frozenset()): 39043184998122354968635474677330498542864661988399598709411830703425204209650825540787157763668286722,\n",
       "              ((484,),\n",
       "               frozenset()): 63173200356011969809443437297358849022080673265589795452673441480303628721313666802004216758598573763,\n",
       "              ((485,),\n",
       "               frozenset()): 102216385354134324778078911974689347564945335253989394162085272183728832930964492342791374522266860485,\n",
       "              ((486,),\n",
       "               frozenset()): 165389585710146294587522349272048196587026008519579189614758713664032461652278159144795591280865434248,\n",
       "              ((487,),\n",
       "               frozenset()): 267605971064280619365601261246737544151971343773568583776843985847761294583242651487586965803132294733,\n",
       "              ((488,),\n",
       "               frozenset()): 432995556774426913953123610518785740738997352293147773391602699511793756235520810632382557083997728981,\n",
       "              ((489,),\n",
       "               frozenset()): 700601527838707533318724871765523284890968696066716357168446685359555050818763462119969522887130023714,\n",
       "              ((490,),\n",
       "               frozenset()): 1133597084613134447271848482284309025629966048359864130560049384871348807054284272752352079971127752695,\n",
       "              ((491,),\n",
       "               frozenset()): 1834198612451841980590573354049832310520934744426580487728496070230903857873047734872321602858257776409,\n",
       "              ((492,),\n",
       "               frozenset()): 2967795697064976427862421836334141336150900792786444618288545455102252664927332007624673682829385529104,\n",
       "              ((493,),\n",
       "               frozenset()): 4801994309516818408452995190383973646671835537213025106017041525333156522800379742496995285687643305513,\n",
       "              ((494,),\n",
       "               frozenset()): 7769790006581794836315417026718114982822736329999469724305586980435409187727711750121668968517028834617,\n",
       "              ((495,),\n",
       "               frozenset()): 12571784316098613244768412217102088629494571867212494830322628505768565710528091492618664254204672140130,\n",
       "              ((496,),\n",
       "               frozenset()): 20341574322680408081083829243820203612317308197211964554628215486203974898255803242740333222721700974747,\n",
       "              ((497,),\n",
       "               frozenset()): 32913358638779021325852241460922292241811880064424459384950843991972540608783894735358997476926373114877,\n",
       "              ((498,),\n",
       "               frozenset()): 53254932961459429406936070704742495854129188261636423939579059478176515507039697978099330699648074089624,\n",
       "              ((499,),\n",
       "               frozenset()): 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501,\n",
       "              ((500,),\n",
       "               frozenset()): 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125}})"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cg.caches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## iteration 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from dataclasses import dataclass\n",
    "from functools import wraps\n",
    "from typing import Any, Callable, Tuple, Union\n",
    "from inspect import signature\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class FunctionCall:\n",
    "    func_name: str\n",
    "    args: tuple\n",
    "    kwargs: frozenset\n",
    "\n",
    "ArgsHash = Tuple[Tuple, frozenset]\n",
    "\n",
    "class CacheGraph:\n",
    "    def __init__(self):\n",
    "        self.reset()\n",
    "\n",
    "    def reset(self):\n",
    "        self.stack: list[FunctionCall] = [] # what function is currently being called\n",
    "        self.caches: defaultdict[str, dict[ArgsHash, Any]] = defaultdict(dict) # Results of function calls\n",
    "        self.graph: defaultdict[FunctionCall, set[FunctionCall]] = defaultdict(set) # Call graph, graph[caller] = [callee1, callee2, ...]\n",
    "        self.indegrees: defaultdict[FunctionCall, int] = defaultdict(int) # Number of incoming edges to a node\n",
    "        # Typically aggregated results for a function at a timestep.\n",
    "        self.stored_results: defaultdict[str, dict[int, Any]] = defaultdict(dict) \n",
    "\n",
    "    def check_if_cached(self, function_call: FunctionCall):\n",
    "        name_in_cache = function_call.func_name in self.caches\n",
    "        return name_in_cache and (function_call.args, function_call.kwargs) in self.caches[function_call.func_name]\n",
    "    \n",
    "    def _store_result(self, storage_func: Union[Callable, None], func: Callable, args: tuple, kwargs: dict, raw_result: Any):\n",
    "        \"\"\"We might want to store an intermediate result\"\"\"\n",
    "        if storage_func is None:\n",
    "            return\n",
    "        # These conditions should not trigger, why we assert and not throw an exception\n",
    "        assert len(args) == 1 and isinstance(args[0], int)\n",
    "        assert len(kwargs) == 0\n",
    "        # store the processed result\n",
    "        timestep = args[0]\n",
    "        stored_result = storage_func(raw_result)\n",
    "        self.stored_results[func.__name__][timestep] = stored_result\n",
    "\n",
    "class CacheDecorator:\n",
    "    def __init__(self, func: Callable, cache_graph: CacheGraph, storage_func: Union[Callable, None] = None):\n",
    "        self.func = func\n",
    "        self.graph = cache_graph.graph\n",
    "        self.indegrees = cache_graph.indegrees.copy()\n",
    "        self.cached_values = cache_graph.caches[func.__name__]\n",
    "        self.storage_func = storage_func\n",
    "        sig = signature(func)\n",
    "        self.single_param_timesteps = 't' in sig.parameters and len(sig.parameters) == 1\n",
    "    \n",
    "    def __call__(self, *args, **kwargs):\n",
    "        frozen_kwargs = frozenset(kwargs.items())\n",
    "        function_call = FunctionCall(self.func.__name__, args, frozen_kwargs)\n",
    "        if self.cache_graph.stack:\n",
    "            self.cache_graph.graph[self.cache_graph.stack[-1]].add(function_call)\n",
    "            self.cache_graph.indegrees[function_call] += 1\n",
    "        if not self.cache_graph.check_if_cached(function_call):\n",
    "            self.cache_graph.stack.append(function_call)\n",
    "            result = self.func(*args, **kwargs)\n",
    "            self.cached_values[(args, frozen_kwargs)] = result\n",
    "            if self.single_param_timesteps:\n",
    "                self._store_result(args, result)\n",
    "            self.cache_graph.stack.pop()\n",
    "        return self.cached_values[(args, frozen_kwargs)]\n",
    "    \n",
    "    def _store_result(self, args: tuple, raw_result: Any):\n",
    "        \"\"\"We might want to store an intermediate result\"\"\"\n",
    "        if self.storage_func is None:\n",
    "            return\n",
    "        if self.single_param_timesteps:\n",
    "            timestep = args[0]\n",
    "            stored_result = self.storage_func(raw_result)\n",
    "            self.cache_graph.stored_results[self.func.__name__][timestep] = stored_result\n",
    "\n",
    "class CacheEvictingDecorator:\n",
    "    def __init__(self, func: Callable, cache_graph: CacheGraph, storage_func: Union[Callable, None] = None):\n",
    "        self.func = func\n",
    "        self.cache_graph = cache_graph\n",
    "        self.cached_values = cache_graph.caches[func.__name__]\n",
    "        self.storage_func = storage_func\n",
    "        sig = signature(func)\n",
    "        self.single_param_timesteps = 't' in sig.parameters and len(sig.parameters) == 1\n",
    "    \n",
    "    def __call__(self, *args, **kwargs):\n",
    "        frozen_kwargs = frozenset(kwargs.items())\n",
    "        function_call = FunctionCall(self.func.__name__, args, frozen_kwargs)\n",
    "        if self.cache_graph.stack:\n",
    "            self.cache_graph.graph[self.cache_graph.stack[-1]].add(function_call)\n",
    "            self.cache_graph.indegrees[function_call] += 1\n",
    "        if not self.cache_graph.check_if_cached(function_call):\n",
    "            self.cache_graph.stack.append(function_call)\n",
    "            result = self.func(*args, **kwargs)\n",
    "            self.cached_values[(args, frozen_kwargs)] = result\n",
    "            self._store_result(self.storage_func, self.func, args, kwargs, result)\n",
    "            self.cache_graph.stack.pop()\n",
    "        return self.cached_values[(args, frozen_kwargs)]\n",
    "    \n",
    "    def _store_result(self, args: tuple, raw_result: Any):\n",
    "        \"\"\"We might want to store an intermediate result\"\"\"\n",
    "        if self.storage_func is None:\n",
    "            return\n",
    "        if self.single_param_timesteps:\n",
    "            timestep = args[0]\n",
    "            stored_result = self.storage_func(raw_result)\n",
    "            self.cache_graph.stored_results[self.func.__name__][timestep] = stored_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import signature\n",
    "from inspect import signature\n",
    "from functools import wraps\n",
    "\n",
    "class _Cache:\n",
    "    \"\"\"Cache provides controllable memoization for model methods\"\"\"\n",
    "\n",
    "    def __init__(self, func):\n",
    "        self.func = func\n",
    "        self.param_len = len(signature(func).parameters)\n",
    "        self.has_one_param = self.param_len == 1\n",
    "        self._store = dict()\n",
    "        self.__name__ = \"Cache: \" + func.__name__\n",
    "\n",
    "    def __call__(self, *arg):\n",
    "        if arg in self._store:\n",
    "            return self._store[arg]\n",
    "        else:\n",
    "            result = self.func(*arg)\n",
    "            self._store[arg] = result\n",
    "            return result\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"<Cache Function: {self.func.__name__} Size: {len(self._store)}>\"\n",
    "    \n",
    "    def sum(self):\n",
    "        \"\"\"return the sum of all values in the Cache Function\"\"\"\n",
    "        return sum(self._store.values())\n",
    "    \n",
    "    @property\n",
    "    def values(self):\n",
    "        return list(self._store.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Cache provides controllable memoization for model methods'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibonacci(n):\n",
    "    \"\"\"hello\"\"\"\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    return fibonacci(n-1) + fibonacci(n-2)\n",
    "\n",
    "cached_fib = _Cache(fibonacci)\n",
    "cached_fib.__doc__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}