{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Control Flow Graph\n", "\n", "The code in this notebook helps with obtaining the control flow graph of python functions." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "**Prerequisites**\n", "\n", "* This notebook needs some understanding on advanced concepts in Python, notably \n", " * classes" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Control Flow Graph\n", "\n", "The class `PyCFG` allows one to obtain the control flow graph.\n", "\n", "```Python\n", "from ControlFlow import gen_cfg, to_graph\n", "cfg = gen_cfg(inspect.getsource(my_function))\n", "to_graph(cfg)\n", "```" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.469452Z", "iopub.status.busy": "2022-01-11T09:40:27.468757Z", "iopub.status.idle": "2022-01-11T09:40:27.606777Z", "shell.execute_reply": "2022-01-11T09:40:27.607174Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import bookutils" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.611408Z", "iopub.status.busy": "2022-01-11T09:40:27.610477Z", "iopub.status.idle": "2022-01-11T09:40:27.612937Z", "shell.execute_reply": "2022-01-11T09:40:27.613824Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from bookutils import print_content" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.618561Z", "iopub.status.busy": "2022-01-11T09:40:27.617693Z", "iopub.status.idle": "2022-01-11T09:40:27.619848Z", "shell.execute_reply": "2022-01-11T09:40:27.620365Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import ast\n", "import re" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.624125Z", "iopub.status.busy": "2022-01-11T09:40:27.623556Z", "iopub.status.idle": "2022-01-11T09:40:27.628277Z", "shell.execute_reply": "2022-01-11T09:40:27.628899Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from graphviz import Source, Digraph" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Registry" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.633877Z", "iopub.status.busy": "2022-01-11T09:40:27.633179Z", "iopub.status.idle": "2022-01-11T09:40:27.635304Z", "shell.execute_reply": "2022-01-11T09:40:27.635719Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "REGISTRY_IDX = 0" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.639583Z", "iopub.status.busy": "2022-01-11T09:40:27.638939Z", "iopub.status.idle": "2022-01-11T09:40:27.640646Z", "shell.execute_reply": "2022-01-11T09:40:27.641247Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "REGISTRY = {}" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.645910Z", "iopub.status.busy": "2022-01-11T09:40:27.645029Z", "iopub.status.idle": "2022-01-11T09:40:27.647335Z", "shell.execute_reply": "2022-01-11T09:40:27.647985Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def get_registry_idx():\n", " global REGISTRY_IDX\n", " v = REGISTRY_IDX\n", " REGISTRY_IDX += 1\n", " return v" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.652357Z", "iopub.status.busy": "2022-01-11T09:40:27.651659Z", "iopub.status.idle": "2022-01-11T09:40:27.653682Z", "shell.execute_reply": "2022-01-11T09:40:27.654136Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def reset_registry():\n", " global REGISTRY_IDX\n", " global REGISTRY\n", " REGISTRY_IDX = 0\n", " REGISTRY = {}" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.658025Z", "iopub.status.busy": "2022-01-11T09:40:27.657482Z", "iopub.status.idle": "2022-01-11T09:40:27.659399Z", "shell.execute_reply": "2022-01-11T09:40:27.659919Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def register_node(node):\n", " node.rid = get_registry_idx()\n", " REGISTRY[node.rid] = node" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.664991Z", "iopub.status.busy": "2022-01-11T09:40:27.664303Z", "iopub.status.idle": "2022-01-11T09:40:27.666300Z", "shell.execute_reply": "2022-01-11T09:40:27.666717Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def get_registry():\n", " return dict(REGISTRY)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### CFGNode\n", "We start with the `CFGNode` representing each node in the control flow graph.\n", "\\todo{Augmented and annotated assignments (`a += 1`), (`a:int = 1`)}." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.677873Z", "iopub.status.busy": "2022-01-11T09:40:27.676933Z", "iopub.status.idle": "2022-01-11T09:40:27.679453Z", "shell.execute_reply": "2022-01-11T09:40:27.679928Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class CFGNode(dict):\n", " def __init__(self, parents=[], ast=None):\n", " assert type(parents) is list\n", " register_node(self)\n", " self.parents = parents\n", " self.ast_node = ast\n", " self.update_children(parents) # requires self.rid\n", " self.children = []\n", " self.calls = []\n", "\n", " def i(self):\n", " return str(self.rid)\n", "\n", " def update_children(self, parents):\n", " for p in parents:\n", " p.add_child(self)\n", "\n", " def add_child(self, c):\n", " if c not in self.children:\n", " self.children.append(c)\n", "\n", " def lineno(self):\n", " return self.ast_node.lineno if hasattr(self.ast_node, 'lineno') else 0\n", "\n", " def __str__(self):\n", " return \"id:%d line[%d] parents: %s : %s\" % (\n", " self.rid, self.lineno(), str([p.rid for p in self.parents]),\n", " self.source())\n", "\n", " def __repr__(self):\n", " return str(self)\n", "\n", " def __eq__(self, other):\n", " return self.rid == other.rid\n", "\n", " def __neq__(self, other):\n", " return self.rid != other.rid\n", "\n", " def set_parents(self, p):\n", " self.parents = p\n", "\n", " def add_parent(self, p):\n", " if p not in self.parents:\n", " self.parents.append(p)\n", "\n", " def add_parents(self, ps):\n", " for p in ps:\n", " self.add_parent(p)\n", "\n", " def add_calls(self, func):\n", " self.calls.append(func)\n", "\n", " def source(self):\n", " return ast.unparse(self.ast_node).strip()\n", "\n", " def to_json(self):\n", " return {\n", " 'id': self.rid,\n", " 'parents': [p.rid for p in self.parents],\n", " 'children': [c.rid for c in self.children],\n", " 'calls': self.calls,\n", " 'at': self.lineno(),\n", " 'ast': self.source()\n", " }" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### PyCFG\n", "\n", "Next, the `PyCFG` class which is responsible for parsing, and holding the graph." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.685743Z", "iopub.status.busy": "2022-01-11T09:40:27.684914Z", "iopub.status.idle": "2022-01-11T09:40:27.687214Z", "shell.execute_reply": "2022-01-11T09:40:27.687702Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG:\n", " def __init__(self):\n", " self.founder = CFGNode(\n", " parents=[], ast=ast.parse('start').body[0]) # sentinel\n", " self.founder.ast_node.lineno = 0\n", " self.functions = {}\n", " self.functions_node = {}" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.691884Z", "iopub.status.busy": "2022-01-11T09:40:27.691352Z", "iopub.status.idle": "2022-01-11T09:40:27.693300Z", "shell.execute_reply": "2022-01-11T09:40:27.693849Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def parse(self, src):\n", " return ast.parse(src)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.699576Z", "iopub.status.busy": "2022-01-11T09:40:27.698831Z", "iopub.status.idle": "2022-01-11T09:40:27.700875Z", "shell.execute_reply": "2022-01-11T09:40:27.701293Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def walk(self, node, myparents):\n", " fname = \"on_%s\" % node.__class__.__name__.lower()\n", " if hasattr(self, fname):\n", " fn = getattr(self, fname)\n", " v = fn(node, myparents)\n", " return v\n", " else:\n", " return myparents" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.707468Z", "iopub.status.busy": "2022-01-11T09:40:27.706787Z", "iopub.status.idle": "2022-01-11T09:40:27.708406Z", "shell.execute_reply": "2022-01-11T09:40:27.708964Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_module(self, node, myparents):\n", " \"\"\"\n", " Module(stmt* body)\n", " \"\"\"\n", " # each time a statement is executed unconditionally, make a link from\n", " # the result to next statement\n", " p = myparents\n", " for n in node.body:\n", " p = self.walk(n, p)\n", " return p" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.715691Z", "iopub.status.busy": "2022-01-11T09:40:27.714889Z", "iopub.status.idle": "2022-01-11T09:40:27.716703Z", "shell.execute_reply": "2022-01-11T09:40:27.717383Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_augassign(self, node, myparents):\n", " \"\"\"\n", " AugAssign(expr target, operator op, expr value)\n", " \"\"\"\n", " p = [CFGNode(parents=myparents, ast=node)]\n", " p = self.walk(node.value, p)\n", "\n", " return p" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.722165Z", "iopub.status.busy": "2022-01-11T09:40:27.721438Z", "iopub.status.idle": "2022-01-11T09:40:27.723475Z", "shell.execute_reply": "2022-01-11T09:40:27.723886Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_annassign(self, node, myparents):\n", " \"\"\"\n", " AnnAssign(expr target, expr annotation, expr? value, int simple)\n", " \"\"\"\n", " p = [CFGNode(parents=myparents, ast=node)]\n", " p = self.walk(node.value, p)\n", "\n", " return p" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.729758Z", "iopub.status.busy": "2022-01-11T09:40:27.728730Z", "iopub.status.idle": "2022-01-11T09:40:27.731007Z", "shell.execute_reply": "2022-01-11T09:40:27.731456Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_assign(self, node, myparents):\n", " \"\"\"\n", " Assign(expr* targets, expr value)\n", " \"\"\"\n", " if len(node.targets) > 1:\n", " raise NotImplemented('Parallel assignments')\n", "\n", " p = [CFGNode(parents=myparents, ast=node)]\n", " p = self.walk(node.value, p)\n", "\n", " return p" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.736357Z", "iopub.status.busy": "2022-01-11T09:40:27.735407Z", "iopub.status.idle": "2022-01-11T09:40:27.737638Z", "shell.execute_reply": "2022-01-11T09:40:27.738659Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_pass(self, node, myparents):\n", " return [CFGNode(parents=myparents, ast=node)]" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.745623Z", "iopub.status.busy": "2022-01-11T09:40:27.744337Z", "iopub.status.idle": "2022-01-11T09:40:27.747145Z", "shell.execute_reply": "2022-01-11T09:40:27.748154Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_break(self, node, myparents):\n", " parent = myparents[0]\n", " while not hasattr(parent, 'exit_nodes'):\n", " # we have ordered parents\n", " parent = parent.parents[0]\n", "\n", " assert hasattr(parent, 'exit_nodes')\n", " p = CFGNode(parents=myparents, ast=node)\n", "\n", " # make the break one of the parents of label node.\n", " parent.exit_nodes.append(p)\n", "\n", " # break doesn't have immediate children\n", " return []" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.755017Z", "iopub.status.busy": "2022-01-11T09:40:27.754091Z", "iopub.status.idle": "2022-01-11T09:40:27.756929Z", "shell.execute_reply": "2022-01-11T09:40:27.756244Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_continue(self, node, myparents):\n", " parent = myparents[0]\n", " while not hasattr(parent, 'exit_nodes'):\n", " # we have ordered parents\n", " parent = parent.parents[0]\n", " assert hasattr(parent, 'exit_nodes')\n", " p = CFGNode(parents=myparents, ast=node)\n", "\n", " # make continue one of the parents of the original test node.\n", " parent.add_parent(p)\n", "\n", " # return the parent because a continue is not the parent\n", " # for the just next node\n", " return []" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.767491Z", "iopub.status.busy": "2022-01-11T09:40:27.766306Z", "iopub.status.idle": "2022-01-11T09:40:27.768942Z", "shell.execute_reply": "2022-01-11T09:40:27.769688Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_for(self, node, myparents):\n", " # node.target in node.iter: node.body\n", " # The For loop in python (no else) can be translated\n", " # as follows:\n", " # \n", " # for a in iterator:\n", " # mystatements\n", " #\n", " # __iv = iter(iterator)\n", " # while __iv.__length_hint() > 0:\n", " # a = next(__iv)\n", " # mystatements\n", "\n", " init_node = CFGNode(parents=myparents,\n", " ast=ast.parse('__iv = iter(%s)' % ast.unparse(node.iter).strip()).body[0])\n", " ast.copy_location(init_node.ast_node, node.iter)\n", "\n", " _test_node = CFGNode(\n", " parents=[init_node],\n", " ast=ast.parse('_for: __iv.__length__hint__() > 0').body[0])\n", " ast.copy_location(_test_node.ast_node, node)\n", "\n", " # we attach the label node here so that break can find it.\n", " _test_node.exit_nodes = []\n", " test_node = self.walk(node.iter, [_test_node])\n", "\n", " extract_node = CFGNode(parents=test_node,\n", " ast=ast.parse('%s = next(__iv)' % ast.unparse(node.target).strip()).body[0])\n", " ast.copy_location(extract_node.ast_node, node.iter)\n", "\n", " # now we evaluate the body, one at a time.\n", " p1 = [extract_node]\n", " for n in node.body:\n", " p1 = self.walk(n, p1)\n", "\n", " # the test node is looped back at the end of processing.\n", " _test_node.add_parents(p1)\n", "\n", " return _test_node.exit_nodes + test_node" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.779045Z", "iopub.status.busy": "2022-01-11T09:40:27.777640Z", "iopub.status.idle": "2022-01-11T09:40:27.780555Z", "shell.execute_reply": "2022-01-11T09:40:27.781442Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_while(self, node, myparents):\n", " # For a while, the earliest parent is the node.test\n", " _test_node = CFGNode(\n", " parents=myparents,\n", " ast=ast.parse(\n", " '_while: %s' % ast.unparse(node.test).strip()).body[0])\n", " ast.copy_location(_test_node.ast_node, node.test)\n", " _test_node.exit_nodes = []\n", " test_node = self.walk(node.test, [_test_node])\n", "\n", " # we attach the label node here so that break can find it.\n", "\n", " # now we evaluate the body, one at a time.\n", " assert len(test_node) == 1\n", " p1 = test_node\n", " for n in node.body:\n", " p1 = self.walk(n, p1)\n", "\n", " # the test node is looped back at the end of processing.\n", " _test_node.add_parents(p1)\n", "\n", " # link label node back to the condition.\n", " return _test_node.exit_nodes + test_node" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.791887Z", "iopub.status.busy": "2022-01-11T09:40:27.790780Z", "iopub.status.idle": "2022-01-11T09:40:27.793616Z", "shell.execute_reply": "2022-01-11T09:40:27.794476Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_if(self, node, myparents):\n", " _test_node = CFGNode(\n", " parents=myparents,\n", " ast=ast.parse(\n", " '_if: %s' % ast.unparse(node.test).strip()).body[0])\n", " ast.copy_location(_test_node.ast_node, node.test)\n", " test_node = self.walk(node.test, [ _test_node])\n", " assert len(test_node) == 1\n", " g1 = test_node\n", " for n in node.body:\n", " g1 = self.walk(n, g1)\n", " g2 = test_node\n", " for n in node.orelse:\n", " g2 = self.walk(n, g2)\n", " return g1 + g2" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.800804Z", "iopub.status.busy": "2022-01-11T09:40:27.799758Z", "iopub.status.idle": "2022-01-11T09:40:27.803802Z", "shell.execute_reply": "2022-01-11T09:40:27.802349Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_binop(self, node, myparents):\n", " left = self.walk(node.left, myparents)\n", " right = self.walk(node.right, left)\n", " return right" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.810501Z", "iopub.status.busy": "2022-01-11T09:40:27.809506Z", "iopub.status.idle": "2022-01-11T09:40:27.812199Z", "shell.execute_reply": "2022-01-11T09:40:27.812997Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_compare(self, node, myparents):\n", " left = self.walk(node.left, myparents)\n", " right = self.walk(node.comparators[0], left)\n", " return right" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.819694Z", "iopub.status.busy": "2022-01-11T09:40:27.818506Z", "iopub.status.idle": "2022-01-11T09:40:27.821200Z", "shell.execute_reply": "2022-01-11T09:40:27.821854Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_unaryop(self, node, myparents):\n", " return self.walk(node.operand, myparents)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.831764Z", "iopub.status.busy": "2022-01-11T09:40:27.830508Z", "iopub.status.idle": "2022-01-11T09:40:27.833075Z", "shell.execute_reply": "2022-01-11T09:40:27.833672Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_call(self, node, myparents):\n", " def get_func(node):\n", " if type(node.func) is ast.Name:\n", " mid = node.func.id\n", " elif type(node.func) is ast.Attribute:\n", " mid = node.func.attr\n", " elif type(node.func) is ast.Call:\n", " mid = get_func(node.func)\n", " else:\n", " raise Exception(str(type(node.func)))\n", " return mid\n", " #mid = node.func.value.id\n", "\n", " p = myparents\n", " for a in node.args:\n", " p = self.walk(a, p)\n", " mid = get_func(node)\n", " myparents[0].add_calls(mid)\n", "\n", " # these need to be unlinked later if our module actually defines these\n", " # functions. Otherwsise we may leave them around.\n", " # during a call, the direct child is not the next\n", " # statement in text.\n", " for c in p:\n", " c.calllink = 0\n", " return p" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.839645Z", "iopub.status.busy": "2022-01-11T09:40:27.838575Z", "iopub.status.idle": "2022-01-11T09:40:27.840745Z", "shell.execute_reply": "2022-01-11T09:40:27.841315Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_expr(self, node, myparents):\n", " p = [CFGNode(parents=myparents, ast=node)]\n", " return self.walk(node.value, p)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.851843Z", "iopub.status.busy": "2022-01-11T09:40:27.850633Z", "iopub.status.idle": "2022-01-11T09:40:27.853081Z", "shell.execute_reply": "2022-01-11T09:40:27.853737Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_return(self, node, myparents):\n", " if type(myparents) is tuple:\n", " parent = myparents[0][0]\n", " else:\n", " parent = myparents[0]\n", "\n", " val_node = self.walk(node.value, myparents)\n", " # on return look back to the function definition.\n", " while not hasattr(parent, 'return_nodes'):\n", " parent = parent.parents[0]\n", " assert hasattr(parent, 'return_nodes')\n", "\n", " p = CFGNode(parents=val_node, ast=node)\n", "\n", " # make the break one of the parents of label node.\n", " parent.return_nodes.append(p)\n", "\n", " # return doesnt have immediate children\n", " return []" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.865440Z", "iopub.status.busy": "2022-01-11T09:40:27.864323Z", "iopub.status.idle": "2022-01-11T09:40:27.866804Z", "shell.execute_reply": "2022-01-11T09:40:27.867681Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def on_functiondef(self, node, myparents):\n", " # a function definition does not actually continue the thread of\n", " # control flow\n", " # name, args, body, decorator_list, returns\n", " fname = node.name\n", " args = node.args\n", " returns = node.returns\n", "\n", " enter_node = CFGNode(\n", " parents=[],\n", " ast=ast.parse('enter: %s(%s)' % (node.name, ', '.join(\n", " [a.arg for a in node.args.args]))).body[0]) # sentinel\n", " enter_node.calleelink = True\n", " ast.copy_location(enter_node.ast_node, node)\n", " exit_node = CFGNode(\n", " parents=[],\n", " ast=ast.parse('exit: %s(%s)' % (node.name, ', '.join(\n", " [a.arg for a in node.args.args]))).body[0]) # sentinel\n", " exit_node.fn_exit_node = True\n", " ast.copy_location(exit_node.ast_node, node)\n", " enter_node.return_nodes = [] # sentinel\n", "\n", " p = [enter_node]\n", " for n in node.body:\n", " p = self.walk(n, p)\n", "\n", " for n in p:\n", " if n not in enter_node.return_nodes:\n", " enter_node.return_nodes.append(n)\n", "\n", " for n in enter_node.return_nodes:\n", " exit_node.add_parent(n)\n", "\n", " self.functions[fname] = [enter_node, exit_node]\n", " self.functions_node[enter_node.lineno()] = fname\n", "\n", " return myparents" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.875278Z", "iopub.status.busy": "2022-01-11T09:40:27.874100Z", "iopub.status.idle": "2022-01-11T09:40:27.876613Z", "shell.execute_reply": "2022-01-11T09:40:27.877307Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def get_defining_function(self, node):\n", " if node.lineno() in self.functions_node:\n", " return self.functions_node[node.lineno()]\n", " if not node.parents:\n", " self.functions_node[node.lineno()] = ''\n", " return ''\n", " val = self.get_defining_function(node.parents[0])\n", " self.functions_node[node.lineno()] = val\n", " return val" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.888015Z", "iopub.status.busy": "2022-01-11T09:40:27.886846Z", "iopub.status.idle": "2022-01-11T09:40:27.889565Z", "shell.execute_reply": "2022-01-11T09:40:27.890120Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def link_functions(self):\n", " for nid, node in REGISTRY.items():\n", " if node.calls:\n", " for calls in node.calls:\n", " if calls in self.functions:\n", " enter, exit = self.functions[calls]\n", " enter.add_parent(node)\n", " if node.children:\n", " # # until we link the functions up, the node\n", " # # should only have succeeding node in text as\n", " # # children.\n", " # assert(len(node.children) == 1)\n", " # passn = node.children[0]\n", " # # We require a single pass statement after every\n", " # # call (which means no complex expressions)\n", " # assert(type(passn.ast_node) == ast.Pass)\n", "\n", " # # unlink the call statement\n", " assert node.calllink > -1\n", " node.calllink += 1\n", " for i in node.children:\n", " i.add_parent(exit)\n", " # passn.set_parents([exit])\n", " # ast.copy_location(exit.ast_node, passn.ast_node)\n", "\n", " # #for c in passn.children: c.add_parent(exit)\n", " # #passn.ast_node = exit.ast_node" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.896255Z", "iopub.status.busy": "2022-01-11T09:40:27.895059Z", "iopub.status.idle": "2022-01-11T09:40:27.897963Z", "shell.execute_reply": "2022-01-11T09:40:27.897506Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def update_functions(self):\n", " for nid, node in REGISTRY.items():\n", " _n = self.get_defining_function(node)" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.902405Z", "iopub.status.busy": "2022-01-11T09:40:27.901654Z", "iopub.status.idle": "2022-01-11T09:40:27.903773Z", "shell.execute_reply": "2022-01-11T09:40:27.904386Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def update_children(self):\n", " for nid, node in REGISTRY.items():\n", " for p in node.parents:\n", " p.add_child(node)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "button": false, "execution": { "iopub.execute_input": "2022-01-11T09:40:27.910618Z", "iopub.status.busy": "2022-01-11T09:40:27.909741Z", "iopub.status.idle": "2022-01-11T09:40:27.911960Z", "shell.execute_reply": "2022-01-11T09:40:27.912582Z" }, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class PyCFG(PyCFG):\n", " def gen_cfg(self, src):\n", " \"\"\"\n", " >>> i = PyCFG()\n", " >>> i.walk(\"100\")\n", " 5\n", " \"\"\"\n", " node = self.parse(src)\n", " nodes = self.walk(node, [self.founder])\n", " self.last_node = CFGNode(parents=nodes, ast=ast.parse('stop').body[0])\n", " ast.copy_location(self.last_node.ast_node, self.founder.ast_node)\n", " self.update_children()\n", " self.update_functions()\n", " self.link_functions()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Supporting Functions" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.919176Z", "iopub.status.busy": "2022-01-11T09:40:27.918159Z", "iopub.status.idle": "2022-01-11T09:40:27.920727Z", "shell.execute_reply": "2022-01-11T09:40:27.921417Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def compute_dominator(cfg, start=0, key='parents'):\n", " dominator = {}\n", " dominator[start] = {start}\n", " all_nodes = set(cfg.keys())\n", " rem_nodes = all_nodes - {start}\n", " for n in rem_nodes:\n", " dominator[n] = all_nodes\n", "\n", " c = True\n", " while c:\n", " c = False\n", " for n in rem_nodes:\n", " pred_n = cfg[n][key]\n", " doms = [dominator[p] for p in pred_n]\n", " i = set.intersection(*doms) if doms else set()\n", " v = {n} | i\n", " if dominator[n] != v:\n", " c = True\n", " dominator[n] = v\n", " return dominator" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.926276Z", "iopub.status.busy": "2022-01-11T09:40:27.925639Z", "iopub.status.idle": "2022-01-11T09:40:27.927877Z", "shell.execute_reply": "2022-01-11T09:40:27.928409Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def compute_flow(pythonfile):\n", " cfg, first, last = get_cfg(pythonfile)\n", " return cfg, compute_dominator(\n", " cfg, start=first), compute_dominator(\n", " cfg, start=last, key='children')" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.934359Z", "iopub.status.busy": "2022-01-11T09:40:27.933315Z", "iopub.status.idle": "2022-01-11T09:40:27.935386Z", "shell.execute_reply": "2022-01-11T09:40:27.935762Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def gen_cfg(fnsrc, remove_start_stop=True):\n", " reset_registry()\n", " cfg = PyCFG()\n", " cfg.gen_cfg(fnsrc)\n", " cache = dict(REGISTRY)\n", " if remove_start_stop:\n", " return {\n", " k: cache[k]\n", " for k in cache if cache[k].source() not in {'start', 'stop'}\n", " }\n", " else:\n", " return cache" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.943083Z", "iopub.status.busy": "2022-01-11T09:40:27.942445Z", "iopub.status.idle": "2022-01-11T09:40:27.944537Z", "shell.execute_reply": "2022-01-11T09:40:27.945218Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def get_cfg(src):\n", " reset_registry()\n", " cfg = PyCFG()\n", " cfg.gen_cfg(src)\n", " cache = dict(REGISTRY)\n", " g = {}\n", " for k, v in cache.items():\n", " j = v.to_json()\n", " at = j['at']\n", " parents_at = [cache[p].to_json()['at'] for p in j['parents']]\n", " children_at = [cache[c].to_json()['at'] for c in j['children']]\n", " if at not in g:\n", " g[at] = {'parents': set(), 'children': set()}\n", " # remove dummy nodes\n", " ps = set([p for p in parents_at if p != at])\n", " cs = set([c for c in children_at if c != at])\n", " g[at]['parents'] |= ps\n", " g[at]['children'] |= cs\n", " if v.calls:\n", " g[at]['calls'] = v.calls\n", " g[at]['function'] = cfg.functions_node[v.lineno()]\n", " return (g, cfg.founder.ast_node.lineno, cfg.last_node.ast_node.lineno)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.963331Z", "iopub.status.busy": "2022-01-11T09:40:27.961951Z", "iopub.status.idle": "2022-01-11T09:40:27.965176Z", "shell.execute_reply": "2022-01-11T09:40:27.966174Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def to_graph(cache, arcs=[]):\n", " graph = Digraph(comment='Control Flow Graph')\n", " colors = {0: 'blue', 1: 'red'}\n", " kind = {0: 'T', 1: 'F'}\n", " cov_lines = set(i for i, j in arcs)\n", " for nid, cnode in cache.items():\n", " lineno = cnode.lineno()\n", " shape, peripheries = 'oval', '1'\n", " if isinstance(cnode.ast_node, ast.AnnAssign):\n", " if cnode.ast_node.target.id in {'_if', '_for', '_while'}:\n", " shape = 'diamond'\n", " elif cnode.ast_node.target.id in {'enter', 'exit'}:\n", " shape, peripheries = 'oval', '2'\n", " else:\n", " shape = 'rectangle'\n", " graph.node(cnode.i(), \"%d: %s\" % (lineno, unhack(cnode.source())),\n", " shape=shape, peripheries=peripheries)\n", " for pn in cnode.parents:\n", " plineno = pn.lineno()\n", " if hasattr(pn, 'calllink') and pn.calllink > 0 and not hasattr(\n", " cnode, 'calleelink'):\n", " graph.edge(pn.i(), cnode.i(), style='dotted', weight=100)\n", " continue\n", "\n", " if arcs:\n", " if (plineno, lineno) in arcs:\n", " graph.edge(pn.i(), cnode.i(), color='green')\n", " elif plineno == lineno and lineno in cov_lines:\n", " graph.edge(pn.i(), cnode.i(), color='green')\n", " # child is exit and parent is covered\n", " elif hasattr(cnode, 'fn_exit_node') and plineno in cov_lines:\n", " graph.edge(pn.i(), cnode.i(), color='green')\n", " # parent is exit and one of its parents is covered.\n", " elif hasattr(pn, 'fn_exit_node') and len(\n", " set(n.lineno() for n in pn.parents) | cov_lines) > 0:\n", " graph.edge(pn.i(), cnode.i(), color='green')\n", " # child is a callee (has calleelink) and one of the parents is covered.\n", " elif plineno in cov_lines and hasattr(cnode, 'calleelink'):\n", " graph.edge(pn.i(), cnode.i(), color='green')\n", " else:\n", " graph.edge(pn.i(), cnode.i(), color='red')\n", " else:\n", " order = {c.i(): i for i, c in enumerate(pn.children)}\n", " if len(order) < 2:\n", " graph.edge(pn.i(), cnode.i())\n", " else:\n", " o = order[cnode.i()]\n", " graph.edge(pn.i(), cnode.i(), color=colors[o], label=kind[o])\n", " return graph" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.972690Z", "iopub.status.busy": "2022-01-11T09:40:27.971666Z", "iopub.status.idle": "2022-01-11T09:40:27.973685Z", "shell.execute_reply": "2022-01-11T09:40:27.974321Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def unhack(v):\n", " for i in ['if', 'while', 'for', 'elif']:\n", " v = re.sub(r'^_%s:' % i, '%s:' % i, v)\n", " return v" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Examples" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### check_triangle" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.982974Z", "iopub.status.busy": "2022-01-11T09:40:27.981872Z", "iopub.status.idle": "2022-01-11T09:40:27.984501Z", "shell.execute_reply": "2022-01-11T09:40:27.985335Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def check_triangle(a, b, c):\n", " if a == b:\n", " if a == c:\n", " if b == c:\n", " return \"Equilateral\"\n", " else:\n", " return \"Isosceles\"\n", " else:\n", " return \"Isosceles\"\n", " else:\n", " if b != c:\n", " if a == c:\n", " return \"Isosceles\"\n", " else:\n", " return \"Scalene\"\n", " else:\n", " return \"Isosceles\"" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:27.990934Z", "iopub.status.busy": "2022-01-11T09:40:27.989926Z", "iopub.status.idle": "2022-01-11T09:40:27.992509Z", "shell.execute_reply": "2022-01-11T09:40:27.993053Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import inspect" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:28.006692Z", "iopub.status.busy": "2022-01-11T09:40:28.005754Z", "iopub.status.idle": "2022-01-11T09:40:28.607270Z", "shell.execute_reply": "2022-01-11T09:40:28.607676Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: check_triangle(a, b, c)\n", "\n", "\n", "\n", "3\n", "\n", "2: if: a == b\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: check_triangle(a, b, c)\n", "\n", "\n", "\n", "6\n", "\n", "5: return 'Equilateral'\n", "\n", "\n", "\n", "6->2\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "7: return 'Isosceles'\n", "\n", "\n", "\n", "7->2\n", "\n", "\n", "\n", "\n", "\n", "8\n", "\n", "9: return 'Isosceles'\n", "\n", "\n", "\n", "8->2\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "13: return 'Isosceles'\n", "\n", "\n", "\n", "11->2\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "15: return 'Scalene'\n", "\n", "\n", "\n", "12->2\n", "\n", "\n", "\n", "\n", "\n", "13\n", "\n", "17: return 'Isosceles'\n", "\n", "\n", "\n", "13->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "3: if: a == c\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "T\n", "\n", "\n", "\n", "9\n", "\n", "11: if: b != c\n", "\n", "\n", "\n", "3->9\n", "\n", "\n", "F\n", "\n", "\n", "\n", "4->8\n", "\n", "\n", "F\n", "\n", "\n", "\n", "5\n", "\n", "4: if: b == c\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "T\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "T\n", "\n", "\n", "\n", "5->7\n", "\n", "\n", "F\n", "\n", "\n", "\n", "9->13\n", "\n", "\n", "F\n", "\n", "\n", "\n", "10\n", "\n", "12: if: a == c\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10->12\n", "\n", "\n", "F\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(check_triangle)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### cgi_decode\n", "\n", "Note that we do not yet support _augmented assignments_: i.e assignments such as `+=`" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:28.614902Z", "iopub.status.busy": "2022-01-11T09:40:28.614363Z", "iopub.status.idle": "2022-01-11T09:40:28.616214Z", "shell.execute_reply": "2022-01-11T09:40:28.616746Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def cgi_decode(s):\n", " hex_values = {\n", " '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n", " '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n", " 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n", " 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n", " }\n", "\n", " t = \"\"\n", " i = 0\n", " while i < len(s):\n", " c = s[i]\n", " if c == '+':\n", " t += ' '\n", " elif c == '%':\n", " digit_high, digit_low = s[i + 1], s[i + 2]\n", " i += 2\n", " if digit_high in hex_values and digit_low in hex_values:\n", " v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", " t += chr(v)\n", " else:\n", " raise ValueError(\"Invalid encoding\")\n", " else:\n", " t += c\n", " i += 1\n", " return t" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:28.624054Z", "iopub.status.busy": "2022-01-11T09:40:28.619799Z", "iopub.status.idle": "2022-01-11T09:40:29.048871Z", "shell.execute_reply": "2022-01-11T09:40:29.049484Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: cgi_decode(s)\n", "\n", "\n", "\n", "3\n", "\n", "2: hex_values = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15, 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: cgi_decode(s)\n", "\n", "\n", "\n", "18\n", "\n", "26: return t\n", "\n", "\n", "\n", "18->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "9: t = ''\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "\n", "\n", "\n", "5\n", "\n", "10: i = 0\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "11: while: i < len(s)\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "6->18\n", "\n", "\n", "F\n", "\n", "\n", "\n", "7\n", "\n", "12: c = s[i]\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "T\n", "\n", "\n", "\n", "17\n", "\n", "25: i += 1\n", "\n", "\n", "\n", "17->6\n", "\n", "\n", "\n", "\n", "\n", "8\n", "\n", "13: if: c == '+'\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "14: t += ' '\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10\n", "\n", "15: if: c == '%'\n", "\n", "\n", "\n", "8->10\n", "\n", "\n", "F\n", "\n", "\n", "\n", "9->17\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "16: (digit_high, digit_low) = (s[i + 1], s[i + 2])\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "T\n", "\n", "\n", "\n", "16\n", "\n", "24: t += c\n", "\n", "\n", "\n", "10->16\n", "\n", "\n", "F\n", "\n", "\n", "\n", "12\n", "\n", "17: i += 2\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "\n", "18: if: digit_high in hex_values and digit_low in hex_values\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "13->17\n", "\n", "\n", "F\n", "\n", "\n", "\n", "14\n", "\n", "19: v = hex_values[digit_high] * 16 + hex_values[digit_low]\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "T\n", "\n", "\n", "\n", "15\n", "\n", "20: t += chr(v)\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "15->17\n", "\n", "\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(cgi_decode)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### gcd" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:29.055288Z", "iopub.status.busy": "2022-01-11T09:40:29.054755Z", "iopub.status.idle": "2022-01-11T09:40:29.056339Z", "shell.execute_reply": "2022-01-11T09:40:29.056718Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def gcd(a, b):\n", " if a\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: gcd(a, b)\n", "\n", "\n", "\n", "3\n", "\n", "2: if: a < b\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: gcd(a, b)\n", "\n", "\n", "\n", "11\n", "\n", "11: return a\n", "\n", "\n", "\n", "11->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "3: c: int = a\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "T\n", "\n", "\n", "\n", "7\n", "\n", "7: while: b != 0\n", "\n", "\n", "\n", "3->7\n", "\n", "\n", "F\n", "\n", "\n", "\n", "5\n", "\n", "4: a: int = b\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "5: b: int = c\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "F\n", "\n", "\n", "\n", "8\n", "\n", "8: c: int = a\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10\n", "\n", "10: b: int = c % b\n", "\n", "\n", "\n", "10->7\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "9: a: int = b\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(gcd)))" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:29.480556Z", "iopub.status.busy": "2022-01-11T09:40:29.479626Z", "iopub.status.idle": "2022-01-11T09:40:29.482080Z", "shell.execute_reply": "2022-01-11T09:40:29.481512Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def compute_gcd(x, y):\n", " if x > y:\n", " small = y\n", " else:\n", " small = x\n", " for i in range(1, small+1):\n", " if((x % i == 0) and (y % i == 0)):\n", " gcd = i\n", "\n", " return gcd" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:29.488637Z", "iopub.status.busy": "2022-01-11T09:40:29.487853Z", "iopub.status.idle": "2022-01-11T09:40:29.898316Z", "shell.execute_reply": "2022-01-11T09:40:29.898703Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: compute_gcd(x, y)\n", "\n", "\n", "\n", "3\n", "\n", "2: if: x > y\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: compute_gcd(x, y)\n", "\n", "\n", "\n", "11\n", "\n", "10: return gcd\n", "\n", "\n", "\n", "11->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "3: small = y\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "T\n", "\n", "\n", "\n", "5\n", "\n", "5: small = x\n", "\n", "\n", "\n", "3->5\n", "\n", "\n", "F\n", "\n", "\n", "\n", "6\n", "\n", "6: __iv = iter(range(1, small + 1))\n", "\n", "\n", "\n", "4->6\n", "\n", "\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "6: for: __iv.__length__hint__() > 0\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "\n", "\n", "\n", "7->11\n", "\n", "\n", "F\n", "\n", "\n", "\n", "8\n", "\n", "6: i = next(__iv)\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10\n", "\n", "8: gcd = i\n", "\n", "\n", "\n", "10->7\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "7: if: x % i == 0 and y % i == 0\n", "\n", "\n", "\n", "9->7\n", "\n", "\n", "F\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "T\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(compute_gcd)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### fib\n", "\n", "Note that the *for-loop* requires additional massaging. While we show the labels correctly, the *comparison node* needs to be extracted. Hence, the representation is not accurate." ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:29.903426Z", "iopub.status.busy": "2022-01-11T09:40:29.902889Z", "iopub.status.idle": "2022-01-11T09:40:29.904469Z", "shell.execute_reply": "2022-01-11T09:40:29.904857Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def fib(n,):\n", " ls = [0, 1]\n", " for i in range(n-2):\n", " ls.append(ls[-1] + ls[-2])\n", " return ls" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:29.910185Z", "iopub.status.busy": "2022-01-11T09:40:29.909599Z", "iopub.status.idle": "2022-01-11T09:40:30.321004Z", "shell.execute_reply": "2022-01-11T09:40:30.321452Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: fib(n)\n", "\n", "\n", "\n", "3\n", "\n", "2: ls = [0, 1]\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: fib(n)\n", "\n", "\n", "\n", "8\n", "\n", "5: return ls\n", "\n", "\n", "\n", "8->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "3: __iv = iter(range(n - 2))\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "\n", "\n", "\n", "5\n", "\n", "3: for: __iv.__length__hint__() > 0\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "5->8\n", "\n", "\n", "F\n", "\n", "\n", "\n", "6\n", "\n", "3: i = next(__iv)\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "T\n", "\n", "\n", "\n", "7\n", "\n", "4: ls.append(ls[-1] + ls[-2])\n", "\n", "\n", "\n", "7->5\n", "\n", "\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(fib)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "#### quad_solver" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.327719Z", "iopub.status.busy": "2022-01-11T09:40:30.327181Z", "iopub.status.idle": "2022-01-11T09:40:30.328833Z", "shell.execute_reply": "2022-01-11T09:40:30.329207Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def quad_solver(a, b, c):\n", " discriminant = b^2 - 4*a*c\n", " r1, r2 = 0, 0\n", " i1, i2 = 0, 0\n", " if discriminant >= 0:\n", " droot = math.sqrt(discriminant)\n", " r1 = (-b + droot) / (2*a)\n", " r2 = (-b - droot) / (2*a)\n", " else:\n", " droot = math.sqrt(-1 * discriminant)\n", " droot_ = droot/(2*a)\n", " r1, i1 = -b/(2*a), droot_\n", " r2, i2 = -b/(2*a), -droot_\n", " if i1 == 0 and i2 == 0:\n", " return (r1, r2)\n", " return ((r1,i1), (r2,i2))" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.338030Z", "iopub.status.busy": "2022-01-11T09:40:30.335833Z", "iopub.status.idle": "2022-01-11T09:40:30.745436Z", "shell.execute_reply": "2022-01-11T09:40:30.745831Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "\n", "1: enter: quad_solver(a, b, c)\n", "\n", "\n", "\n", "3\n", "\n", "2: discriminant = b ^ 2 - 4 * a * c\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "\n", "1: exit: quad_solver(a, b, c)\n", "\n", "\n", "\n", "15\n", "\n", "15: return (r1, r2)\n", "\n", "\n", "\n", "15->2\n", "\n", "\n", "\n", "\n", "\n", "16\n", "\n", "16: return ((r1, i1), (r2, i2))\n", "\n", "\n", "\n", "16->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "3: (r1, r2) = (0, 0)\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "\n", "\n", "\n", "5\n", "\n", "4: (i1, i2) = (0, 0)\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "5: if: discriminant >= 0\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "6: droot = math.sqrt(discriminant)\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "T\n", "\n", "\n", "\n", "10\n", "\n", "10: droot = math.sqrt(-1 * discriminant)\n", "\n", "\n", "\n", "6->10\n", "\n", "\n", "F\n", "\n", "\n", "\n", "8\n", "\n", "7: r1 = (-b + droot) / (2 * a)\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "8: r2 = (-b - droot) / (2 * a)\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "14\n", "\n", "14: if: i1 == 0 and i2 == 0\n", "\n", "\n", "\n", "9->14\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "11: droot_ = droot / (2 * a)\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "12: (r1, i1) = (-b / (2 * a), droot_)\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "\n", "13: (r2, i2) = (-b / (2 * a), -droot_)\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "T\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "F\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_graph(gen_cfg(inspect.getsource(quad_solver)))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Call Graph\n", "### Install: Pyan Static Call Graph Lifter" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.749751Z", "iopub.status.busy": "2022-01-11T09:40:30.749142Z", "iopub.status.idle": "2022-01-11T09:40:30.750853Z", "shell.execute_reply": "2022-01-11T09:40:30.751222Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import os" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.754380Z", "iopub.status.busy": "2022-01-11T09:40:30.753859Z", "iopub.status.idle": "2022-01-11T09:40:30.899545Z", "shell.execute_reply": "2022-01-11T09:40:30.899958Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import networkx as nx # type: ignore" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Call Graph Helpers" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.903562Z", "iopub.status.busy": "2022-01-11T09:40:30.902950Z", "iopub.status.idle": "2022-01-11T09:40:30.904448Z", "shell.execute_reply": "2022-01-11T09:40:30.904994Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import shutil" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.908907Z", "iopub.status.busy": "2022-01-11T09:40:30.908250Z", "iopub.status.idle": "2022-01-11T09:40:30.910611Z", "shell.execute_reply": "2022-01-11T09:40:30.910997Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "PYAN = 'pyan3' if shutil.which('pyan3') is not None else 'pyan'\n", "\n", "if shutil.which(PYAN) is None:\n", " # If installed from pypi, pyan may still be missing\n", " os.system('pip install \"git+https://github.com/uds-se/pyan#egg=pyan\"')\n", " PYAN = 'pyan3' if shutil.which('pyan3') is not None else 'pyan'\n", "\n", "assert shutil.which(PYAN) is not None" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.914932Z", "iopub.status.busy": "2022-01-11T09:40:30.914406Z", "iopub.status.idle": "2022-01-11T09:40:30.915939Z", "shell.execute_reply": "2022-01-11T09:40:30.916370Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def construct_callgraph(code, name=\"callgraph\"):\n", " file_name = name + \".py\"\n", " with open(file_name, 'w') as f:\n", " f.write(code)\n", " cg_file = name + '.dot'\n", " os.system(f'{PYAN} {file_name} --uses --defines --colored --grouped --annotated --dot > {cg_file}')" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.919805Z", "iopub.status.busy": "2022-01-11T09:40:30.919295Z", "iopub.status.idle": "2022-01-11T09:40:30.920877Z", "shell.execute_reply": "2022-01-11T09:40:30.921250Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def callgraph(code, name=\"callgraph\"):\n", " if not os.path.isfile(name + '.dot'):\n", " construct_callgraph(code, name)\n", " return Source.from_file(name + '.dot')" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.924670Z", "iopub.status.busy": "2022-01-11T09:40:30.924157Z", "iopub.status.idle": "2022-01-11T09:40:30.925907Z", "shell.execute_reply": "2022-01-11T09:40:30.926293Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def get_callgraph(code, name=\"callgraph\"):\n", " if not os.path.isfile(name + '.dot'):\n", " construct_callgraph(code, name)\n", " return nx.drawing.nx_pydot.read_dot(name + '.dot')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Example: Maze\n", "\n", "To provide a meaningful example where you can easily change the code complexity and target location, we generate the maze source code from the maze provided as string. This example is loosely based on an old [blog post](https://feliam.wordpress.com/2010/10/07/the-symbolic-maze/) on symbolic execution by Felipe Andres Manzano (Quick shout-out!).\n", "\n", "You simply specify the maze as a string. Like so." ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.929342Z", "iopub.status.busy": "2022-01-11T09:40:30.928744Z", "iopub.status.idle": "2022-01-11T09:40:30.930334Z", "shell.execute_reply": "2022-01-11T09:40:30.930881Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "maze_string = \"\"\"\n", "+-+-----+\n", "|X| |\n", "| | --+ |\n", "| | | |\n", "| +-- | |\n", "| |#|\n", "+-----+-+\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Each character in `maze_string` represents a tile. For each tile, a tile-function is generated. \n", "* If the current tile is \"benign\" (` `), the tile-function corresponding to the next input character (D, U, L, R) is called. Unexpected input characters are ignored. If no more input characters are left, it returns \"VALID\" and the current maze state.\n", "* If the current tile is a \"trap\" (`+`,`|`,`-`), it returns \"INVALID\" and the current maze state.\n", "* If the current tile is the \"target\" (`#`), it returns \"SOLVED\" and the current maze state.\n", "\n", "The code is generated using the function `generate_maze_code`. " ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.934283Z", "iopub.status.busy": "2022-01-11T09:40:30.933730Z", "iopub.status.idle": "2022-01-11T09:40:30.935698Z", "shell.execute_reply": "2022-01-11T09:40:30.936151Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "def maze(s: str) -> str:\n", " return \"\" # Will be overwritten by exec()" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.939569Z", "iopub.status.busy": "2022-01-11T09:40:30.938969Z", "iopub.status.idle": "2022-01-11T09:40:30.940475Z", "shell.execute_reply": "2022-01-11T09:40:30.941029Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "def target_tile() -> str:\n", " return ' ' # Will be overwritten by exec()" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.944657Z", "iopub.status.busy": "2022-01-11T09:40:30.944004Z", "iopub.status.idle": "2022-01-11T09:40:30.945791Z", "shell.execute_reply": "2022-01-11T09:40:30.946294Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def generate_print_maze(maze_string):\n", " return \"\"\"\n", "def print_maze(out, row, col):\n", " output = out +\"\\\\n\"\n", " c_row = 0\n", " c_col = 0\n", " for c in list(\\\"\\\"\\\"%s\\\"\\\"\\\"):\n", " if c == '\\\\n':\n", " c_row += 1\n", " c_col = 0\n", " output += \"\\\\n\"\n", " else:\n", " if c_row == row and c_col == col: output += \"X\"\n", " elif c == \"X\": output += \" \"\n", " else: output += c\n", " c_col += 1\n", " return output\n", "\"\"\" % maze_string" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.950469Z", "iopub.status.busy": "2022-01-11T09:40:30.949691Z", "iopub.status.idle": "2022-01-11T09:40:30.951747Z", "shell.execute_reply": "2022-01-11T09:40:30.952127Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def generate_trap_tile(row, col):\n", " return \"\"\"\n", "def tile_%d_%d(input, index):\n", " try: HTMLParser().feed(input)\n", " except: pass\n", " return print_maze(\"INVALID\", %d, %d)\n", "\"\"\" % (row, col, row, col)" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.956534Z", "iopub.status.busy": "2022-01-11T09:40:30.955937Z", "iopub.status.idle": "2022-01-11T09:40:30.957491Z", "shell.execute_reply": "2022-01-11T09:40:30.957925Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def generate_good_tile(c, row, col):\n", " code = \"\"\"\n", "def tile_%d_%d(input, index):\n", " if (index == len(input)): return print_maze(\"VALID\", %d, %d)\n", " elif input[index] == 'L': return tile_%d_%d(input, index + 1)\n", " elif input[index] == 'R': return tile_%d_%d(input, index + 1)\n", " elif input[index] == 'U': return tile_%d_%d(input, index + 1)\n", " elif input[index] == 'D': return tile_%d_%d(input, index + 1)\n", " else : return tile_%d_%d(input, index + 1)\n", "\"\"\" % (row, col, row, col,\n", " row, col - 1, \n", " row, col + 1, \n", " row - 1, col, \n", " row + 1, col,\n", " row, col)\n", "\n", " if c == \"X\":\n", " code += \"\"\"\n", "def maze(input):\n", " return tile_%d_%d(list(input), 0)\n", "\"\"\" % (row, col)\n", "\n", " return code" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.961232Z", "iopub.status.busy": "2022-01-11T09:40:30.960663Z", "iopub.status.idle": "2022-01-11T09:40:30.962133Z", "shell.execute_reply": "2022-01-11T09:40:30.962567Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def generate_target_tile(row, col):\n", " return \"\"\"\n", "def tile_%d_%d(input, index):\n", " return print_maze(\"SOLVED\", %d, %d)\n", "\n", "def target_tile():\n", " return \"tile_%d_%d\"\n", "\"\"\" % (row, col, row, col, row, col)" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.967290Z", "iopub.status.busy": "2022-01-11T09:40:30.966772Z", "iopub.status.idle": "2022-01-11T09:40:30.968443Z", "shell.execute_reply": "2022-01-11T09:40:30.968876Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def generate_maze_code(maze, name=\"maze\"):\n", " row = 0\n", " col = 0\n", " code = generate_print_maze(maze)\n", "\n", " for c in list(maze):\n", " if c == '\\n':\n", " row += 1\n", " col = 0\n", " else:\n", " if c == \"-\" or c == \"+\" or c == \"|\":\n", " code += generate_trap_tile(row, col)\n", " elif c == \" \" or c == \"X\":\n", " code += generate_good_tile(c, row, col)\n", " elif c == \"#\":\n", " code += generate_target_tile(row, col)\n", " else:\n", " print(\"Invalid maze! Try another one.\")\n", " col += 1\n", "\n", " return code" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Now you can generate the maze code for an arbitrary maze." ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:30.972051Z", "iopub.status.busy": "2022-01-11T09:40:30.971538Z", "iopub.status.idle": "2022-01-11T09:40:30.973275Z", "shell.execute_reply": "2022-01-11T09:40:30.973710Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "maze_code = generate_maze_code(maze_string)" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:31.026290Z", "iopub.status.busy": "2022-01-11T09:40:31.014977Z", "iopub.status.idle": "2022-01-11T09:40:31.216367Z", "shell.execute_reply": "2022-01-11T09:40:31.216815Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[34mdef\u001b[39;49;00m \u001b[32mprint_maze\u001b[39;49;00m(out, row, col):\n", " output = out +\u001b[33m\"\u001b[39;49;00m\u001b[33m\\n\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\n", " c_row = \u001b[34m0\u001b[39;49;00m\n", " c_col = \u001b[34m0\u001b[39;49;00m\n", " \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m \u001b[36mlist\u001b[39;49;00m(\u001b[33m\"\"\"\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m+-+-----+\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m|X| |\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m| | --+ |\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m| | | |\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m| +-- | |\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m| |#|\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m+-----+-+\u001b[39;49;00m\u001b[33m\u001b[39;49;00m\n", "\u001b[33m\"\"\"\u001b[39;49;00m):\n", " \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m\\n\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m:\n", " c_row += \u001b[34m1\u001b[39;49;00m\n", " c_col = \u001b[34m0\u001b[39;49;00m\n", " output += \u001b[33m\"\u001b[39;49;00m\u001b[33m\\n\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\n", " \u001b[34melse\u001b[39;49;00m:\n", " \u001b[34mif\u001b[39;49;00m c_row == row \u001b[35mand\u001b[39;49;00m c_col == col: output += \u001b[33m\"\u001b[39;49;00m\u001b[33mX\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\n", " \u001b[34melif\u001b[39;49;00m c == \u001b[33m\"\u001b[39;49;00m\u001b[33mX\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m: output += \u001b[33m\"\u001b[39;49;00m\u001b[33m \u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\n", " \u001b[34melse\u001b[39;49;00m: output += c\n", " c_col += \u001b[34m1\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m output\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_0(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mmaze\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m):\n", " \u001b[34mreturn\u001b[39;49;00m tile_2_1(\u001b[36mlist\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m), \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_8(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_1_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_2_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_0(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_3_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_3_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_8(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_2_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_3_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_0(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_4_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_4_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_4_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_4_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_8(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_3_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_4_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_0(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_5_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_5_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_8(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_4_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_5_7(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_0(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_7_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_6_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_1(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_7_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_6_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_2(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_7_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_6_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_3(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_7_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_6_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mif\u001b[39;49;00m (index == \u001b[36mlen\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m)): \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mL\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_4(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mR\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_6_6(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mU\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_5_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melif\u001b[39;49;00m \u001b[36minput\u001b[39;49;00m[index] == \u001b[33m'\u001b[39;49;00m\u001b[33mD\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m: \u001b[34mreturn\u001b[39;49;00m tile_7_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", " \u001b[34melse\u001b[39;49;00m : \u001b[34mreturn\u001b[39;49;00m tile_6_5(\u001b[36minput\u001b[39;49;00m, index + \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mSOLVED\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtarget_tile\u001b[39;49;00m():\n", " \u001b[34mreturn\u001b[39;49;00m \u001b[33m\"\u001b[39;49;00m\u001b[33mtile_6_7\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m0\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m1\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m2\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m3\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m4\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m5\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m6\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m)\n", "\n", "\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\n", " \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\n", " \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\n", " \u001b[34mreturn\u001b[39;49;00m print_maze(\u001b[33m\"\u001b[39;49;00m\u001b[33mINVALID\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m, \u001b[34m7\u001b[39;49;00m, \u001b[34m8\u001b[39;49;00m)" ] } ], "source": [ "print_content(maze_code, filename='.py')" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:31.226593Z", "iopub.status.busy": "2022-01-11T09:40:31.226051Z", "iopub.status.idle": "2022-01-11T09:40:31.227812Z", "shell.execute_reply": "2022-01-11T09:40:31.228351Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "exec(maze_code)" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:31.232312Z", "iopub.status.busy": "2022-01-11T09:40:31.231597Z", "iopub.status.idle": "2022-01-11T09:40:31.234312Z", "shell.execute_reply": "2022-01-11T09:40:31.234689Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "VALID\n", "\n", "+-+-----+\n", "| | |\n", "| | --+ |\n", "| | | |\n", "| +-- |X|\n", "| |#|\n", "+-----+-+\n", "\n" ] } ], "source": [ "# Appending one more 'D', you have reached the target.\n", "print(maze(\"DDDDRRRRUULLUURRRRDDD\"))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This is the corresponding call graph." ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:31.238345Z", "iopub.status.busy": "2022-01-11T09:40:31.237708Z", "iopub.status.idle": "2022-01-11T09:40:32.141921Z", "shell.execute_reply": "2022-01-11T09:40:32.142476Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "cluster_G\n", "\n", "\n", "\n", "cluster_callgraphX\n", "\n", "callgraph\n", "\n", "\n", "\n", "callgraphX\n", "\n", "callgraph\n", "\n", "\n", "\n", "callgraphX__maze\n", "\n", "maze\n", "(callgraph.py:84)\n", "\n", "\n", "\n", "callgraphX->callgraphX__maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__print_maze\n", "\n", "print_maze\n", "(callgraph.py:2)\n", "\n", "\n", "\n", "callgraphX->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__target_tile\n", "\n", "target_tile\n", "(callgraph.py:358)\n", "\n", "\n", "\n", "callgraphX->callgraphX__target_tile\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_0\n", "\n", "tile_1_0\n", "(callgraph.py:26)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_1\n", "\n", "tile_1_1\n", "(callgraph.py:31)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_2\n", "\n", "tile_1_2\n", "(callgraph.py:36)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_3\n", "\n", "tile_1_3\n", "(callgraph.py:41)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_4\n", "\n", "tile_1_4\n", "(callgraph.py:46)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_5\n", "\n", "tile_1_5\n", "(callgraph.py:51)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_6\n", "\n", "tile_1_6\n", "(callgraph.py:56)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_7\n", "\n", "tile_1_7\n", "(callgraph.py:61)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_8\n", "\n", "tile_1_8\n", "(callgraph.py:66)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_1_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_0\n", "\n", "tile_2_0\n", "(callgraph.py:71)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1\n", "\n", "tile_2_1\n", "(callgraph.py:76)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_2\n", "\n", "tile_2_2\n", "(callgraph.py:87)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3\n", "\n", "tile_2_3\n", "(callgraph.py:92)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4\n", "\n", "tile_2_4\n", "(callgraph.py:100)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5\n", "\n", "tile_2_5\n", "(callgraph.py:108)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6\n", "\n", "tile_2_6\n", "(callgraph.py:116)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7\n", "\n", "tile_2_7\n", "(callgraph.py:124)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_8\n", "\n", "tile_2_8\n", "(callgraph.py:132)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_2_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_0\n", "\n", "tile_3_0\n", "(callgraph.py:137)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1\n", "\n", "tile_3_1\n", "(callgraph.py:142)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_2\n", "\n", "tile_3_2\n", "(callgraph.py:150)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3\n", "\n", "tile_3_3\n", "(callgraph.py:155)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_4\n", "\n", "tile_3_4\n", "(callgraph.py:163)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_5\n", "\n", "tile_3_5\n", "(callgraph.py:168)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_6\n", "\n", "tile_3_6\n", "(callgraph.py:173)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7\n", "\n", "tile_3_7\n", "(callgraph.py:178)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_8\n", "\n", "tile_3_8\n", "(callgraph.py:186)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_3_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_0\n", "\n", "tile_4_0\n", "(callgraph.py:191)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1\n", "\n", "tile_4_1\n", "(callgraph.py:196)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_2\n", "\n", "tile_4_2\n", "(callgraph.py:204)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3\n", "\n", "tile_4_3\n", "(callgraph.py:209)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4\n", "\n", "tile_4_4\n", "(callgraph.py:217)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5\n", "\n", "tile_4_5\n", "(callgraph.py:225)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_6\n", "\n", "tile_4_6\n", "(callgraph.py:233)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7\n", "\n", "tile_4_7\n", "(callgraph.py:238)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_8\n", "\n", "tile_4_8\n", "(callgraph.py:246)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_4_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_0\n", "\n", "tile_5_0\n", "(callgraph.py:251)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1\n", "\n", "tile_5_1\n", "(callgraph.py:256)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_2\n", "\n", "tile_5_2\n", "(callgraph.py:264)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_3\n", "\n", "tile_5_3\n", "(callgraph.py:269)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_4\n", "\n", "tile_5_4\n", "(callgraph.py:274)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5\n", "\n", "tile_5_5\n", "(callgraph.py:279)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_6\n", "\n", "tile_5_6\n", "(callgraph.py:287)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7\n", "\n", "tile_5_7\n", "(callgraph.py:292)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_8\n", "\n", "tile_5_8\n", "(callgraph.py:300)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_5_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_0\n", "\n", "tile_6_0\n", "(callgraph.py:305)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1\n", "\n", "tile_6_1\n", "(callgraph.py:310)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2\n", "\n", "tile_6_2\n", "(callgraph.py:318)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3\n", "\n", "tile_6_3\n", "(callgraph.py:326)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4\n", "\n", "tile_6_4\n", "(callgraph.py:334)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5\n", "\n", "tile_6_5\n", "(callgraph.py:342)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_6\n", "\n", "tile_6_6\n", "(callgraph.py:350)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_7\n", "\n", "tile_6_7\n", "(callgraph.py:355)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_8\n", "\n", "tile_6_8\n", "(callgraph.py:361)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_6_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_0\n", "\n", "tile_7_0\n", "(callgraph.py:366)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_1\n", "\n", "tile_7_1\n", "(callgraph.py:371)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_2\n", "\n", "tile_7_2\n", "(callgraph.py:376)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_3\n", "\n", "tile_7_3\n", "(callgraph.py:381)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_4\n", "\n", "tile_7_4\n", "(callgraph.py:386)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_5\n", "\n", "tile_7_5\n", "(callgraph.py:391)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_6\n", "\n", "tile_7_6\n", "(callgraph.py:396)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_7\n", "\n", "tile_7_7\n", "(callgraph.py:401)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_8\n", "\n", "tile_7_8\n", "(callgraph.py:406)\n", "\n", "\n", "\n", "callgraphX->callgraphX__tile_7_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__maze->callgraphX__tile_2_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_1_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__tile_1_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__tile_2_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__tile_2_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__tile_2_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_1->callgraphX__tile_3_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__tile_1_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__tile_2_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__tile_2_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__tile_2_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_3->callgraphX__tile_3_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__tile_1_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__tile_2_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__tile_2_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__tile_2_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_4->callgraphX__tile_3_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__tile_1_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__tile_2_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__tile_2_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__tile_2_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_5->callgraphX__tile_3_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__tile_1_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__tile_2_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__tile_2_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__tile_2_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_6->callgraphX__tile_3_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__tile_1_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__tile_2_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__tile_2_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__tile_2_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_7->callgraphX__tile_3_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_2_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__tile_2_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__tile_3_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__tile_3_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__tile_3_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_1->callgraphX__tile_4_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__tile_2_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__tile_3_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__tile_3_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__tile_3_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_3->callgraphX__tile_4_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__tile_2_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__tile_3_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__tile_3_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__tile_3_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_7->callgraphX__tile_4_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_3_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__tile_3_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__tile_4_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__tile_4_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__tile_4_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_1->callgraphX__tile_5_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__tile_3_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__tile_4_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__tile_4_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__tile_4_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_3->callgraphX__tile_5_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__tile_3_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__tile_4_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__tile_4_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__tile_4_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_4->callgraphX__tile_5_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__tile_3_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__tile_4_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__tile_4_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__tile_4_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_5->callgraphX__tile_5_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__tile_3_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__tile_4_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__tile_4_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__tile_4_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_7->callgraphX__tile_5_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_4_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__tile_4_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__tile_5_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__tile_5_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__tile_5_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_1->callgraphX__tile_6_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__tile_4_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__tile_5_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__tile_5_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__tile_5_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_5->callgraphX__tile_6_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__tile_4_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__tile_5_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__tile_5_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__tile_5_8\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_7->callgraphX__tile_6_7\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_5_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__tile_5_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__tile_6_0\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__tile_6_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__tile_6_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_1->callgraphX__tile_7_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__tile_5_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__tile_6_1\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__tile_6_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__tile_6_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_2->callgraphX__tile_7_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__tile_5_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__tile_6_2\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__tile_6_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__tile_6_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_3->callgraphX__tile_7_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__tile_5_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__tile_6_3\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__tile_6_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__tile_6_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_4->callgraphX__tile_7_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__tile_5_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__tile_6_4\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__tile_6_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__tile_6_6\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_5->callgraphX__tile_7_5\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_6_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_0->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_1->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_2->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_3->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_4->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_5->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_6->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_7->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n", "callgraphX__tile_7_8->callgraphX__print_maze\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "callgraph(maze_code)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Cleanup\n", "\n", "We're done, so we clean up:" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "execution": { "iopub.execute_input": "2022-01-11T09:40:32.150004Z", "iopub.status.busy": "2022-01-11T09:40:32.148899Z", "iopub.status.idle": "2022-01-11T09:40:32.152503Z", "shell.execute_reply": "2022-01-11T09:40:32.151899Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "if os.path.exists('callgraph.dot'):\n", " os.remove('callgraph.dot')\n", "\n", "if os.path.exists('callgraph.py'):\n", " os.remove('callgraph.py')" ] } ], "metadata": { "ipub": { "bibliography": "fuzzingbook.bib", "toc": true }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.7" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": true }, "toc-autonumbering": false, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }