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?
15 import matplotlib
.pyplot
as plt
17 # Use PIL to save some image metadata
19 from PIL
import PngImagePlugin
23 class Direction(enum
.Enum
):
29 turn_lefts
= {Direction
.UP
: Direction
.LEFT
, Direction
.LEFT
: Direction
.DOWN
,
30 Direction
.DOWN
: Direction
.RIGHT
, Direction
.RIGHT
: Direction
.UP
}
32 turn_rights
= {Direction
.UP
: Direction
.RIGHT
, Direction
.RIGHT
: Direction
.DOWN
,
33 Direction
.DOWN
: Direction
.LEFT
, Direction
.LEFT
: Direction
.UP
}
44 Step
= collections
.namedtuple('Step', ['x', 'y', 'dir'])
45 Mistake
= collections
.namedtuple('Mistake', ['i', 'step'])
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
)
63 def trace_tour(tour
, startx
=0, starty
=0, startdir
=Direction
.RIGHT
):
64 current
= Step(startx
, starty
, startdir
)
68 current
= advance(current
, current
.dir)
70 current
= advance(current
, turn_left(current
.dir))
72 current
= advance(current
, turn_right(current
.dir))
80 return [(s
.x
, s
.y
) for s
in trace
]
86 return (trace
[-1].x
== 0
88 and len(set(positions(trace
))) + 1 == len(trace
))
93 def chunks(items
, n
=2):
94 return [items
[i
:i
+n
] for i
in range(len(items
) - n
+ 1)]
97 # Using the [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)
102 return abs(sum(s
.x
* t
.y
- t
.x
* s
.y
for s
, t
in chunks(trace
, 2))) // 2
107 def step(s
, current
):
109 return advance(current
, current
.dir)
111 return advance(current
, turn_left(current
.dir))
113 return advance(current
, turn_right(current
.dir))
120 def valid_prefix(tour
):
121 current
= Step(0, 0, Direction
.RIGHT
)
125 current
= step(s
, current
)
127 if (current
.x
, current
.y
) in posns
:
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
)
140 def mistake_positions(trace
, debug
=False):
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):
152 return mistakes
+ [Mistake(len(trace
)+1, current
)]
157 def returns_to_origin(mistake_positions
):
158 return [i
for i
, m
in mistake_positions
159 if (m
.x
, m
.y
) == (0, 0)]
164 def random_walk(steps
=1000):
165 return ''.join(random
.choice('FFLR') for _
in range(steps
))
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
))
180 plot_wh
= {Direction
.UP
: (0, 1), Direction
.LEFT
: (-1, 0),
181 Direction
.DOWN
: (0, -1), Direction
.RIGHT
: (1, 0)}
183 def plot_trace(trace
, colour
='k', xybounds
=None, fig
=None, subplot_details
=None, filename
=None):
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])
196 plt
.xlim([xl
-1, xh
+1])
197 plt
.ylim([yl
-1, yh
+1])
199 plt
.savefig(filename
)
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
]
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))
225 # direction before entering the loop
226 direction_before
= trace
[mistake_loop_start
].dir
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 )
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]
245 def trim_all_loops(tour
, mistake_reduction_attempt_limit
=10):
246 trace
= trace_tour(tour
)
248 if trace
[-1].x
== 0 and trace
[-1].y
== 0:
250 mistakes
= mistake_positions(trace
)
252 old_mistake_count
= len(mistakes
)
253 mistake_reduction_tries
= 0
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
263 mistake_reduction_tries
+= 1
264 if mistake_reduction_tries
>= mistake_reduction_attempt_limit
:
272 def reverse_tour(tour
):
276 elif tour_step
== 'L':
281 return ''.join(swap(s
) for s
in reversed(tour
))
286 def wander_near(locus
, current
, limit
=10):
287 valid_proposal
= False
288 while not valid_proposal
:
289 s
= random
.choice('FFFRL')
291 proposed
= advance(current
, current
.dir)
293 proposed
= advance(current
, turn_left(current
.dir))
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))
304 def seek(goal
, current
):
305 dx
= current
.x
- goal
.x
306 dy
= current
.y
- goal
.y
308 if dx
< 0 and abs(dx
) > abs(dy
): # to the left
310 if current
.dir == Direction
.RIGHT
:
312 elif current
.dir == Direction
.UP
:
316 elif dx
> 0 and abs(dx
) > abs(dy
): # to the right
318 if current
.dir == Direction
.LEFT
:
320 elif current
.dir == Direction
.UP
:
324 elif dy
> 0 and abs(dx
) <= abs(dy
): # above
326 if current
.dir == Direction
.DOWN
:
328 elif current
.dir == Direction
.RIGHT
:
334 if current
.dir == Direction
.UP
:
336 elif current
.dir == Direction
.LEFT
:
341 proposed
= advance(current
, current
.dir)
343 proposed
= advance(current
, turn_left(current
.dir))
345 proposed
= advance(current
, turn_right(current
.dir))
347 # print('At {} going to {}, currently {}, by step {} to {}'.format(current, goal, side, s, proposed))
354 def guided_walk(loci
, locus_limit
=5, wander_limit
=10, seek_step_limit
=20):
356 current
= Step(0, 0, Direction
.RIGHT
)
360 if abs(current
.x
- loci
[l
].x
) < locus_limit
and abs(current
.y
- loci
[l
].y
) < locus_limit
:
362 if l
== len(loci
) - 1:
364 s
, proposed
= wander_near(loci
[l
], current
, limit
=wander_limit
)
367 # print('!! Finished loci')
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
)
376 if seek_steps
>= seek_step_limit
:
384 def square_tour(a
=80):
385 "a is width of square"
386 return ('F' * a
+ 'L') * 4
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
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
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
)]
411 current
= Step(0, 0, Direction
.RIGHT
)
413 for hp
in heart_points
:
414 while not (current
.x
== hp
.x
and current
.y
== hp
.y
):
415 s
, proposed
= seek(hp
, current
)
419 def heart_tour_func(): return heart_tour
425 # while success_count <= 20:
426 # lc = trace_tour(square_tour(a=10))
427 # rw = guided_walk(lc, wander_limit=4, locus_limit=2)
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')
439 # while success_count <= 20:
440 # lc = trace_tour(square_tour())
441 # rw = guided_walk(lc)
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')
453 # while success_count <= 20:
454 # lc = trace_tour(cross_tour())
455 # rw = guided_walk(lc)
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')
467 # while success_count <= 20:
468 # lc = trace_tour(quincunx_tour())
469 # rw = guided_walk(lc)
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')
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)
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)
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)
510 with
open('tours-random-walk.txt') as f
:
511 for i
, tour_s
in enumerate(f
.readlines()):
512 tour
= tour_s
.strip()
513 filename
= 'tour-{:03}-s{:04}-m{:03}-walk.png'.format(i
, len(tour
), len(mistake_positions(trace_tour(tour
))))
514 plot_trace(trace_tour(tour
), filename
=filename
)
515 im
= Image
.open(filename
)
516 meta
= PngImagePlugin
.PngInfo()
517 meta
.add_text('Description', tour
)
518 im
.save(filename
, 'PNG', pnginfo
=meta
)