When True Was True When It Should Have Been False

(or Why The Devil Is In The Details)

Another 'whoops' moment in class today - another little lesson learned by the teacher: always read the documentation carefully.

In this case, my students had been given the problem of how to 'clean up' a list in Python so that it contained only integers or floats – any strings, tuples, booleans, etc. would need to be removed.

A simple enough task - simply loop over the list and check the type of each item. But here's where the documentation (or more precisely, a cursory read of it) lead us astray.

The Python docs say this about the inbuilt type() function:

type(object)

Return the type of an object. The return value is a type object. The isinstance() built-in function is recommended for testing the type of an object.

So we should use isinstance()? Okay, let's look at that then:

isinstance(object, classinfo)

Return true if the object argument is an instance of the classinfo argument, or of a (direct or indirect) subclass thereof.

So, we can do something like isinstance(i, (int, float)) to check the if the type of i is an integer or float.

And all seemed well right up to the point when this list:

[3, 4.5, "word", True, (3, 5)]

should have been reduced to:

[3, 4.5]

but instead became:

[3, 4.5, True]

Wha...? How did that boolean slip through?

Back to the documentation:

isinstance(object, classinfo)

Return true if the object argument is an instance of the classinfo argument, or of a (direct or indirect) subclass thereof. 

When we look at the documentation on numeric data types, we find this:

There are four distinct numeric types: plain integers, long integers, floating point numbers, and complex numbers. In addition, Booleans are a subtype of plain integers.

So this:

isinstance(True, int)

returns True rather than False.

I can see some good reasons why booleans have been defined as a subtype of integers (and it's not only Python where this is the case), but it caught us offguard all the same.

So the point of today's lesson - read the documentation carefully, make sure you get your head around the finer details. Not the point I had planned to make, but maybe a better lesson as a result.

The Pluses Problem

On his blog, Rational Mathematics Education, Michael Goldenberg mentions this problem by way of one Maria Miller (her blog here.)

How many addition signs should be put between digits of the number 987654321 and where should we put them to get a total of 99?

Michael finished his blog entry with "It would also be great if anyone has other extension ideas for this ... The one I'd suggest right away is: What happens if we change 99 to other values?"

This got me thinking along a slightly different line - what other totals have multiple solutions and could I write a program to find them?

It turns out that there are 209 possible totals (including 987654321), of which 31 can be formed in more than one way. Four totals (153, 171, 180, 189) can be formed in four different ways, seven totals can be formed in three different ways, and the rest in two different ways.

The program to find this is conceptually quite simple... if you can get your head around recursion.

The logic: for a given number, take the first n digits (where n is progressively a number from 1 to the total number of digits), convert to a single value, then with the remainder, do the same thing again.

Programming this in Python ended up being simple, but not before I went down a few blind alleys:

def Chunkit(x,p=[]):
for i in range(len(x)):
   p.append(int(x[:i+1]))
   if i == len(x)-1:
       print p, sum(p)
       print
   else:
       Chunkit(x[i+1:])
   p.pop()
return p

num = raw_input("Enter a number: ")
Chunkit(str(num))

The sticking point was line 9:

p.pop()

At first, it's not obvious why this is necessary, but if you leave it out (as I initially did), you soon see the consequences.

With the program written and working correctly (with a few additions to produce the list of totals and how often they occur), exploring the original problem led to the results given above. It also allowed me to examine different number sequences, such as 123456789, which can be made to total 99 three different ways rather than two. (And totals of 153 and 162 can be made five different ways.) Or 123454321, which can be made to total 97 in eight different ways.

Of course, having posted here what I think is a fairly neat solution (only 13 lines of code), no doubt some script-kiddy will pop up with a four line solution in Ruby or OCaml or whatever is the trendy language this week. But at least I now have another interesting problem to discuss with my students.