06-tour-shapes/tour-shape-plots.py

   1
   2 # coding: utf-8
   3
   4 # 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":
   5 # 1. which tours are closed?
   6 # 2. what is the area enclosed by the tour?
   7
   8 # In[1]:
   9
  10 import collections
  11 import enum
  12 import random
  13 import os
  14
  15 import matplotlib.pyplot as plt
  16
  17 # Use PIL to save some image metadata
  18 from PIL import Image
  19 from PIL import PngImagePlugin
  20
  21 # In[2]:
  22
  23 class Direction(enum.Enum):
  24     UP = 1
  25     RIGHT = 2
  26     DOWN = 3
  27     LEFT = 4
  28
  29 turn_lefts = {Direction.UP: Direction.LEFT, Direction.LEFT: Direction.DOWN,
  30               Direction.DOWN: Direction.RIGHT, Direction.RIGHT: Direction.UP}
  31
  32 turn_rights = {Direction.UP: Direction.RIGHT, Direction.RIGHT: Direction.DOWN,
  33                Direction.DOWN: Direction.LEFT, Direction.LEFT: Direction.UP}
  34
  35 def turn_left(d):
  36     return turn_lefts[d]
  37
  38 def turn_right(d):
  39     return turn_rights[d]
  40
  41
  42 # In[3]:
  43
  44 Step = collections.namedtuple('Step', ['x', 'y', 'dir'])
  45 Mistake = collections.namedtuple('Mistake', ['i', 'step'])
  46
  47
  48 # In[4]:
  49
  50 def advance(step, d):
  51     if d == Direction.UP:
  52         return Step(step.x, step.y+1, d)
  53     elif d == Direction.DOWN:
  54         return Step(step.x, step.y-1, d)
  55     elif d == Direction.LEFT:
  56         return Step(step.x-1, step.y, d)
  57     elif d == Direction.RIGHT:
  58         return Step(step.x+1, step.y, d)
  59
  60
  61 # In[5]:
  62
  63 def trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):
  64     current = Step(startx, starty, startdir)
  65     trace = [current]
  66     for s in tour:
  67         if s == 'F':
  68             current = advance(current, current.dir)
  69         elif s == 'L':
  70             current = advance(current, turn_left(current.dir))
  71         elif s == 'R':
  72             current = advance(current, turn_right(current.dir))
  73         trace += [current]
  74     return trace
  75
  76
  77 # In[6]:
  78
  79 def positions(trace):
  80     return [(s.x, s.y) for s in trace]
  81
  82
  83 # In[7]:
  84
  85 def valid(trace):
  86     return (trace[-1].x == 0
  87             and trace[-1].y == 0
  88             and len(set(positions(trace))) + 1 == len(trace))
  89
  90
  91 # In[8]:
  92
  93 def chunks(items, n=2):
  94     return [items[i:i+n] for i in range(len(items) - n + 1)]
  95
  96
  97 # Using the [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)
  98
  99 # In[9]:
 100
 101 def shoelace(trace):
 102     return abs(sum(s.x * t.y - t.x * s.y for s, t in chunks(trace, 2))) // 2
 103
 104
 105 # In[10]:
 106
 107 def step(s, current):
 108     if s == 'F':
 109         return advance(current, current.dir)
 110     elif s == 'L':
 111         return advance(current, turn_left(current.dir))
 112     elif s == 'R':
 113         return advance(current, turn_right(current.dir))
 114     else:
 115         raise ValueError
 116
 117
 118 # In[11]:
 119
 120 def valid_prefix(tour):
 121     current = Step(0, 0, Direction.RIGHT)
 122     prefix = []
 123     posns = []
 124     for s in tour:
 125         current = step(s, current)
 126         prefix += [s]
 127         if (current.x, current.y) in posns:
 128             return ''
 129         elif current.x == 0 and current.y == 0:
 130             return ''.join(prefix)
 131         posns += [(current.x, current.y)]
 132     if current.x == 0 and current.y == 0:
 133         return ''.join(prefix)
 134     else:
 135         return ''
 136
 137
 138 # In[12]:
 139
 140 def mistake_positions(trace, debug=False):
 141     mistakes = []
 142     current = trace[0]
 143     posns = [(0, 0)]
 144     for i, current in enumerate(trace[1:]):
 145         if (current.x, current.y) in posns:
 146             if debug: print(i, current)
 147             mistakes += [Mistake(i+1, current)]
 148         posns += [(current.x, current.y)]
 149     if (current.x, current.y) == (0, 0):
 150         return mistakes[:-1]
 151     else:
 152         return mistakes + [Mistake(len(trace)+1, current)]
 153
 154
 155 # In[13]:
 156
 157 def returns_to_origin(mistake_positions):
 158     return [i for i, m in mistake_positions
 159            if (m.x, m.y) == (0, 0)]
 160
 161
 162 # In[14]:
 163
 164 def random_walk(steps=1000):
 165     return ''.join(random.choice('FFLR') for _ in range(steps))
 166
 167
 168 # In[15]:
 169
 170 def bounds(trace):
 171     return (max(s.x for s in trace),
 172             max(s.y for s in trace),
 173             min(s.x for s in trace),
 174             min(s.y for s in trace))
 175
 176
 177 # In[16]:
 178
 179
 180 plot_wh = {Direction.UP: (0, 1), Direction.LEFT: (-1, 0),
 181            Direction.DOWN: (0, -1), Direction.RIGHT: (1, 0)}
 182
 183 def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):
 184     # plt.axis('on')
 185     plt.axis('off')
 186     plt.axes().set_aspect('equal')
 187     for s, t in chunks(trace, 2):
 188         w, h = plot_wh[t.dir]
 189         plt.arrow(s.x, s.y, w, h, head_width=0.1, head_length=0.1, fc=colour, ec=colour, length_includes_head=True)
 190     xh, yh, xl, yl = bounds(trace)
 191     if xybounds is not None:
 192         bxh, byh, bxl, byl = xybounds
 193         plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])
 194         plt.ylim([min(yl, byl)-1, max(yh, byh)+1])
 195     else:
 196         plt.xlim([xl-1, xh+1])
 197         plt.ylim([yl-1, yh+1])
 198     if filename:
 199         plt.savefig(filename)
 200     plt.close()
 201
 202
 203 # In[17]:
 204
 205 def trim_loop(tour):
 206     trace = trace_tour(tour)
 207     mistakes = mistake_positions(trace)
 208     end_mistake_index = 0
 209 #     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))
 210     # while this mistake extends to the next step in the trace...
 211     while (mistakes[end_mistake_index].i + 1 < len(trace) and
 212            end_mistake_index + 1 < len(mistakes) and
 213            mistakes[end_mistake_index].i + 1 ==
 214            mistakes[end_mistake_index + 1].i):
 215 #         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))
 216         # push this mistake finish point later
 217         end_mistake_index += 1
 218     mistake = mistakes[end_mistake_index]
 219
 220     # find the first location that mentions where this mistake ends (which the point where the loop starts)
 221     mistake_loop_start = max(i for i, loc in enumerate(trace[:mistake.i])
 222                              if (loc.x, loc.y) == (mistake.step.x, mistake.step.y))
 223 #     print('Dealing with mistake from', mistake_loop_start, 'to', mistake.i, ', trace has len', len(trace))
 224
 225     # direction before entering the loop
 226     direction_before = trace[mistake_loop_start].dir
 227
 228     # find the new instruction to turn from heading before the loop to heading after the loop
 229     new_instruction = 'F'
 230     if (mistake.i + 1) < len(trace):
 231         if turn_left(direction_before) == trace[mistake.i + 1].dir:
 232             new_instruction = 'L'
 233         if turn_right(direction_before) == trace[mistake.i + 1].dir:
 234             new_instruction = 'R'
 235 #     if (mistake.i + 1) < len(trace):
 236 #         print('turning from', direction_before, 'to', trace[mistake.i + 1].dir, 'with', new_instruction )
 237 #     else:
 238 #         print('turning from', direction_before, 'to BEYOND END', 'with', new_instruction )
 239     return tour[:mistake_loop_start] + new_instruction + tour[mistake.i+1:]
 240 #     return mistake, mistake_loop_start, trace[mistake_loop_start-2:mistake_loop_start+8]
 241
 242
 243 # In[18]:
 244
 245 def trim_all_loops(tour, mistake_reduction_attempt_limit=10):
 246     trace = trace_tour(tour)
 247     mistake_limit = 1
 248     if trace[-1].x == 0 and trace[-1].y == 0:
 249         mistake_limit = 0
 250     mistakes = mistake_positions(trace)
 251
 252     old_mistake_count = len(mistakes)
 253     mistake_reduction_tries = 0
 254
 255     while len(mistakes) > mistake_limit and mistake_reduction_tries < mistake_reduction_attempt_limit:
 256         tour = trim_loop(tour)
 257         trace = trace_tour(tour)
 258         mistakes = mistake_positions(trace)
 259         if len(mistakes) < old_mistake_count:
 260             old_mistake_count = len(mistakes)
 261             mistake_reduction_tries = 0
 262         else:
 263             mistake_reduction_tries += 1
 264     if mistake_reduction_tries >= mistake_reduction_attempt_limit:
 265         return ''
 266     else:
 267         return tour
 268
 269
 270 # In[19]:
 271
 272 def reverse_tour(tour):
 273     def swap(tour_step):
 274         if tour_step == 'R':
 275             return 'L'
 276         elif tour_step == 'L':
 277             return 'R'
 278         else:
 279             return tour_step
 280
 281     return ''.join(swap(s) for s in reversed(tour))
 282
 283
 284 # In[20]:
 285
 286 def wander_near(locus, current, limit=10):
 287     valid_proposal = False
 288     while not valid_proposal:
 289         s = random.choice('FFFRL')
 290         if s == 'F':
 291             proposed = advance(current, current.dir)
 292         elif s == 'L':
 293             proposed = advance(current, turn_left(current.dir))
 294         elif s == 'R':
 295             proposed = advance(current, turn_right(current.dir))
 296         if abs(proposed.x - locus.x) < limit and abs(proposed.y - locus.y) < limit:
 297             valid_proposal = True
 298 #     print('At {} going to {} by step {} to {}'.format(current, locus, s, proposed))
 299     return s, proposed
 300
 301
 302 # In[21]:
 303
 304 def seek(goal, current):
 305     dx = current.x - goal.x
 306     dy = current.y - goal.y
 307
 308     if dx < 0 and abs(dx) > abs(dy): # to the left
 309         side = 'left'
 310         if current.dir == Direction.RIGHT:
 311             s = 'F'
 312         elif current.dir == Direction.UP:
 313             s = 'R'
 314         else:
 315             s = 'L'
 316     elif dx > 0 and abs(dx) > abs(dy): # to the right
 317         side = 'right'
 318         if current.dir == Direction.LEFT:
 319             s = 'F'
 320         elif current.dir == Direction.UP:
 321             s = 'L'
 322         else:
 323             s = 'R'
 324     elif dy > 0 and abs(dx) <= abs(dy): # above
 325         side = 'above'
 326         if current.dir == Direction.DOWN:
 327             s = 'F'
 328         elif current.dir == Direction.RIGHT:
 329             s = 'R'
 330         else:
 331             s = 'L'
 332     else: # below
 333         side = 'below'
 334         if current.dir == Direction.UP:
 335             s = 'F'
 336         elif current.dir == Direction.LEFT:
 337             s = 'R'
 338         else:
 339             s = 'L'
 340     if s == 'F':
 341         proposed = advance(current, current.dir)
 342     elif s == 'L':
 343         proposed = advance(current, turn_left(current.dir))
 344     elif s == 'R':
 345         proposed = advance(current, turn_right(current.dir))
 346
 347 #     print('At {} going to {}, currently {},  by step {} to {}'.format(current, goal, side, s, proposed))
 348
 349     return s, proposed
 350
 351
 352 # In[22]:
 353
 354 def guided_walk(loci, locus_limit=5, wander_limit=10, seek_step_limit=20):
 355     trail = ''
 356     current = Step(0, 0, Direction.RIGHT)
 357     l = 0
 358     finished = False
 359     while not finished:
 360         if abs(current.x - loci[l].x) < locus_limit and abs(current.y - loci[l].y) < locus_limit:
 361             l += 1
 362             if l == len(loci) - 1:
 363                 finished = True
 364         s, proposed = wander_near(loci[l], current, limit=wander_limit)
 365         trail += s
 366         current = proposed
 367 #     print('!! Finished loci')
 368     seek_steps = 0
 369     while not (current.x == loci[l].x and current.y == loci[l].y) and seek_steps < seek_step_limit:
 370 #         error = max(abs(current.x - loci[l].x), abs(current.y - loci[l].y))
 371 #         s, proposed = wander_near(loci[l], current, limit=error+1)
 372         s, proposed = seek(loci[l], current)
 373         trail += s
 374         current = proposed
 375         seek_steps += 1
 376     if seek_steps >= seek_step_limit:
 377         return ''
 378     else:
 379         return trail
 380
 381
 382 # In[24]:
 383
 384 def square_tour(a=80):
 385     "a is width of square"
 386     return ('F' * a + 'L') * 4
 387
 388
 389 # In[25]:
 390
 391 def cross_tour(a=50, b=40):
 392     "a is width of cross arm, b is length of cross arm"
 393     return ('F' *  a + 'L' + 'F' * b + 'R' + 'F' * b + 'L') * 4
 394
 395
 396 # In[26]:
 397
 398 def quincunx_tour(a=60, b=30, c=50):
 399     "a is length of indent, b is indent/outdent distance, c is outdent outer length"
 400     return ('F' * a + 'R' + 'F' * b + 'L' + 'F' * c + 'L' + 'F' * c + 'L' + 'F' * b + 'R') * 4
 401
 402
 403 # In[27]:
 404
 405 heart_points = [Step(60, 50, Direction.UP), Step(50, 90, Direction.UP),
 406                 Step(20, 70, Direction.UP),
 407                 Step(-40, 90, Direction.UP), Step(-60, 80, Direction.UP),
 408                 Step(0, 0, Direction.RIGHT)]
 409
 410 heart_tour = ''
 411 current = Step(0, 0, Direction.RIGHT)
 412
 413 for hp in heart_points:
 414     while not (current.x == hp.x and current.y == hp.y):
 415         s, proposed = seek(hp, current)
 416         heart_tour += s
 417         current = proposed
 418
 419 def heart_tour_func(): return heart_tour
 420
 421
 422 # In[28]:
 423
 424 # success_count = 0
 425 # while success_count <= 20:
 426 #     lc = trace_tour(square_tour(a=10))
 427 #     rw = guided_walk(lc, wander_limit=4, locus_limit=2)
 428 #     if rw:
 429 #         rw_trimmed = trim_all_loops(rw)
 430 #         if len(rw_trimmed) > 10:
 431 #             with open('small-squares.txt', 'a') as f:
 432 #                 f.write(rw_trimmed + '\n')
 433 #                 success_count += 1
 434
 435
 436 # In[29]:
 437
 438 # success_count = 0
 439 # while success_count <= 20:
 440 #     lc = trace_tour(square_tour())
 441 #     rw = guided_walk(lc)
 442 #     if rw:
 443 #         rw_trimmed = trim_all_loops(rw)
 444 #         if len(rw_trimmed) > 10:
 445 #             with open('large-squares.txt', 'a') as f:
 446 #                 f.write(rw_trimmed + '\n')
 447 #                 success_count += 1
 448
 449
 450 # In[30]:
 451
 452 # success_count = 0
 453 # while success_count <= 20:
 454 #     lc = trace_tour(cross_tour())
 455 #     rw = guided_walk(lc)
 456 #     if rw:
 457 #         rw_trimmed = trim_all_loops(rw)
 458 #         if len(rw_trimmed) > 10:
 459 #             with open('cross.txt', 'a') as f:
 460 #                 f.write(rw_trimmed + '\n')
 461 #                 success_count += 1
 462
 463
 464 # In[31]:
 465
 466 # success_count = 0
 467 # while success_count <= 20:
 468 #     lc = trace_tour(quincunx_tour())
 469 #     rw = guided_walk(lc)
 470 #     if rw:
 471 #         rw_trimmed = trim_all_loops(rw)
 472 #         if len(rw_trimmed) > 10:
 473 #             with open('quincunx.txt', 'a') as f:
 474 #                 f.write(rw_trimmed + '\n')
 475 #                 success_count += 1
 476
 477
 478 # In[32]:
 479
 480 # with open('tours.txt') as f:
 481 #     for i, tour_s in enumerate(f.readlines()):
 482 #         tour = tour_s.strip()
 483 #         filename = 'tour-{:03}-s{:04}-m{:03}.png'.format(i, len(tour), len(mistake_positions(trace_tour(tour))))
 484 #         plot_trace(trace_tour(tour), filename=filename)
 485 #         im = Image.open(filename)
 486 #         meta = PngImagePlugin.PngInfo()
 487 #         meta.add_text('Description', tour)
 488 #         im.save(filename, 'PNG', pnginfo=meta)
 489
 490 # with open('tours-with-mistakes.txt') as f:
 491 #     for i, tour_s in enumerate(f.readlines()):
 492 #         tour = tour_s.strip()
 493 #         filename = 'tour-{:03}-s{:04}-m{:03}.png'.format(i, len(tour), len(mistake_positions(trace_tour(tour))))
 494 #         plot_trace(trace_tour(tour), filename=filename)
 495 #         im = Image.open(filename)
 496 #         meta = PngImagePlugin.PngInfo()
 497 #         meta.add_text('Description', tour)
 498 #         im.save(filename, 'PNG', pnginfo=meta)
 499
 500 # with open('tours-open.txt') as f:
 501 #     for i, tour_s in enumerate(f.readlines()):
 502 #         tour = tour_s.strip()
 503 #         filename = 'tour-{:03}-s{:04}-m{:03}-open.png'.format(i, len(tour), len(mistake_positions(trace_tour(tour))))
 504 #         plot_trace(trace_tour(tour), filename=filename)
 505 #         im = Image.open(filename)
 506 #         meta = PngImagePlugin.PngInfo()
 507 #         meta.add_text('Description', tour)
 508 #         im.save(filename, 'PNG', pnginfo=meta)
 509
 510 # with open('tours-random-walk.txt') as f:
 511 with open('samples.txt') as f:
 512     for i, tour_s in enumerate(f.readlines()):
 513         tour = tour_s.strip()
 514         filename = 'sample-tour-{:03}-s{:04}-m{:03}-walk.png'.format(i, len(tour), len(mistake_positions(trace_tour(tour))))
 515         plot_trace(trace_tour(tour), filename=filename)
 516         im = Image.open(filename)
 517         meta = PngImagePlugin.PngInfo()
 518         meta.add_text('Description', tour)
 519         im.save(filename, 'PNG', pnginfo=meta)