Enumerate paths on a pixel grid of varying path lengths

enumeratewalks.py

import itertools
import numpy as np
from PIL import Image
from operator import itemgetter
from collections import defaultdict
import base64
import io

dirs_map = {
    (1, 0)  : 'R',
    (-1, 0) : 'L',
    (0, 1)  : 'U',
    (0, -1) : 'D',
    }

inv_dirs_map = {v : k for k, v in dirs_map.items()}

opposites = {
    (inv_dirs_map['R'], inv_dirs_map['L']),
    (inv_dirs_map['L'], inv_dirs_map['R']),
    (inv_dirs_map['U'], inv_dirs_map['D']),
    (inv_dirs_map['D'], inv_dirs_map['U']),
    }

dirs = list(dirs_map.keys())

def neighbors(point):
    x, y = point
    for a, b in dirs:
        yield x + a, b + y

def run_walk(steps):
    cur = 0, 0
    used = {cur}
    walk = [cur]
    for i, (a, b) in enumerate(steps):
        to = (cur[0] + a, cur[1] + b)

        if any(n in used for n in neighbors(to) if n != cur) or (i > 0 and (steps[i - 1], steps[i]) in opposites):
            return None

        used.add(to)
        walk.append(to)
        cur = to

    if cur[1] != 0 or cur[0] < 0:
        return None

    return walk

def gapsize(path):
    return path[-1][0]  # x coord of last location

def walk_to_string(steps):
    return ''.join(dirs_map[x] for x in steps)

def sign(x):
    if x >= 0:
        return 1
    return -1

def walk_bbox(path):
    min_x = min(map(itemgetter(0), path))
    max_x = max(map(itemgetter(0), path))
    min_y = min(map(itemgetter(1), path))
    max_y = max(map(itemgetter(1), path))

    return (min_x, max_x, min_y, max_y)

def compute_image_size(by_gapsize, vertical_padding=4, padding_multiplier=2):
    N = sum(map(len, by_gapsize.values()))
    it = lambda: itertools.chain.from_iterable(by_gapsize.values())

    width = max(max_x - min_x for _, _, (min_x, max_x, _, _) in it())
    height = sum(max_y - min_y for _, _, (_, _, min_y, max_y) in it())

    iw = width + 3
    ih = height + (N - 1) * vertical_padding + len(by_gapsize) * vertical_padding * padding_multiplier

    return iw, ih

def make_image(L, vertical_padding=4, padding_multiplier=2):
    by_gapsize = defaultdict(list)
    for w in itertools.product(dirs_map, repeat=L):
        path = run_walk(w)
        if path is not None:
            by_gapsize[gapsize(path)].append((w, path, walk_bbox(path)))

    vertical_padding = 4

    w, h = compute_image_size(by_gapsize, vertical_padding=vertical_padding, padding_multiplier=padding_multiplier)

    b = np.ones((h, w), dtype=np.uint8)

    row = 1
    for walks in (by_gapsize[k] for k in sorted(by_gapsize.keys())):
        for w, path, (min_x, _, min_y, max_y) in walks:
            height = max_y - min_y

            origin = (-min_x + 1, row - min_y)
            for x, y in path:
                b[origin[1] + y, origin[0] + x] = 0

            row += height + vertical_padding

        row += vertical_padding * 2

    im = Image.fromarray(b * 255, mode='L')
    return by_gapsize, im

def save_image(L, output, scale=1):
    by_gapsize , im = make_image(L)
    # print('Saved {} walks to {}'.format(sum(map(len, by_gapsize.values())), output))
    im = im.resize((im.size[0] * scale, im.size[1] * scale))
    im.save(output, format='png')

style = '''
<style>

img.walk-image {
  image-rendering: pixelated;
  width: 50px;
}

</style>
'''

print(style)

for L in range(1, 10 + 1):
    print('<h2>L = {}</h2>'.format(L))
    with io.BytesIO() as fh:
        save_image(L, fh)
        fh.seek(0)
        encoded = base64.b64encode(fh.read()).decode()

    print('<img class="walk-image" src="data:image/png;base64, {}" />'.format(encoded))
    print('<hr>')