Next post Previous post

Interrupted loops

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 break nor 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 else clause; 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 break statement.

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.

  1. There are at least a couple of third-party libraries that provide goto, but I didn’t want to resort to them. ↩

Next post Previous post