4 "cell_type": "markdown",
7 "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",
8 "1. which tours are closed?\n",
9 "2. what is the area enclosed by the tour?"
20 "import collections\n",
25 "import matplotlib.pyplot as plt\n",
26 "%matplotlib inline\n"
37 "class Direction(enum.Enum):\n",
43 "turn_lefts = {Direction.UP: Direction.LEFT, Direction.LEFT: Direction.DOWN,\n",
44 " Direction.DOWN: Direction.RIGHT, Direction.RIGHT: Direction.UP}\n",
46 "turn_rights = {Direction.UP: Direction.RIGHT, Direction.RIGHT: Direction.DOWN,\n",
47 " Direction.DOWN: Direction.LEFT, Direction.LEFT: Direction.UP}\n",
49 "def turn_left(d):\n",
50 " return turn_lefts[d]\n",
52 "def turn_right(d):\n",
53 " return turn_rights[d]\n"
64 "Step = collections.namedtuple('Step', ['x', 'y', 'dir'])\n",
65 "Mistake = collections.namedtuple('Mistake', ['i', 'step'])"
76 "def advance(step, d):\n",
77 " if d == Direction.UP:\n",
78 " return Step(step.x, step.y+1, d)\n",
79 " elif d == Direction.DOWN:\n",
80 " return Step(step.x, step.y-1, d)\n",
81 " elif d == Direction.LEFT:\n",
82 " return Step(step.x-1, step.y, d)\n",
83 " elif d == Direction.RIGHT:\n",
84 " return Step(step.x+1, step.y, d)"
95 "def step(s, current):\n",
97 " return advance(current, current.dir)\n",
99 " return advance(current, turn_left(current.dir))\n",
101 " return advance(current, turn_right(current.dir))\n",
108 "execution_count": 6,
114 "def trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):\n",
115 " current = Step(startx, starty, startdir)\n",
116 " trace = [current]\n",
118 " current = step(s, current)\n",
119 " trace += [current]\n",
125 "execution_count": 7,
131 "def positions(trace):\n",
132 " return [(s.x, s.y) for s in trace]"
137 "execution_count": 8,
143 "def valid(trace):\n",
144 " return (trace[-1].x == 0 \n",
145 " and trace[-1].y == 0 \n",
146 " and len(set(positions(trace))) + 1 == len(trace))"
151 "execution_count": 9,
157 "def valid_prefix(tour):\n",
158 " current = Step(0, 0, Direction.RIGHT)\n",
162 " current = step(s, current)\n",
164 " if (current.x, current.y) in posns:\n",
166 " elif current.x == 0 and current.y == 0: \n",
167 " return ''.join(prefix)\n",
168 " posns += [(current.x, current.y)]\n",
169 " if current.x == 0 and current.y == 0:\n",
170 " return ''.join(prefix)\n",
177 "execution_count": 10,
183 "def mistake_positions(trace, debug=False):\n",
185 " current = trace[0]\n",
186 " posns = [(0, 0)]\n",
187 " for i, current in enumerate(trace[1:]):\n",
188 " if (current.x, current.y) in posns:\n",
189 " if debug: print(i, current)\n",
190 " mistakes += [Mistake(i+1, current)]\n",
191 " posns += [(current.x, current.y)]\n",
192 " if (current.x, current.y) == (0, 0):\n",
193 " return mistakes[:-1]\n",
195 " return mistakes + [Mistake(len(trace)+1, current)]"
200 "execution_count": 11,
206 "def returns_to_origin(mistake_positions):\n",
207 " return [i for i, m in mistake_positions\n",
208 " if (m.x, m.y) == (0, 0)]"
213 "execution_count": 12,
219 "sample_tours = ['FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL']"
224 "execution_count": 13,
230 "def bounds(trace):\n",
231 " return (max(s.x for s in trace),\n",
232 " max(s.y for s in trace),\n",
233 " min(s.x for s in trace),\n",
234 " min(s.y for s in trace))"
239 "execution_count": 14,
245 "plot_wh = {Direction.UP: (0, 1), Direction.LEFT: (-1, 0),\n",
246 " Direction.DOWN: (0, -1), Direction.RIGHT: (1, 0)}"
251 "execution_count": 15,
257 "def chunks(items, n=2):\n",
258 " return [items[i:i+n] for i in range(len(items) - n + 1)]"
263 "execution_count": 16,
269 "def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):\n",
271 " plt.axes().set_aspect('equal')\n",
272 " for s, t in chunks(trace, 2):\n",
273 " w, h = plot_wh[t.dir]\n",
274 " 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",
275 " xh, yh, xl, yl = bounds(trace)\n",
276 " if xybounds is not None: \n",
277 " bxh, byh, bxl, byl = xybounds\n",
278 " plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])\n",
279 " plt.ylim([min(yl, byl)-1, max(yh, byh)+1])\n",
281 " plt.xlim([xl-1, xh+1])\n",
282 " plt.ylim([yl-1, yh+1])\n",
284 " plt.savefig(filename)"
288 "cell_type": "markdown",
296 "execution_count": 23,
305 "execution_count": 23,
307 "output_type": "execute_result"
311 "with open('06-tours.txt') as f:\n",
312 " tours = [t.strip() for t in f.readlines()]\n",
318 "execution_count": 24,
327 "execution_count": 24,
329 "output_type": "execute_result"
333 "sum(len(t) for t in tours if valid(trace_tour(t)))"
338 "execution_count": 45,
343 "output_type": "stream",
345 "1 loop, best of 3: 209 ms per loop\n"
351 "sum(len(t) for t in tours if valid(trace_tour(t)))"
355 "cell_type": "markdown",
363 "execution_count": 25,
368 "output_type": "stream",
370 "1 loop, best of 3: 1min 29s per loop\n"
377 " for i, pi in enumerate(tours) \n",
378 " for j, pj in enumerate(tours)\n",
380 " if not valid(trace_tour(pi))\n",
381 " if not valid(trace_tour(pj))\n",
382 " if valid(trace_tour(pi + pj))]"
387 "execution_count": 31,
408 "execution_count": 31,
410 "output_type": "execute_result"
415 " for i, pi in enumerate(tours) \n",
416 " for j, pj in enumerate(tours)\n",
418 " if not valid(trace_tour(pi))\n",
419 " if not valid(trace_tour(pj))\n",
420 " if valid(trace_tour(pi + pj))]"
425 "execution_count": 42,
434 "execution_count": 42,
436 "output_type": "execute_result"
440 "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
442 " sum(len(pi + pj) \n",
443 " for i, pi in enumerate(tours) \n",
444 " for j, pj in enumerate(tours)\n",
446 " if not valid(trace_tour(pi))\n",
447 " if not valid(trace_tour(pj))\n",
448 " if valid(trace_tour(pi + pj)))\n",
454 "execution_count": 34,
459 "output_type": "stream",
479 " tr = trace_tour(t)\n",
480 " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
482 " if l1 not in l1s:\n",
488 " print(l1, len(l1s[l1]))"
493 "execution_count": 30,
514 "execution_count": 30,
516 "output_type": "execute_result"
520 "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
525 "execution_count": 27,
530 "output_type": "stream",
532 "1 loop, best of 3: 1min 28s per loop\n"
538 "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
540 " sum(len(pi + pj) \n",
541 " for i, pi in enumerate(tours) \n",
542 " for j, pj in enumerate(tours)\n",
544 " if not valid(trace_tour(pi))\n",
545 " if not valid(trace_tour(pj))\n",
546 " if valid(trace_tour(pi + pj)))\n",
552 "execution_count": 50,
562 " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
563 " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
564 " for t1 in candidates:\n",
565 " for t2 in candidates:\n",
568 " if (t12) not in tried:\n",
569 " tried += [(t12)]\n",
570 " if valid(trace_tour(t12)):\n",
571 " good_is += [(tours.index(t1), tours.index(t2))]\n",
577 "execution_count": 51,
586 "execution_count": 51,
588 "output_type": "execute_result"
592 "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
594 " sum(len(t12) for t12 in goods)\n",
600 "execution_count": 52,
605 "output_type": "stream",
607 "1 loop, best of 3: 1.16 s per loop\n"
616 " tr = trace_tour(t)\n",
617 " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
619 " if l1 not in l1s:\n",
626 " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
627 " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
628 " for t1 in candidates:\n",
629 " for t2 in candidates:\n",
632 " if (t12) not in tried:\n",
633 " tried += [(t12)]\n",
634 " if valid(trace_tour(t12)):\n",
637 "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
639 " sum(len(t12) for t12 in goods)\n",
645 "execution_count": null,
655 "display_name": "Python 3",
656 "language": "python",
664 "file_extension": ".py",
665 "mimetype": "text/x-python",
667 "nbconvert_exporter": "python",
668 "pygments_lexer": "ipython3",