{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Laser display boards\n", "\n", "You're off on your first sightseening trip of your holiday and you need to catch the right llama-rickshaw to get there. You arrive all keen at the llama-rickshaw station, only to find a scene of chaos. The bad news is that there are lots of llama-rickshaws heading to different places. The good news is that above each bay is a display board that shows where that llama-rickshaw is heading. The bad news is that all the display boards have gone down. The good news is that the station staff are handing out the machine-code instructions to generate the messages on the board. \n", "\n", "Given your l33t haxor skilz, it will be no problem to recreate the messages on the display boards.\n", "\n", "The board is grid, 80 pixels wide and 8 pixels tall, with row 1 being the top row and column 1 being the left column. The pixels are changed with these commands:\n", "\n", "* `top A B` switches the state of the pixels in the topmost row from columns A to B inclusive. If a pixel was lit, it becomes dark; if it was dark, it becomes lit.\n", "* `left A B` is similar, but works on the left edge, toggling the state of pixels in the leftmost column in rows A to B inclusive. \n", "* `rotate column A B` rotates column A by B spaces down. Pixels that are moved beyond the bottom edge \"wrap around\" to the top edge.\n", "* `rotate row A B` rotates row A by B spaces to the right. Pixels that are moved beyond the right edge \"wrap around\" to the left edge.\n", "\n", "You can assume all numbers are integers, the row and column values are always valid, and `A` $\\le$ `B` in the `left` and `top` commands." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For instance, with a smaller grid that is 10 pixels wide and 4 tall, this is what a sample sequence of instructions would do.\n", "\n", "* `top 1 6` turns on the first six pixels on the top row.\n", "```\n", "******....\n", "..........\n", "..........\n", "..........\n", "```\n", "\n", "* `rotate column 2 3` moves the lit pixel on the second column to the bottom row.\n", "```\n", "*.****....\n", "..........\n", "..........\n", ".*........\n", "```\n", "\n", "* `top 3 10` turns off the pixels in columns 4, 5, and 6, and turns on the pixels in columns 7 to 10.\n", "\n", "```\n", "*.....****\n", "..........\n", "..........\n", ".*........\n", "```\n", "\n", "* `rotate column 8 5` moves the one lit pixel in column 8 down five rows, wrapping it all the way around the display and leaving the board with one lit pixel in that column one row lower.\n", "```\n", "*.....*.**\n", ".......*..\n", "..........\n", ".*........\n", "```\n", "\n", "* `rotate row 2 6` moves that pixel off the right edge of the display, to it wraps around to appear in column 4.\n", "```\n", "*.....*.**\n", "...*......\n", "..........\n", ".*........\n", "```\n", "\n", "* `left 1 3` toggles the pixels in rows 1, 2, and 3 of the first column. The top left pixel (previously on) turns off, while the pixels in rows 2 and 3 come on.\n", "```\n", "......*.**\n", "*..*......\n", "*.........\n", ".*........\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 1\n", "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 ` `. 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, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import time\n", "import re\n", "from IPython.display import clear_output" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "WIDTH = 80\n", "HEIGHT = 8" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def new_grid(w=WIDTH, h=HEIGHT):\n", " return ['.' * w for r in range(1, h+1)]" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def print_grid(grid, md=False, suppress_dots=False):\n", " if md:\n", " print('```')\n", " for row in grid:\n", " if suppress_dots:\n", " print(re.sub(r'\\.', ' ', row))\n", " else:\n", " print(row)\n", " if md:\n", " print('```')" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def top(grid, l, r):\n", " new_segment = ''\n", " for i in range(l-1, r):\n", " if grid[0][i] == '.':\n", " new_segment += '*'\n", " else:\n", " new_segment += '.'\n", " grid[0] = grid[0][:l-1] + new_segment + grid[0][r:]\n", " return grid" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def left(grid, t, b):\n", " for i in range(t-1, b):\n", " if grid[i][0] == '.':\n", " grid[i] = '*' + grid[i][1:]\n", " else:\n", " grid[i] = '.' + grid[i][1:]\n", " return grid" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def rotate_column(grid, c, raw_n):\n", " n = raw_n % len(grid)\n", " col = [row[c-1] for row in grid]\n", " new_col = col[-n:] + col[:-n]\n", " for i in range(len(grid)):\n", " grid[i] = grid[i][:c-1] + new_col[i] + grid[i][c:]\n", " return grid" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def rotate_row(grid, r, raw_n):\n", " n = raw_n % len(grid[0])\n", " grid[r-1] = grid[r-1][-n:] + grid[r-1][:-n]\n", " return grid" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "command_dispatch = {'left': left, 'top': top,\n", " 'rotate row': rotate_row,\n", " 'rotate column': rotate_column}" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def parse(command):\n", " cmd, a, b = command.rsplit(maxsplit=2)\n", " return cmd, int(a), int(b) " ] }, { "cell_type": "code", "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, 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", " 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(overprint_delay)\n", " if md: \n", " print('`{}`'.format(c))\n", " else:\n", " print(c)\n", " print_grid(grid, md=md)\n", " print()\n", " if overprint:\n", " clear_output(wait=True)\n", " if show_each_step: \n", " print('Final')\n", " print_grid(grid, md=md)\n", " return grid" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "237" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cmds = [c.strip() for c in open('05-pixels.txt').readlines()]\n", "len(cmds)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "188" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = interpret(cmds)\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": {}, "source": [ "## Part 2\n", "When you've executed your commands, what does the board say your destination is?" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "...****..............*...................*.....*..............*.................\n", "......*..............*...................***..**..............*.................\n", "......*.*****.*****.****.*****..****.....*.*.***.*****.*****.****.*****..****...\n", "......*.....*.*...*..*.......*..*........*..**.*.....*.*...*..*.......*..*......\n", "......*.*****.*...*..*...*****..*........*..*..*.*****.*...*..*...*****..*......\n", "......*.*...*.*...*..*...*...*..*........*.....*.*...*.*...*..*...*...*..*......\n", "...*..*.*..**.*...*..**..*..**..*........*.....*.*..**.*...*..**..*..**..*......\n", "....**...**.*.*...*...**..**.*..*........*.....*..**.*.*...*...**..**.*..*......\n" ] } ], "source": [ "print_grid(g)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " **** * * * * \n", " * * *** ** * \n", " * ***** ***** **** ***** **** * * *** ***** ***** **** ***** **** \n", " * * * * * * * * ** * * * * * * * \n", " * ***** * * * ***** * * * * ***** * * * ***** * \n", " * * * * * * * * * * * * * * * * * * * \n", " * * * ** * * ** * ** * * * * ** * * ** * ** * \n", " ** ** * * * ** ** * * * * ** * * * ** ** * * \n" ] } ], "source": [ "print_grid(g, suppress_dots=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "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.5.2+" } }, "nbformat": 4, "nbformat_minor": 2 }