{
"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"
],
"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"
],
"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"
],
"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"
],
"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"
],
"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"
],
"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"
],
"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
}