October 9, 2020 at 8:51 PM by Dr. Drang
A few days ago, I ran across last week’s edition of Matt Parker’s Maths Puzzles. It’s a simple challenge: rearrange the numbers 1–9, inclusive, so that each sequential pair sum to a prime number.
It’s not hard to come up with a solution. After all, the original sequence,
1, 2, 3, 4, 5, 6, 7, 8, 9
has lots of pairs that add to primes, and it takes only a switch of the 5 and 7 to get a sequence that works:
1, 2, 3, 4, 7, 6, 5, 8, 9
What’s more interesting is to come up with all the solutions, and it’s natural to assume that that’s best done by writing a program.
My first thought was to use brute force. Generate all the permutations of the list and go through them, keeping only the ones that meet the prime pairs criterion. Brute force is often the best solution when you need an answer quickly and want a solution that’s easy to explain.
“Quickly” is in the eye of the beholder. A clever algorithm will undoubtedly run much faster, but it may take much longer to work out and debug than the dumb algorithm takes to run. Clever algorithms are essential when a program has to run again and again, but brute force is often the way to go when your program is a one-off.
Looking at every permutation seemed feasible in this case, as there are only 9! = 362,880 ways to arrange the nine numbers. And I wouldn’t have to come up with a way to get all the permutations, because the
itertools library already has a function for that. So I started writing:
python: 1: from itertools import permutations 2: 3: # Initialization 4: numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9] 5: primes = [3, 5, 7, 11, 13, 17] 6: winners =  7: 8: # Loop though the permutations, collecting only prime pairs 9: for p in permutations(numbers): 10: for i in range(1, 9): 11: if p[i-1] + p[i] not in primes: 12: break
At this point, I had to stop and think. The problem is that the
break statement will only break me out of the inner loop, the one that starts on Line 10. But when I run into a pair that don’t add to a prime, I want to move on to the next item in the outer loop, like a
continue statement. Neither
continue have a way to specify how far out to break or where to continue from. Old Fortran habits started to bubble up in my brain, and I began to wish for a
goto statement, but Python doesn’t have one.1
A clumsy solution is to add a flag variable for keeping track of whether you broke out of the inner loop or exited it normally.
python: 1: from itertools import permutations 2: 3: # Initialization 4: numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9] 5: primes = [3, 5, 7, 11, 13, 17] 6: winners =  7: 8: # Loop though the permutations, collecting only prime pairs 9: for p in permutations(numbers): 10: allPrimes = True 11: for i in range(1, 9): 12: if p[i-1] + p[i] not in primes: 13: allPrimes = False 14: break 15: if allPrimes: 16: winners.append(p) 17: 18: # Print the results 19: print(len(winners)) 20: for p in winners: 21: print(p)
I know I’m doing a brute force solution, but I have some pride and didn’t like the way this looked.
A few years ago Ned Batchelder wrote a post about breaking out of two loops, and here’s what he had to say about this method:
Use boolean variables to note that the loop is done, and check the variable in the outer loop to execute a second break. This is a low-tech solution, and may be right for some cases, but is mostly just extra noise and bookkeeping.
In this case, we’re not really breaking out of two loops, but the idea is the same: extra noise and bookkeeping.
Batchelder’s suggestion is to use a function to handle the inner loop and simplify the outer loop. Like this:
python: 1: from itertools import permutations 2: 3: # Initialization 4: numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9] 5: primes = [3, 5, 7, 11, 13, 17] 6: winners =  7: 8: def primePairs(s): 9: '''Do all the pairs in s sum to a prime?''' 10: for i in range(1, 9): 11: if s[i-1] + s[i] not in primes: 12: return False 13: return True 14: 15: # Loop though the permutations, collecting only prime pairs 16: for p in permutations(numbers): 17: if primePairs(p): 18: winners.append(p) 19: 20: # Print the results 21: print(len(winners)) 22: for p in winners: 23: print(p)
This is slightly longer but is definitely easier to understand. We’ve applied some good old-fashioned structured programming ideas to put the sequence checker into its own function. It’s clear what it does, and by isolating it, we’ve also made the main loop, Lines 16–18, clearer.
But Python has another trick up its sleeve. In the clumsy solution, we used a flag variable,
allPrimes, to keep track of whether we exited the loop normally or by
breaking out. But Python already has a way to do that: the
else clause of a
for loop. Here’s what the docs say:
Loop statements may have an
elseclause; it is executed when the loop terminates through exhaustion of the iterable (with
for) or when the condition becomes false (with
while), but not when the loop is terminated by a
I confess I’ve never used this before, but it’s really simple:
python: 1: from itertools import permutations 2: 3: # Initialization 4: numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9] 5: primes = [3, 5, 7, 11, 13, 17] 6: winners =  7: 8: # Loop though the permutations, collecting only prime pairs 9: for p in permutations(numbers): 10: for i in range(1, 9): 11: if p[i-1] + p[i] not in primes: 12: break 13: else: 14: winners.append(p) 15: 16: # Print the results 17: print(len(winners)) 18: for p in winners: 19: print(p)
If we get to the end of the inner
for loop without breaking, the
winners.append(p) statement in the
else clause is executed. If we run into a non-prime sum in Line 11, the
break in Line 12 breaks us out of the entire
for/else construct and we move on to the next permutation in the outer loop.
I’m not sure whether I prefer the function solution or this one. My natural tendency is to go with the shorter code, but
else doesn’t strike me as the right word to describe what this code is doing. In fact, my first instinct is to think that the
else clause is invoked when the loop doesn’t complete normally, which is the exact opposite of how it behaves.
Whether I ever write code with a
for/else again, it’s good to know it exists and how to use it.
And if you were wondering, there are 140 ways to reorder the list to get all the sequential pairs to sum to a prime number. You could argue that there are really only 70, with the other 70 being the same sequences in reverse. I won’t take sides; I was just here to hone my Python skills.
There are at least a couple of third-party libraries that provide
goto, but I didn’t want to resort to them. ↩
October 5, 2020 at 11:07 PM by Dr. Drang
The recent death of Bob Gibson got me thinking about his pitching duels with Fergie Jenkins. In my imagination, they were matched up every time the Cubs and Cardinals played each other, but the rational part of my brain tells me that can’t be so. So I decided to look it up.
My data source was Retrosheet, which has records of games going back to 1871. I downloaded the years Gibson and Jenkins overlapped, 1965–1975, concatenated those eleven CSV files, and extracted—via Pandas—the games in which the two started against each other.
Here are the results. Only nine games, which is a bit short of my imagination, but the quality of those games is pretty much what I remembered. If you want a short summary of how the game was different back in the late 60s and early 70s—especially with regard to pitching—you couldn’t do much better than this table.
To start with, they both figured in the decision in eight of the nine games.1 In seven of the games, the winning pitcher went the distance; in six of the games, both pitchers went the distance. And why not? Look at those scores.
Even better, look at how short the games were. Except for the two that got out of control,2 these games were only about two hours long. And those last two games in 1971 and 1972: both under two hours and one of them went ten innings! Even so, everyone who bought a ticket got their money’s worth.
And I have to say I’m delighted to see that Fergie won five of those decisions. There’s nothing better than picturing the anger of Cardinal fans after those games. ↩
I didn’t want to put too much information in the table, but I can tell you that both teams used four pitchers in the 1967 game, and the Cubs used six and the Cardinals three in the August 4, 1968, game (which also went 13 innings, so 3½ hours isn’t out of bounds). ↩
October 5, 2020 at 10:51 AM by Dr. Drang
So, it turns out™︎ yesterday’s widget/shortcut/script for generating passwords needed more testing. Every individual component worked, and they worked together well on a single device, but as I learned last night, they didn’t work when shifting from one device to another.
Here’s the problem. Let’s say I’m on my iPhone and I generate a password by tapping the button in the Shortcuts widget. It works fine. Later, I’m on my iPad and I try to generate a password the same way. I tap the button, and it gives me this error:
To fix this error and get the shortcut to run on the iPad, I have to open the New Password shortcut,
and reselect the script that Pyto runs. Yes, I know it says it’s going to run the script
pw.py, and that’s the script I want it to run, but for some reason Pyto doesn’t believe it, and I have to select
pw.py again as the script to run. Now the shortcut works perfectly on my iPad and will continue to do so.
But—and you know where this is going, right?—now the shortcut won’t run on my iPhone until I go into Shortcuts and reselect
pw.py on that device. And after I’ve done that, the shortcut won’t run on the iPad. And so on, ping-ponging back and forth. For some reason, the Run Script action for Pyto doesn’t know that the
pw.py on the iPhone is the same
pw.py that’s on the iPad. Even though they’re the same file, synced through iCloud.
I made a note to send a bug report to Pyto about this, but in the meantime, I wanted a shortcut that works.
The first step was to change the Run Script action to Run Code. This allowed me to keep the Python source code in the shortcut itself, which eliminated the
Then I needed to change how the script accessed the list of words. Recall that originally,
pw.py read a file called
words.py that was saved in the same directory as
pw.py itself. The code for that was simple:
python: with open('words.py') as f: words = f.readlines()
But apparently the change from Run Script to Run Code changed the environment under which the code runs, so
open('words.py') didn’t work anymore. I needed a more robust way to refer to the file of words.
The solution was bookmarks, which work in Pyto more or less the same way they work in Scriptable: you establish a bookmark to a file saved anywhere in iCloud Drive, and from that point on you can refer to that file through the bookmark. Establishing the bookmark is done through user interaction, which satisfies iOS’s privacy concerns, and Pyto then keeps track of the file and handles the permissions.
By switching to bookmarks, I eliminated the need to keep
words.py in the same directory as the
pw.py script. Thinking that I could use bookmarks for other scripts that access data files, I created a
common-data folder in my iCloud Drive root directory and put the
word.py file there. And I changed its name to
words.txt, which is what it should have been in the first place.
pw.py is now this:
python: 1: from secrets import choice, randbelow 2: import pasteboard 3: import bookmarks 4: 5: # Get the list of words 4-6 characters long. 6: wordPath = bookmarks.FileBookmark('words46').path 7: with open(wordPath) as f: 8: words = f.readlines() 9: 10: # Select 4 words from the list. 11: pwords = [ choice(words).strip() for i in range(4) ] 12: 13: # Add a numeral and a "special" character. 14: # Capitalize one of the words. 15: numeral = str(randbelow(10)) 16: special = choice('!@#$%^&*') 17: pNum = randbelow(4) 18: pSpec = randbelow(4) 19: pCap = randbelow(4) 20: pwords[pNum] = pwords[pNum] + numeral 21: pwords[pSpec] = pwords[pSpec] + special 22: pwords[pCap] = pwords[pCap].capitalize() 23: 24: # Assemble the password and put it on the clipboard. 25: pw = '-'.join(pwords) 26: pasteboard.set_string(pw)
The only difference is the bookmarks stuff in Lines 6–8.
I had to first run this from within Pyto to create the bookmark. When it hit Line 6, the file picker appeared, and I was asked to select the file that will be given the
words46 bookmark. I navigated through iCloud Drive to select the
words.txt file. From that point on, Pyto knows what
words46 is and won’t ask me again. Well, it won’t ask me on that device. Apparently bookmarks don’t sync—which is probably right from a security point of view—so I had run
pw.py on each device to establish the bookmark everywhere.
With that done, I copied the new source code for
pw.py and pasted it into the Run Code action of the shortcut. Now I have a shortcut and a widget button that works on all my devices and doesn’t get confused anymore.
October 4, 2020 at 10:36 AM by Dr. Drang
When I switched from 1Password to Apple’s built-in password manager, I had concerns about the reliability of Apple’s system, but overall I’ve been pleased with how things have worked out. There’s just one problem I’ve run into. It doesn’t show up often, but the annoyance it causes when it does show up has led me to build a workaround.
When you need a new password, iOS offers to create one for you.
This notice appears when you put the cursor in a password field, and the field itself gets highlighted with part of the strong password iOS made.
If all goes well, your new login works and all the details are saved in your iCloud Keychain for later use. But sometimes the website’s logic and Apple’s don’t mesh, and your new credentials aren’t saved. Now you have an account for which you don’t know the password. Lovely.
The obvious solution would be to copy the iOS-created password to the clipboard before tapping the button that creates the new account. That way, if iCloud Keychain doesn’t save the new credentials, you can add them directly. Unfortunately, iOS doesn’t allow you to copy the password field when the strong password it created is in there. So you have to go the “I forgot my password” route with the website to get a new new password to replace the old new password you just created a few seconds ago. I always feel like the website is judging me when I have to do this.
Presumably, Apple refuses to let you copy the password it just made because there’s a security risk to having a password on the clipboard. But there’s also a security risk to having a password manager that doesn’t save your password.
To get around this problem, I wrote a script to generate passwords for me using a variant of the Diceware method. It was written in Pythonista, and used lists of words that I’d gathered for my Countdown anagram script. It did a good job of generating passwords, but because Pythonista doesn’t work well with Shortcuts, it was clumsy to use.
Enter Pyto, an iOS Python app that does work well with Shortcuts, and iOS 14 widgets, which make it easier than ever to run Shortcuts without digging into the Shortcuts app itself.
Now I have a medium-sized Shortcuts widget with four shortcuts.
Tapping the New Password button puts a new password on my clipboard. I can then paste this into the password field on the website where I’m creating a new account. If the credentials get saved to iCloud Keychain, great. If the credentials don’t get saved to iCloud Keychain, the password is still there on my clipboard, and I can use it to add a new login manually to the Passwords section of Settings. Either way, I then copy something else to the clipboard to overwrite the password.
The New Password shortcut is just a call to run a Pyto script:
(The comment is there mainly to force Shortcuts to use the icon I chose. I’ve noticed that single-step shortcuts often get displayed with the icon of the step rather than the icon of the shortcut itself. Before I added the comment, the widget button for this shortcut was shown with the Pyto icon instead of the key icon.)
The Pyto script is pretty simple:
python: 1: from secrets import choice, randbelow 2: import pasteboard 3: 4: # Get a list of words that are 4-6 characters long. 5: with open('words.py') as f: 6: words = f.readlines() 7: 8: # Select 4 words from the list. 9: pwords = [ choice(words).strip() for i in range(4) ] 10: 11: # Add a numeral and a "special" character. 12: # Capitalize one of the words. 13: numeral = str(randbelow(10)) 14: special = choice('!@#$%^&*') 15: pNum = randbelow(4) 16: pSpec = randbelow(4) 17: pCap = randbelow(4) 18: pwords[pNum] = pwords[pNum] + numeral 19: pwords[pSpec] = pwords[pSpec] + special 20: pwords[pCap] = pwords[pCap].capitalize() 21: 22: # Assemble the password and put it on the clipboard. 23: pw = '-'.join(pwords) 24: pasteboard.set_string(pw)
Note first that this script uses the relatively new
secrets module instead of
random to generate random numbers. The
secrets module was built specifically to use in cryptographic applications like this.
words.py file that’s opened and read in Lines 5–6 is a text file consisting of about 28,000 words that are 4–6 letters long, one per line. It’s not a Python source code file, but I had to give it a
.py extension to save it in Pyto’s Documents directory along with the scripts. Pyto really should be less strict about what file types can be saved there.
Line 9 selects four words from the list. Lines 13, 15, and 18 add a numeral to the end of one of the words. Lines 14, 16, and 19 add a “special” character to one of the words. Lines 17 and 20 capitalize one of the words. The additions and capitalization are done because some websites won’t accept passwords without them.
Finally, Line 23 puts the words together with hyphens and Line 24 copies the result to the clipboard. Here’s an example of the kind of password it generates:
You can tell that the word list I used is based on a Scrabble-type dictionary and not a common-words dictionary. I keep my conure’s cage behind a rideau in the tawery.
With this widget on my iPhone and iPads, I can avoid the occasional hiccups of iCloud Keychain without digging through lists of shortcuts or scripts. A good password is always just one tap away.
Update Oct 5, 2020 10:52 AM
I needed to make a couple of changes to get this working consistently across all my devices.