{
 "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": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "226"
      ]
     },
     "execution_count": 17,
     "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": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61762"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(len(t) for t in tours if valid(trace_tour(t)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(1 for t in tours if valid(trace_tour(t)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "123845"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(len(t) for t in tours)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 214 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": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80622"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(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",
    " + \n",
    " sum(len(t) for t in tours if valid(trace_tour(t))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1min 32s 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": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "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": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "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": 25,
   "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": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(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": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "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": 28,
   "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": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80622"
      ]
     },
     "execution_count": 29,
     "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": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.18 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": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(goods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "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": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(good_is)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(136, 9),\n",
       " (70, 48),\n",
       " (123, 51),\n",
       " (152, 63),\n",
       " (201, 83),\n",
       " (212, 113),\n",
       " (16, 125),\n",
       " (91, 128),\n",
       " (110, 134),\n",
       " (168, 150),\n",
       " (142, 193),\n",
       " (116, 194),\n",
       " (208, 204)]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(good_is, key=lambda p: p[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(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",
       " (21, 1),\n",
       " (24, 1),\n",
       " (132, 2),\n",
       " (26, 2),\n",
       " (28, 1),\n",
       " (29, 1),\n",
       " (34, 2),\n",
       " (36, 1),\n",
       " (37, 3),\n",
       " (166, 2),\n",
       " (40, 2),\n",
       " (41, 2),\n",
       " (44, 3),\n",
       " (46, 1),\n",
       " (48, 2),\n",
       " (50, 3),\n",
       " (52, 2),\n",
       " (53, 1),\n",
       " (54, 1),\n",
       " (56, 2),\n",
       " (57, 3),\n",
       " (58, 1),\n",
       " (59, 2),\n",
       " (61, 1),\n",
       " (64, 1),\n",
       " (66, 2),\n",
       " (68, 1),\n",
       " (70, 1),\n",
       " (74, 1),\n",
       " (75, 1),\n",
       " (76, 3),\n",
       " (77, 1),\n",
       " (81, 1),\n",
       " (82, 2),\n",
       " (86, 1),\n",
       " (88, 1),\n",
       " (90, 1),\n",
       " (94, 1),\n",
       " (97, 1),\n",
       " (98, 1),\n",
       " (101, 2),\n",
       " (106, 1),\n",
       " (107, 1),\n",
       " (114, 2),\n",
       " (117, 3),\n",
       " (127, 1)]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(l, len(l1s[l])) for l in l1s.keys()]"
   ]
  },
  {
   "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
}