letterlocks.py

# Notes and code about "Letter Lockpicking"
# http://puzzles.bostonpython.com/lock.html
# Jon Kiparsky  (jon.kiparsky@gmail.com)


# Starting set of rings:

rings = ['BDMJPRSTLN', 
         'AEIOUYRTLH', 
         'ACDEORSTLN', 
         'DHKYRSTLNE']

# get a word list. We only care about 4-letter words here. 

def get_wordlist(n = 4):
    '''
    return a list of legal words of length n
    '''
    words = open('/usr/share/dict/words','r').read().upper().split('\n')
    return [word for word in words if len(word)== n]


w4 = get_wordlist()

# reduce the word list by eliminating trivially impossible words, ie
# words which can't be represented on this lock

for i in range (4):
    w4 = [w for w in w4 if w[i] in rings[i]]    

# Incidentally, this produces an answer to Question 1: the length of
# the resulting list is the number of words that can appear on this
# lock: 1213


# Now address question 2. Since the search space is small, a crude
# approach does the job. We'll just try each possible word as a
# setting, take all of the settings producing triples or more, and
# then look for chemicals, foods, and times.

def words_for_setting(setting, rings, words):
    '''get the words generated by some setting, a setting being a string
    of length 4
    '''
    rings = [ring[ring.find(c):] + ring [:ring.find(c)] for (ring, c)
             in zip(rings, setting)]
    combos = ["".join(tup) for tup in zip(*rings)]
    return [word for word in combos if word in words]

 
 # try each plausible word in the dictionary as a setting, make a list of the resulting tuples

all_settings = [words_for_setting(word, rings, w4) for word in w4]
triples_plus = [sorted(s) for s in all_settings if len(s)>=3] 
deduped = {l[0]:l for l in triples_plus}.values()

# the deduped list has all of the settings with n-tuples, n>=3. By inspection, we find 
# ['BEET', 'DIOL', 'MORN'] which meets the criteria. 


# Question 3 is trivially answered by counting the entries in the de-duped list of 3+-tuples.
# I get 81 settings producing tuples of n >=3, or 250 individual words appearing in such tuples.
# 317 settings producing twins, implying 634 individual words which have twin settings
# 74 settings producing triples, implying 222 invidual words appearing in triples. 


## Problem 4: what combination of 10 dials produces the largest tuple
## of 4-letter words 
#Restriction: letters on any dial must be unique  to that dial.

def compatible (w, wset):
    '''
    return a subset of wset, all words in wset which are compatible with w (do not share character c at any point
    '''
    return [word for word in wset if all ([c1 != c2 for (c1, c2) in zip (w, word)])]


def stupid_maximal_rings(words):
    '''
    search for the set of rings that produces the largest word-tuple
    what we're looking for is the largest set of 4-letter words such that for all word pairs  
    word1 and word2 in the set c[i] of word1 != c[i] of word2  
    To begin with, a completely blind and greedy search, utterly stupid algorithm.
    '''
    rest = list(words) # work on a local copy
    wordlist =[]
    while len (rest) > 0:
        wordlist.append( rest[0])
        rest = compatible(rest[0], rest)
    return wordlist

stupid_result = stupid_maximal_rings(w4)
# result: ['AANI', 'BEAD', 'CHEE', 'DIBS', 'EBON', 'FLIP',
# 'GOFF','HUCK', 'ICHO', 'KNUB', 'LYRA', 'ODYL', 'UGLY']

# So we can get a 13-tuple with absolutely no effort at all. A bit
# more cleverness will probably produce some improvement.

# The first part of problem 5 seems to be solved by this approach as well, since the
# method of solution generated "siamese twin" tuple. s
#