--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "Given a sequence of {F|L|R}, each of which is \"move forward one step\", \"turn left, then move forward one step\", \"turn right, then move forward one step\":\n",
+ "1. which tours are closed?\n",
+ "2. what is the area enclosed by the tour?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import collections\n",
+ "import enum\n",
+ "import random\n",
+ "import os\n",
+ "\n",
+ "import matplotlib.pyplot as plt\n",
+ "%matplotlib inline\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "class Direction(enum.Enum):\n",
+ " UP = 1\n",
+ " RIGHT = 2\n",
+ " DOWN = 3\n",
+ " LEFT = 4\n",
+ " \n",
+ "turn_lefts = {Direction.UP: Direction.LEFT, Direction.LEFT: Direction.DOWN,\n",
+ " Direction.DOWN: Direction.RIGHT, Direction.RIGHT: Direction.UP}\n",
+ "\n",
+ "turn_rights = {Direction.UP: Direction.RIGHT, Direction.RIGHT: Direction.DOWN,\n",
+ " Direction.DOWN: Direction.LEFT, Direction.LEFT: Direction.UP}\n",
+ "\n",
+ "def turn_left(d):\n",
+ " return turn_lefts[d]\n",
+ "\n",
+ "def turn_right(d):\n",
+ " return turn_rights[d]\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "Step = collections.namedtuple('Step', ['x', 'y', 'dir'])\n",
+ "Mistake = collections.namedtuple('Mistake', ['i', 'step'])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def advance(step, d):\n",
+ " if d == Direction.UP:\n",
+ " return Step(step.x, step.y+1, d)\n",
+ " elif d == Direction.DOWN:\n",
+ " return Step(step.x, step.y-1, d)\n",
+ " elif d == Direction.LEFT:\n",
+ " return Step(step.x-1, step.y, d)\n",
+ " elif d == Direction.RIGHT:\n",
+ " return Step(step.x+1, step.y, d)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def step(s, current):\n",
+ " if s == 'F':\n",
+ " return advance(current, current.dir)\n",
+ " elif s == 'L':\n",
+ " return advance(current, turn_left(current.dir))\n",
+ " elif s == 'R':\n",
+ " return advance(current, turn_right(current.dir))\n",
+ " else:\n",
+ " raise ValueError"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):\n",
+ " current = Step(startx, starty, startdir)\n",
+ " trace = [current]\n",
+ " for s in tour:\n",
+ " current = step(s, current)\n",
+ " trace += [current]\n",
+ " return trace "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def positions(trace):\n",
+ " return [(s.x, s.y) for s in trace]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def valid(trace):\n",
+ " return (trace[-1].x == 0 \n",
+ " and trace[-1].y == 0 \n",
+ " and len(set(positions(trace))) + 1 == len(trace))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def valid_prefix(tour):\n",
+ " current = Step(0, 0, Direction.RIGHT)\n",
+ " prefix = []\n",
+ " posns = []\n",
+ " for s in tour:\n",
+ " current = step(s, current)\n",
+ " prefix += [s]\n",
+ " if (current.x, current.y) in posns:\n",
+ " return ''\n",
+ " elif current.x == 0 and current.y == 0: \n",
+ " return ''.join(prefix)\n",
+ " posns += [(current.x, current.y)]\n",
+ " if current.x == 0 and current.y == 0:\n",
+ " return ''.join(prefix)\n",
+ " else:\n",
+ " return ''"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def mistake_positions(trace, debug=False):\n",
+ " mistakes = []\n",
+ " current = trace[0]\n",
+ " posns = [(0, 0)]\n",
+ " for i, current in enumerate(trace[1:]):\n",
+ " if (current.x, current.y) in posns:\n",
+ " if debug: print(i, current)\n",
+ " mistakes += [Mistake(i+1, current)]\n",
+ " posns += [(current.x, current.y)]\n",
+ " if (current.x, current.y) == (0, 0):\n",
+ " return mistakes[:-1]\n",
+ " else:\n",
+ " return mistakes + [Mistake(len(trace)+1, current)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def returns_to_origin(mistake_positions):\n",
+ " return [i for i, m in mistake_positions\n",
+ " if (m.x, m.y) == (0, 0)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "sample_tours = ['FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def bounds(trace):\n",
+ " return (max(s.x for s in trace),\n",
+ " max(s.y for s in trace),\n",
+ " min(s.x for s in trace),\n",
+ " min(s.y for s in trace))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "plot_wh = {Direction.UP: (0, 1), Direction.LEFT: (-1, 0),\n",
+ " Direction.DOWN: (0, -1), Direction.RIGHT: (1, 0)}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def chunks(items, n=2):\n",
+ " return [items[i:i+n] for i in range(len(items) - n + 1)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):\n",
+ " plt.axis('on')\n",
+ " plt.axes().set_aspect('equal')\n",
+ " for s, t in chunks(trace, 2):\n",
+ " w, h = plot_wh[t.dir]\n",
+ " plt.arrow(s.x, s.y, w, h, head_width=0.1, head_length=0.1, fc=colour, ec=colour, length_includes_head=True)\n",
+ " xh, yh, xl, yl = bounds(trace)\n",
+ " if xybounds is not None: \n",
+ " bxh, byh, bxl, byl = xybounds\n",
+ " plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])\n",
+ " plt.ylim([min(yl, byl)-1, max(yh, byh)+1])\n",
+ " else:\n",
+ " plt.xlim([xl-1, xh+1])\n",
+ " plt.ylim([yl-1, yh+1])\n",
+ " if filename:\n",
+ " plt.savefig(filename)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Part 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "226"
+ ]
+ },
+ "execution_count": 23,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "with open('06-tours.txt') as f:\n",
+ " tours = [t.strip() for t in f.readlines()]\n",
+ "len(tours)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "61762"
+ ]
+ },
+ "execution_count": 24,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(len(t) for t in tours if valid(trace_tour(t)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 209 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "sum(len(t) for t in tours if valid(trace_tour(t)))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Part 2"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1min 29s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "[(i, j) \n",
+ " for i, pi in enumerate(tours) \n",
+ " for j, pj in enumerate(tours)\n",
+ " if i != j\n",
+ " if not valid(trace_tour(pi))\n",
+ " if not valid(trace_tour(pj))\n",
+ " if valid(trace_tour(pi + pj))]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(16, 125),\n",
+ " (70, 48),\n",
+ " (91, 128),\n",
+ " (110, 134),\n",
+ " (116, 194),\n",
+ " (123, 51),\n",
+ " (136, 9),\n",
+ " (142, 193),\n",
+ " (152, 63),\n",
+ " (168, 150),\n",
+ " (201, 83),\n",
+ " (208, 204),\n",
+ " (212, 113)]"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[(i, j) \n",
+ " for i, pi in enumerate(tours) \n",
+ " for j, pj in enumerate(tours)\n",
+ " if i != j\n",
+ " if not valid(trace_tour(pi))\n",
+ " if not valid(trace_tour(pj))\n",
+ " if valid(trace_tour(pi + pj))]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "80622"
+ ]
+ },
+ "execution_count": 42,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(pi + pj) \n",
+ " for i, pi in enumerate(tours) \n",
+ " for j, pj in enumerate(tours)\n",
+ " if i != j\n",
+ " if not valid(trace_tour(pi))\n",
+ " if not valid(trace_tour(pj))\n",
+ " if valid(trace_tour(pi + pj)))\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 1\n",
+ "2 1\n",
+ "3 4\n",
+ "4 5\n",
+ "5 7\n",
+ "6 3\n",
+ "7 1\n",
+ "8 2\n",
+ "9 2\n",
+ "11 2\n",
+ "18 1\n",
+ "19 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "l1s = {}\n",
+ "for t in tours:\n",
+ " tr = trace_tour(t)\n",
+ " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
+ " if l1 > 0:\n",
+ " if l1 not in l1s:\n",
+ " l1s[l1] = []\n",
+ " l1s[l1] += [t]\n",
+ "\n",
+ "for l1 in l1s:\n",
+ " if l1 < 20:\n",
+ " print(l1, len(l1s[l1]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(0, 124),\n",
+ " (1, 1),\n",
+ " (2, 1),\n",
+ " (3, 4),\n",
+ " (4, 5),\n",
+ " (5, 7),\n",
+ " (6, 3),\n",
+ " (7, 1),\n",
+ " (8, 2),\n",
+ " (9, 2),\n",
+ " (11, 2),\n",
+ " (18, 1),\n",
+ " (19, 1)]"
+ ]
+ },
+ "execution_count": 30,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1min 28s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(pi + pj) \n",
+ " for i, pi in enumerate(tours) \n",
+ " for j, pj in enumerate(tours)\n",
+ " if i != j\n",
+ " if not valid(trace_tour(pi))\n",
+ " if not valid(trace_tour(pj))\n",
+ " if valid(trace_tour(pi + pj)))\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "good_is = []\n",
+ "goods = []\n",
+ "tried = []\n",
+ "for l1 in l1s:\n",
+ " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
+ " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
+ " for t1 in candidates:\n",
+ " for t2 in candidates:\n",
+ " if t1 != t2:\n",
+ " t12 = t1 + t2\n",
+ " if (t12) not in tried:\n",
+ " tried += [(t12)]\n",
+ " if valid(trace_tour(t12)):\n",
+ " good_is += [(tours.index(t1), tours.index(t2))]\n",
+ " goods += [t12]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 51,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "80622"
+ ]
+ },
+ "execution_count": 51,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(t12) for t12 in goods)\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1.16 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "\n",
+ "l1s = {}\n",
+ "for t in tours:\n",
+ " tr = trace_tour(t)\n",
+ " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
+ " if l1 > 0:\n",
+ " if l1 not in l1s:\n",
+ " l1s[l1] = []\n",
+ " l1s[l1] += [t]\n",
+ "\n",
+ "goods = []\n",
+ "tried = []\n",
+ "for l1 in l1s:\n",
+ " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
+ " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
+ " for t1 in candidates:\n",
+ " for t2 in candidates:\n",
+ " if t1 != t2:\n",
+ " t12 = t1 + t2\n",
+ " if (t12) not in tried:\n",
+ " tried += [(t12)]\n",
+ " if valid(trace_tour(t12)):\n",
+ " goods += [t12]\n",
+ "\n",
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(t12) for t12 in goods)\n",
+ ")"
+ ]
+ },
+ {
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff