Tumbleword guidance.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
For Tumbleword by Jer Thorp | |
https://tumbleword.glitch.me/ | |
""" | |
from collections import defaultdict | |
from time import time | |
import random | |
start_word = 'charade' | |
start_remaining = 42 | |
cost_of_cut = 3 | |
cost_of_bump = 1 | |
update_rate = 1 | |
restart_rate = 5 | |
max_word_length = len(start_word) | |
search_depth = 6 # limit on cost-per-move | |
search_width = 100 # how many nearby words to consider | |
min_states_for_restart = 1000 | |
words = open('wordlist6.txt').read().splitlines() | |
words = [e for e in words if len(e) < max_word_length] | |
def trim_char(word, i): | |
return word[:i] + word[i+1:] | |
class Memoize: | |
def __init__(self, f): | |
self.f = f | |
self.memo = {} | |
def __call__(self, *args): | |
if not args in self.memo: | |
self.memo[args] = self.f(*args) | |
return self.memo[args] | |
charset = 'abcdefghijklmnopqrstuvwxyz' | |
@Memoize | |
def character_dist(c1,c2): | |
n1 = ord(c1) | |
n2 = ord(c2) | |
return min( | |
abs(n1-n2), | |
abs(n2-n1), | |
abs(n1-n2+len(charset)), | |
abs(n2-n1+len(charset))) | |
# from a to b (transitions are not bidirectional) | |
@Memoize | |
def difference_count_nobump(a, b): | |
if len(a) == len(b): | |
return sum([character_dist(ac, bc) for ac,bc in zip(list(a), list(b))]) | |
options = [difference_count_nobump(trim_char(a, i), b) for i in range(len(a))] | |
return 3 + min(*options) | |
def bump(a, i): | |
return a[i:] + a[:i] | |
def bump_cost(i, word_length): | |
if i < word_length / 2: | |
return i | |
return abs(i - word_length) | |
@Memoize | |
def difference_count(a, b): | |
al = len(a) | |
bl = len(b) | |
# short circuit to disable cutting | |
# if al > bl: | |
# return None | |
if bl > al: # if bl is longer, impossible | |
return None | |
if al > bl + 1: # if bl is more than one character smaller, ignore | |
return None | |
bumped_differences = [difference_count_nobump(bump(a, i), b) + bump_cost(i, bl) for i in range(len(a))] | |
return min(bumped_differences) | |
@Memoize | |
def word_set(a): | |
result = [] | |
for b in words: | |
if a == b: | |
continue | |
diff = difference_count(a, b) | |
if diff is None or diff > search_depth: | |
continue | |
result.append((b, diff)) | |
result.sort(key=lambda x: x[1]) | |
return result | |
def greedy_solve(score, remaining, word_path): | |
cur_word = word_path[-1] | |
dead_end = True | |
for next_word, diff in word_set(cur_word): | |
if next_word in word_path: | |
continue | |
else: | |
dead_end = False | |
break | |
if dead_end or diff > remaining: | |
return score, remaining, word_path | |
next_score = score + len(next_word) | |
next_remaining = remaining - diff | |
next_path = [*word_path, next_word] | |
return greedy_solve(next_score, next_remaining, next_path) | |
last_updated = 0 | |
last_restarted = 0 | |
best_end_score = None | |
best_end_state = None | |
# state includes: | |
# 0 estimated score at finish | |
# 1 true cumulative score | |
# 2 remaining moves | |
# 3 word path | |
def start_state(): | |
states = [[0, 0, start_remaining, [start_word]]] | |
states[0][0] = greedy_solve(0, start_remaining, [start_word]) | |
return states | |
states = start_state() | |
try: | |
while True: | |
states.sort(reverse=True) | |
# pick states randomly, but focus on better options | |
i = int((random.random() ** 10) * len(states)) | |
cur_state = states[i] | |
del states[i] # pop this state | |
_, score, remaining, word_path = cur_state # unpack cur state | |
cur_word = word_path[-1] | |
if time() - last_updated > update_rate: | |
# clear_output(wait=True) | |
if best_end_state is None: | |
print(' '.join(word_path), score, '...') # processing | |
else: | |
print(' '.join(best_end_state[-1]), best_end_score) # found a finished game | |
last_updated = time() | |
from collections import defaultdict | |
from time import time | |
import random | |
start_word = 'charade' | |
start_remaining = 42 | |
cost_of_cut = 3 | |
cost_of_bump = 1 | |
update_rate = 1 | |
restart_rate = 5 | |
max_word_length = len(start_word) | |
search_depth = 6 # limit on cost-per-move | |
search_width = 100 # how many nearby words to consider | |
min_states_for_restart = 1000 | |
words = open('wordlist6.txt').read().splitlines() | |
words = [e for e in words if len(e) < max_word_length] | |
def trim_char(word, i): | |
return word[:i] + word[i+1:] | |
class Memoize: | |
def __init__(self, f): | |
self.f = f | |
self.memo = {} | |
def __call__(self, *args): | |
if not args in self.memo: | |
self.memo[args] = self.f(*args) | |
return self.memo[args] | |
charset = 'abcdefghijklmnopqrstuvwxyz' | |
@Memoize | |
def character_dist(c1,c2): | |
n1 = ord(c1) | |
n2 = ord(c2) | |
return min( | |
abs(n1-n2), | |
abs(n2-n1), | |
abs(n1-n2+len(charset)), | |
abs(n2-n1+len(charset))) | |
# from a to b (transitions are not bidirectional) | |
@Memoize | |
def difference_count_nobump(a, b): | |
if len(a) == len(b): | |
return sum([character_dist(ac, bc) for ac,bc in zip(list(a), list(b))]) | |
options = [difference_count_nobump(trim_char(a, i), b) for i in range(len(a))] | |
return cost_of_cut + min(*options) | |
def bump(a, i): | |
return a[i:] + a[:i] | |
def bump_cost(i, word_length): | |
if i < word_length / 2: | |
return cost_of_bump * i | |
return cost_of_bump * abs(i - word_length) | |
@Memoize | |
def difference_count(a, b): | |
al = len(a) | |
bl = len(b) | |
# short circuit to disable cutting | |
# if al > bl: | |
# return None | |
if bl > al: # if bl is longer, impossible | |
return None | |
if al > bl + 1: # if bl is more than one character smaller, ignore | |
return None | |
bumped_differences = [difference_count_nobump(bump(a, i), b) + bump_cost(i, bl) for i in range(len(a))] | |
return min(bumped_differences) | |
@Memoize | |
def word_set(a): | |
result = [] | |
for b in words: | |
if a == b: | |
continue | |
diff = difference_count(a, b) | |
if diff is None or diff > search_depth: | |
continue | |
result.append((b, diff)) | |
result.sort(key=lambda x: x[1]) | |
return result | |
def greedy_solve(score, remaining, word_path): | |
cur_word = word_path[-1] | |
dead_end = True | |
for next_word, diff in word_set(cur_word): | |
if next_word in word_path: | |
continue | |
else: | |
dead_end = False | |
break | |
if dead_end or diff > remaining: | |
return score, remaining, word_path | |
next_score = score + len(next_word) | |
next_remaining = remaining - diff | |
next_path = [*word_path, next_word] | |
return greedy_solve(next_score, next_remaining, next_path) | |
last_updated = 0 | |
last_restarted = 0 | |
best_end_score = None | |
best_end_state = None | |
# state includes: | |
# 0 estimated score at finish | |
# 1 true cumulative score | |
# 2 remaining moves | |
# 3 word path | |
def start_state(): | |
states = [[0, 0, start_remaining, [start_word]]] | |
states[0][0] = greedy_solve(0, start_remaining, [start_word]) | |
return states | |
states = start_state() | |
try: | |
while True: | |
states.sort(reverse=True) | |
# pick states randomly, but focus on better options | |
i = int((random.random() ** 10) * len(states)) | |
cur_state = states[i] | |
del states[i] # pop this state | |
_, score, remaining, word_path = cur_state # unpack cur state | |
cur_word = word_path[-1] | |
if time() - last_updated > update_rate: | |
# clear_output(wait=True) | |
if best_end_state is None: | |
print(' '.join(word_path), score, '...') # processing | |
else: | |
print(' '.join(best_end_state[-1]), best_end_score) # found a finished game | |
last_updated = time() | |
# pick top N words | |
next_words = word_set(cur_word) | |
# create new states for each | |
dead_end = True | |
used = 0 | |
initial_diff = None | |
for next_word, diff in next_words: | |
if next_word in word_path: | |
continue | |
if diff > remaining: | |
continue | |
# heuristic to ignore more-expensive tumbles | |
if initial_diff is None: | |
initial_diff = diff | |
if diff > initial_diff + 1: | |
continue | |
finish_score_estimate = greedy_solve(score, remaining, word_path)[0] | |
next_score = score + len(next_word) | |
next_remaining = remaining - diff | |
next_path = [*word_path, next_word] | |
state = [finish_score_estimate, next_score, next_remaining, next_path] | |
states.append(state) | |
dead_end = False | |
used += 1 | |
if used >= search_width: | |
break | |
if dead_end: | |
if best_end_score is None or score >= best_end_score: | |
best_end_state = cur_state | |
best_end_score = score | |
if len(states) == 0: | |
print('finished') | |
print(best_end_state) | |
break | |
# restart every so often if we've already explored a lot | |
if time() - last_restarted > restart_rate: | |
if len(states) > min_states_for_restart: | |
states = start_state() | |
last_restarted = time() | |
except KeyboardInterrupt: | |
pass |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment