An efficient XKCD Password

OK, this will be the last installment on passwords, then we will move on to other interesting stuff. The thing that bothers me about the long passwords is that they can be very cumbersome to type. If there are too many characters that need to be typed with my left hand or my right hand I feel like that really slows me down. I like to have a password that I can type rapidly and that means that more often than not, the letters should alternate from being typed with my left hand to my right hand.

So, how can we write a program that quantifies this notion that the letters of the word alternate from hand to hand? First we will have to make an assumption that we are using the standard QWERTY keyboard. Then we can make two strings that represent the characters typed by the left hand and the characters typed by the right hand:

leftHand = "asdfgzxcvbqwert"
rightHand = "lkjhpoiuymn"

Lets look at a program that calculates the score for a word referenced by a variable named word.

In the code above we want to look at pairs of letters. The letter at index position i and hte letter at index position i+1. In order to do this we can not use a for loop of the type for ch in word because in this pattern ch is a character not a numeric index. the for loop: for i in range(len(word)-1) is a good choice because i is a numeric index. You should also notice that the value of i ranges from 0 to one less than the length, which allows for i+1 to index the last character of the word without going past the end of the word.

The if/elif block asks the important question is the letter at position i in the left hand AND is the letter at i+1 in the right hand. If so we’ll increase our score counter by 1 to indicate that we have found a pair of letters that alternates between hands. The elif clause is necessary because there are two ways a pair of letters might alternate left-right or right-left.

Now, you can play around with the example above, and modify it to use different words, but this is really a case where a function is called for.

Notice that the code has not really changed exept that we have encapsulated our algorithm inside a function definition, and added a return statement at the end. Now we can use the altscore function to calculate a score any word in our wordlist. Lets use the score function and something called list comprehensions to create four lists of words, four, five, six, and seven letter words. Further, we will limit the words we keep to those that have a score of .7 or better.

First, we will do this the long way around and then show the beauty and elegance of a list comprehension.

fours = []
for word in wordlist:
   if len(word) == 4 and altscore(word) >= 0.7:
      fours.append(word)

The above code should be pretty clear and easy to understand. But this pattern, we might say of ‘filtering’ one list to create a new list is so common that we can elegantly capture this pattern in a single line using a list comprehension.

Lets put all the pieces together now to create an xkcd password that is fast to type, and less than 20 characters in length.

Lets look at makePassword in a bit more detail. We are using a pattern called ‘trial and error’ or sometimes called ‘guess and check.’ That is, we’ll generate a password and then we’ll test it to see if it meets our criteria, in this case we want the length to be more than 10 and less than or equal to 12 characters. If our password meets these criteria we are done. If the password is too long or too short we’ll try again. People use trial and error all the time, but often computer programmers forget about this as a perfectly good solution for a program, preferring to write a program that will get the right answer the first time everytime. Nevertheless this is a the guess and check approach is usually simpler if you are willing to let the program try a bunch of wrong answers. If the odds are against finding a solution then you could get unlucky and your program could run for a a very long time.

The while not done while statement is a common way to say keep doing this loop until some the variable done is set to True Its very important to have some kind of condition that sets the done variable inside the loop or else your program may never finish.

This concludes our exploration of generating a password. And is the last entry for January. I’ll be back next month with more fun problems.

Next Section - Its Only a Little Math