Added a new day 3, rearranged days
[ou-summer-of-code-2017.git] / 05-display-board / display-board-solution.ipynb
diff --git a/05-display-board/display-board-solution.ipynb b/05-display-board/display-board-solution.ipynb
new file mode 100644 (file)
index 0000000..1ea9fc0
--- /dev/null
@@ -0,0 +1,401 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Laser display boards\n",
+    "\n",
+    "You need to navigate your way through Heathwick Airport to find the correct gate. The bad news is that all the display boards have gone down. The good news is that the terminal 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 pixles 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 `toggle` 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",
+    "* `toggle 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",
+    "* `toggle 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 1` moves the one lit pixel in column 8 down one row.\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](03-pixels.txt). How many pixels would be lit on the board, if it was working?"
+   ]
+  },
+  {
+   "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": 11,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def interpret(commands, grid=None, w=WIDTH, h=HEIGHT, \n",
+    "              show_each_step=False, md=False, overprint=False):\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",
+    "        else:\n",
+    "            raise ValueError('Unknown command')\n",
+    "        if show_each_step:\n",
+    "            if overprint:\n",
+    "                time.sleep(0.25)\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": "markdown",
+   "metadata": {},
+   "source": [
+    "## Part 2\n",
+    "Where does the flight go from gate 9¾?"
+   ]
+  },
+  {
+   "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
+}