walk_fast.py

import time
import math
import sys
import struct

data = """* 8 1 7 8 8 5 2 9 5 9 5
8 5 1 1 5 6 9 4 4 5 2 1
7 2 3 5 2 9 2 6 9 3 9 4
9 2 5 9 8 9 5 7 7 5 9 6
2 4 6 7 1 4 2 6 6 2 5 8
2 8 1 5 3 8 4 9 7 5 2 3
2 9 3 5 6 7 2 4 9 4 2 5
6 3 1 7 8 2 3 3 6 7 9 3
2 5 7 4 2 7 8 5 5 3 5 8
5 2 9 8 3 6 1 4 9 5 6 3
4 6 9 8 5 4 9 7 6 4 6 8
2 7 7 1 9 9 7 3 7 2 2 ^"""
chips = 444

height = len(data.split('\n'))
last_height = height - 1
width = len(data.split('\n')[0].split())
last_width = width - 1
first_row = last_width
last_row = height * last_width
data = data.replace(' ', '').replace('\n', '')
start = data.index('*')
goal = data.index('^')
data = data.replace('*', '0')
data = data.replace('^', '5')
data = [ord(c) - 48 for c in data]

n = 0
e = 1
s = 2
w = 3
charmoves = "nesw".encode()

movements = {
    "e": 1,
    "s": width,
    "w": -1,
    "n": -width,
}


def path_string2(moves, depth):
    result = bytearray(32)
    for i in range(31, -1, -1):
        result[i] = charmoves[moves & 3]
        moves >>= 2
    return result[:depth].decode()


intmoves = [0] * 65536

def gen_intmoves():
    i = 0
    for c1 in charmoves:
        for c2 in charmoves:
            for c3 in charmoves:
                for c4 in charmoves:
                    for c5 in charmoves:
                        for c6 in charmoves:
                            for c7 in charmoves:
                                for c8 in charmoves:
                                    intmoves[i] = (c8<<56) + (c7<<48) + (c6<<40) + (c5<<32) + (c4<<24) + (c3<<16) + (c2<<8) + (c1)
                                    i += 1

def path_string(moves, depth):
    result = [0] * 4
    for i in range(3, -1, -1):
        result[i] = intmoves[moves & 0xffff]
        moves >>= 16
    return struct.pack("QQQQ", *result).decode('ascii')[:depth]

def neighbors(position):
    x = position % width
    y = position // width
    n = []
    if x < width - 1:
        n.append(position + 1)
    if y < height - 1:
        n.append(position + width)
    if x > 0:
        n.append(position - 1)
    if y > 0:
        n.append(position - width)
    return n

neighs = [neighbors(i) for i in range(len(data))]

def print_map(m):
    for k, v in m.items():
        p = k &0xffff
        c = k >> 32
        print(p % width, p // width, c, [path_string(x, 32) for x in v])

def solve(chips):
    mn = abs(start % width - goal % width) + abs(start // width - goal // width)
    mx = math.ceil(math.sqrt(chips * 2))
    split = mx // 2 - 1
    depths = range(mn, mx + 1, 2)
    backs = [{} for _ in range(len(depths))]
    for i, max_depth in enumerate(depths):
        backs[i][goal] = [0]
        for depth in range(max_depth - 1, split, -1):
            backs[i] = rev(backs[i], depth)
            # print_map(backs[i])
    print(len(backs[-1]))
    print("backs", time.time() - a, file=sys.stderr)
    forwards = {}
    forwards[(chips << 32) + start] = [0]
    for depth in range(split):
    # for depth in range(split):
        forwards = fwd(forwards, depth)
    print(len(forwards))
    print("forwards", time.time() - a, file=sys.stderr)

    x = time.time()
    paths = {}
    for i, depth in enumerate(depths):
        paths[depth] = combine(forwards, backs[i], split)
    print("combine", time.time() - a, file=sys.stderr)

    # Alternative (slower) path generaton runs another fwd step and finds
    #             keys that intersect
    # forwards = fwd(forwards, split)
    # for i, depth in enumerate(depths):
    #     paths[depth] = []
    #     for k in set(backs[i].keys()).intersection(set(forwards.keys())):
    #         for p2 in backs[i][k]:
    #             for p1 in forwards[k]:
    #                 paths[depth].append(p1 + p2)
    # print("intersect", time.time() - a, file=sys.stderr)
    return paths


def combine(last, current, depth):
    paths = []
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        for pos in neighs[last_pos]:
            current_chip = last_chip
            current_chip -= data[pos]
            if pos != start and pos != goal:
                current_chip -= depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key)
            if current_record is None:
                continue
            for p1 in record:
                m = direction(last_pos, pos)
                m <<= 62 - depth*2
                for p2 in current_record:
                    paths.append(p1+m+p2)
    return paths

def fwd(last, depth):
    current = {}
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        for pos in neighs[last_pos]:
            current_chip = last_chip
            current_chip -= data[pos]
            if pos != start and pos != goal:
                current_chip -= depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key, [])
            for p in record:
                m = direction(last_pos, pos)
                m <<= 62 - depth*2
                current_record.append(p+m)
            current[pos_key] = current_record
    return current

def rev(last, depth):
    current = {}
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        for pos in neighs[last_pos]:
            current_chip = last_chip
            current_chip += data[last_pos]
            if last_pos != start and last_pos != goal:
                current_chip += depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key, [])
            for p in record:
                m = direction(pos, last_pos)
                m <<= 62 - depth*2
                current_record.append(p+m)
            current[pos_key] = current_record
    return current

def direction(fr, to):
    diff = to - fr
    if diff == 1:
        return e
    elif diff == width:
        return s
    elif diff == -1:
        return w
    return s

gen_intmoves()
a = time.time()
solutions = solve(chips)
print([(i, len(x)) for i, x in solutions.items()])
string_solutions = []
for depth, paths in solutions.items():
    for path in paths:
        string_solutions.append(path_string(path, depth))

print("stringify",time.time() - a, file=sys.stderr)
print(len(string_solutions))
print(string_solutions[:10])

walk_fast_string.py

import ctypes
import struct
import time
import math
import sys

data = """* 8 1 7 8 8 5 2 9 5 9 5
8 5 1 1 5 6 9 4 4 5 2 1
7 2 3 5 2 9 2 6 9 3 9 4
9 2 5 9 8 9 5 7 7 5 9 6
2 4 6 7 1 4 2 6 6 2 5 8
2 8 1 5 3 8 4 9 7 5 2 3
2 9 3 5 6 7 2 4 9 4 2 5
6 3 1 7 8 2 3 3 6 7 9 3
2 5 7 4 2 7 8 5 5 3 5 8
5 2 9 8 3 6 1 4 9 5 6 3
4 6 9 8 5 4 9 7 6 4 6 8
2 7 7 1 9 9 7 3 7 2 2 ^"""
chips = 444

height = len(data.split('\n'))
last_height = height - 1
width = len(data.split('\n')[0].split())
last_width = width - 1
first_row = last_width
last_row = height * last_width
data = data.replace(' ', '').replace('\n', '')
start = data.index('*')
goal = data.index('^')
data = data.replace('*', '0')
data = data.replace('^', '5')
data = [ord(c) - 48 for c in data]

n = 0
e = 1
s = 2
w = 3
charmoves = "nesw".encode()

movements = {
    "e": 1,
    "s": width,
    "w": -1,
    "n": -width,
}


def path_string2(moves, depth):
    result = bytearray(32)
    for i in range(31, -1, -1):
        result[i] = charmoves[moves & 3]
        moves >>= 2
    return result[:depth].decode()


def neighbors(position):
    x = position % width
    y = position // width
    n = []
    if x < width - 1:
        n.append((position + 1, 'e', 'w'))
    if y < height - 1:
        n.append((position + width, 's', 'n'))
    if x > 0:
        n.append((position - 1, 'w', 'e'))
    if y > 0:
        n.append((position - width, 'n', 's'))
    return n


def print_map(m):
    for k, v in m.items():
        p = k &0xffff
        c = k >> 32
        print(p % width, p // width, c, [path_string(x, 32) for x in v])

def solve(chips):
    # linear
    mn = abs(start % width - goal % width) + abs(start // width - goal // width)
    mx = math.ceil(math.sqrt(chips * 2))
    split = mx // 2 - 1
    rev_cutoff = 290
    fwd_cutoff = 260
    print(rev_cutoff, fwd_cutoff)
    backwards = {}
    backwards[goal] = ['']
    for depth in range(mx - 1, split, -1):
        backwards = rev(backwards, depth, rev_cutoff)
        if (depth - mn) % 2 == 0:
            backwards[goal] = ['']

        # print_map(backs[i])
    print(len(backwards))
    print("backwards", time.time() - a, file=sys.stderr)
    forwards = {}
    forwards[(chips << 32) + start] = ['']
    for depth in range(split):
    # for depth in range(split):
        forwards = fwd(forwards, depth, fwd_cutoff)
    print(len(forwards))
    print("forwards", time.time() - a, file=sys.stderr)

    return combine(forwards, backwards, split)


def combine(last, current, depth):
    paths = []
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        for (pos, f, _) in neighs[last_pos]:
            current_chip = last_chip
            current_chip -= data[pos]
            if pos != start and pos != goal:
                current_chip -= depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key)
            if current_record is None:
                continue
            for p1 in record:
                for p2 in current_record:
                    paths.append(p1+f+p2)
    return paths

def fwd(last, depth, cutoff):
    current = {}
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        if last_chip < cutoff:
            continue
        for (pos, f, _) in neighs[last_pos]:
            current_chip = last_chip
            current_chip -= data[pos]
            if pos != start and pos != goal:
                current_chip -= depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key, [])
            for p in record:
                current_record.append(p + f)
            current[pos_key] = current_record
    return current

def rev(last, depth, cutoff):
    current = {}
    for last_key, record in last.items():
        last_pos = last_key & 0xffff
        last_chip = last_key >> 32
        if last_chip > cutoff:
            continue
        for (pos, _, r) in neighs[last_pos]:
            current_chip = last_chip
            current_chip += data[last_pos]
            if last_pos != start and last_pos != goal:
                current_chip += depth
            pos_key = (current_chip << 32) + pos
            current_record = current.get(pos_key, [])
            for p in record:
                current_record.append(r + p)
            current[pos_key] = current_record
    return current

a = time.time()
neighs = [neighbors(i) for i in range(len(data))]
print("neighbors", time.time() - a, file=sys.stderr)
solutions = solve(chips)
print(len(solutions))
print(solutions[:10])
print("complete", time.time() - a, file=sys.stderr)