{
"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": "2024-01-18T17:31:30.761307Z",
"iopub.status.busy": "2024-01-18T17:31:30.761119Z",
"iopub.status.idle": "2024-01-18T17:31:30.817010Z",
"shell.execute_reply": "2024-01-18T17:31:30.816512Z"
},
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import bookutils.setup"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"button": false,
"execution": {
"iopub.execute_input": "2024-01-18T17:31:30.819506Z",
"iopub.status.busy": "2024-01-18T17:31:30.819307Z",
"iopub.status.idle": "2024-01-18T17:31:30.821341Z",
"shell.execute_reply": "2024-01-18T17:31:30.820970Z"
},
"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": "2024-01-18T17:31:30.823414Z",
"iopub.status.busy": "2024-01-18T17:31:30.823274Z",
"iopub.status.idle": "2024-01-18T17:31:30.824956Z",
"shell.execute_reply": "2024-01-18T17:31:30.824630Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import ast\n",
"import re"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:30.826805Z",
"iopub.status.busy": "2024-01-18T17:31:30.826671Z",
"iopub.status.idle": "2024-01-18T17:31:30.835215Z",
"shell.execute_reply": "2024-01-18T17:31:30.834887Z"
},
"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": "2024-01-18T17:31:30.837143Z",
"iopub.status.busy": "2024-01-18T17:31:30.837001Z",
"iopub.status.idle": "2024-01-18T17:31:30.838874Z",
"shell.execute_reply": "2024-01-18T17:31:30.838548Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"REGISTRY_IDX = 0"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:30.840587Z",
"iopub.status.busy": "2024-01-18T17:31:30.840462Z",
"iopub.status.idle": "2024-01-18T17:31:30.842254Z",
"shell.execute_reply": "2024-01-18T17:31:30.841879Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"REGISTRY = {}"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:30.843929Z",
"iopub.status.busy": "2024-01-18T17:31:30.843796Z",
"iopub.status.idle": "2024-01-18T17:31:30.845756Z",
"shell.execute_reply": "2024-01-18T17:31:30.845435Z"
},
"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": "2024-01-18T17:31:30.847486Z",
"iopub.status.busy": "2024-01-18T17:31:30.847350Z",
"iopub.status.idle": "2024-01-18T17:31:30.849235Z",
"shell.execute_reply": "2024-01-18T17:31:30.848944Z"
},
"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": "2024-01-18T17:31:30.850888Z",
"iopub.status.busy": "2024-01-18T17:31:30.850776Z",
"iopub.status.idle": "2024-01-18T17:31:30.852761Z",
"shell.execute_reply": "2024-01-18T17:31:30.852492Z"
},
"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": "2024-01-18T17:31:30.854418Z",
"iopub.status.busy": "2024-01-18T17:31:30.854293Z",
"iopub.status.idle": "2024-01-18T17:31:30.856228Z",
"shell.execute_reply": "2024-01-18T17:31:30.855877Z"
},
"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": "2024-01-18T17:31:30.857948Z",
"iopub.status.busy": "2024-01-18T17:31:30.857833Z",
"iopub.status.idle": "2024-01-18T17:31:30.863219Z",
"shell.execute_reply": "2024-01-18T17:31:30.862965Z"
},
"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": "2024-01-18T17:31:30.864736Z",
"iopub.status.busy": "2024-01-18T17:31:30.864650Z",
"iopub.status.idle": "2024-01-18T17:31:30.866703Z",
"shell.execute_reply": "2024-01-18T17:31:30.866467Z"
},
"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": "2024-01-18T17:31:30.868128Z",
"iopub.status.busy": "2024-01-18T17:31:30.868047Z",
"iopub.status.idle": "2024-01-18T17:31:30.869806Z",
"shell.execute_reply": "2024-01-18T17:31:30.869574Z"
},
"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": "2024-01-18T17:31:30.871401Z",
"iopub.status.busy": "2024-01-18T17:31:30.871304Z",
"iopub.status.idle": "2024-01-18T17:31:30.873298Z",
"shell.execute_reply": "2024-01-18T17:31:30.873061Z"
},
"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": "2024-01-18T17:31:30.874702Z",
"iopub.status.busy": "2024-01-18T17:31:30.874620Z",
"iopub.status.idle": "2024-01-18T17:31:30.876648Z",
"shell.execute_reply": "2024-01-18T17:31:30.876421Z"
},
"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": "2024-01-18T17:31:30.878036Z",
"iopub.status.busy": "2024-01-18T17:31:30.877957Z",
"iopub.status.idle": "2024-01-18T17:31:30.879846Z",
"shell.execute_reply": "2024-01-18T17:31:30.879603Z"
},
"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": "2024-01-18T17:31:30.881264Z",
"iopub.status.busy": "2024-01-18T17:31:30.881186Z",
"iopub.status.idle": "2024-01-18T17:31:30.883061Z",
"shell.execute_reply": "2024-01-18T17:31:30.882829Z"
},
"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": "2024-01-18T17:31:30.884464Z",
"iopub.status.busy": "2024-01-18T17:31:30.884386Z",
"iopub.status.idle": "2024-01-18T17:31:30.886387Z",
"shell.execute_reply": "2024-01-18T17:31:30.886160Z"
},
"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": "2024-01-18T17:31:30.887737Z",
"iopub.status.busy": "2024-01-18T17:31:30.887658Z",
"iopub.status.idle": "2024-01-18T17:31:30.889460Z",
"shell.execute_reply": "2024-01-18T17:31:30.889174Z"
},
"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": "2024-01-18T17:31:30.890823Z",
"iopub.status.busy": "2024-01-18T17:31:30.890741Z",
"iopub.status.idle": "2024-01-18T17:31:30.892885Z",
"shell.execute_reply": "2024-01-18T17:31:30.892663Z"
},
"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": "2024-01-18T17:31:30.894258Z",
"iopub.status.busy": "2024-01-18T17:31:30.894178Z",
"iopub.status.idle": "2024-01-18T17:31:30.896317Z",
"shell.execute_reply": "2024-01-18T17:31:30.896089Z"
},
"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": "2024-01-18T17:31:30.897837Z",
"iopub.status.busy": "2024-01-18T17:31:30.897745Z",
"iopub.status.idle": "2024-01-18T17:31:30.901089Z",
"shell.execute_reply": "2024-01-18T17:31:30.900794Z"
},
"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": "2024-01-18T17:31:30.902778Z",
"iopub.status.busy": "2024-01-18T17:31:30.902657Z",
"iopub.status.idle": "2024-01-18T17:31:30.905242Z",
"shell.execute_reply": "2024-01-18T17:31:30.904974Z"
},
"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": "2024-01-18T17:31:30.906987Z",
"iopub.status.busy": "2024-01-18T17:31:30.906850Z",
"iopub.status.idle": "2024-01-18T17:31:30.909370Z",
"shell.execute_reply": "2024-01-18T17:31:30.909123Z"
},
"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": "2024-01-18T17:31:30.910847Z",
"iopub.status.busy": "2024-01-18T17:31:30.910746Z",
"iopub.status.idle": "2024-01-18T17:31:30.912540Z",
"shell.execute_reply": "2024-01-18T17:31:30.912304Z"
},
"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": "2024-01-18T17:31:30.914029Z",
"iopub.status.busy": "2024-01-18T17:31:30.913931Z",
"iopub.status.idle": "2024-01-18T17:31:30.915704Z",
"shell.execute_reply": "2024-01-18T17:31:30.915487Z"
},
"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": "2024-01-18T17:31:30.917092Z",
"iopub.status.busy": "2024-01-18T17:31:30.916992Z",
"iopub.status.idle": "2024-01-18T17:31:30.918703Z",
"shell.execute_reply": "2024-01-18T17:31:30.918474Z"
},
"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": "2024-01-18T17:31:30.920147Z",
"iopub.status.busy": "2024-01-18T17:31:30.920051Z",
"iopub.status.idle": "2024-01-18T17:31:30.922788Z",
"shell.execute_reply": "2024-01-18T17:31:30.922554Z"
},
"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": "2024-01-18T17:31:30.924225Z",
"iopub.status.busy": "2024-01-18T17:31:30.924115Z",
"iopub.status.idle": "2024-01-18T17:31:30.925853Z",
"shell.execute_reply": "2024-01-18T17:31:30.925627Z"
},
"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": "2024-01-18T17:31:30.927468Z",
"iopub.status.busy": "2024-01-18T17:31:30.927372Z",
"iopub.status.idle": "2024-01-18T17:31:30.929664Z",
"shell.execute_reply": "2024-01-18T17:31:30.929430Z"
},
"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": "2024-01-18T17:31:30.931166Z",
"iopub.status.busy": "2024-01-18T17:31:30.931053Z",
"iopub.status.idle": "2024-01-18T17:31:30.934362Z",
"shell.execute_reply": "2024-01-18T17:31:30.934110Z"
},
"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": "2024-01-18T17:31:30.935745Z",
"iopub.status.busy": "2024-01-18T17:31:30.935665Z",
"iopub.status.idle": "2024-01-18T17:31:30.937792Z",
"shell.execute_reply": "2024-01-18T17:31:30.937560Z"
},
"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": "2024-01-18T17:31:30.939216Z",
"iopub.status.busy": "2024-01-18T17:31:30.939140Z",
"iopub.status.idle": "2024-01-18T17:31:30.941631Z",
"shell.execute_reply": "2024-01-18T17:31:30.941387Z"
},
"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": "2024-01-18T17:31:30.943056Z",
"iopub.status.busy": "2024-01-18T17:31:30.942958Z",
"iopub.status.idle": "2024-01-18T17:31:30.944746Z",
"shell.execute_reply": "2024-01-18T17:31:30.944522Z"
},
"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": "2024-01-18T17:31:30.946154Z",
"iopub.status.busy": "2024-01-18T17:31:30.946079Z",
"iopub.status.idle": "2024-01-18T17:31:30.947866Z",
"shell.execute_reply": "2024-01-18T17:31:30.947597Z"
},
"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": "2024-01-18T17:31:30.949264Z",
"iopub.status.busy": "2024-01-18T17:31:30.949185Z",
"iopub.status.idle": "2024-01-18T17:31:30.951306Z",
"shell.execute_reply": "2024-01-18T17:31:30.951070Z"
},
"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": "2024-01-18T17:31:30.952733Z",
"iopub.status.busy": "2024-01-18T17:31:30.952658Z",
"iopub.status.idle": "2024-01-18T17:31:30.955315Z",
"shell.execute_reply": "2024-01-18T17:31:30.954961Z"
},
"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": "2024-01-18T17:31:30.956894Z",
"iopub.status.busy": "2024-01-18T17:31:30.956797Z",
"iopub.status.idle": "2024-01-18T17:31:30.958754Z",
"shell.execute_reply": "2024-01-18T17:31:30.958524Z"
},
"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": "2024-01-18T17:31:30.960162Z",
"iopub.status.busy": "2024-01-18T17:31:30.960082Z",
"iopub.status.idle": "2024-01-18T17:31:30.962212Z",
"shell.execute_reply": "2024-01-18T17:31:30.961977Z"
},
"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": "2024-01-18T17:31:30.963627Z",
"iopub.status.busy": "2024-01-18T17:31:30.963548Z",
"iopub.status.idle": "2024-01-18T17:31:30.979444Z",
"shell.execute_reply": "2024-01-18T17:31:30.979178Z"
},
"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": "2024-01-18T17:31:30.981021Z",
"iopub.status.busy": "2024-01-18T17:31:30.980932Z",
"iopub.status.idle": "2024-01-18T17:31:30.986051Z",
"shell.execute_reply": "2024-01-18T17:31:30.985801Z"
},
"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": "2024-01-18T17:31:30.987471Z",
"iopub.status.busy": "2024-01-18T17:31:30.987395Z",
"iopub.status.idle": "2024-01-18T17:31:30.989361Z",
"shell.execute_reply": "2024-01-18T17:31:30.989120Z"
},
"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": "2024-01-18T17:31:30.990879Z",
"iopub.status.busy": "2024-01-18T17:31:30.990797Z",
"iopub.status.idle": "2024-01-18T17:31:30.992965Z",
"shell.execute_reply": "2024-01-18T17:31:30.992721Z"
},
"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": "2024-01-18T17:31:30.994427Z",
"iopub.status.busy": "2024-01-18T17:31:30.994346Z",
"iopub.status.idle": "2024-01-18T17:31:30.995912Z",
"shell.execute_reply": "2024-01-18T17:31:30.995682Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import inspect"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:30.997373Z",
"iopub.status.busy": "2024-01-18T17:31:30.997278Z",
"iopub.status.idle": "2024-01-18T17:31:31.380705Z",
"shell.execute_reply": "2024-01-18T17:31:31.380311Z"
},
"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": "2024-01-18T17:31:31.400769Z",
"iopub.status.busy": "2024-01-18T17:31:31.400619Z",
"iopub.status.idle": "2024-01-18T17:31:31.403987Z",
"shell.execute_reply": "2024-01-18T17:31:31.403718Z"
},
"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": "2024-01-18T17:31:31.405701Z",
"iopub.status.busy": "2024-01-18T17:31:31.405562Z",
"iopub.status.idle": "2024-01-18T17:31:31.787992Z",
"shell.execute_reply": "2024-01-18T17:31:31.787583Z"
},
"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": "2024-01-18T17:31:31.789714Z",
"iopub.status.busy": "2024-01-18T17:31:31.789595Z",
"iopub.status.idle": "2024-01-18T17:31:31.791844Z",
"shell.execute_reply": "2024-01-18T17:31:31.791558Z"
},
"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": "2024-01-18T17:31:32.178326Z",
"iopub.status.busy": "2024-01-18T17:31:32.178190Z",
"iopub.status.idle": "2024-01-18T17:31:32.180587Z",
"shell.execute_reply": "2024-01-18T17:31:32.180338Z"
},
"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": "2024-01-18T17:31:32.182165Z",
"iopub.status.busy": "2024-01-18T17:31:32.182033Z",
"iopub.status.idle": "2024-01-18T17:31:32.554467Z",
"shell.execute_reply": "2024-01-18T17:31:32.554047Z"
},
"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": "2024-01-18T17:31:32.556464Z",
"iopub.status.busy": "2024-01-18T17:31:32.556316Z",
"iopub.status.idle": "2024-01-18T17:31:32.558494Z",
"shell.execute_reply": "2024-01-18T17:31:32.558212Z"
},
"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": "2024-01-18T17:31:32.559939Z",
"iopub.status.busy": "2024-01-18T17:31:32.559829Z",
"iopub.status.idle": "2024-01-18T17:31:32.931816Z",
"shell.execute_reply": "2024-01-18T17:31:32.931479Z"
},
"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": "2024-01-18T17:31:32.933722Z",
"iopub.status.busy": "2024-01-18T17:31:32.933588Z",
"iopub.status.idle": "2024-01-18T17:31:32.936788Z",
"shell.execute_reply": "2024-01-18T17:31:32.936453Z"
},
"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": "2024-01-18T17:31:32.938338Z",
"iopub.status.busy": "2024-01-18T17:31:32.938244Z",
"iopub.status.idle": "2024-01-18T17:31:33.324026Z",
"shell.execute_reply": "2024-01-18T17:31:33.323618Z"
},
"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": "2024-01-18T17:31:33.325777Z",
"iopub.status.busy": "2024-01-18T17:31:33.325646Z",
"iopub.status.idle": "2024-01-18T17:31:33.327484Z",
"shell.execute_reply": "2024-01-18T17:31:33.327217Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import os"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:33.328889Z",
"iopub.status.busy": "2024-01-18T17:31:33.328791Z",
"iopub.status.idle": "2024-01-18T17:31:33.388702Z",
"shell.execute_reply": "2024-01-18T17:31:33.388428Z"
},
"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": "2024-01-18T17:31:33.390282Z",
"iopub.status.busy": "2024-01-18T17:31:33.390167Z",
"iopub.status.idle": "2024-01-18T17:31:33.392032Z",
"shell.execute_reply": "2024-01-18T17:31:33.391743Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import shutil"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:33.393537Z",
"iopub.status.busy": "2024-01-18T17:31:33.393431Z",
"iopub.status.idle": "2024-01-18T17:31:33.395829Z",
"shell.execute_reply": "2024-01-18T17:31:33.395578Z"
},
"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": "2024-01-18T17:31:33.397188Z",
"iopub.status.busy": "2024-01-18T17:31:33.397079Z",
"iopub.status.idle": "2024-01-18T17:31:33.399188Z",
"shell.execute_reply": "2024-01-18T17:31:33.398945Z"
},
"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": "2024-01-18T17:31:33.400613Z",
"iopub.status.busy": "2024-01-18T17:31:33.400520Z",
"iopub.status.idle": "2024-01-18T17:31:33.402684Z",
"shell.execute_reply": "2024-01-18T17:31:33.402407Z"
},
"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": "2024-01-18T17:31:33.404165Z",
"iopub.status.busy": "2024-01-18T17:31:33.404074Z",
"iopub.status.idle": "2024-01-18T17:31:33.406330Z",
"shell.execute_reply": "2024-01-18T17:31:33.405944Z"
},
"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",
"\n",
" # This is deprecated:\n",
" # return nx.drawing.nx_pydot.read_dot(name + '.dot')\n",
" \n",
" return nx.nx_agraph.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": "2024-01-18T17:31:33.407965Z",
"iopub.status.busy": "2024-01-18T17:31:33.407838Z",
"iopub.status.idle": "2024-01-18T17:31:33.409496Z",
"shell.execute_reply": "2024-01-18T17:31:33.409213Z"
},
"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": "2024-01-18T17:31:33.410965Z",
"iopub.status.busy": "2024-01-18T17:31:33.410855Z",
"iopub.status.idle": "2024-01-18T17:31:33.412471Z",
"shell.execute_reply": "2024-01-18T17:31:33.412217Z"
},
"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": "2024-01-18T17:31:33.413932Z",
"iopub.status.busy": "2024-01-18T17:31:33.413842Z",
"iopub.status.idle": "2024-01-18T17:31:33.415510Z",
"shell.execute_reply": "2024-01-18T17:31:33.415275Z"
},
"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": "2024-01-18T17:31:33.417005Z",
"iopub.status.busy": "2024-01-18T17:31:33.416877Z",
"iopub.status.idle": "2024-01-18T17:31:33.418791Z",
"shell.execute_reply": "2024-01-18T17:31:33.418552Z"
},
"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": "2024-01-18T17:31:33.420124Z",
"iopub.status.busy": "2024-01-18T17:31:33.420014Z",
"iopub.status.idle": "2024-01-18T17:31:33.421820Z",
"shell.execute_reply": "2024-01-18T17:31:33.421549Z"
},
"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": "2024-01-18T17:31:33.423293Z",
"iopub.status.busy": "2024-01-18T17:31:33.423185Z",
"iopub.status.idle": "2024-01-18T17:31:33.425228Z",
"shell.execute_reply": "2024-01-18T17:31:33.424995Z"
},
"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": "2024-01-18T17:31:33.426649Z",
"iopub.status.busy": "2024-01-18T17:31:33.426552Z",
"iopub.status.idle": "2024-01-18T17:31:33.428323Z",
"shell.execute_reply": "2024-01-18T17:31:33.428077Z"
},
"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": "2024-01-18T17:31:33.429710Z",
"iopub.status.busy": "2024-01-18T17:31:33.429608Z",
"iopub.status.idle": "2024-01-18T17:31:33.432003Z",
"shell.execute_reply": "2024-01-18T17:31:33.431787Z"
},
"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": "2024-01-18T17:31:33.433378Z",
"iopub.status.busy": "2024-01-18T17:31:33.433276Z",
"iopub.status.idle": "2024-01-18T17:31:33.434948Z",
"shell.execute_reply": "2024-01-18T17:31:33.434695Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"maze_code = generate_maze_code(maze_string)"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:33.436283Z",
"iopub.status.busy": "2024-01-18T17:31:33.436202Z",
"iopub.status.idle": "2024-01-18T17:31:33.748959Z",
"shell.execute_reply": "2024-01-18T17:31:33.748311Z"
},
"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):\u001b[37m\u001b[39;49;00m\n",
" output = out +\u001b[33m\"\u001b[39;49;00m\u001b[33m\\n\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" c_row = \u001b[34m0\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" c_col = \u001b[34m0\u001b[39;49;00m\u001b[37m\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):\u001b[37m\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:\u001b[37m\u001b[39;49;00m\n",
" c_row += \u001b[34m1\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" c_col = \u001b[34m0\u001b[39;49;00m\u001b[37m\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\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melse\u001b[39;49;00m:\u001b[37m\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\u001b[37m\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\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melse\u001b[39;49;00m: output += c\u001b[37m\u001b[39;49;00m\n",
" c_col += \u001b[34m1\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m output\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_1_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mmaze\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m):\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_2_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_3_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_4_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_5_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtarget_tile\u001b[39;49;00m():\u001b[37m\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\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_6_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_0\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_1\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_2\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_3\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_4\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_5\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_6\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_7\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m\n",
"\u001b[37m\u001b[39;49;00m\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mtile_7_8\u001b[39;49;00m(\u001b[36minput\u001b[39;49;00m, index):\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mtry\u001b[39;49;00m: HTMLParser().feed(\u001b[36minput\u001b[39;49;00m)\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mexcept\u001b[39;49;00m: \u001b[34mpass\u001b[39;49;00m\u001b[37m\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)\u001b[37m\u001b[39;49;00m"
]
}
],
"source": [
"print_content(maze_code, filename='.py')"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:33.751601Z",
"iopub.status.busy": "2024-01-18T17:31:33.751436Z",
"iopub.status.idle": "2024-01-18T17:31:33.757459Z",
"shell.execute_reply": "2024-01-18T17:31:33.757100Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"exec(maze_code)"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:31:33.759326Z",
"iopub.status.busy": "2024-01-18T17:31:33.759195Z",
"iopub.status.idle": "2024-01-18T17:31:33.767142Z",
"shell.execute_reply": "2024-01-18T17:31:33.762969Z"
},
"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": "2024-01-18T17:31:33.807194Z",
"iopub.status.busy": "2024-01-18T17:31:33.806793Z",
"iopub.status.idle": "2024-01-18T17:31:34.426842Z",
"shell.execute_reply": "2024-01-18T17:31:34.426438Z"
},
"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": "2024-01-18T17:31:34.428899Z",
"iopub.status.busy": "2024-01-18T17:31:34.428802Z",
"iopub.status.idle": "2024-01-18T17:31:34.431120Z",
"shell.execute_reply": "2024-01-18T17:31:34.430832Z"
},
"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.10.2"
},
"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
}