creslmdab rdwso ucks

 

I still recall vividly how my least favorite type of homework assignment in the third grade (to be sure, I disliked all homework assignments in third grade) was when we would be given a sheet with a long list of scrambled words that the student had to unscramble. I didn't see the point in it. It seemed to be just so much busywork, a way to prevent us from frittering away too much of our afternoons watching cartoons or replicating Evel Knievel's latest stunt on our bicycles using crude jump ramps made from plywood and two-by-fours. What it didn't seem like was something with any intrinsic pedagogical value.

When my daughter was in third grade, she came to me with a homework assignment that she was struggling with. I looked at the sheet she handed me and saw to my horror that nothing had changed in thirty years. Third grade teachers still loved assigning long lists of scrambled words to unscramble, and I still had a hard time discerning the pedagogical value of it all.

It was one of those moments of dialectical tension that every parent faces. Nobody enjoys seeing their children struggle, but it's also a parent's responsibility to teach a certain amount of self reliance. The nature of the assignment didn't make things any easier. If your kid is having a hard time with a math assignment, you can walk through the technique to solve the problem one step at a time. If it's a history assignment your kid's not sure about, you can hop online or take a ride to the library and consult historical sources. If your kid needs to know the definition of habeas corpus for civics class, you can refer them to Homeland Security Secretary Kristi Noem for her expertise. Scrambled words are different. There's no established step-by-step technique, no authoritative source to consult. Either the word magically pops into your head after staring at the scrambled word for a while, or enough time spent staring goes by that you throw in the towel. If it's your kid who's thrown in the towel, it's awfully hard to find where the line is between trying to be helpful and taking away the opportunity for her to finish the assignment on her own. And after all those years, I didn't find scrambled words to be any less repugnant than I did when I was in school, so even if I hadn't been feeling any misgivings about helping, I still wasn't exactly looking forward to it. Then, in a moment of inspiration, I stumbled onto an idea, one that had its own unique educational value and one that could very well make scrambled word homework assignments obsolete once and for all.

I spent the first half of my adult working life in the printing industry doing prepress work, assembling copy and images into film—and later PDFs optimized for print production—that were used to make the plates that would go on the presses. From the mid 2000s through the early 2010s, the prepress side of the printing industry underwent an automation revolution. As I've written about, more than once, I was fortunate enough to make a mid-career transition to being one of the people doing the automating, which is considerably more fun than being one of the people put out of a job by automation. My daughter's third grade year coincided with the early days of that career transition. 

As an exercise, I decided to try to write a program that would unscramble scrambled words. The approach was a very simple, brute-force solution to the problem. The program allowed the user to enter a scrambled word, then it calculated all possible permutations of the letters of that word and ran each permutation through a spell checker. Those permutations that passed spell check were displayed as candidate solutions. The program worked, but it had a couple quirks.

For one thing, the candidate list would display a number of nonsense words along with the solution. This has to do with how spell checkers worked at the time¹. Spell checkers would use a hash function to calculate a hash of the word to be checked, and then compare that hash value to a dictionary of known hash values of English² words. A hash function is a function that takes a word or other data as input, and returns a single integer as output. Hash functions are very useful for computing, and are used for everything from speeding up searches to securely storing passwords. There is one limitation to hash functions, however. The number of available hash values is finite and limited by the computer's architecture and the way the programming language being used implements the integer type. For a spell checker, this means that there are more possible permutations of twenty-six letters than there are available hash values. It's possible, for example, that a particular hash function might give the same value to iabastol as to bicycle. The computer doesn't know that iabastol isn't a word. The computer doesn't think that you really entered bicycle. The computer doesn't realize that iabastol is just a failed attempt to unscramble oslbiata to sailboat. The computer doesn't care; it only knows that it has a valid hash value, and so it considers iabastol to be a correctly spelled word. In computer science parlance, this is a hash collision. In the real world, hash collisions are extremely rare, and users can type words all day long without worrying about the spell checker giving them a false negative because of a hash collision. My program, on the other hand, was a long ways away from the intended use case for a spell checker. By flooding the spell checker with millions (sometimes even billions, more on that later) of permutations of letters, we were bound to run into a few hash collisions.

Another quirk we noticed had to do with performance. Words of up to eight letters could be unscrambled in milliseconds, imperceptibly fast for the user. A nine-letter word would take a second or so. A ten-letter word would take a distinctly noticeable number of seconds and an eleven-letter word would take a couple minutes. We never saw a solution to a twelve-letter word or bigger; the time taken to compute was impractical if not intractable. What was happening? The number of possible permutations of a collection of letters scales with the factorial of the number of letters. Factorial scaling starts out slow, but then it balloons out of control quickly, and is something to be avoided in programming. Fortunately, the assignment was made up entirely words whose length fell within the program's performance limitations.

While it might feel a bit like cheating to use a computer program to finish a homework assignment, I didn't see it that way at all and I still don't see it that way. My daughter and I were together every step of the way as we specced out and then implemented the program. We learned how to precisely describe a problem and a set of step-by-step instructions to solve the problem. We learned about permutations. We learned what a hash function is, and what a hash collision is. We learned first-hand about factorial time complexity. In short, we got more educational value out of that one little homework assignment than any third grade teacher could have dreamed of.

About a year later (in response to a fourth-grade scrambled words assignment, if memory serves) I implemented a much more elegant solution that didn't suffer from the same time complexity or nonsense words. As I was researching this article, I found that there are now a number of online word unscramblers. Preventing their use on homework assignments would be impossible. The W6KSR nest has been empty for nearly a decade, and anyone who currently has school-age children is welcome to let us know in the comments what's currently going on, but I'm going to take an educated guess that scrambled word homework assignments are a thing of the past. You're welcome. 

1. I tried it out as part of my research for writing this article; spell checkers have gotten much more sophisticated in the last twenty years.

2. Or whatever language the program is localized to