Tumbleword guidance.

tumbleword.py

"""
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