Things that make you go hmmm

Anyone else notice that many prognostications about the future of AI are expressed with the same unwarranted certainty that AI is itself criticized for? Hmmmm.

GitHub repo updated

It occurred to me that I should update my GitHub repo with some code I've written in the last few months, including the Spelling Bee script from the last post, and a Chrome extension I wrote that forces all tabs to open in a single window.

Repo is here: engyrus

Creating and Solving Spelling Bee Puzzles in Python

 I enjoy playing the New York Times' game Spelling Bee. I wondered about how to write a Python script that creates and solves Spelling Bee puzzles and decided to take a stab at it.

For those who aren't familiar, each puzzle is built on a seed word containing exactly seven unique letters. These are randomly arranged in a hexagon format resembling a honeycomb. You make words at least four letters long from these letters (you can use letters more than once) and the puzzle judges them as real words or not. One letter is placed in the center of the puzzle and must appear in all words. The words are scored based on their lengths and the game designates you as a genius (or lesser skill levels) based on your score. Every puzzle has one or more pangrams that use all the letters in the puzzle at least once; one is the seed word. although there can be more.

It turns out you don't need much code at all to generate a puzzle that meets the criteria. Given a list of English words, you can easily identify all the ones that could be a seed word (contain only letters and have exactly seven unique ones). Then you can either pick one at random or ask the user to enter one (making sure it qualifies) as the seed for a puzzle.

Most Unix-like systems have a word list at /usr/share/dict/words. This list exists on Mac OS X, so I've used it. The list does have a flaw: it's much bigger than the one the New York Times uses. (I've often been surprised by the words that aren't recognized by the official Spelling Bee puzzle.) This means that not only will the solution set be somewhat different from the Times' answers, you'll see a number of obscure and naughty words that you'd never see in theirs. No big deal, it'll work with any word list so you can substitute whatever you want. Exercise for the reader and all that.

The basic approach I took is:

1. Read all the words into a list. Make a second list containing only the words that could be seed words (exactly seven unique letters).
2. Ask the user to select a seed word or allow the script to choose one randomly. If the user enters one, it is validated against the seed word list. If the user allows the script to choose one, they're further asked for a sequence of letters that should appear in the seed (I have noticed that puzzles often contain "ing" or another sequence of letters that constrains the solutions, so I added the ability to do that, if you want).
• The user may also just enter a string of 7 unique letters that are not a word. (You might have this instead of the actual seed word if you are trying to solve an existing puzzle.) The script will find the first pangram made of those letters and use that as the seed word.
3. Ask the user to choose which letter should be in the center of the puzzle, or again choose it randomly.
4. Find all the words in the word list that are solutions to the puzzle. These are the ones that are at least four letters long, contain only letters from the seed word, and contain the center letter.

The script can be used either to generate puzzles (by finding good seed words, trying to solve, then checking your answers) or to help solve a puzzle, including the ones in the Times.

You could expand it into an actual game that you can play, with a GUI and all that, but I'll leave that for you. Here's the code.

# bee.py - using UNIX word list, create a puzzle like the New York Times' 

#          "Spelling Bee," along with all possible solutions

# The UNIX word list is more extensive than the Times' list; you'll see

# some mighty obscure words, and also some totally inappropriate ones.

import random, itertools

all_words = open("/usr/share/dict/words").read().splitlines()

# read potential seed words: at least 7 unique letters and no uppercase or punctuation

seed_words = [word for word in all_words if len(word) > 6 and word.isalpha() and 

              len(set(word)) == 7 and word.lower() == word]

print(len(seed_words), "seed words")

# get or randomly choose seed word for puzzle

seed_word = ""

while seed_word not in seed_words:

    seed_word = input("seed word, exactly 7 unique letters (enter for random): " ).lower()

    if seed_word == "":

        required_letters = input(

            "... substring the random word must contain: ").lower()

        seed_word = random.choice(seed_words)

        while required_letters != "" and required_letters not in seed_word:

            seed_word = random.choice(seed_words)

        print("seed word:", seed_word.upper())

    else:

        # the user entered a word but it is not a seed word

        if seed_word not in seed_words:

            seed_word = set(seed_word.lower())

            if len(seed_word) == 7:

                seed_word = min(itertools.chain((

                    word for word in seed_words if set(word) == seed_word), ""), key=len)

                if seed_word:

                    print("seed word:", seed_word.upper())

            else:

                seed_word = ""

