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",
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 trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):\n",
96 " current = Step(startx, starty, startdir)\n",
97 " trace = [current]\n",
100 " current = advance(current, current.dir)\n",
102 " current = advance(current, turn_left(current.dir))\n",
104 " current = advance(current, turn_right(current.dir))\n",
105 " trace += [current]\n",
111 "execution_count": 6,
117 "def positions(trace):\n",
118 " return [(s.x, s.y) for s in trace]"
123 "execution_count": 7,
129 "def valid(trace):\n",
130 " return (trace[-1].x == 0 \n",
131 " and trace[-1].y == 0 \n",
132 " and len(set(positions(trace))) + 1 == len(trace))"
137 "execution_count": 8,
143 "def chunks(items, n=2):\n",
144 " return [items[i:i+n] for i in range(len(items) - n + 1)]"
148 "cell_type": "markdown",
151 "Using the [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)"
156 "execution_count": 9,
162 "def shoelace(trace):\n",
163 " return abs(sum(s.x * t.y - t.x * s.y for s, t in chunks(trace, 2))) // 2"
168 "execution_count": 10,
174 "def step(s, current):\n",
176 " return advance(current, current.dir)\n",
178 " return advance(current, turn_left(current.dir))\n",
180 " return advance(current, turn_right(current.dir))\n",
187 "execution_count": 11,
193 "def valid_prefix(tour):\n",
194 " current = Step(0, 0, Direction.RIGHT)\n",
198 " current = step(s, current)\n",
200 " if (current.x, current.y) in posns:\n",
202 " elif current.x == 0 and current.y == 0: \n",
203 " return ''.join(prefix)\n",
204 " posns += [(current.x, current.y)]\n",
205 " if current.x == 0 and current.y == 0:\n",
206 " return ''.join(prefix)\n",
213 "execution_count": 12,
219 "def mistake_positions(trace, debug=False):\n",
221 " current = trace[0]\n",
222 " posns = [(0, 0)]\n",
223 " for i, current in enumerate(trace[1:]):\n",
224 " if (current.x, current.y) in posns:\n",
225 " if debug: print(i, current)\n",
226 " mistakes += [Mistake(i+1, current)]\n",
227 " posns += [(current.x, current.y)]\n",
228 " if (current.x, current.y) == (0, 0):\n",
229 " return mistakes[:-1]\n",
231 " return mistakes + [Mistake(len(trace)+1, current)]"
236 "execution_count": 13,
242 "def returns_to_origin(mistake_positions):\n",
243 " return [i for i, m in mistake_positions\n",
244 " if (m.x, m.y) == (0, 0)]"
249 "execution_count": 14,
255 "def random_walk(steps=1000):\n",
256 " return ''.join(random.choice('FFLR') for _ in range(steps))"
261 "execution_count": 15,
267 "def bounds(trace):\n",
268 " return (max(s.x for s in trace),\n",
269 " max(s.y for s in trace),\n",
270 " min(s.x for s in trace),\n",
271 " min(s.y for s in trace))"
276 "execution_count": 16,
282 "def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):\n",
284 " plt.axes().set_aspect('equal')\n",
285 " for s, t in chunks(trace, 2):\n",
286 " w, h = plot_wh[t.dir]\n",
287 " 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",
288 " xh, yh, xl, yl = bounds(trace)\n",
289 " if xybounds is not None: \n",
290 " bxh, byh, bxl, byl = xybounds\n",
291 " plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])\n",
292 " plt.ylim([min(yl, byl)-1, max(yh, byh)+1])\n",
294 " plt.xlim([xl-1, xh+1])\n",
295 " plt.ylim([yl-1, yh+1])\n",
297 " plt.savefig(filename)"
302 "execution_count": 17,
308 "def trim_loop(tour):\n",
309 " trace = trace_tour(tour)\n",
310 " mistakes = mistake_positions(trace)\n",
311 " end_mistake_index = 0\n",
312 "# print('end_mistake_index {} pointing to trace position {}; {} mistakes and {} in trace; {}'.format(end_mistake_index, mistakes[end_mistake_index].i, len(mistakes), len(trace), mistakes))\n",
313 " # while this mistake extends to the next step in the trace...\n",
314 " while (mistakes[end_mistake_index].i + 1 < len(trace) and \n",
315 " end_mistake_index + 1 < len(mistakes) and\n",
316 " mistakes[end_mistake_index].i + 1 == \n",
317 " mistakes[end_mistake_index + 1].i):\n",
318 "# print('end_mistake_index {} pointing to trace position {}; {} mistakes and {} in trace'.format(end_mistake_index, mistakes[end_mistake_index].i, len(mistakes), len(trace), mistakes))\n",
319 " # push this mistake finish point later\n",
320 " end_mistake_index += 1\n",
321 " mistake = mistakes[end_mistake_index]\n",
323 " # find the first location that mentions where this mistake ends (which the point where the loop starts)\n",
324 " mistake_loop_start = max(i for i, loc in enumerate(trace[:mistake.i])\n",
325 " if (loc.x, loc.y) == (mistake.step.x, mistake.step.y))\n",
326 "# print('Dealing with mistake from', mistake_loop_start, 'to', mistake.i, ', trace has len', len(trace))\n",
328 " # direction before entering the loop\n",
329 " direction_before = trace[mistake_loop_start].dir\n",
331 " # find the new instruction to turn from heading before the loop to heading after the loop\n",
332 " new_instruction = 'F'\n",
333 " if (mistake.i + 1) < len(trace):\n",
334 " if turn_left(direction_before) == trace[mistake.i + 1].dir:\n",
335 " new_instruction = 'L'\n",
336 " if turn_right(direction_before) == trace[mistake.i + 1].dir:\n",
337 " new_instruction = 'R'\n",
338 "# if (mistake.i + 1) < len(trace):\n",
339 "# print('turning from', direction_before, 'to', trace[mistake.i + 1].dir, 'with', new_instruction )\n",
341 "# print('turning from', direction_before, 'to BEYOND END', 'with', new_instruction )\n",
342 " return tour[:mistake_loop_start] + new_instruction + tour[mistake.i+1:]\n",
343 "# return mistake, mistake_loop_start, trace[mistake_loop_start-2:mistake_loop_start+8]"
348 "execution_count": 18,
354 "def trim_all_loops(tour, mistake_reduction_attempt_limit=10):\n",
355 " trace = trace_tour(tour)\n",
356 " mistake_limit = 1\n",
357 " if trace[-1].x == 0 and trace[-1].y == 0:\n",
358 " mistake_limit = 0\n",
359 " mistakes = mistake_positions(trace)\n",
361 " old_mistake_count = len(mistakes)\n",
362 " mistake_reduction_tries = 0\n",
364 " while len(mistakes) > mistake_limit and mistake_reduction_tries < mistake_reduction_attempt_limit:\n",
365 " tour = trim_loop(tour)\n",
366 " trace = trace_tour(tour)\n",
367 " mistakes = mistake_positions(trace)\n",
368 " if len(mistakes) < old_mistake_count:\n",
369 " old_mistake_count = len(mistakes)\n",
370 " mistake_reduction_tries = 0\n",
372 " mistake_reduction_tries += 1\n",
373 " if mistake_reduction_tries >= mistake_reduction_attempt_limit:\n",
381 "execution_count": 19,
387 "def reverse_tour(tour):\n",
388 " def swap(tour_step):\n",
389 " if tour_step == 'R':\n",
391 " elif tour_step == 'L':\n",
394 " return tour_step\n",
396 " return ''.join(swap(s) for s in reversed(tour))"
401 "execution_count": 20,
407 "def wander_near(locus, current, limit=10):\n",
408 " valid_proposal = False\n",
409 " while not valid_proposal:\n",
410 " s = random.choice('FFFRL')\n",
412 " proposed = advance(current, current.dir)\n",
414 " proposed = advance(current, turn_left(current.dir))\n",
416 " proposed = advance(current, turn_right(current.dir))\n",
417 " if abs(proposed.x - locus.x) < limit and abs(proposed.y - locus.y) < limit:\n",
418 " valid_proposal = True\n",
419 "# print('At {} going to {} by step {} to {}'.format(current, locus, s, proposed))\n",
420 " return s, proposed"
425 "execution_count": 21,
431 "def seek(goal, current):\n",
432 " dx = current.x - goal.x\n",
433 " dy = current.y - goal.y\n",
435 " if dx < 0 and abs(dx) > abs(dy): # to the left\n",
437 " if current.dir == Direction.RIGHT:\n",
439 " elif current.dir == Direction.UP:\n",
443 " elif dx > 0 and abs(dx) > abs(dy): # to the right\n",
445 " if current.dir == Direction.LEFT:\n",
447 " elif current.dir == Direction.UP:\n",
451 " elif dy > 0 and abs(dx) <= abs(dy): # above\n",
453 " if current.dir == Direction.DOWN:\n",
455 " elif current.dir == Direction.RIGHT:\n",
461 " if current.dir == Direction.UP:\n",
463 " elif current.dir == Direction.LEFT:\n",
468 " proposed = advance(current, current.dir)\n",
470 " proposed = advance(current, turn_left(current.dir))\n",
472 " proposed = advance(current, turn_right(current.dir))\n",
474 "# print('At {} going to {}, currently {}, by step {} to {}'.format(current, goal, side, s, proposed))\n",
476 " return s, proposed"
481 "execution_count": 22,
487 "def guided_walk(loci, locus_limit=5, wander_limit=10, seek_step_limit=20):\n",
489 " current = Step(0, 0, Direction.RIGHT) \n",
491 " finished = False\n",
492 " while not finished:\n",
493 " if abs(current.x - loci[l].x) < locus_limit and abs(current.y - loci[l].y) < locus_limit:\n",
495 " if l == len(loci) - 1:\n",
496 " finished = True\n",
497 " s, proposed = wander_near(loci[l], current, limit=wander_limit)\n",
499 " current = proposed\n",
500 "# print('!! Finished loci')\n",
502 " while not (current.x == loci[l].x and current.y == loci[l].y) and seek_steps < seek_step_limit:\n",
503 "# error = max(abs(current.x - loci[l].x), abs(current.y - loci[l].y))\n",
504 "# s, proposed = wander_near(loci[l], current, limit=error+1)\n",
505 " s, proposed = seek(loci[l], current)\n",
507 " current = proposed\n",
508 " seek_steps += 1\n",
509 " if seek_steps >= seek_step_limit:\n",
517 "execution_count": 24,
521 "def square_tour(a=80):\n",
522 " \"a is width of square\"\n",
523 " return ('F' * a + 'L') * 4"
528 "execution_count": 25,
532 "def cross_tour(a=50, b=40):\n",
533 " \"a is width of cross arm, b is length of cross arm\"\n",
534 " return ('F' * a + 'L' + 'F' * b + 'R' + 'F' * b + 'L') * 4"
539 "execution_count": 26,
543 "def quincunx_tour(a=60, b=30, c=50):\n",
544 " \"a is length of indent, b is indent/outdent distance, c is outdent outer length\"\n",
545 " return ('F' * a + 'R' + 'F' * b + 'L' + 'F' * c + 'L' + 'F' * c + 'L' + 'F' * b + 'R') * 4\n"
550 "execution_count": 27,
554 "heart_points = [Step(60, 50, Direction.UP), Step(50, 90, Direction.UP),\n",
555 " Step(20, 70, Direction.UP), \n",
556 " Step(-40, 90, Direction.UP), Step(-60, 80, Direction.UP), \n",
557 " Step(0, 0, Direction.RIGHT)]\n",
560 "current = Step(0, 0, Direction.RIGHT)\n",
562 "for hp in heart_points:\n",
563 " while not (current.x == hp.x and current.y == hp.y):\n",
564 " s, proposed = seek(hp, current)\n",
565 " heart_tour += s\n",
566 " current = proposed\n",
568 "def heart_tour_func(): return heart_tour"
573 "execution_count": 28,
579 "# success_count = 0\n",
580 "# while success_count <= 20:\n",
581 "# lc = trace_tour(square_tour(a=10))\n",
582 "# rw = guided_walk(lc, wander_limit=4, locus_limit=2)\n",
584 "# rw_trimmed = trim_all_loops(rw)\n",
585 "# if len(rw_trimmed) > 10:\n",
586 "# with open('small-squares.txt', 'a') as f:\n",
587 "# f.write(rw_trimmed + '\\n')\n",
588 "# success_count += 1"
593 "execution_count": 29,
599 "# success_count = 0\n",
600 "# while success_count <= 20:\n",
601 "# lc = trace_tour(square_tour())\n",
602 "# rw = guided_walk(lc)\n",
604 "# rw_trimmed = trim_all_loops(rw)\n",
605 "# if len(rw_trimmed) > 10:\n",
606 "# with open('large-squares.txt', 'a') as f:\n",
607 "# f.write(rw_trimmed + '\\n')\n",
608 "# success_count += 1"
613 "execution_count": 30,
619 "# success_count = 0\n",
620 "# while success_count <= 20:\n",
621 "# lc = trace_tour(cross_tour())\n",
622 "# rw = guided_walk(lc)\n",
624 "# rw_trimmed = trim_all_loops(rw)\n",
625 "# if len(rw_trimmed) > 10:\n",
626 "# with open('cross.txt', 'a') as f:\n",
627 "# f.write(rw_trimmed + '\\n')\n",
628 "# success_count += 1"
633 "execution_count": 31,
639 "# success_count = 0\n",
640 "# while success_count <= 20:\n",
641 "# lc = trace_tour(quincunx_tour())\n",
642 "# rw = guided_walk(lc)\n",
644 "# rw_trimmed = trim_all_loops(rw)\n",
645 "# if len(rw_trimmed) > 10:\n",
646 "# with open('quincunx.txt', 'a') as f:\n",
647 "# f.write(rw_trimmed + '\\n')\n",
648 "# success_count += 1"
653 "execution_count": 32,
659 "patterns = [square_tour, cross_tour, quincunx_tour, heart_tour_func]\n",
660 "tours_filename = 'tours.txt'\n",
663 " os.remove(tours_filename)\n",
667 "success_count = 0\n",
668 "while success_count < 100:\n",
669 " lc = trace_tour(random.choice(patterns)())\n",
670 " rw = guided_walk(lc)\n",
672 " rw_trimmed = trim_all_loops(rw)\n",
673 " if len(rw_trimmed) > 10:\n",
674 " with open(tours_filename, 'a') as f:\n",
675 " f.write(rw_trimmed + '\\n')\n",
676 " success_count += 1"
681 "execution_count": null,
691 "display_name": "Python 3",
692 "language": "python",
700 "file_extension": ".py",
701 "mimetype": "text/x-python",
703 "nbconvert_exporter": "python",
704 "pygments_lexer": "ipython3",