Skip to content

Instantly share code, notes, and snippets.

@kylemcdonald
Last active December 21, 2022 23:56
Embed
What would you like to do?
Tumbleword guidance.
"""
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