# get or choose center letter for puzzle, which must appear in all answers

seed_letters = set(seed_word)

center_letter = ""

while len(center_letter) != 1 or center_letter not in seed_letters:

    center_letter = input("center letter (enter for random): ").lower()

    if center_letter == "":

        center_letter = random.choice(seed_word)

        print("center letter:", center_letter.upper())

# print puzzle, randomized but with center letter in middle

puzzle_letters = list(set(seed_word.upper()))

random.shuffle(puzzle_letters)

# put the center letter in the center

center_index = puzzle_letters.index(center_letter.upper())

puzzle_letters[center_index], puzzle_letters[3] = puzzle_letters[3], puzzle_letters[center_index]

print("puzzle:  {0} {1}\n        {2} {3} {4}\n         {5} {6}".format(*puzzle_letters))

# generate solution words. print with pangrams in caps

solution_words = [word for word in all_words if len(word) > 3 and center_letter in word 

                  and not set(word).difference(seed_word)]

print(len(solution_words), "solution words:", sorted(

    word.upper() if len(set(word)) == 7 else word for word in solution_words))

SPT #5: The endless print

 The blog roars back to life; with a hiss and a clank, suddenly a new Stupid Python Trick appears!

This one's a quickie. Python`s print() function takes an end argument that lets you change what gets printed after the rest of things in that call have been printed. By default, this is a newline. It's common to set this to an empty string to suppress the newline:

print("There is no newline", end="")

But you can do the same by just including what you want to print as the end argument.

print(end="There is no newline")

By my count, that saves us four whole keystrokes: two quotes, a comma, and a space! Are we feeling stupid yet?

Release: AutoRemote Push (Unofficial)

To learn some new stuff and sharpen my JavaScript saw, I've developed my first Firefox add-on. It's called AutoRemote Push (Unofficial) and it's useful for people who want to send links from Firefox to their Android device using João Dias's AutoRemote app.

Install it here

Source code here

SJST #1: Multiline string literals

I've recently been doing some JavaScript programming for the Welcome Screen feature included with some of our products. The Welcome Screen is a QWebView: basically a complete Web browser embedded in the application. The Welcome Screen itself is a mini Web application implemented using HTML, CSS, and JavaScript. So here's Stupid JavaScript Tricks #1, which presents an awful hack to simulate multi-line string literals in JavaScript. As usual, programmer beware.

The more I work with JavaScript, the more I appreciate Python, which, by comparison, is a quite thoughtfully-designed programming language. One of the things that's very convenient about Python is its ability to construct multiple-line string literals using triple quote marks:

haiku = """
Triple quoted strings
Programmer's able helper
When writing poems
"""

If you need to embed HTML, or CSS, or a shell script, or some test data, or really anything else that contains newlines, in your Python code, you can easily see how this would be useful. It's significantly more readable, and more maintainable, than cramming that all into a single line with \n escapes in it, or using a syntax-heavy workaround like defining a list and then joining it.

Python's designers were so thoughtful that they even allow the use of triple single quotes on the off chance that your string literal happens to contain three double quote marks in a row. (Who knows, maybe you've embedded some Python code with multi-line string literals of its own! Which is a bad idea, generally, but hey.)

Now, think of a programming language that is used quite frequently for Web applications, in which you can easily imagine you might find yourself with a need to represent decently-sized snippets of HTML and/or CSS, and try to guess what feature it doesn't have.

That's right. JavaScript does not have decent syntax for multi-line string literals. Well, that's not quite true; ECMAScript 6 (a language standard for JavaScript) allows the definition of template strings using backticks (`). However, the ECMAScript 6 standard is only a couple years old, which means you might not be able to use it depending on what browsers you need to support. In my use case, it isn't supported by the version of WebKit provided by the version of Qt we're using in our applications.

So... skanky hack to the rescue. It turns out that JavaScript can easily convert pretty much any object into some sort of string representation. The string representation of a function is the function's source code. That's pretty handy when debugging, and it'd be nice if we didn't have to use the inspect module with Python to get the same thing (if we're lucky and the function was defined in a source file). But I digress.

By making the body of the function a big-ass comment using the C-style /* ... */ syntax, we can put whatever text we want into it—with line breaks wherever we need them, since line breaks are perfectly legal inside block comments. We can then get that function's text representation, nibble off the JavaScript function boilerplate, and end up with the string we want.

Unfortunately, this will break if the text we want to represent contains */ (which might be a problem with CSS if you ever put comments into your stylesheets, as they use this syntax, and JavaScript doesn't support nesting block comments). Inventing further kludgey workarounds for this is left as an exercise.

Here's how such a "text definition" might look:

var haiku = function() {/*

A horrible hack!
Is this much better than not
Having it at all?

*/}.toString().slice(15, -3).trim();

alert(haiku);

Now, this works... unless you're stuck using the JavaScript version in our Welcome Screen, which doesn't allow method calls on function objects until they've been finalized. The upshot is we can't actually assign the string in a single statement; instead we must do this:

var haiku = function() {/*

A horrible hack!
Is this much better than not
Having it at all?

*/}

haiku = haiku.toString();
haiku = haiku.slice(haiku.indexOf("/*")+2,
        haiku.lastIndexOf("*/")).trim();

alert(haiku);

In this code we actually search for the comment delimiters rather than hard-coding their positions, which is something that bugged me about that initial version. Let's write a function to do it; then we can pass in an anonymous function defined right in the function call. (In Python we'd use it as a decorator using the @ syntax, but then, in Python we wouldn't have this problem to begin with.)

function multi(func) {
    t = func.toString();
    return t.slice(t.indexOf("/*")+2, t.lastIndexOf("*/")).trim();
}

var haiku = multi(function() {/*

So many haiku!
Or is it haikus? Don't care.
The cheese stands alone.

*/})

alert(haiku);

All right. So it's there, and it's stinky, and it works. Should you use it in your Web apps? Probably not. But let's not ever pretend we're all saints. Sometimes, you do what works.

SPT #4: There is no try

"Stupid Python Tricks" explores sexy ways to whip Python features until they beg for mercy. Stupid Python Tricks may well be fifty different shades of gray. Reader discretion is advised.

I've recently been wishing that Python`s set type had a method like add() but which returned a Boolean indicating whether the item being added was already in the set. We could add this behavior to the add() method without fear of breaking much code, since most uses will ignore the return value, but I'd rather keep add() as fast as possible. So let's call this new method added() and have it return True if the item needed to be added, and False otherwise. You can derive a new class from set, so let's go ahead and do that:

class Set(set):
   def added(self, item):
       result = item not in self   # True if item needs to be added
       self.add(item)
       return result

Note our self.added() here is not conditional in any way; it doesn't need to be. set.add() is idempotent: adding the same item multiple times doesn't hurt anything, and it's actually faster to do the add() even if it's not necessary (since that stays in the fast C implementation of the set type) than to try to avoid the unnecessary add() with an if statement.

Our new method is convenient for deduplicating lists while retaining the order of their items:

pies = ["apple", "banana cream", "apple", "boysenberry",
        "apple", "pumpkin", "banana cream"]
seen =  Set()  # keeps track of pies we have already seen
pies[:] = (pie for pie in pies if seen.added(pie))
print(pies)

Result: ["apple", "banana cream", "boysenberry", "pumpkin"]

Be right back; I'm hungry for pie now.

OK. Our added() method works fine. There's nothing wrong with it. But doesn't it seem a little... inelegant... to have to store the result of the set membership test in a local variable, add the new item, and finally return the value we previously squirreled away? Why can't we simply return the result, and then do the add? Because the return ends the function's execution? Don't be silly; we won't let that stop us!

class Set(set):
   def added(self, item):
       try:     return item not in self
       finally: self.add(item)

Not only is this an unconventional use of try, it's also a wee bit slower than our earlier version. And that's why we call it "Stupid Python Tricks."