X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;ds=sidebyside;f=06-tour-shapes%2Ftour-creation-for-background.ipynb;fp=06-tour-shapes%2Ftour-creation-for-background.ipynb;h=7fe0db26c9d102eaf82da3a41ee425f522ba49a3;hb=fda89d02980df6c79d05dfdc8db9bea3d7856254;hp=0000000000000000000000000000000000000000;hpb=c9bb6cf75bc365fd0fec028c8994ad7ea04cc366;p=ou-summer-of-code-2017.git diff --git a/06-tour-shapes/tour-creation-for-background.ipynb b/06-tour-shapes/tour-creation-for-background.ipynb new file mode 100644 index 0000000..7fe0db2 --- /dev/null +++ b/06-tour-shapes/tour-creation-for-background.ipynb @@ -0,0 +1,710 @@ +{ + "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" + ] + }, + { + "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 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", + " if s == 'F':\n", + " current = advance(current, current.dir)\n", + " elif s == 'L':\n", + " current = advance(current, turn_left(current.dir))\n", + " elif s == 'R':\n", + " current = advance(current, turn_right(current.dir))\n", + " trace += [current]\n", + " return trace " + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def positions(trace):\n", + " return [(s.x, s.y) for s in trace]" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "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": 8, + "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": "markdown", + "metadata": {}, + "source": [ + "Using the [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def shoelace(trace):\n", + " return abs(sum(s.x * t.y - t.x * s.y for s, t in chunks(trace, 2))) // 2" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "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": 11, + "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": 12, + "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": 13, + "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": 14, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def random_walk(steps=1000):\n", + " return ''.join(random.choice('FFLR') for _ in range(steps))" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "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": 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": "code", + "execution_count": 17, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def trim_loop(tour):\n", + " trace = trace_tour(tour)\n", + " mistakes = mistake_positions(trace)\n", + " end_mistake_index = 0\n", + "# 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", + " # while this mistake extends to the next step in the trace...\n", + " while (mistakes[end_mistake_index].i + 1 < len(trace) and \n", + " end_mistake_index + 1 < len(mistakes) and\n", + " mistakes[end_mistake_index].i + 1 == \n", + " mistakes[end_mistake_index + 1].i):\n", + "# 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", + " # push this mistake finish point later\n", + " end_mistake_index += 1\n", + " mistake = mistakes[end_mistake_index]\n", + " \n", + " # find the first location that mentions where this mistake ends (which the point where the loop starts)\n", + " mistake_loop_start = max(i for i, loc in enumerate(trace[:mistake.i])\n", + " if (loc.x, loc.y) == (mistake.step.x, mistake.step.y))\n", + "# print('Dealing with mistake from', mistake_loop_start, 'to', mistake.i, ', trace has len', len(trace))\n", + " \n", + " # direction before entering the loop\n", + " direction_before = trace[mistake_loop_start].dir\n", + " \n", + " # find the new instruction to turn from heading before the loop to heading after the loop\n", + " new_instruction = 'F'\n", + " if (mistake.i + 1) < len(trace):\n", + " if turn_left(direction_before) == trace[mistake.i + 1].dir:\n", + " new_instruction = 'L'\n", + " if turn_right(direction_before) == trace[mistake.i + 1].dir:\n", + " new_instruction = 'R'\n", + "# if (mistake.i + 1) < len(trace):\n", + "# print('turning from', direction_before, 'to', trace[mistake.i + 1].dir, 'with', new_instruction )\n", + "# else:\n", + "# print('turning from', direction_before, 'to BEYOND END', 'with', new_instruction )\n", + " return tour[:mistake_loop_start] + new_instruction + tour[mistake.i+1:]\n", + "# return mistake, mistake_loop_start, trace[mistake_loop_start-2:mistake_loop_start+8]" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def trim_all_loops(tour, mistake_reduction_attempt_limit=10):\n", + " trace = trace_tour(tour)\n", + " mistake_limit = 1\n", + " if trace[-1].x == 0 and trace[-1].y == 0:\n", + " mistake_limit = 0\n", + " mistakes = mistake_positions(trace)\n", + " \n", + " old_mistake_count = len(mistakes)\n", + " mistake_reduction_tries = 0\n", + " \n", + " while len(mistakes) > mistake_limit and mistake_reduction_tries < mistake_reduction_attempt_limit:\n", + " tour = trim_loop(tour)\n", + " trace = trace_tour(tour)\n", + " mistakes = mistake_positions(trace)\n", + " if len(mistakes) < old_mistake_count:\n", + " old_mistake_count = len(mistakes)\n", + " mistake_reduction_tries = 0\n", + " else:\n", + " mistake_reduction_tries += 1\n", + " if mistake_reduction_tries >= mistake_reduction_attempt_limit:\n", + " return ''\n", + " else:\n", + " return tour" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def reverse_tour(tour):\n", + " def swap(tour_step):\n", + " if tour_step == 'R':\n", + " return 'L'\n", + " elif tour_step == 'L':\n", + " return 'R'\n", + " else:\n", + " return tour_step\n", + " \n", + " return ''.join(swap(s) for s in reversed(tour))" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def wander_near(locus, current, limit=10):\n", + " valid_proposal = False\n", + " while not valid_proposal:\n", + " s = random.choice('FFFRL')\n", + " if s == 'F':\n", + " proposed = advance(current, current.dir)\n", + " elif s == 'L':\n", + " proposed = advance(current, turn_left(current.dir))\n", + " elif s == 'R':\n", + " proposed = advance(current, turn_right(current.dir))\n", + " if abs(proposed.x - locus.x) < limit and abs(proposed.y - locus.y) < limit:\n", + " valid_proposal = True\n", + "# print('At {} going to {} by step {} to {}'.format(current, locus, s, proposed))\n", + " return s, proposed" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def seek(goal, current):\n", + " dx = current.x - goal.x\n", + " dy = current.y - goal.y\n", + "\n", + " if dx < 0 and abs(dx) > abs(dy): # to the left\n", + " side = 'left'\n", + " if current.dir == Direction.RIGHT:\n", + " s = 'F'\n", + " elif current.dir == Direction.UP:\n", + " s = 'R'\n", + " else:\n", + " s = 'L'\n", + " elif dx > 0 and abs(dx) > abs(dy): # to the right\n", + " side = 'right'\n", + " if current.dir == Direction.LEFT:\n", + " s = 'F'\n", + " elif current.dir == Direction.UP:\n", + " s = 'L'\n", + " else:\n", + " s = 'R'\n", + " elif dy > 0 and abs(dx) <= abs(dy): # above\n", + " side = 'above'\n", + " if current.dir == Direction.DOWN:\n", + " s = 'F'\n", + " elif current.dir == Direction.RIGHT:\n", + " s = 'R'\n", + " else:\n", + " s = 'L'\n", + " else: # below\n", + " side = 'below'\n", + " if current.dir == Direction.UP:\n", + " s = 'F'\n", + " elif current.dir == Direction.LEFT:\n", + " s = 'R'\n", + " else:\n", + " s = 'L'\n", + " if s == 'F':\n", + " proposed = advance(current, current.dir)\n", + " elif s == 'L':\n", + " proposed = advance(current, turn_left(current.dir))\n", + " elif s == 'R':\n", + " proposed = advance(current, turn_right(current.dir))\n", + " \n", + "# print('At {} going to {}, currently {}, by step {} to {}'.format(current, goal, side, s, proposed))\n", + "\n", + " return s, proposed" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def guided_walk(loci, locus_limit=5, wander_limit=10, seek_step_limit=20):\n", + " trail = ''\n", + " current = Step(0, 0, Direction.RIGHT) \n", + " l = 0\n", + " finished = False\n", + " while not finished:\n", + " if abs(current.x - loci[l].x) < locus_limit and abs(current.y - loci[l].y) < locus_limit:\n", + " l += 1\n", + " if l == len(loci) - 1:\n", + " finished = True\n", + " s, proposed = wander_near(loci[l], current, limit=wander_limit)\n", + " trail += s\n", + " current = proposed\n", + "# print('!! Finished loci')\n", + " seek_steps = 0\n", + " while not (current.x == loci[l].x and current.y == loci[l].y) and seek_steps < seek_step_limit:\n", + "# error = max(abs(current.x - loci[l].x), abs(current.y - loci[l].y))\n", + "# s, proposed = wander_near(loci[l], current, limit=error+1)\n", + " s, proposed = seek(loci[l], current)\n", + " trail += s\n", + " current = proposed\n", + " seek_steps += 1\n", + " if seek_steps >= seek_step_limit:\n", + " return ''\n", + " else:\n", + " return trail" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": {}, + "outputs": [], + "source": [ + "def square_tour(a=80):\n", + " \"a is width of square\"\n", + " return ('F' * a + 'L') * 4" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": {}, + "outputs": [], + "source": [ + "def cross_tour(a=50, b=40):\n", + " \"a is width of cross arm, b is length of cross arm\"\n", + " return ('F' * a + 'L' + 'F' * b + 'R' + 'F' * b + 'L') * 4" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": {}, + "outputs": [], + "source": [ + "def quincunx_tour(a=60, b=30, c=50):\n", + " \"a is length of indent, b is indent/outdent distance, c is outdent outer length\"\n", + " return ('F' * a + 'R' + 'F' * b + 'L' + 'F' * c + 'L' + 'F' * c + 'L' + 'F' * b + 'R') * 4\n" + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "metadata": {}, + "outputs": [], + "source": [ + "heart_points = [Step(60, 50, Direction.UP), Step(50, 90, Direction.UP),\n", + " Step(20, 70, Direction.UP), \n", + " Step(-40, 90, Direction.UP), Step(-60, 80, Direction.UP), \n", + " Step(0, 0, Direction.RIGHT)]\n", + "\n", + "heart_tour = ''\n", + "current = Step(0, 0, Direction.RIGHT)\n", + "\n", + "for hp in heart_points:\n", + " while not (current.x == hp.x and current.y == hp.y):\n", + " s, proposed = seek(hp, current)\n", + " heart_tour += s\n", + " current = proposed\n", + "\n", + "def heart_tour_func(): return heart_tour" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "# success_count = 0\n", + "# while success_count <= 20:\n", + "# lc = trace_tour(square_tour(a=10))\n", + "# rw = guided_walk(lc, wander_limit=4, locus_limit=2)\n", + "# if rw:\n", + "# rw_trimmed = trim_all_loops(rw)\n", + "# if len(rw_trimmed) > 10:\n", + "# with open('small-squares.txt', 'a') as f:\n", + "# f.write(rw_trimmed + '\\n')\n", + "# success_count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "# success_count = 0\n", + "# while success_count <= 20:\n", + "# lc = trace_tour(square_tour())\n", + "# rw = guided_walk(lc)\n", + "# if rw:\n", + "# rw_trimmed = trim_all_loops(rw)\n", + "# if len(rw_trimmed) > 10:\n", + "# with open('large-squares.txt', 'a') as f:\n", + "# f.write(rw_trimmed + '\\n')\n", + "# success_count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "# success_count = 0\n", + "# while success_count <= 20:\n", + "# lc = trace_tour(cross_tour())\n", + "# rw = guided_walk(lc)\n", + "# if rw:\n", + "# rw_trimmed = trim_all_loops(rw)\n", + "# if len(rw_trimmed) > 10:\n", + "# with open('cross.txt', 'a') as f:\n", + "# f.write(rw_trimmed + '\\n')\n", + "# success_count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "# success_count = 0\n", + "# while success_count <= 20:\n", + "# lc = trace_tour(quincunx_tour())\n", + "# rw = guided_walk(lc)\n", + "# if rw:\n", + "# rw_trimmed = trim_all_loops(rw)\n", + "# if len(rw_trimmed) > 10:\n", + "# with open('quincunx.txt', 'a') as f:\n", + "# f.write(rw_trimmed + '\\n')\n", + "# success_count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "patterns = [square_tour, cross_tour, quincunx_tour, heart_tour_func]\n", + "tours_filename = 'tours.txt'\n", + "\n", + "try:\n", + " os.remove(tours_filename)\n", + "except OSError:\n", + " pass\n", + "\n", + "success_count = 0\n", + "while success_count < 100:\n", + " lc = trace_tour(random.choice(patterns)())\n", + " rw = guided_walk(lc)\n", + " if rw:\n", + " rw_trimmed = trim_all_loops(rw)\n", + " if len(rw_trimmed) > 10:\n", + " with open(tours_filename, 'a') as f:\n", + " f.write(rw_trimmed + '\\n')\n", + " success_count += 1" + ] + }, + { + "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 +}