Skip to content

Instantly share code, notes, and snippets.

@bostikforever

bostikforever/improv.py Secret

Last active March 19, 2023 17:58
Show Gist options
  • Save bostikforever/62b2f551566383f385c4a307482e5425 to your computer and use it in GitHub Desktop.
Save bostikforever/62b2f551566383f385c4a307482e5425 to your computer and use it in GitHub Desktop.
Download ZIP
"Improved" solution to @vishvananda's "Python is slow" problem.
Raw
improv.py
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
diff_movements = {
1: "e",
width: "s",
-1: "w",
-width: "n",
}
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for _, move, legit in movements:
if legit:
yield position + move
def path_to_moves(path):
return "".join(map(to_move, pairwise(path)))
def to_move(start_end):
start, end = start_end
diff = end - start
move = diff_movements.get(diff, None)
# assert move
return move
def _pairwise(iterable):
import itertools
first, second = itertools.tee(iterable)
return zip(first, itertools.islice(second, 1, None))
def pairwise(iterable):
try:
import itertools
return itertools.pairwise(iterable)
except AttributeError:
return _pairwise(iterable)
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(goal_chip, neighbor, depth)] = [goal]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N-1):
for depth in range(max_depth, -1, -1):
pos_key = (target_chip, pos, depth)
pos_values = []
for neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor_chip, neighbor, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append(neighbor_key)
if pos_values:
sub_solutions[pos_key] = pos_values
# all_paths = get_paths(sub_solutions, (chips, start, 0), verify)
# if limit is not None:
# all_paths = itertools.islice(all_paths, limit)
# with open("output.txt", "w") as output:
# output.writelines(map(lambda x: f"{x}\n", all_paths))
return count_paths(sub_solutions, (chips, start, 0))
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
if curr == goal:
return 1
return sum(
count_paths(sub_solutions, next_frag) for next_frag in sub_solutions[curr]
)
def get_paths(sub_solutions, curr, verify, *, path=None):
if path is None:
cost, pos, depth = curr
path = [pos]
if curr == goal:
# if verify:
# assert verify_path(path), "Failed to verify path %s" % path
yield path_to_moves(path)
return
for next_path_frag in sub_solutions[curr]:
if next_path_frag == goal:
next_pos = next_path_frag
else:
cost, next_pos, depth = next_path_frag
path.append(next_pos)
yield from get_paths(sub_solutions, next_path_frag, verify, path=path)
path.pop()
print(solution(limit=None, verify=True))
Raw
improv_with_count_opt.py
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
diff_movements = {
1: "e",
width: "s",
-1: "w",
-width: "n",
}
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for _, move, legit in movements:
if legit:
yield position + move
def path_to_moves(path):
return "".join(map(to_move, pairwise(path)))
def to_move(start_end):
start, end = start_end
diff = end - start
move = diff_movements.get(diff, None)
# assert move
return move
def _pairwise(iterable):
import itertools
first, second = itertools.tee(iterable)
return zip(first, itertools.islice(second, 1, None))
def pairwise(iterable):
try:
import itertools
return itertools.pairwise(iterable)
except AttributeError:
return _pairwise(iterable)
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(goal_chip, neighbor, depth)] = [goal]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N-1):
for depth in range(max_depth, -1, -1):
pos_key = (target_chip, pos, depth)
pos_values = []
for neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor_chip, neighbor, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append(neighbor_key)
if pos_values:
sub_solutions[pos_key] = pos_values
# all_paths = get_paths(sub_solutions, (chips, start, 0), verify)
# if limit is not None:
# all_paths = itertools.islice(all_paths, limit)
# with open("output.txt", "w") as output:
# output.writelines(map(lambda x: f"{x}\n", all_paths))
return count_paths(sub_solutions, (chips, start, 0))
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
import functools
@functools.cache
def count_paths_impl(curr):
if curr == goal:
return 1
return sum(
count_paths_impl(next_frag) for next_frag in sub_solutions[curr]
)
return count_paths_impl(curr)
def get_paths(sub_solutions, curr, verify, *, path=None):
if path is None:
cost, pos, depth = curr
path = [pos]
if curr == goal:
# if verify:
# assert verify_path(path), "Failed to verify path %s" % path
yield path_to_moves(path)
return
for next_path_frag in sub_solutions[curr]:
if next_path_frag == goal:
next_pos = next_path_frag
else:
cost, next_pos, depth = next_path_frag
path.append(next_pos)
yield from get_paths(sub_solutions, next_path_frag, verify, path=path)
path.pop()
print(solution(limit=None, verify=True))
Raw
improve_simplify.py
import array
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
GOAL_STATE = goal
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for move, move_diff, legit in movements:
if legit:
yield move, position + move_diff
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for move, neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(neighbor, goal_chip, depth)] = [(move, GOAL_STATE)]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N - 1):
for depth in range(max_depth, -1, -1):
pos_key = (pos, target_chip, depth)
pos_values = []
for move, neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor, neighbor_chip, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append((move, neighbor_key))
if pos_values:
sub_solutions[pos_key] = pos_values
start_state = (start, chips, 0)
all_paths = get_paths(sub_solutions, start_state, verify)
if limit is not None:
all_paths = itertools.islice(all_paths, limit)
with open("output.txt", "w") as output:
for path in all_paths:
output.write(path)
output.write("\n")
return count_paths(sub_solutions, start_state)
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
import functools
@functools.cache
def count_paths_impl(curr):
if curr == GOAL_STATE:
return 1
return sum(count_paths_impl(next_frag) for _, next_frag in sub_solutions[curr])
return count_paths_impl(curr)
def get_paths(sub_solutions, curr, verify):
moves = []
def get_paths_impl(curr, moves):
for move, next_state in sub_solutions[curr]:
moves.append(move)
if next_state is GOAL_STATE:
yield "".join(moves)
else:
yield from get_paths_impl(next_state, moves)
moves.pop()
return get_paths_impl(curr, moves)
print(solution(limit=None, verify=True))
Raw
improve_simplify_no_gen.py
import array
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
GOAL_STATE = goal
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for move, move_diff, legit in movements:
if legit:
yield move, position + move_diff
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for move, neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(neighbor, goal_chip, depth)] = [(move, GOAL_STATE)]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N - 1):
for depth in range(max_depth, -1, -1):
pos_key = (pos, target_chip, depth)
pos_values = []
for move, neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor, neighbor_chip, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append((move, neighbor_key))
if pos_values:
sub_solutions[pos_key] = pos_values
start_state = (start, chips, 0)
# if limit is not None:
# all_paths = itertools.islice(all_paths, limit)
with open("output.txt", "w") as output:
def write_to_file(moves_str):
output.write(moves_str)
output.write("\n")
get_paths(sub_solutions, start_state, write_to_file, verify)
return count_paths(sub_solutions, start_state)
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
import functools
@functools.cache
def count_paths_impl(curr):
if curr == GOAL_STATE:
return 1
return sum(count_paths_impl(next_frag) for _, next_frag in sub_solutions[curr])
return count_paths_impl(curr)
def get_paths(sub_solutions, curr, action, verify):
moves = []
def get_paths_impl(curr, moves):
for move, next_state in sub_solutions[curr]:
moves.append(move)
if next_state is GOAL_STATE:
moves_str = "".join(moves)
action(moves_str)
else:
get_paths_impl(next_state, moves)
moves.pop()
return get_paths_impl(curr, moves)
print(solution(limit=None, verify=True))
Raw
improve_simplify_no_gen_with_lengthen.py
import array
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
GOAL_STATE = goal
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for move, move_diff, legit in movements:
if legit:
yield move, position + move_diff
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for move, neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(neighbor, goal_chip, depth)] = [(move, GOAL_STATE)]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N - 1):
for depth in range(max_depth, -1, -1):
pos_key = (pos, target_chip, depth)
pos_values = []
for move, neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor, neighbor_chip, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append((move, neighbor_key))
if pos_values:
sub_solutions[pos_key] = pos_values
start_state = (start, chips, 0)
# can vary memory cost by varying length of path fragments (exponentially)
# already 4-move fragments (i.e. 2 iterations) require 9Gib, this means slower
# exceution depending on the machine...
# with 2-move fragments, we have half cut the total run time by 2-3 times, but pay a
# ~3 fold cost in memory (1.4GB vs 450MB with the default 1 move fragments)
# Also lengthen_paths can be parallelized easily, but for the 2 move fragments it
# only costs ~4 seconds.
import time
t0 = time.monotonic_ns()
sub_solutions = lengthen_paths(sub_solutions, 1)
t1 = time.monotonic_ns()
print("lengthen time:", (t1 - t0) / 1e9)
# if limit is not None:
# all_paths = itertools.islice(all_paths, limit)
with open("output.txt", "w") as output:
def write_to_file(moves_str):
output.write(moves_str)
output.write("\n")
get_paths(sub_solutions, start_state, write_to_file, verify)
return count_paths(sub_solutions, start_state)
def lengthen_paths(sub_solutions, iters):
def lengthen_paths_impl(state_space):
results = {}
for state_key, neighbors in state_space.items():
results[state_key] = []
for move_frag_1, neighbor_key_1 in neighbors:
if neighbor_key_1 is GOAL_STATE:
results[state_key].append((move_frag_1, neighbor_key_1))
continue
for move_frag_2, neighbor_key_2 in state_space[neighbor_key_1]:
results[state_key].append(
(move_frag_1 + move_frag_2, neighbor_key_2)
)
return results
ret = sub_solutions
for _ in range(iters):
ret = lengthen_paths_impl(ret)
return ret
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
import functools
@functools.cache
def count_paths_impl(curr):
if curr == GOAL_STATE:
return 1
return sum(count_paths_impl(next_frag) for _, next_frag in sub_solutions[curr])
return count_paths_impl(curr)
def get_paths(sub_solutions, curr, action, verify):
moves = []
def get_paths_impl(curr, moves):
for move, next_state in sub_solutions[curr]:
moves.append(move)
if next_state is GOAL_STATE:
moves_str = "".join(moves)
action(moves_str)
else:
get_paths_impl(next_state, moves)
moves.pop()
return get_paths_impl(curr, moves)
print(solution(limit=None, verify=True))
Raw
improve_simplify_with_lengthen.py
import array
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 ^
""".strip()
chips = 444
height = len(data.split("\n"))
width = len(data.split("\n")[0].split())
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]
GOAL_STATE = goal
def neighbors(position):
x = position % width
y = position // width
movements = (
("e", 1, x < width - 1),
("s", width, y < height - 1),
("w", -1, x > 0),
("n", -width, y > 0),
)
for move, move_diff, legit in movements:
if legit:
yield move, position + move_diff
def solution(*, limit=None, verify=False):
import math
import itertools
# max depth beyond which we will exhaust our chips only on additional costs
max_depth = int(math.ceil(math.sqrt(chips * 2))) + 1
sub_solutions = {}
# initialize with base case
goal_chip = data[goal]
for move, neighbor in neighbors(goal):
for depth in range(max_depth + 1):
sub_solutions[(neighbor, goal_chip, depth)] = [(move, GOAL_STATE)]
N = len(data)
for target_chip in range(goal_chip + 1, chips + 1):
for pos in range(N - 1):
for depth in range(max_depth, -1, -1):
pos_key = (pos, target_chip, depth)
pos_values = []
for move, neighbor in neighbors(pos):
neighbor_chip = target_chip - depth - data[neighbor]
neighbor_key = (neighbor, neighbor_chip, depth + 1)
if neighbor_key not in sub_solutions:
continue
pos_values.append((move, neighbor_key))
if pos_values:
sub_solutions[pos_key] = pos_values
start_state = (start, chips, 0)
# can vary memory cost by varying length of path fragments (exponentially)
# already 4-move fragments (i.e. 2 iterations) require 9Gib, this means slower
# exceution depending on the machine...
# with 2-move fragments, we have half cut the total run time by 2-3 times, but pay a
# ~3 fold cost in memory (1.4GB vs 450MB with the default 1 move fragments)
# Also lengthen_paths can be parallelized easily, but for the 2 move fragments it
# only costs ~4 seconds.
import time
t0 = time.monotonic_ns()
sub_solutions = lengthen_paths(sub_solutions, 1)
t1 = time.monotonic_ns()
print("lengthen time:", (t1-t0)/1e9)
all_paths = get_paths(sub_solutions, start_state, verify)
if limit is not None:
all_paths = itertools.islice(all_paths, limit)
with open("output.txt", "w") as output:
for path in all_paths:
output.write(path)
output.write("\n")
return count_paths(sub_solutions, start_state)
def lengthen_paths(sub_solutions, iters):
def lengthen_paths_impl(state_space):
results = {}
for state_key, neighbors in state_space.items():
results[state_key] = []
for move_frag_1, neighbor_key_1 in neighbors:
if neighbor_key_1 is GOAL_STATE:
results[state_key].append((move_frag_1, neighbor_key_1))
continue
for move_frag_2, neighbor_key_2 in state_space[neighbor_key_1]:
results[state_key].append(
(move_frag_1 + move_frag_2, neighbor_key_2)
)
return results
ret = sub_solutions
for _ in range(iters):
ret = lengthen_paths_impl(ret)
return ret
def verify_path(path):
import itertools
add_cost = 0
path_chips = chips
N = len(data)
assert path[0] == start, "Path %s does not begin with start pos %s" % (path, start)
assert path[-1] == N - 1, "Path %s does not end with goal pos %s" % (path, goal)
inner_steps = itertools.islice(path, 1, len(path) - 1)
for step in inner_steps:
path_chips -= data[step] + add_cost
add_cost += 1
assert (
path_chips == data[goal]
), "Chips would not be exhasted by final step. Expected %s, have %s" % (
data[goal],
path_chips,
)
return True
def count_paths(sub_solutions, curr):
import functools
@functools.cache
def count_paths_impl(curr):
if curr == GOAL_STATE:
return 1
return sum(count_paths_impl(next_frag) for _, next_frag in sub_solutions[curr])
return count_paths_impl(curr)
def get_paths(sub_solutions, curr, verify):
moves = []
def get_paths_impl(curr, moves):
for move, next_state in sub_solutions[curr]:
moves.append(move)
if next_state is GOAL_STATE:
yield "".join(moves)
else:
yield from get_paths_impl(next_state, moves)
moves.pop()
return get_paths_impl(curr, moves)
print(solution(limit=None, verify=True))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment