Last active
December 21, 2023 20:10
-
-
Save abahgat/f2275f1d4d24efd89820346bea05265c to your computer and use it in GitHub Desktop.
Advent of Code 2023 Day 20
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "provenance": [], | |
| "collapsed_sections": [ | |
| "0bi6UD_gA4OA" | |
| ], | |
| "authorship_tag": "ABX9TyMUZY1O43fVv/e/AuZkuHVH", | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| }, | |
| "language_info": { | |
| "name": "python" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/abahgat/f2275f1d4d24efd89820346bea05265c/2023day20.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Day 20: Pulse Propagation" | |
| ], | |
| "metadata": { | |
| "id": "DN9A25PF__m0" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Setup" | |
| ], | |
| "metadata": { | |
| "id": "3shlQ2dOAoY1" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "### Sample" | |
| ], | |
| "metadata": { | |
| "id": "hN1ERBynAz-x" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "id": "I1b2WjNq_8mJ" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "sample_loop1000 = \"\"\"broadcaster -> a, b, c\n", | |
| "%a -> b\n", | |
| "%b -> c\n", | |
| "%c -> inv\n", | |
| "&inv -> a\"\"\"\n", | |
| "sample_loop32m = \"\"\"broadcaster -> a\n", | |
| "%a -> inv, con\n", | |
| "&inv -> b\n", | |
| "%b -> con\n", | |
| "&con -> output\"\"\"" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "### Parse" | |
| ], | |
| "metadata": { | |
| "id": "PJmL_R9nA1sw" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from typing import Dict, List, Set\n", | |
| "from dataclasses import dataclass\n", | |
| "from functools import cached_property\n", | |
| "\n", | |
| "@dataclass\n", | |
| "class Graph:\n", | |
| " transitions: Dict[str, List[str]]\n", | |
| " inputs: Dict[str, Set[str]]\n", | |
| " types: Dict[str, str] # Node name to type\n", | |
| "\n", | |
| "def parse(s):\n", | |
| " transitions: Dict[str, List[str]] = {}\n", | |
| " types: Dict[str, str] = {}\n", | |
| " inputs: Dict[str, Set[str]] = defaultdict(set)\n", | |
| " for l in s.splitlines():\n", | |
| " source, dest = l.split(' -> ')\n", | |
| " source_prefix, source_suffix = source[:1], source[1:]\n", | |
| " if source_prefix in ['%', '&']:\n", | |
| " types[source_suffix] = source_prefix\n", | |
| " source = source_suffix\n", | |
| " transitions[source] = dest.split(', ')\n", | |
| " for d in transitions[source]:\n", | |
| " inputs[d].add(source)\n", | |
| " return Graph(transitions, inputs, types)" | |
| ], | |
| "metadata": { | |
| "id": "jLo30rAZAu1L" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "### Input" | |
| ], | |
| "metadata": { | |
| "id": "0bi6UD_gA4OA" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "inputstr = \"\"\"%db -> cq\n", | |
| "%rj -> gp, nd\n", | |
| "%ff -> bk\n", | |
| "%rc -> gp\n", | |
| "%bk -> tv\n", | |
| "%xz -> tf, bn\n", | |
| "%gs -> bn\n", | |
| "%ps -> rs, gp\n", | |
| "%jr -> gp, cg\n", | |
| "&pm -> vf\n", | |
| "%pn -> pp, rt\n", | |
| "%nv -> jr\n", | |
| "%rs -> nv\n", | |
| "%kz -> mj\n", | |
| "%nd -> rc, gp\n", | |
| "%nm -> rt, db\n", | |
| "%dg -> rt, xl\n", | |
| "%vg -> gn\n", | |
| "%hc -> vr\n", | |
| "%ft -> lf, bn\n", | |
| "%mj -> hc, cz\n", | |
| "%vb -> ft\n", | |
| "%qd -> cz, sz\n", | |
| "%pp -> rt\n", | |
| "%cq -> rt, vg\n", | |
| "%sr -> vb\n", | |
| "%lf -> vx, bn\n", | |
| "%lh -> pn, rt\n", | |
| "%ls -> sl, cz\n", | |
| "%tv -> gp, rj\n", | |
| "%tf -> sr, bn\n", | |
| "&mk -> vf\n", | |
| "%bs -> rt, lh\n", | |
| "%vx -> bn, gs\n", | |
| "&bn -> fs, bv, vb, mk, sr, bz, cf\n", | |
| "%rr -> ls\n", | |
| "%bv -> xz\n", | |
| "%hp -> bs, rt\n", | |
| "&pk -> vf\n", | |
| "%cg -> rq\n", | |
| "%gn -> rt, dg\n", | |
| "&cz -> hc, kz, rr, hf, sh\n", | |
| "%sl -> cz, kz\n", | |
| "broadcaster -> sh, nm, ps, fs\n", | |
| "%cf -> bv\n", | |
| "&vf -> rx\n", | |
| "&rt -> pk, xl, nm, vg, db\n", | |
| "%xl -> hp\n", | |
| "%sh -> rr, cz\n", | |
| "%bz -> cf\n", | |
| "%fz -> dn, cz\n", | |
| "&gp -> rs, nv, pm, cg, ff, bk, ps\n", | |
| "%fs -> bz, bn\n", | |
| "&hf -> vf\n", | |
| "%vr -> cz, qd\n", | |
| "%rq -> gp, ff\n", | |
| "%sz -> cz, fz\n", | |
| "%dn -> cz\"\"\"" | |
| ], | |
| "metadata": { | |
| "id": "n17xBur3A6RQ" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Part 1" | |
| ], | |
| "metadata": { | |
| "id": "Vxw5Gp2CzdvB" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from typing import Set, Tuple\n", | |
| "from collections import defaultdict\n", | |
| "from dataclasses import field\n", | |
| "\n", | |
| "@dataclass\n", | |
| "class Pulse:\n", | |
| " source: str\n", | |
| " high: bool\n", | |
| " destination: str\n", | |
| "\n", | |
| " def __str__(self):\n", | |
| " return \" \".join([\n", | |
| " self.source, '-high->' if self.high else '-low->', self.destination])\n", | |
| "\n", | |
| "@dataclass\n", | |
| "class GraphState:\n", | |
| " flip_flop_ons: Set[str] = field(default_factory=lambda: set())\n", | |
| " conj_hi_mem: Dict[str, Set[str]] = field(default_factory=lambda: defaultdict(set))\n", | |
| "\n", | |
| "@dataclass\n", | |
| "class GraphOutcome:\n", | |
| " state: GraphState\n", | |
| " pulses: List[Pulse]\n", | |
| "\n", | |
| "def process_pulse(pulse: Pulse,\n", | |
| " graph: Graph,\n", | |
| " state: GraphState) -> List[Pulse]:\n", | |
| " node = pulse.destination\n", | |
| " send_high: bool = pulse.high\n", | |
| "\n", | |
| " if node not in graph.transitions:\n", | |
| " return []\n", | |
| "\n", | |
| " node_type = graph.types.get(pulse.destination, None)\n", | |
| " if node_type == '%': # Flip-flop\n", | |
| " if pulse.high:\n", | |
| " return []\n", | |
| " if node in state.flip_flop_ons:\n", | |
| " state.flip_flop_ons.remove(node)\n", | |
| " send_high = False\n", | |
| " else:\n", | |
| " state.flip_flop_ons.add(node)\n", | |
| " send_high = True\n", | |
| " elif node_type == '&': # Conjunction\n", | |
| " memory = state.conj_hi_mem[node]\n", | |
| " memory.add(pulse.source) if pulse.high else memory.discard(pulse.source)\n", | |
| " send_high = graph.inputs[node] != memory\n", | |
| "\n", | |
| " return [Pulse(node, send_high, next_node) for next_node in graph.transitions[node]]\n", | |
| "\n", | |
| "def run_graph(graph: Graph, state: GraphState) -> GraphOutcome:\n", | |
| " past_pulses = []\n", | |
| " pending_pulses = [Pulse('button', False, 'broadcaster')]\n", | |
| " while pending_pulses:\n", | |
| " active_pulse = pending_pulses.pop(0)\n", | |
| " new_pulses = process_pulse(active_pulse, graph, state)\n", | |
| " pending_pulses += new_pulses\n", | |
| " past_pulses.append(active_pulse)\n", | |
| " return GraphOutcome(state, past_pulses)\n", | |
| "\n", | |
| "def tally(pulses: List[Pulse]) -> Tuple[int, int]:\n", | |
| " his, los = 0, 0\n", | |
| " for p in pulses:\n", | |
| " if p.high:\n", | |
| " his += 1\n", | |
| " else:\n", | |
| " los += 1\n", | |
| " return (his, los)\n", | |
| "\n", | |
| "def part1(s: str) -> int:\n", | |
| " graph = parse(s)\n", | |
| " state = GraphState()\n", | |
| " totpulses = []\n", | |
| " for _ in range(0, 1000):\n", | |
| " outcome = run_graph(graph, state)\n", | |
| " totpulses.extend(outcome.pulses)\n", | |
| " state = outcome.state\n", | |
| " his, los = tally(totpulses)\n", | |
| " return his * los\n", | |
| "\n", | |
| "outcome = run_graph(parse(sample_loop1000), GraphState())\n", | |
| "print(tally(outcome.pulses))\n", | |
| "\n", | |
| "state = GraphState()\n", | |
| "for i in range(0, 4):\n", | |
| " o = run_graph(parse(sample_loop32m), state)\n", | |
| " for p in o.pulses:\n", | |
| " print(p)\n", | |
| " print()\n", | |
| " print(state)\n", | |
| " print()\n", | |
| "\n", | |
| "print(\"First sample\", part1(sample_loop1000))\n", | |
| "print(\"Second sample\", part1(sample_loop32m))\n", | |
| "print(\"Part 1\", part1(inputstr))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Iu2JYtJi0Cov", | |
| "outputId": "dbda7c69-4ce3-4cec-d375-3852a05549d0" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "(4, 8)\n", | |
| "button -low-> broadcaster\n", | |
| "broadcaster -low-> a\n", | |
| "a -high-> inv\n", | |
| "a -high-> con\n", | |
| "inv -low-> b\n", | |
| "con -high-> output\n", | |
| "b -high-> con\n", | |
| "con -low-> output\n", | |
| "\n", | |
| "GraphState(flip_flop_ons={'a', 'b'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': {'a'}, 'con': {'a', 'b'}}))\n", | |
| "\n", | |
| "button -low-> broadcaster\n", | |
| "broadcaster -low-> a\n", | |
| "a -low-> inv\n", | |
| "a -low-> con\n", | |
| "inv -high-> b\n", | |
| "con -high-> output\n", | |
| "\n", | |
| "GraphState(flip_flop_ons={'b'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': set(), 'con': {'b'}}))\n", | |
| "\n", | |
| "button -low-> broadcaster\n", | |
| "broadcaster -low-> a\n", | |
| "a -high-> inv\n", | |
| "a -high-> con\n", | |
| "inv -low-> b\n", | |
| "con -low-> output\n", | |
| "b -low-> con\n", | |
| "con -high-> output\n", | |
| "\n", | |
| "GraphState(flip_flop_ons={'a'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': {'a'}, 'con': {'a'}}))\n", | |
| "\n", | |
| "button -low-> broadcaster\n", | |
| "broadcaster -low-> a\n", | |
| "a -low-> inv\n", | |
| "a -low-> con\n", | |
| "inv -high-> b\n", | |
| "con -high-> output\n", | |
| "\n", | |
| "GraphState(flip_flop_ons=set(), conj_hi_mem=defaultdict(<class 'set'>, {'inv': set(), 'con': set()}))\n", | |
| "\n", | |
| "First sample 32000000\n", | |
| "Second sample 11687500\n", | |
| "Part 1 680278040\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Part 2\n", | |
| "\n", | |
| "> The final machine responsible for moving the sand down to Island Island has a module attached named rx. The machine turns on when a **single low pulse** is sent to `rx`.\n", | |
| ">\n", | |
| "> Reset all modules to their default states. Waiting for all pulses to be fully handled after each button press, **what is the fewest number of button presses required to deliver a single low pulse to the module named `rx`**?\n", | |
| "\n", | |
| "Graph's too large, it will take too many iterations to run in full. Closed form solution?" | |
| ], | |
| "metadata": { | |
| "id": "9kubHlqDm0FE" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import graphviz as gv\n", | |
| "\n", | |
| "def plot(graph: Graph):\n", | |
| " g = gv.Digraph() # engine='neato'\n", | |
| " for source, destinations in graph.transitions.items():\n", | |
| " for destination in destinations:\n", | |
| " g.edge(source, destination)\n", | |
| " for node, typ in graph.types.items():\n", | |
| " if typ == '&':\n", | |
| " g.node(node, shape='house')\n", | |
| " elif typ == '%':\n", | |
| " g.node(node, shape='triangle')\n", | |
| " return g\n", | |
| "\n", | |
| "plot(parse(inputstr))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 1000 | |
| }, | |
| "id": "R6xnYLp8oVOf", | |
| "outputId": "c9ae0139-b067-4a7f-9f73-8fc69d968e60" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.43.0 (0)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"1572pt\" height=\"1736pt\"\n viewBox=\"0.00 0.00 1572.00 1736.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 1732)\">\n<title>%3</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-1732 1568,-1732 1568,4 -4,4\"/>\n<!-- db -->\n<g id=\"node1\" class=\"node\">\n<title>db</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"161,-1728 122.01,-1693.5 199.99,-1693.5 161,-1728\"/>\n<text text-anchor=\"middle\" x=\"161\" y=\"-1701.3\" font-family=\"Times,serif\" font-size=\"14.00\">db</text>\n</g>\n<!-- cq -->\n<g id=\"node2\" class=\"node\">\n<title>cq</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"161,-1646 123.11,-1611.5 198.89,-1611.5 161,-1646\"/>\n<text text-anchor=\"middle\" x=\"161\" y=\"-1619.3\" font-family=\"Times,serif\" font-size=\"14.00\">cq</text>\n</g>\n<!-- db->cq -->\n<g id=\"edge1\" class=\"edge\">\n<title>db->cq</title>\n<path fill=\"none\" stroke=\"black\" d=\"M161,-1693.21C161,-1683.72 161,-1669.41 161,-1656.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"164.5,-1656.07 161,-1646.07 157.5,-1656.07 164.5,-1656.07\"/>\n</g>\n<!-- vg -->\n<g id=\"node19\" class=\"node\">\n<title>vg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"181,-1564 142.01,-1529.5 219.99,-1529.5 181,-1564\"/>\n<text text-anchor=\"middle\" x=\"181\" y=\"-1537.3\" font-family=\"Times,serif\" font-size=\"14.00\">vg</text>\n</g>\n<!-- cq->vg -->\n<g id=\"edge37\" class=\"edge\">\n<title>cq->vg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M163.7,-1611.21C166.32,-1600.71 170.42,-1584.3 173.98,-1570.1\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"177.41,-1570.81 176.44,-1560.26 170.61,-1569.11 177.41,-1570.81\"/>\n</g>\n<!-- rt -->\n<g id=\"node46\" class=\"node\">\n<title>rt</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"179,-1305.56 152,-1318 125,-1305.56 125.03,-1285.44 178.97,-1285.44 179,-1305.56\"/>\n<text text-anchor=\"middle\" x=\"152\" y=\"-1296.3\" font-family=\"Times,serif\" font-size=\"14.00\">rt</text>\n</g>\n<!-- cq->rt -->\n<g id=\"edge36\" class=\"edge\">\n<title>cq->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M154.08,-1611.43C147.18,-1600.19 137.04,-1581.66 133,-1564 113.44,-1478.51 133.8,-1373.68 145.28,-1326.34\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"148.75,-1326.91 147.78,-1316.36 141.96,-1325.21 148.75,-1326.91\"/>\n</g>\n<!-- rj -->\n<g id=\"node3\" class=\"node\">\n<title>rj</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1368,-508 1335.51,-473.5 1400.49,-473.5 1368,-508\"/>\n<text text-anchor=\"middle\" x=\"1368\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">rj</text>\n</g>\n<!-- nd -->\n<g id=\"node16\" class=\"node\">\n<title>nd</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1368,-426 1329.01,-391.5 1406.99,-391.5 1368,-426\"/>\n<text text-anchor=\"middle\" x=\"1368\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">nd</text>\n</g>\n<!-- rj->nd -->\n<g id=\"edge3\" class=\"edge\">\n<title>rj->nd</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1368,-473.21C1368,-463.72 1368,-449.41 1368,-436.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1371.5,-436.07 1368,-426.07 1364.5,-436.07 1371.5,-436.07\"/>\n</g>\n<!-- gp -->\n<g id=\"node51\" class=\"node\">\n<title>gp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1294,-244.56 1267,-257 1240,-244.56 1240.03,-224.44 1293.97,-224.44 1294,-244.56\"/>\n<text text-anchor=\"middle\" x=\"1267\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">gp</text>\n</g>\n<!-- rj->gp -->\n<g id=\"edge2\" class=\"edge\">\n<title>rj->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1356.92,-473.46C1346.05,-462.54 1329.74,-444.51 1320,-426 1292.03,-372.86 1277.27,-303.19 1270.92,-266.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1274.35,-265.31 1269.28,-256.01 1267.44,-266.44 1274.35,-265.31\"/>\n</g>\n<!-- ff -->\n<g id=\"node4\" class=\"node\">\n<title>ff</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1429,-754 1395.4,-719.5 1462.6,-719.5 1429,-754\"/>\n<text text-anchor=\"middle\" x=\"1429\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">ff</text>\n</g>\n<!-- bk -->\n<g id=\"node6\" class=\"node\">\n<title>bk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1394,-672 1355.01,-637.5 1432.99,-637.5 1394,-672\"/>\n<text text-anchor=\"middle\" x=\"1394\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">bk</text>\n</g>\n<!-- ff->bk -->\n<g id=\"edge4\" class=\"edge\">\n<title>ff->bk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1424.28,-719.21C1419.38,-708.02 1411.55,-690.11 1405.07,-675.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1408.28,-673.9 1401.06,-666.14 1401.86,-676.71 1408.28,-673.9\"/>\n</g>\n<!-- rc -->\n<g id=\"node5\" class=\"node\">\n<title>rc</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1349,-344 1313.81,-309.5 1384.19,-309.5 1349,-344\"/>\n<text text-anchor=\"middle\" x=\"1349\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">rc</text>\n</g>\n<!-- rc->gp -->\n<g id=\"edge5\" class=\"edge\">\n<title>rc->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1337.94,-309.21C1324.72,-296.31 1302.36,-274.49 1286.27,-258.8\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1288.55,-256.13 1278.95,-251.65 1283.66,-261.14 1288.55,-256.13\"/>\n</g>\n<!-- tv -->\n<g id=\"node30\" class=\"node\">\n<title>tv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1394,-590 1358.81,-555.5 1429.19,-555.5 1394,-590\"/>\n<text text-anchor=\"middle\" x=\"1394\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">tv</text>\n</g>\n<!-- bk->tv -->\n<g id=\"edge6\" class=\"edge\">\n<title>bk->tv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1394,-637.21C1394,-627.72 1394,-613.41 1394,-600.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1397.5,-600.07 1394,-590.07 1390.5,-600.07 1397.5,-600.07\"/>\n</g>\n<!-- xz -->\n<g id=\"node7\" class=\"node\">\n<title>xz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"803,-836 765.11,-801.5 840.89,-801.5 803,-836\"/>\n<text text-anchor=\"middle\" x=\"803\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">xz</text>\n</g>\n<!-- tf -->\n<g id=\"node31\" class=\"node\">\n<title>tf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"803,-754 770.51,-719.5 835.49,-719.5 803,-754\"/>\n<text text-anchor=\"middle\" x=\"803\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">tf</text>\n</g>\n<!-- xz->tf -->\n<g id=\"edge7\" class=\"edge\">\n<title>xz->tf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M803,-801.21C803,-791.72 803,-777.41 803,-764.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"806.5,-764.07 803,-754.07 799.5,-764.07 806.5,-764.07\"/>\n</g>\n<!-- bn -->\n<g id=\"node35\" class=\"node\">\n<title>bn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"820,-1146.56 793,-1159 766,-1146.56 766.03,-1126.44 819.97,-1126.44 820,-1146.56\"/>\n<text text-anchor=\"middle\" x=\"793\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">bn</text>\n</g>\n<!-- xz->bn -->\n<g id=\"edge8\" class=\"edge\">\n<title>xz->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M812.05,-828.11C818.76,-839.46 827.36,-856.09 831,-872 851.41,-961.22 818.77,-1069.81 801.98,-1116.65\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"798.65,-1115.59 798.48,-1126.18 805.22,-1118.01 798.65,-1115.59\"/>\n</g>\n<!-- gs -->\n<g id=\"node8\" class=\"node\">\n<title>gs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-262 716.11,-227.5 791.89,-227.5 754,-262\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">gs</text>\n</g>\n<!-- gs->bn -->\n<g id=\"edge9\" class=\"edge\">\n<title>gs->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M735.97,-245.73C688.92,-261.94 566,-312.81 566,-402 566,-978 566,-978 566,-978 566,-1026.36 563.64,-1047.96 598,-1082 640.42,-1124.02 711.86,-1135.84 755.48,-1139.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"755.48,-1142.52 765.68,-1139.64 755.91,-1135.54 755.48,-1142.52\"/>\n</g>\n<!-- ps -->\n<g id=\"node9\" class=\"node\">\n<title>ps</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1087,-1246 1049.11,-1211.5 1124.89,-1211.5 1087,-1246\"/>\n<text text-anchor=\"middle\" x=\"1087\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">ps</text>\n</g>\n<!-- rs -->\n<g id=\"node14\" class=\"node\">\n<title>rs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1179,-1164 1145.4,-1129.5 1212.6,-1129.5 1179,-1164\"/>\n<text text-anchor=\"middle\" x=\"1179\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">rs</text>\n</g>\n<!-- ps->rs -->\n<g id=\"edge10\" class=\"edge\">\n<title>ps->rs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1099.41,-1211.21C1114.89,-1197.75 1141.53,-1174.58 1159.69,-1158.79\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1162.12,-1161.32 1167.37,-1152.11 1157.53,-1156.04 1162.12,-1161.32\"/>\n</g>\n<!-- ps->gp -->\n<g id=\"edge11\" class=\"edge\">\n<title>ps->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1082.49,-1211.39C1078,-1185.51 1078,-1117.09 1078,-1060 1078,-1060 1078,-1060 1078,-402 1078,-349.71 1095.08,-334 1133,-298 1160.24,-272.14 1201.08,-256.19 1230.67,-247.71\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1231.88,-251.01 1240.63,-245.02 1230.06,-244.25 1231.88,-251.01\"/>\n</g>\n<!-- jr -->\n<g id=\"node10\" class=\"node\">\n<title>jr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1194,-1000 1161.51,-965.5 1226.49,-965.5 1194,-1000\"/>\n<text text-anchor=\"middle\" x=\"1194\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">jr</text>\n</g>\n<!-- cg -->\n<g id=\"node40\" class=\"node\">\n<title>cg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1238,-918 1200.11,-883.5 1275.89,-883.5 1238,-918\"/>\n<text text-anchor=\"middle\" x=\"1238\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">cg</text>\n</g>\n<!-- jr->cg -->\n<g id=\"edge13\" class=\"edge\">\n<title>jr->cg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1199.93,-965.21C1206.34,-953.56 1216.76,-934.62 1225.07,-919.51\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1228.17,-921.13 1229.92,-910.68 1222.04,-917.76 1228.17,-921.13\"/>\n</g>\n<!-- jr->gp -->\n<g id=\"edge12\" class=\"edge\">\n<title>jr->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1191.56,-965.45C1185.83,-939.72 1172,-871.62 1172,-814 1172,-814 1172,-814 1172,-402 1172,-343.29 1219,-287.02 1246.89,-258.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1249.52,-261.12 1254.19,-251.61 1244.61,-256.14 1249.52,-261.12\"/>\n</g>\n<!-- pm -->\n<g id=\"node11\" class=\"node\">\n<title>pm</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1088.24,-167.56 1060,-180 1031.76,-167.56 1031.79,-147.44 1088.21,-147.44 1088.24,-167.56\"/>\n<text text-anchor=\"middle\" x=\"1060\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">pm</text>\n</g>\n<!-- vf -->\n<g id=\"node45\" class=\"node\">\n<title>vf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"573,-95.56 546,-108 519,-95.56 519.03,-75.44 572.97,-75.44 573,-95.56\"/>\n<text text-anchor=\"middle\" x=\"546\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">vf</text>\n</g>\n<!-- pm->vf -->\n<g id=\"edge14\" class=\"edge\">\n<title>pm->vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1031.63,-157.14C944.52,-145.27 680.86,-109.37 583.05,-96.05\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"583.41,-92.56 573.03,-94.68 582.47,-99.5 583.41,-92.56\"/>\n</g>\n<!-- pn -->\n<g id=\"node12\" class=\"node\">\n<title>pn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"105,-918 66.01,-883.5 143.99,-883.5 105,-918\"/>\n<text text-anchor=\"middle\" x=\"105\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">pn</text>\n</g>\n<!-- pp -->\n<g id=\"node25\" class=\"node\">\n<title>pp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"67,-836 28.01,-801.5 105.99,-801.5 67,-836\"/>\n<text text-anchor=\"middle\" x=\"67\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">pp</text>\n</g>\n<!-- pn->pp -->\n<g id=\"edge15\" class=\"edge\">\n<title>pn->pp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99.88,-883.21C94.49,-871.88 85.84,-853.66 78.76,-838.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"81.84,-837.08 74.39,-829.55 75.52,-840.09 81.84,-837.08\"/>\n</g>\n<!-- pn->rt -->\n<g id=\"edge16\" class=\"edge\">\n<title>pn->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99.68,-913.79C91.31,-943.42 76,-1004.86 76,-1058 76,-1142 76,-1142 76,-1142 76,-1194.69 111.11,-1248.29 133.6,-1277.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"131.15,-1279.75 140.12,-1285.37 136.61,-1275.37 131.15,-1279.75\"/>\n</g>\n<!-- nv -->\n<g id=\"node13\" class=\"node\">\n<title>nv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1179,-1082 1140.01,-1047.5 1217.99,-1047.5 1179,-1082\"/>\n<text text-anchor=\"middle\" x=\"1179\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">nv</text>\n</g>\n<!-- nv->jr -->\n<g id=\"edge17\" class=\"edge\">\n<title>nv->jr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1181.02,-1047.21C1182.96,-1036.88 1185.97,-1020.83 1188.6,-1006.79\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1192.12,-1007.04 1190.52,-996.57 1185.24,-1005.75 1192.12,-1007.04\"/>\n</g>\n<!-- rs->nv -->\n<g id=\"edge18\" class=\"edge\">\n<title>rs->nv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1179,-1129.21C1179,-1119.72 1179,-1105.41 1179,-1092.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1182.5,-1092.07 1179,-1082.07 1175.5,-1092.07 1182.5,-1092.07\"/>\n</g>\n<!-- kz -->\n<g id=\"node15\" class=\"node\">\n<title>kz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"162,-836 124.11,-801.5 199.89,-801.5 162,-836\"/>\n<text text-anchor=\"middle\" x=\"162\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">kz</text>\n</g>\n<!-- mj -->\n<g id=\"node22\" class=\"node\">\n<title>mj</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"234,-754 192.31,-719.5 275.69,-719.5 234,-754\"/>\n<text text-anchor=\"middle\" x=\"234\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">mj</text>\n</g>\n<!-- kz->mj -->\n<g id=\"edge19\" class=\"edge\">\n<title>kz->mj</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171.71,-801.21C182.95,-788.72 201.72,-767.86 215.72,-752.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"218.46,-754.5 222.55,-744.73 213.26,-749.82 218.46,-754.5\"/>\n</g>\n<!-- nd->rc -->\n<g id=\"edge20\" class=\"edge\">\n<title>nd->rc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1365.44,-391.21C1362.93,-380.64 1359,-364.09 1355.61,-349.82\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1358.98,-348.87 1353.26,-339.95 1352.17,-350.49 1358.98,-348.87\"/>\n</g>\n<!-- nd->gp -->\n<g id=\"edge21\" class=\"edge\">\n<title>nd->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1375.51,-391.38C1388.55,-371.51 1412.23,-328.02 1393,-298 1373.6,-267.71 1333.93,-253.02 1304.26,-246.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.75,-242.56 1294.23,-243.88 1303.27,-249.4 1304.75,-242.56\"/>\n</g>\n<!-- nm -->\n<g id=\"node17\" class=\"node\">\n<title>nm</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"352,-1246 306.51,-1211.5 397.49,-1211.5 352,-1246\"/>\n<text text-anchor=\"middle\" x=\"352\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">nm</text>\n</g>\n<!-- nm->db -->\n<g id=\"edge23\" class=\"edge\">\n<title>nm->db</title>\n<path fill=\"none\" stroke=\"black\" d=\"M348.96,-1244.11C344.84,-1273.15 338,-1328.56 338,-1376 338,-1542 338,-1542 338,-1542 338,-1616.9 250.68,-1666.51 198.7,-1689.4\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"197.26,-1686.21 189.44,-1693.36 200.01,-1692.64 197.26,-1686.21\"/>\n</g>\n<!-- nm->rt -->\n<g id=\"edge22\" class=\"edge\">\n<title>nm->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M335.82,-1234.01C326.94,-1237.83 315.99,-1242.18 306,-1246 266.36,-1261.17 220.27,-1277.85 188.76,-1288.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"187.47,-1285.11 179.06,-1291.56 189.66,-1291.76 187.47,-1285.11\"/>\n</g>\n<!-- dg -->\n<g id=\"node18\" class=\"node\">\n<title>dg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"257,-1400 218.01,-1365.5 295.99,-1365.5 257,-1400\"/>\n<text text-anchor=\"middle\" x=\"257\" y=\"-1373.3\" font-family=\"Times,serif\" font-size=\"14.00\">dg</text>\n</g>\n<!-- dg->rt -->\n<g id=\"edge24\" class=\"edge\">\n<title>dg->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M241.96,-1365.25C224.47,-1352.76 195.42,-1332.01 175.07,-1317.48\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"176.85,-1314.45 166.68,-1311.48 172.78,-1320.14 176.85,-1314.45\"/>\n</g>\n<!-- xl -->\n<g id=\"node47\" class=\"node\">\n<title>xl</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"253,-1246 217.81,-1211.5 288.19,-1211.5 253,-1246\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">xl</text>\n</g>\n<!-- dg->xl -->\n<g id=\"edge25\" class=\"edge\">\n<title>dg->xl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M256.71,-1365.07C256.12,-1342.53 254.74,-1290.13 253.84,-1255.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"257.33,-1255.43 253.57,-1245.52 250.33,-1255.61 257.33,-1255.43\"/>\n</g>\n<!-- gn -->\n<g id=\"node41\" class=\"node\">\n<title>gn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"219,-1482 180.01,-1447.5 257.99,-1447.5 219,-1482\"/>\n<text text-anchor=\"middle\" x=\"219\" y=\"-1455.3\" font-family=\"Times,serif\" font-size=\"14.00\">gn</text>\n</g>\n<!-- vg->gn -->\n<g id=\"edge26\" class=\"edge\">\n<title>vg->gn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M186.12,-1529.21C191.51,-1517.88 200.16,-1499.66 207.24,-1484.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"210.48,-1486.09 211.61,-1475.55 204.16,-1483.08 210.48,-1486.09\"/>\n</g>\n<!-- hc -->\n<g id=\"node20\" class=\"node\">\n<title>hc</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"276,-672 238.11,-637.5 313.89,-637.5 276,-672\"/>\n<text text-anchor=\"middle\" x=\"276\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">hc</text>\n</g>\n<!-- vr -->\n<g id=\"node54\" class=\"node\">\n<title>vr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"316,-590 279.71,-555.5 352.29,-555.5 316,-590\"/>\n<text text-anchor=\"middle\" x=\"316\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">vr</text>\n</g>\n<!-- hc->vr -->\n<g id=\"edge27\" class=\"edge\">\n<title>hc->vr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M281.39,-637.21C287.13,-625.74 296.4,-607.21 303.9,-592.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"307.17,-593.48 308.51,-582.97 300.91,-590.35 307.17,-593.48\"/>\n</g>\n<!-- ft -->\n<g id=\"node21\" class=\"node\">\n<title>ft</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"904,-508 871.51,-473.5 936.49,-473.5 904,-508\"/>\n<text text-anchor=\"middle\" x=\"904\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">ft</text>\n</g>\n<!-- lf -->\n<g id=\"node27\" class=\"node\">\n<title>lf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"923,-426 890.51,-391.5 955.49,-391.5 923,-426\"/>\n<text text-anchor=\"middle\" x=\"923\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">lf</text>\n</g>\n<!-- ft->lf -->\n<g id=\"edge28\" class=\"edge\">\n<title>ft->lf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M906.56,-473.21C909.09,-462.57 913.06,-445.87 916.46,-431.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"919.9,-432.18 918.81,-421.64 913.09,-430.57 919.9,-432.18\"/>\n</g>\n<!-- ft->bn -->\n<g id=\"edge29\" class=\"edge\">\n<title>ft->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M908.04,-503.87C914.39,-533.61 926,-595.21 926,-648 926,-978 926,-978 926,-978 926,-1029.48 908.38,-1042.81 875,-1082 861.74,-1097.57 843.42,-1111.05 827.46,-1121.08\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"825.61,-1118.11 818.88,-1126.29 829.24,-1124.09 825.61,-1118.11\"/>\n</g>\n<!-- mj->hc -->\n<g id=\"edge30\" class=\"edge\">\n<title>mj->hc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M239.66,-719.21C245.69,-707.74 255.42,-689.21 263.29,-674.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"266.59,-675.45 268.14,-664.97 260.39,-672.2 266.59,-675.45\"/>\n</g>\n<!-- cz -->\n<g id=\"node42\" class=\"node\">\n<title>cz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"395,-900.56 368,-913 341,-900.56 341.03,-880.44 394.97,-880.44 395,-900.56\"/>\n<text text-anchor=\"middle\" x=\"368\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">cz</text>\n</g>\n<!-- mj->cz -->\n<g id=\"edge31\" class=\"edge\">\n<title>mj->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M240.37,-748.87C249.18,-770.66 266.67,-809 290,-836 303.01,-851.05 320.57,-864.54 335.74,-874.71\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"334.05,-877.78 344.34,-880.3 337.86,-871.92 334.05,-877.78\"/>\n</g>\n<!-- vb -->\n<g id=\"node23\" class=\"node\">\n<title>vb</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-590 715.01,-555.5 792.99,-555.5 754,-590\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">vb</text>\n</g>\n<!-- vb->ft -->\n<g id=\"edge32\" class=\"edge\">\n<title>vb->ft</title>\n<path fill=\"none\" stroke=\"black\" d=\"M773.92,-555.38C801.56,-540.64 851.43,-514.04 880.74,-498.4\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"882.66,-501.35 889.83,-493.56 879.36,-495.17 882.66,-501.35\"/>\n</g>\n<!-- qd -->\n<g id=\"node24\" class=\"node\">\n<title>qd</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"334,-508 295.01,-473.5 372.99,-473.5 334,-508\"/>\n<text text-anchor=\"middle\" x=\"334\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">qd</text>\n</g>\n<!-- qd->cz -->\n<g id=\"edge33\" class=\"edge\">\n<title>qd->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M342.2,-500.84C348.21,-512.31 356.15,-528.76 361,-544 375.25,-588.77 380,-601.01 380,-648 380,-732 380,-732 380,-732 380,-781.19 374.43,-838.56 370.88,-870.12\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"367.39,-869.82 369.72,-880.16 374.34,-870.62 367.39,-869.82\"/>\n</g>\n<!-- sz -->\n<g id=\"node56\" class=\"node\">\n<title>sz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"334,-426 297.71,-391.5 370.29,-391.5 334,-426\"/>\n<text text-anchor=\"middle\" x=\"334\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">sz</text>\n</g>\n<!-- qd->sz -->\n<g id=\"edge34\" class=\"edge\">\n<title>qd->sz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M334,-473.21C334,-463.72 334,-449.41 334,-436.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"337.5,-436.07 334,-426.07 330.5,-436.07 337.5,-436.07\"/>\n</g>\n<!-- pp->rt -->\n<g id=\"edge35\" class=\"edge\">\n<title>pp->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M61.68,-831.79C53.31,-861.42 38,-922.86 38,-976 38,-1142 38,-1142 38,-1142 38,-1192.54 52.91,-1206.15 84,-1246 94.1,-1258.94 108.03,-1270.53 120.65,-1279.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"118.89,-1282.57 129.12,-1285.35 122.85,-1276.8 118.89,-1282.57\"/>\n</g>\n<!-- sr -->\n<g id=\"node26\" class=\"node\">\n<title>sr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-672 720.4,-637.5 787.6,-637.5 754,-672\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">sr</text>\n</g>\n<!-- sr->vb -->\n<g id=\"edge38\" class=\"edge\">\n<title>sr->vb</title>\n<path fill=\"none\" stroke=\"black\" d=\"M754,-637.21C754,-627.72 754,-613.41 754,-600.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"757.5,-600.07 754,-590.07 750.5,-600.07 757.5,-600.07\"/>\n</g>\n<!-- vx -->\n<g id=\"node34\" class=\"node\">\n<title>vx</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"923,-344 884.01,-309.5 961.99,-309.5 923,-344\"/>\n<text text-anchor=\"middle\" x=\"923\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">vx</text>\n</g>\n<!-- lf->vx -->\n<g id=\"edge39\" class=\"edge\">\n<title>lf->vx</title>\n<path fill=\"none\" stroke=\"black\" d=\"M923,-391.21C923,-381.72 923,-367.41 923,-354.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"926.5,-354.07 923,-344.07 919.5,-354.07 926.5,-354.07\"/>\n</g>\n<!-- lf->bn -->\n<g id=\"edge40\" class=\"edge\">\n<title>lf->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M929.59,-419.31C941.18,-447.68 964,-510.59 964,-566 964,-978 964,-978 964,-978 964,-1030.71 944.84,-1045.31 907,-1082 885.14,-1103.2 854,-1118.32 829.78,-1127.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"828.34,-1124.61 820.21,-1131.4 830.8,-1131.16 828.34,-1124.61\"/>\n</g>\n<!-- lh -->\n<g id=\"node28\" class=\"node\">\n<title>lh</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"139,-1000 103.81,-965.5 174.19,-965.5 139,-1000\"/>\n<text text-anchor=\"middle\" x=\"139\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">lh</text>\n</g>\n<!-- lh->pn -->\n<g id=\"edge41\" class=\"edge\">\n<title>lh->pn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M134.41,-965.21C129.7,-954.12 122.19,-936.45 115.94,-921.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"118.99,-919.98 111.86,-912.14 112.55,-922.71 118.99,-919.98\"/>\n</g>\n<!-- lh->rt -->\n<g id=\"edge42\" class=\"edge\">\n<title>lh->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M136.47,-997.56C135.14,-1008.79 133.66,-1023.16 133,-1036 128.45,-1124.27 141.57,-1229 148.3,-1275.14\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"144.88,-1275.95 149.82,-1285.32 151.8,-1274.92 144.88,-1275.95\"/>\n</g>\n<!-- ls -->\n<g id=\"node29\" class=\"node\">\n<title>ls</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"332,-1082 298.4,-1047.5 365.6,-1047.5 332,-1082\"/>\n<text text-anchor=\"middle\" x=\"332\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">ls</text>\n</g>\n<!-- ls->cz -->\n<g id=\"edge44\" class=\"edge\">\n<title>ls->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M334.36,-1047.37C340,-1022 354.37,-957.34 362.38,-921.27\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"365.8,-922.02 364.56,-911.5 358.97,-920.5 365.8,-922.02\"/>\n</g>\n<!-- sl -->\n<g id=\"node43\" class=\"node\">\n<title>sl</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"294,-1000 260.4,-965.5 327.6,-965.5 294,-1000\"/>\n<text text-anchor=\"middle\" x=\"294\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">sl</text>\n</g>\n<!-- ls->sl -->\n<g id=\"edge43\" class=\"edge\">\n<title>ls->sl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M326.88,-1047.21C321.42,-1035.74 312.62,-1017.21 305.5,-1002.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"308.56,-1000.5 301.11,-992.97 302.24,-1003.51 308.56,-1000.5\"/>\n</g>\n<!-- tv->rj -->\n<g id=\"edge46\" class=\"edge\">\n<title>tv->rj</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1390.49,-555.21C1386.91,-544.19 1381.22,-526.67 1376.45,-512.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1379.76,-510.87 1373.34,-502.44 1373.1,-513.03 1379.76,-510.87\"/>\n</g>\n<!-- tv->gp -->\n<g id=\"edge45\" class=\"edge\">\n<title>tv->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1398.91,-555.47C1416.15,-516.73 1469.8,-380.15 1410,-298 1385.35,-264.14 1337.48,-250.01 1303.94,-244.13\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.46,-240.67 1294.04,-242.56 1303.36,-247.58 1304.46,-240.67\"/>\n</g>\n<!-- tf->sr -->\n<g id=\"edge47\" class=\"edge\">\n<title>tf->sr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M796.39,-719.21C789.08,-707.27 777.09,-687.7 767.73,-672.41\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"770.51,-670.25 762.3,-663.55 764.54,-673.91 770.51,-670.25\"/>\n</g>\n<!-- tf->bn -->\n<g id=\"edge48\" class=\"edge\">\n<title>tf->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M813.77,-743.12C836.64,-767.96 888,-830.79 888,-894 888,-978 888,-978 888,-978 888,-1035.22 843.35,-1090.12 815.27,-1118.99\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"812.44,-1116.88 807.84,-1126.43 817.39,-1121.83 812.44,-1116.88\"/>\n</g>\n<!-- mk -->\n<g id=\"node32\" class=\"node\">\n<title>mk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"832.24,-167.56 804,-180 775.76,-167.56 775.79,-147.44 832.21,-147.44 832.24,-167.56\"/>\n<text text-anchor=\"middle\" x=\"804\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">mk</text>\n</g>\n<!-- mk->vf -->\n<g id=\"edge49\" class=\"edge\">\n<title>mk->vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M775.4,-153.24C727.29,-140.19 630.4,-113.9 579.3,-100.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"579.99,-96.6 569.42,-97.35 578.16,-103.35 579.99,-96.6\"/>\n</g>\n<!-- bs -->\n<g id=\"node33\" class=\"node\">\n<title>bs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"180,-1082 142.11,-1047.5 217.89,-1047.5 180,-1082\"/>\n<text text-anchor=\"middle\" x=\"180\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">bs</text>\n</g>\n<!-- bs->lh -->\n<g id=\"edge51\" class=\"edge\">\n<title>bs->lh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M174.47,-1047.21C168.55,-1035.67 158.98,-1016.98 151.27,-1001.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.2,-999.99 146.53,-992.68 147.97,-1003.18 154.2,-999.99\"/>\n</g>\n<!-- bs->rt -->\n<g id=\"edge50\" class=\"edge\">\n<title>bs->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M176.76,-1079.3C174.93,-1090.57 172.68,-1105.07 171,-1118 163.69,-1174.26 157.28,-1240.65 154.11,-1275.28\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"150.62,-1275.07 153.2,-1285.35 157.59,-1275.71 150.62,-1275.07\"/>\n</g>\n<!-- vx->gs -->\n<g id=\"edge53\" class=\"edge\">\n<title>vx->gs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M900.56,-309.38C869.15,-294.51 812.25,-267.57 779.35,-252\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"780.5,-248.67 769.96,-247.56 777.5,-255 780.5,-248.67\"/>\n</g>\n<!-- vx->bn -->\n<g id=\"edge52\" class=\"edge\">\n<title>vx->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M933.98,-334.42C955.69,-360.29 1002,-422.67 1002,-484 1002,-978 1002,-978 1002,-978 1002,-1031.36 982.49,-1047.24 942,-1082 909.69,-1109.74 862.6,-1125.06 830.05,-1132.88\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"829,-1129.53 820.03,-1135.17 830.55,-1136.36 829,-1129.53\"/>\n</g>\n<!-- bn->vb -->\n<g id=\"edge56\" class=\"edge\">\n<title>bn->vb</title>\n<path fill=\"none\" stroke=\"black\" d=\"M766,-1138.89C728.04,-1135.79 659.44,-1124.28 623,-1082 592.32,-1046.41 604,-1024.99 604,-978 604,-978 604,-978 604,-730 604,-657.48 685.92,-603.67 728.68,-580.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"730.44,-583.56 737.66,-575.8 727.18,-577.36 730.44,-583.56\"/>\n</g>\n<!-- bn->sr -->\n<g id=\"edge58\" class=\"edge\">\n<title>bn->sr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M781.81,-1126.26C762.85,-1102.23 724.56,-1050.3 705,-1000 687.97,-956.21 686,-942.99 686,-896 686,-896 686,-896 686,-812 686,-757.82 718.74,-700.83 738.78,-671.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"741.74,-672.89 744.54,-662.67 735.98,-668.91 741.74,-672.89\"/>\n</g>\n<!-- bn->mk -->\n<g id=\"edge57\" class=\"edge\">\n<title>bn->mk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M820.31,-1137.55C859.11,-1132.82 930.72,-1119.34 978,-1082 1020.23,-1048.65 1040,-1031.81 1040,-978 1040,-978 1040,-978 1040,-320 1040,-226.11 908.91,-184.96 842.13,-170.09\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"842.51,-166.6 832,-167.93 841.05,-173.44 842.51,-166.6\"/>\n</g>\n<!-- bv -->\n<g id=\"node37\" class=\"node\">\n<title>bv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"783,-918 744.01,-883.5 821.99,-883.5 783,-918\"/>\n<text text-anchor=\"middle\" x=\"783\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">bv</text>\n</g>\n<!-- bn->bv -->\n<g id=\"edge55\" class=\"edge\">\n<title>bn->bv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M793.79,-1126.43C795.41,-1095.68 798.51,-1018.35 793,-954 792.18,-944.38 790.6,-933.97 788.94,-924.65\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"792.35,-923.88 787.06,-914.7 785.48,-925.18 792.35,-923.88\"/>\n</g>\n<!-- cf -->\n<g id=\"node44\" class=\"node\">\n<title>cf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"749,-1000 713.81,-965.5 784.19,-965.5 749,-1000\"/>\n<text text-anchor=\"middle\" x=\"749\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">cf</text>\n</g>\n<!-- bn->cf -->\n<g id=\"edge60\" class=\"edge\">\n<title>bn->cf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M789.25,-1126.19C782.02,-1099.56 766.02,-1040.67 756.52,-1005.68\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"759.79,-1004.38 753.79,-995.65 753.04,-1006.21 759.79,-1004.38\"/>\n</g>\n<!-- bz -->\n<g id=\"node49\" class=\"node\">\n<title>bz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"670,-1082 632.11,-1047.5 707.89,-1047.5 670,-1082\"/>\n<text text-anchor=\"middle\" x=\"670\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">bz</text>\n</g>\n<!-- bn->bz -->\n<g id=\"edge59\" class=\"edge\">\n<title>bn->bz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M772.13,-1126.43C750.21,-1112.17 715.81,-1089.79 693.08,-1075.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"694.71,-1071.89 684.41,-1069.38 690.89,-1077.76 694.71,-1071.89\"/>\n</g>\n<!-- fs -->\n<g id=\"node52\" class=\"node\">\n<title>fs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"749,-1246 715.4,-1211.5 782.6,-1211.5 749,-1246\"/>\n<text text-anchor=\"middle\" x=\"749\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">fs</text>\n</g>\n<!-- bn->fs -->\n<g id=\"edge54\" class=\"edge\">\n<title>bn->fs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M789.79,-1157.85C784.2,-1170.81 774.21,-1189.17 765.34,-1202.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"762.44,-1200.97 759.72,-1211.21 768.23,-1204.9 762.44,-1200.97\"/>\n</g>\n<!-- rr -->\n<g id=\"node36\" class=\"node\">\n<title>rr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"382,-1164 348.4,-1129.5 415.6,-1129.5 382,-1164\"/>\n<text text-anchor=\"middle\" x=\"382\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">rr</text>\n</g>\n<!-- rr->ls -->\n<g id=\"edge61\" class=\"edge\">\n<title>rr->ls</title>\n<path fill=\"none\" stroke=\"black\" d=\"M375.26,-1129.21C367.8,-1117.27 355.56,-1097.7 346.01,-1082.41\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"348.74,-1080.18 340.47,-1073.55 342.8,-1083.89 348.74,-1080.18\"/>\n</g>\n<!-- bv->xz -->\n<g id=\"edge62\" class=\"edge\">\n<title>bv->xz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M785.7,-883.21C788.34,-872.64 792.48,-856.09 796.05,-841.82\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"799.48,-842.5 798.51,-831.95 792.69,-840.8 799.48,-842.5\"/>\n</g>\n<!-- hp -->\n<g id=\"node38\" class=\"node\">\n<title>hp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"219,-1164 180.01,-1129.5 257.99,-1129.5 219,-1164\"/>\n<text text-anchor=\"middle\" x=\"219\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">hp</text>\n</g>\n<!-- hp->bs -->\n<g id=\"edge63\" class=\"edge\">\n<title>hp->bs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M213.74,-1129.21C208.18,-1117.81 199.22,-1099.43 191.94,-1084.48\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"194.97,-1082.72 187.44,-1075.26 188.68,-1085.78 194.97,-1082.72\"/>\n</g>\n<!-- hp->rt -->\n<g id=\"edge64\" class=\"edge\">\n<title>hp->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M212.15,-1158.06C200.23,-1185.98 175.65,-1243.58 161.89,-1275.83\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"158.53,-1274.77 157.83,-1285.34 164.97,-1277.52 158.53,-1274.77\"/>\n</g>\n<!-- pk -->\n<g id=\"node39\" class=\"node\">\n<title>pk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"256,-167.56 229,-180 202,-167.56 202.03,-147.44 255.97,-147.44 256,-167.56\"/>\n<text text-anchor=\"middle\" x=\"229\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">pk</text>\n</g>\n<!-- pk->vf -->\n<g id=\"edge65\" class=\"edge\">\n<title>pk->vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M256.03,-155.03C313.33,-142.38 446.97,-112.87 510.82,-98.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"511.8,-102.14 520.81,-96.56 510.29,-95.3 511.8,-102.14\"/>\n</g>\n<!-- rq -->\n<g id=\"node55\" class=\"node\">\n<title>rq</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1429,-836 1392.71,-801.5 1465.29,-801.5 1429,-836\"/>\n<text text-anchor=\"middle\" x=\"1429\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">rq</text>\n</g>\n<!-- cg->rq -->\n<g id=\"edge66\" class=\"edge\">\n<title>cg->rq</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1263.36,-883.38C1299.82,-868.11 1366.65,-840.11 1403.3,-824.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1404.91,-827.89 1412.78,-820.79 1402.2,-821.43 1404.91,-827.89\"/>\n</g>\n<!-- gn->dg -->\n<g id=\"edge68\" class=\"edge\">\n<title>gn->dg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M224.12,-1447.21C229.51,-1435.88 238.16,-1417.66 245.24,-1402.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"248.48,-1404.09 249.61,-1393.55 242.16,-1401.08 248.48,-1404.09\"/>\n</g>\n<!-- gn->rt -->\n<g id=\"edge67\" class=\"edge\">\n<title>gn->rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M214.39,-1447.21C203.69,-1422.11 176.9,-1359.34 162.14,-1324.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"165.3,-1323.24 158.15,-1315.42 158.86,-1325.99 165.3,-1323.24\"/>\n</g>\n<!-- cz->kz -->\n<g id=\"edge70\" class=\"edge\">\n<title>cz->kz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M340.89,-884.16C310.03,-872.88 258.17,-853.65 214,-836 205.59,-832.64 196.47,-828.84 188.26,-825.35\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"189.36,-822.02 178.79,-821.31 186.61,-828.45 189.36,-822.02\"/>\n</g>\n<!-- cz->hc -->\n<g id=\"edge69\" class=\"edge\">\n<title>cz->hc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M356.39,-880.03C347.52,-868.76 335.58,-852.17 328,-836 303.4,-783.49 288.31,-717.05 281.1,-679.46\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"284.47,-678.4 279.2,-669.21 277.58,-679.68 284.47,-678.4\"/>\n</g>\n<!-- cz->rr -->\n<g id=\"edge71\" class=\"edge\">\n<title>cz->rr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M368.96,-912.8C371.45,-956.14 378.08,-1071.66 380.8,-1119.16\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"377.31,-1119.42 381.38,-1129.2 384.3,-1119.02 377.31,-1119.42\"/>\n</g>\n<!-- sh -->\n<g id=\"node48\" class=\"node\">\n<title>sh</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"453,-1246 415.11,-1211.5 490.89,-1211.5 453,-1246\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">sh</text>\n</g>\n<!-- cz->sh -->\n<g id=\"edge73\" class=\"edge\">\n<title>cz->sh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M379.03,-908.39C384.85,-920.09 390.57,-938.16 395,-954 420.68,-1045.75 446.85,-1156.5 453.08,-1201.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"449.61,-1201.94 454.22,-1211.47 456.56,-1201.14 449.61,-1201.94\"/>\n</g>\n<!-- hf -->\n<g id=\"node53\" class=\"node\">\n<title>hf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"538,-736.56 511,-749 484,-736.56 484.03,-716.44 537.97,-716.44 538,-736.56\"/>\n<text text-anchor=\"middle\" x=\"511\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">hf</text>\n</g>\n<!-- cz->hf -->\n<g id=\"edge72\" class=\"edge\">\n<title>cz->hf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M395.23,-884.46C417.98,-875.24 449.84,-859.23 470,-836 489.54,-813.47 500.4,-780.52 505.95,-757.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"509.41,-758.34 508.21,-747.81 502.58,-756.79 509.41,-758.34\"/>\n</g>\n<!-- sl->kz -->\n<g id=\"edge75\" class=\"edge\">\n<title>sl->kz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M285.34,-965.37C263.77,-938.89 207.33,-869.63 178.89,-834.73\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"181.33,-832.19 172.3,-826.64 175.91,-836.61 181.33,-832.19\"/>\n</g>\n<!-- sl->cz -->\n<g id=\"edge74\" class=\"edge\">\n<title>sl->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M303.98,-965.21C315.67,-952.57 335.28,-931.38 349.72,-915.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"352.51,-917.9 356.73,-908.19 347.37,-913.15 352.51,-917.9\"/>\n</g>\n<!-- cf->bv -->\n<g id=\"edge80\" class=\"edge\">\n<title>cf->bv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M753.59,-965.21C758.3,-954.12 765.81,-936.45 772.06,-921.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"775.45,-922.71 776.14,-912.14 769.01,-919.98 775.45,-922.71\"/>\n</g>\n<!-- rx -->\n<g id=\"node59\" class=\"node\">\n<title>rx</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"546\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"546\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">rx</text>\n</g>\n<!-- vf->rx -->\n<g id=\"edge81\" class=\"edge\">\n<title>vf->rx</title>\n<path fill=\"none\" stroke=\"black\" d=\"M546,-75.17C546,-66.92 546,-56.15 546,-46.26\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"549.5,-46.02 546,-36.02 542.5,-46.02 549.5,-46.02\"/>\n</g>\n<!-- rt->db -->\n<g id=\"edge86\" class=\"edge\">\n<title>rt->db</title>\n<path fill=\"none\" stroke=\"black\" d=\"M141.11,-1313.44C120.1,-1338.76 76,-1398.95 76,-1458 76,-1542 76,-1542 76,-1542 76,-1599.82 118.98,-1657.32 143.81,-1685.72\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"141.29,-1688.15 150.58,-1693.25 146.5,-1683.48 141.29,-1688.15\"/>\n</g>\n<!-- rt->nm -->\n<g id=\"edge84\" class=\"edge\">\n<title>rt->nm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M179.21,-1286.76C206.83,-1276.2 250.33,-1260.42 288,-1246 298.55,-1241.96 310.18,-1237.34 320.73,-1233.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"322.25,-1236.54 330.44,-1229.82 319.84,-1229.97 322.25,-1236.54\"/>\n</g>\n<!-- rt->vg -->\n<g id=\"edge85\" class=\"edge\">\n<title>rt->vg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M153.37,-1317.52C156.08,-1349.39 162.63,-1421.6 171,-1482 172.72,-1494.45 175.1,-1508.32 177.1,-1519.38\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"173.69,-1520.15 178.94,-1529.34 180.57,-1518.87 173.69,-1520.15\"/>\n</g>\n<!-- rt->pk -->\n<g id=\"edge82\" class=\"edge\">\n<title>rt->pk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M124.57,-1290.7C101.58,-1282.53 69.21,-1268.05 48,-1246 12.71,-1209.31 0,-1192.91 0,-1142 0,-1142 0,-1142 0,-320 0,-227.57 128.47,-185.53 192.96,-170.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"193.76,-173.65 202.73,-168.01 192.2,-166.82 193.76,-173.65\"/>\n</g>\n<!-- rt->xl -->\n<g id=\"edge83\" class=\"edge\">\n<title>rt->xl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M170.52,-1285.24C187.85,-1272.38 213.7,-1253.18 231.84,-1239.72\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"234.1,-1242.39 240.04,-1233.62 229.93,-1236.77 234.1,-1242.39\"/>\n</g>\n<!-- xl->hp -->\n<g id=\"edge87\" class=\"edge\">\n<title>xl->hp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M248.41,-1211.21C243.7,-1200.12 236.19,-1182.45 229.94,-1167.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"232.99,-1165.98 225.86,-1158.14 226.55,-1168.71 232.99,-1165.98\"/>\n</g>\n<!-- sh->rr -->\n<g id=\"edge88\" class=\"edge\">\n<title>sh->rr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M443.42,-1211.21C432.08,-1198.43 412.96,-1176.89 399.07,-1161.23\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"401.6,-1158.81 392.34,-1153.65 396.36,-1163.46 401.6,-1158.81\"/>\n</g>\n<!-- sh->cz -->\n<g id=\"edge89\" class=\"edge\">\n<title>sh->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M446.96,-1211.47C433.29,-1175.4 404.86,-1053.53 377,-954 374.08,-943.56 370.6,-932.15 368.07,-922.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"371.41,-921.14 365.76,-912.18 364.58,-922.71 371.41,-921.14\"/>\n</g>\n<!-- bz->cf -->\n<g id=\"edge90\" class=\"edge\">\n<title>bz->cf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M680.65,-1047.21C693.47,-1034.24 715.18,-1012.25 730.7,-996.53\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"733.21,-998.97 737.75,-989.39 728.23,-994.05 733.21,-998.97\"/>\n</g>\n<!-- fz -->\n<g id=\"node50\" class=\"node\">\n<title>fz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"393,-344 357.81,-309.5 428.19,-309.5 393,-344\"/>\n<text text-anchor=\"middle\" x=\"393\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">fz</text>\n</g>\n<!-- fz->cz -->\n<g id=\"edge92\" class=\"edge\">\n<title>fz->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M397.59,-339.84C404.8,-369.53 418,-431.07 418,-484 418,-732 418,-732 418,-732 418,-783.53 394.62,-840.33 379.84,-871.11\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"376.66,-869.63 375.38,-880.14 382.94,-872.72 376.66,-869.63\"/>\n</g>\n<!-- dn -->\n<g id=\"node57\" class=\"node\">\n<title>dn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"449,-262 410.01,-227.5 487.99,-227.5 449,-262\"/>\n<text text-anchor=\"middle\" x=\"449\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">dn</text>\n</g>\n<!-- fz->dn -->\n<g id=\"edge91\" class=\"edge\">\n<title>fz->dn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M400.55,-309.21C408.94,-297.23 422.7,-277.57 433.42,-262.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"436.45,-264.03 439.32,-253.83 430.72,-260.02 436.45,-264.03\"/>\n</g>\n<!-- gp->ff -->\n<g id=\"edge97\" class=\"edge\">\n<title>gp->ff</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1294.07,-243.15C1329.89,-248.58 1393.26,-262.76 1434,-298 1473.39,-332.07 1488,-349.92 1488,-402 1488,-568 1488,-568 1488,-568 1488,-622.32 1458.35,-681.04 1441.09,-710.62\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1437.91,-709.11 1435.77,-719.49 1443.91,-712.71 1437.91,-709.11\"/>\n</g>\n<!-- gp->bk -->\n<g id=\"edge98\" class=\"edge\">\n<title>gp->bk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1263.86,-256.02C1258.47,-285.02 1248,-348.2 1248,-402 1248,-486 1248,-486 1248,-486 1248,-554.78 1321.53,-607.53 1364.22,-632.36\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1362.65,-635.49 1373.08,-637.37 1366.1,-629.4 1362.65,-635.49\"/>\n</g>\n<!-- gp->ps -->\n<g id=\"edge99\" class=\"edge\">\n<title>gp->ps</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1245.49,-247.39C1220.13,-255.78 1178.59,-271.81 1151,-298 1113.08,-334 1096,-349.71 1096,-402 1096,-1060 1096,-1060 1096,-1060 1096,-1110.85 1096,-1170.68 1092.83,-1201.44\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1089.36,-1201.01 1091.51,-1211.39 1096.29,-1201.93 1089.36,-1201.01\"/>\n</g>\n<!-- gp->pm -->\n<g id=\"edge95\" class=\"edge\">\n<title>gp->pm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1239.94,-228.2C1201.55,-214.29 1131.46,-188.89 1091.01,-174.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1092,-170.87 1081.41,-170.76 1089.62,-177.45 1092,-170.87\"/>\n</g>\n<!-- gp->nv -->\n<g id=\"edge94\" class=\"edge\">\n<title>gp->nv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1248.34,-248.7C1229.26,-258.4 1199.82,-275.7 1181,-298 1148.29,-336.76 1134,-351.28 1134,-402 1134,-896 1134,-896 1134,-896 1134,-942.99 1139.07,-955.13 1153,-1000 1157.06,-1013.07 1163.29,-1027.09 1168.63,-1038.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1165.59,-1039.82 1173.2,-1047.19 1171.85,-1036.68 1165.59,-1039.82\"/>\n</g>\n<!-- gp->rs -->\n<g id=\"edge93\" class=\"edge\">\n<title>gp->rs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1294.05,-239.96C1341.3,-241.23 1439.96,-249.95 1504,-298 1546.68,-330.03 1564,-348.64 1564,-402 1564,-978 1564,-978 1564,-978 1564,-1130.24 1305.08,-1141.73 1211.91,-1140.94\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1211.69,-1137.44 1201.65,-1140.8 1211.6,-1144.44 1211.69,-1137.44\"/>\n</g>\n<!-- gp->cg -->\n<g id=\"edge96\" class=\"edge\">\n<title>gp->cg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1258.83,-253.31C1243.07,-280.3 1210,-343.86 1210,-402 1210,-732 1210,-732 1210,-732 1210,-783.6 1223.97,-843.12 1232.17,-873.63\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1228.86,-874.79 1234.9,-883.49 1235.61,-872.92 1228.86,-874.79\"/>\n</g>\n<!-- fs->bn -->\n<g id=\"edge101\" class=\"edge\">\n<title>fs->bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M750.15,-1211.21C754.88,-1198.73 765.93,-1177.91 775.83,-1162.36\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"778.83,-1164.18 781.47,-1153.92 773.01,-1160.29 778.83,-1164.18\"/>\n</g>\n<!-- fs->bz -->\n<g id=\"edge100\" class=\"edge\">\n<title>fs->bz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M743.82,-1211.37C731.39,-1185.89 699.64,-1120.78 682.1,-1084.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"685.09,-1082.95 677.56,-1075.5 678.79,-1086.02 685.09,-1082.95\"/>\n</g>\n<!-- hf->vf -->\n<g id=\"edge102\" class=\"edge\">\n<title>hf->vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M512,-716.14C513.94,-688.16 518,-622.89 518,-568 518,-568 518,-568 518,-238 518,-194.27 530.11,-144.49 538.4,-115.53\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"541.78,-116.43 541.25,-105.85 535.07,-114.45 541.78,-116.43\"/>\n</g>\n<!-- vr->qd -->\n<g id=\"edge104\" class=\"edge\">\n<title>vr->qd</title>\n<path fill=\"none\" stroke=\"black\" d=\"M318.43,-555.21C320.78,-544.78 324.43,-528.51 327.62,-514.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"331.04,-515.09 329.82,-504.57 324.21,-513.56 331.04,-515.09\"/>\n</g>\n<!-- vr->cz -->\n<g id=\"edge103\" class=\"edge\">\n<title>vr->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M319.05,-587.14C328.04,-643.51 354.41,-808.83 364.25,-870.47\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"360.8,-871.08 365.83,-880.41 367.71,-869.98 360.8,-871.08\"/>\n</g>\n<!-- rq->ff -->\n<g id=\"edge106\" class=\"edge\">\n<title>rq->ff</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1429,-801.21C1429,-791.72 1429,-777.41 1429,-764.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1432.5,-764.07 1429,-754.07 1425.5,-764.07 1432.5,-764.07\"/>\n</g>\n<!-- rq->gp -->\n<g id=\"edge105\" class=\"edge\">\n<title>rq->gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1441.29,-801.18C1467.39,-776.94 1526,-715.23 1526,-650 1526,-650 1526,-650 1526,-402 1526,-349.08 1509.43,-330.93 1468,-298 1419.93,-259.8 1347.69,-246.76 1304.17,-242.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.3,-238.8 1294.02,-241.37 1303.65,-245.77 1304.3,-238.8\"/>\n</g>\n<!-- sz->cz -->\n<g id=\"edge107\" class=\"edge\">\n<title>sz->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M317.39,-410.39C274.61,-428.03 164,-481.81 164,-566 164,-650 164,-650 164,-650 164,-696.99 162.54,-711.7 183,-754 193.56,-775.83 235.88,-821.09 255,-836 278.28,-854.15 308.12,-869.18 331.28,-879.39\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"330.19,-882.73 340.76,-883.46 332.96,-876.3 330.19,-882.73\"/>\n</g>\n<!-- sz->fz -->\n<g id=\"edge108\" class=\"edge\">\n<title>sz->fz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M341.96,-391.21C350.95,-379.02 365.81,-358.86 377.19,-343.44\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"380.29,-345.12 383.41,-335 374.66,-340.97 380.29,-345.12\"/>\n</g>\n<!-- dn->cz -->\n<g id=\"edge109\" class=\"edge\">\n<title>dn->cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M450.48,-260.96C452.54,-291.82 456,-351.33 456,-402 456,-732 456,-732 456,-732 456,-788.17 414.64,-843.46 388.63,-872.68\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"385.91,-870.47 381.75,-880.21 391.08,-875.19 385.91,-870.47\"/>\n</g>\n<!-- broadcaster -->\n<g id=\"node58\" class=\"node\">\n<title>broadcaster</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"632\" cy=\"-1300\" rx=\"51.19\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"632\" y=\"-1296.3\" font-family=\"Times,serif\" font-size=\"14.00\">broadcaster</text>\n</g>\n<!-- broadcaster->ps -->\n<g id=\"edge78\" class=\"edge\">\n<title>broadcaster->ps</title>\n<path fill=\"none\" stroke=\"black\" d=\"M677.71,-1291.47C770.26,-1276.21 977.67,-1242.02 1056.13,-1229.09\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1057.03,-1232.49 1066.32,-1227.41 1055.89,-1225.58 1057.03,-1232.49\"/>\n</g>\n<!-- broadcaster->nm -->\n<g id=\"edge77\" class=\"edge\">\n<title>broadcaster->nm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M587.7,-1290.75C541.73,-1281.69 468.01,-1265.77 406,-1246 397.27,-1243.22 387.95,-1239.65 379.56,-1236.2\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"380.81,-1232.92 370.23,-1232.26 378.08,-1239.37 380.81,-1232.92\"/>\n</g>\n<!-- broadcaster->sh -->\n<g id=\"edge76\" class=\"edge\">\n<title>broadcaster->sh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M600.41,-1285.76C566,-1271.34 511.56,-1248.54 479.36,-1235.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"480.31,-1231.65 469.74,-1231.01 477.61,-1238.11 480.31,-1231.65\"/>\n</g>\n<!-- broadcaster->fs -->\n<g id=\"edge79\" class=\"edge\">\n<title>broadcaster->fs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M655.68,-1283.82C676.52,-1270.46 706.64,-1251.15 726.98,-1238.12\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"729.03,-1240.96 735.56,-1232.61 725.26,-1235.06 729.03,-1240.96\"/>\n</g>\n</g>\n</svg>\n", | |
| "text/plain": [ | |
| "<graphviz.graphs.Digraph at 0x7c481bb7e110>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 5 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "* Graph made of separate components (independent entry and exit points), ending in $pk, mk, pm, hf$.\n", | |
| "* They all have to receive `high` for $vf$ to send `lo` to $rx$.\n", | |
| "* They can get to looping states of independent lengths.\n", | |
| "* If each component loops state in $a, b, c, d$ iterations, $rx$ will flip in $LCM(a,b,c,d)$\n", | |
| "\n", | |
| "Does this behave like a binary adder? Is loop length function of how many flip flop nodes in the component?\n", | |
| "\n", | |
| "* Each flip flop triggers the following one\n", | |
| "* When the top conditional is triggered, it feeds back to flip flops and resets them\n", | |
| "\n", | |
| "Node | Bits\n", | |
| "-----|------\n", | |
| "$hf$ | 12\n", | |
| "$pk$ | 11\n", | |
| "$mk$ | 12?\n", | |
| "$pm$ | 12\n", | |
| "\n", | |
| "Maybe knowing something more of electric circuits would make this solvable by eyeballing?" | |
| ], | |
| "metadata": { | |
| "id": "bFdj5j0MwAy0" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from math import gcd\n", | |
| "\n", | |
| "def part2(s: str) -> int:\n", | |
| " graph = parse(s)\n", | |
| " state = GraphState()\n", | |
| " watches = ['hf', 'pk', 'mk', 'pm']\n", | |
| " loop_periods = {}\n", | |
| " i = 1\n", | |
| " while True:\n", | |
| " outcome = run_graph(graph, state)\n", | |
| " state = outcome.state\n", | |
| " for p in outcome.pulses:\n", | |
| " if p.source in watches and p.high and p.source not in loop_periods:\n", | |
| " loop_periods[p.source] = i\n", | |
| " if len(loop_periods) == 4:\n", | |
| " break\n", | |
| " i += 1\n", | |
| " return loop_periods\n", | |
| "\n", | |
| "periods = part2(inputstr)\n", | |
| "print(periods)\n", | |
| "lcm = 1\n", | |
| "for i in periods.values():\n", | |
| " lcm = lcm * i // gcd(lcm, i)\n", | |
| "print(lcm)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "7aP5oktf1H6S", | |
| "outputId": "fa5feb54-4a5a-4fe6-caf5-2068e8d0f093" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "{'pm': 3881, 'mk': 3889, 'hf': 4013, 'pk': 4021}\n", | |
| "243548140870057\n" | |
| ] | |
| } | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment