vishvananda · March 20, 2023 09:33 · Mar 20, 2023 · Mar 19, 2023 · Mar 18, 2023 · Mar 18, 2023
diff --git a/walk_fast_string.py b/walk_fast_string.py
@@ -67,7 +67,6 @@ def neighbors(position):
         n.append((position - width, 'n', 's'))
     return n
 
-neighs = [neighbors(i) for i in range(len(data))]
 
 def print_map(m):
     for k, v in m.items():
@@ -76,33 +75,32 @@ def print_map(m):
         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
-    depths = range(mn, mx + 1, 2)
-    backs = [{} for _ in range(len(depths))]
-    for i, max_depth in enumerate(depths):
-        backs[i][goal] = ['']
-        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)
+    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)
+        forwards = fwd(forwards, depth, fwd_cutoff)
     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)
-
-    return paths
+    return combine(forwards, backwards, split)
 
 
 def combine(last, current, depth):
@@ -124,11 +122,13 @@ def combine(last, current, depth):
                     paths.append(p1+f+p2)
     return paths
 
-def fwd(last, depth):
+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]
@@ -141,11 +141,13 @@ def fwd(last, depth):
             current[pos_key] = current_record
     return current
 
-def rev(last, depth):
+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]
@@ -159,6 +161,9 @@ def rev(last, depth):
     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([(i, len(x)) for i, x in solutions.items()])
-print(solutions[26][:10])
+print(len(solutions))
+print(solutions[:10])
+print("complete", time.time() - a, file=sys.stderr)
diff --git a/walk_fast_string.py b/walk_fast_string.py
@@ -0,0 +1,164 @@
+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
+
+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
+    depths = range(mn, mx + 1, 2)
+    backs = [{} for _ in range(len(depths))]
+    for i, max_depth in enumerate(depths):
+        backs[i][goal] = ['']
+        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] = ['']
+    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)
+
+    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, 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):
+    current = {}
+    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, [])
+            for p in record:
+                current_record.append(p + f)
+            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, _, 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()
+solutions = solve(chips)
+print([(i, len(x)) for i, x in solutions.items()])
+print(solutions[26][:10])
diff --git a/walk_fast.py b/walk_fast.py
@@ -52,24 +52,27 @@ def path_string2(moves, depth):
     return result[:depth].decode()
 
 
-intmoves = [0] * 256
+intmoves = [0] * 65536
 
 def gen_intmoves():
     i = 0
     for c1 in charmoves:
         for c2 in charmoves:
             for c3 in charmoves:
                 for c4 in charmoves:
-                    intmoves[i] = (c3<<24) + (c4<<16) + (c1<<8) + (c2)
-                    i += 1
+                    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] * 8
-    for i in range(7, -1, -1):
-        result[i] = intmoves[moves & 0xff]
-        moves >>= 8
-    return struct.pack("IIIIIIII", *result).decode()[: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
@@ -109,6 +112,7 @@ def solve(chips):
     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)
@@ -212,4 +216,4 @@ def direction(fr, to):
 
 print("stringify",time.time() - a, file=sys.stderr)
 print(len(string_solutions))
-print(string_solutions[:10])
+print(string_solutions[:10])
diff --git a/walk_fast.py b/walk_fast.py
@@ -109,7 +109,6 @@ def solve(chips):
     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)

diff --git a/walk_fast.py b/walk_fast.py
@@ -0,0 +1,216 @@
+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] * 256
+
+def gen_intmoves():
+    i = 0
+    for c1 in charmoves:
+        for c2 in charmoves:
+            for c3 in charmoves:
+                for c4 in charmoves:
+                    intmoves[i] = (c3<<24) + (c4<<16) + (c1<<8) + (c2)
+                    i += 1
+
+def path_string(moves, depth):
+    result = [0] * 8
+    for i in range(7, -1, -1):
+        result[i] = intmoves[moves & 0xff]
+        moves >>= 8
+    return struct.pack("IIIIIIII", *result).decode()[: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])