"You're standing in front of gate 9¾. You have [the instructions](05-pixels.txt). How many pixels would be lit on the board, if it were working?"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked example solution: Parts 1 and 2\n",
+ "This is an example of building an interpreter for a virtual machine, and then executing a program on it. Thinking about the problem in this way allows me to split the problem into two parts straight away:\n",
+ "\n",
+ "1. Build a virtual machine\n",
+ "2. Build a parser that will take the string representation of instructions and convert a set of commands the machine will understand. \n",
+ "\n",
+ "The second task is difficult until we've decided what the result of that parsing should look like, so let's look at the virtual machine first.\n",
+ "\n",
+ "Neither part is particularly hard. What makes this problem more of a challenge is doing the two parts together, and making sure they mesh in the end."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Virtual machine\n",
+ "\n",
+ "### Representation\n",
+ "The machine is little more than the grid and the operations that act on it. There are only four operations, so let's implement each one as a function that takes as input a machine/grid and returns as output the updated grid (But because of the way Python handles lists, changes are generally done in-place, so we don't _need_ to use the return value.)\n",
+ "\n",
+ "We have some choices about how to implement the grid itself. One approach would be a 2d array of booleans, or a 2d array of characters, or of numbers. Python doesn't do 2d arrays (or fixed-sized arrays at all), so arrays would be lists. \n",
+ "\n",
+ "Using a boolean for each cell has the advantage that the `toggle` operations are simple `not` operations. But, if we represent the cells as characters, we can store the grid as a list of strings. To some extent, it doesn't matter with Python, as lists and strings both offer the same interface of picking out individual parts and sections with the slice notation. \n",
+ "\n",
+ "We could also do something like a 'spare array' representation, using a `dict` to store the grid. The keys would be a `tuple` of `(row, column)` and the value would be the boolean/character/number which is the cell at that position. However, as we're taking slices of grid and acting on them, this is likely to get cumbersome. \n",
+ "\n",
+ "For no particular reason, I chose to represent the grid as a list of strings, with a cell being '\\*' if that pixel is on and '.' if it's off. This has be slight advantage that printing the grid is easier.\n",
+ "\n",
+ "### Commands\n",
+ "You'll notice that the first thing I did was build procedures that create a new grid of a particular size, and print the grid. These are really useful for testing and debugging, as I can easily see what's happening when the other commands go wrong! (The `print_grid` then got a bit more complex to allow for different output formatting.)\n",
+ "\n",
+ "The `top` and `left` commands are fairly straightforward, apart from having to be careful with boundary arithmetic for moving between 1-based and 0-based counting, and inclusive-at-both-end sections. \n",
+ "\n",
+ "The `rotate_column` and `rotate_row` functions use the modulus `%` operation to keep the rotation amount down to a sensible level. The `rotate_row` is the simplest: it forms a new row by joining the last few elements of the row to the first few elements of the row, wrapping the last elements to the front. `rotate_column` does the same thing, but with the added complication of snipping out the column into the `col` variable then rebuilding the rows with the `new_col`."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Parsing\n",
+ "This is much simpler than the first part. \n",
+ "\n",
+ "Each instruction is of the format `<bunch of text> <number> <number>`. That means we can apply the same parsing function to each line without having to worry about which instruction it is, and we can always return the same thing, namely the text and the two numbers. \n",
+ "\n",
+ "Python's `rsplit()` methods splits a string into chunks, by default splitting on whitespace. The `maxsplit` parameter limits how many splits to make, so we don't end up splitting the multi-word command names.\n",
+ "\n",
+ "## Applying instructions\n",
+ "One way to do this is with a multi-way `if` statement (or a `case` statement), but that takes space to write and is fragile when it comes to perhaps adding extra commands. Instead, I'm using a _dispatch table_. \n",
+ "\n",
+ "The general idea is that the table contains the functions and procedures we could call, and we pick which one at run time. This simplifies the code in the `interpet` procedure, as all we do is look up the instruction name in the table and apply the function that comes out of it. This is helped by Python's easy syntax for this sort of thing: the name of a function, used without brackets, is the function itself (the brackets mean \"apply this function\"). \n",
+ "\n",
+ "The `interpret` function just goes along the list of instructions, applying them one at a time. There's some extra bits in there for generating different outputs, and the `clear_output` function is specific to Jupyter notebooks, allowing the next output to be printed in the same place as the last, effectively animating the creation of the message on the display."
+ ]
+ },
{
"cell_type": "code",
"execution_count": 1,
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 18,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def interpret(commands, grid=None, w=WIDTH, h=HEIGHT, \n",
- " show_each_step=False, md=False, overprint=False):\n",
+ " show_each_step=False, md=False, overprint=False, overprint_delay=0.25):\n",
" if grid is None:\n",
" grid = new_grid(w, h)\n",
" for c in commands:\n",
" cmd, a, b = parse(c)\n",
" if cmd in command_dispatch:\n",
- " command_dispatch[cmd](grid, a, b)\n",
+ " grid = command_dispatch[cmd](grid, a, b)\n",
" else:\n",
" raise ValueError('Unknown command')\n",
" if show_each_step:\n",
" if overprint:\n",
- " time.sleep(0.25)\n",
+ " time.sleep(overprint_delay)\n",
" if md: \n",
" print('`{}`'.format(c))\n",
" else:\n",
"sum(1 for c in ''.join(g) if c == '*')"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Final\n",
+ "...****..............*...................*.....*..............*.................\n",
+ "......*..............*...................***..**..............*.................\n",
+ "......*.*****.*****.****.*****..****.....*.*.***.*****.*****.****.*****..****...\n",
+ "......*.....*.*...*..*.......*..*........*..**.*.....*.*...*..*.......*..*......\n",
+ "......*.*****.*...*..*...*****..*........*..*..*.*****.*...*..*...*****..*......\n",
+ "......*.*...*.*...*..*...*...*..*........*.....*.*...*.*...*..*...*...*..*......\n",
+ "...*..*.*..**.*...*..**..*..**..*........*.....*.*..**.*...*..**..*..**..*......\n",
+ "....**...**.*.*...*...**..**.*..*........*.....*..**.*.*...*...**..**.*..*......\n"
+ ]
+ }
+ ],
+ "source": [
+ "g = interpret(cmds, show_each_step=True, overprint=True, overprint_delay=0.1)"
+ ]
+ },
{
"cell_type": "markdown",
"metadata": {},
projects / ou-summer-of-code-2017.git / blobdiff