Solution for Jan 3 2020 fivethirtyeight.com Riddler Classic

spellingbee.py

# Jan 3 2020 Riddler Classic -- find "Spelling Bee" puzzle w/max total word score
# Here we're trying to take Peter Norvig's solution a step further by noting that
# the subsets (independent of a particular honeycomb) can be precalculated, too.
# Does that turn out faster than running combinations()? We'll see.

# We're now representing the center by its index in the honeycomb string.

from collections import Counter

def signature(w):
    return ''.join(sorted(set(w)))


def isPangram(sig):
    return len(sig) == 7


# Word and signature length constraints are inherent in the game.
# The Riddler added the "no 's'" requirement.
def wordConstraints(w):
    return len(w) > 3 and "s" not in w and len(signature(w)) <= 7


def wordScore(w, sig):
    lw = len(w)
    return 1 if lw == 4 else (lw + (7 if isPangram(sig) else 0))


def runEncode(bitmap):
    runs = []
    len = 0
    for i in range(7):
        if bitmap & (1 << i):
            if len == 0:
                pos = i
            len += 1
        elif len > 0:
            runs.append((pos, pos + len))
            len = 0
    if len > 0:
        runs.append((pos, pos + len))
    return runs
        

def rleDict():
    rd = {}
    for center in range(7):
        centerBit = 1 << center
        lsbMask = centerBit - 1
        msbMask = 63 ^ (centerBit | lsbMask)
        rd[center] = [runEncode((n & msbMask) << 1 | centerBit | (n & lsbMask))
                                for n in range(64)]
    return rd


def subsets(puzzle, rd):
    (honeycomb, center) = puzzle
    for rle in rd[center]:
        yield ''.join(honeycomb[m : n] for (m, n) in rle)


def bestPuzzle():
    sp = Counter()
    sigs = set()
    with open("enable1.txt", "r") as f:
        for w in filter(wordConstraints, f.read().splitlines()):
            sig = signature(w)
            sigs.add(sig)
            sp[sig] += wordScore(w, sig)
            
    rd = rleDict()
    
    def gameScore(puzzle):
        return sum(sp[s] for s in subsets(puzzle, rd))
    
    puzzles = ((h, c) for h in filter(isPangram, sigs) for c in range(7))
    return max(((gameScore(p), p) for p in puzzles), key = lambda x:x[0])

OK, this is the last version in Python for me. Peter Norvig did a seriously good job of speeding things up. His code finds the Riddler solution in a shade under two seconds. The major insight is that if you create a dictionary mapping letter sets (what we called the "signature" above) to the sum of values of all the words with that letter set, you can save a bunch of work later.

The current version of the gist uses Norvig's method, except... it occurred to me that you could precalculate the subsets, too, though they'd have to have a form not tied to a particular honeycomb. Would that save any more time?

The answer: I have yet to come up with a good way to take those precalculated sets and a honeycomb and generate the pertinent letter sets that's faster than just using itertools.combinations(), no precalculations, as Norvig does. One can use the above code to solve the Riddler Classic problem... but, at least on my computer, according to the scalene profiler, it takes 6.34 seconds.

Maybe a Go version...