Car Talk Puzzler #1: The Bank Temperature Sign
One of my favorite podcasts is NPR’s Car Talk, and one of my favorite segments of the show is the weekly puzzler, in which listeners have a week to solve a puzzle that is usually automotive in nature. It struck me that this would be an ideal way to illustrate some beginning programming techniques, while also illustrating some real world problem solving uses of programming. Initially I will be posting solutions in Python, but I will probably show how to do them in other ways as well.
PREVIOUS PUZZLER: Stevie and His Moto
Stevie’s riding his motorcycle to work when he sees a big sign displaying the temperature in Fahrenheit and in centigrade. The digits are exactly reversed. He notices the same thing on the way home. What were the temperatures?
This is an ideal choice for a programming solution because it can be brute forced; a computer can try all possible solutions near instantaneously, something they are very good at. Not all of the puzzlers are so conducive to a programmatic solution.
For those who already know the basics of programming, I’ll post my program first. Afterwards I post explanations more geared towards beginners, but there still is something that more advanced programmers might not know in Python.
Here’s my solution:
def fahrenheitToCelsius(temp): return (temp - 32) / 1.8 def reverseString(s): # Step size is -1, so start at the end and work backwards return s[::-1] # Presumably it was above freezing if it's a spring day LOW_TEMP_FAHRENHEIT = 32 # Presumably it was below 100 degrees HIGH_TEMP_FAHRENHEIT = 100 def main(): for temp in range(LOW_TEMP_FAHRENHEIT, HIGH_TEMP_FAHRENHEIT): # Round the float to nearest whole number, cast to integer celsius = int(round(fahrenheitToCelsius(temp))) # Convert the integers to strings so as to be able to reverse the digits fahrenheitString = str(temp) celsiusString = str(celsius) # See if the reversed digits match if fahrenheitString == reverseString(celsiusString): print temp, celsius if __name__ == '__main__': main()
python Temperature.py 61 16 82 28
Tada! The program calculated the correct solution.
Let’s break the problem into a few logical steps:
1) Convert a Fahrenheit temperature to Celsius (we’re going to be able to do this in order to determine what the temperature on the signs must have been)
2) Round a number to the nearest whole number (converting Fahrenheit to Celsius will often leave a fractional part, but most signs don’t display temperature in increments smaller than 1 degree)
3) Reverse the digits of a number (in order to tell whether the temperatures are the reverse of each other)
4) Test a whole bunch of Fahrenheit temperatures to discover the matching Celsius ones, using steps 1 – 3.
Let’s explain each part in order.
Convert Fahrenheit to Celsius
The first part is the most straightforward:
def fahrenheitToCelsius(temp): return (temp - 32) / 1.8
There’s not a lot to say about this part; this is the formula to convert from Fahrenheit to Celsius. If you’re new to Python or programming as a whole, this whole block is known as a method declaration; basically methods take in data, do some calculation with the data, and more often than not, return a new piece of data. In our case, we are passing in the temperature in Fahrenheit, and what comes out of it is a temperature in Celsius. Just to show that this indeed works:
Python 2.6.4 (r264:75708, Oct 26 2009, 08:23:19) [MSC v.1500 32 bit (Intel)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> def fahrenheitToCelsius(temp): ... return (temp - 32) / 1.8 ... >>> fahrenheitToCelsius(212) 100.0 >>> fahrenheitToCelsius(32)
Round a number to nearest whole number
OK, how about rounding a fractional number to the nearest whole number?
Python has a function called, easily enough, round which does exactly that. You choose how many decimal places you want; by default it rounds to 0 (i.e. the nearest whole number)
>>> round (2.252, 2) 2.25 >>> round (2.252 ) 2.0
Notice how even though we round to 0 decimal places, the answer is “2.0”. This is because round returns a double rather than an integer. Integers are what we would think of as “whole numbers” – -1023, 2035, 733, etc. etc. Doubles are an (inexact) representation of a number with a fractional part. It’s a little beyond the scope of this tutorial, but suffice to say there are numbers that a computer cannot represent exactly
>>> round (2.1, 1) 2.1000000000000001
The reason I make the distinction is that we want to treat our numbers as integers; after all we’re rounding them to 0 decimal places, so they are in fact integers. We need the computer to treat them that way. We do this with the int() method
>>> round(2.23501) 2.0 >>> int(2.0) 2
Note too that we can combine these two expressions into one; you’ll often see computer programs written this way, as it allows us to express thoughts more concisely. So the above could be replaced by
>>> int(round(2.23501)) 2
This expression can be read as “after rounding the number to 0 decimal places, convert it to an integer”.
Reverse the digits of a number
How do we reverse the digits of a number? Well, first, we’re going to treat the number as if it were an arbitrary string of letters (characters) rather than numbers. We are going to cast the integer into a string. Strings are a programming concept used to express textual information; they are usually enclosed in quotes.
>>> "hello" 'hello'
The string representation of a number is different than the number itself. For instance, when two strings are “added” together, they become joined (concatenated). When two numbers are added together, they are added in the mathematical sense. For instance
>>> "2" + "2" '22' >>> 2 + 2 4
We are going to treat the numbers as strings because it is fairly easy to reverse the characters of a string, but hard to do so for a number. With a string, you can access each individual character; you cannot (easily) do that with a number. To understand how to reverse the characters of a string, you need to understand a bit about iterating over collections in Python, as well as a concept known as “slice”.
Let’s start with the basic Python data structure known as a list. You can put a heterogenous (mixed) set of objects into a list:
a = [2,3,5,6,"hello","world"]
In this case we’ve put a bunch of numbers, and then two strings into the list data structure. We can get out each element in the list by ‘indexing into’ the array. Unlike in the normal world, in Python you must count starting at 0. So instead of counting 1,2,3,…, you count 0,1,2,… . In other words, if we want to get out the first item we put into the list (the 2), we have to ask for the element at position 0.
>>> a 2
The number within brackets is the index of the element you are accessing from the list.
Now, what if we want the first 3 elements of the list instead of just the first one? To do that, we need to use what’s known as a “slice” in Python. The syntax is [startIndex:endIndex+1]. In other words, if we want the first three elements, those at position 0, 1, and 2, we would ask for
>>> a[0:3] [2, 3, 5]
This can be read as, “start at the element with index 0 and stop before you get to the element with index 3”. Yes, this is a little counter-intuitive – but just stick with me.
What if you want all of the items after a certain point? For instance, I want all the elements including and after the 2nd element. To do that, you omit the second number, but keep the colon. This is saying “start and keep going till you reach the end of the collection”
>>> a[1:] [3, 5, 6, 'hello', 'world']
You can also omit the first number, in which case it is assumed that you want to start at the beginning of the collection
>>> a[:5] [2, 3, 5, 6, 'hello'] >>> a[0:5] [2, 3, 5, 6, 'hello']
What happens if we omit both numbers?
>>> a[:] [2, 3, 5, 6, 'hello', 'world'] >>> a [2, 3, 5, 6, 'hello', 'world']
We get back all the items of the original list! This makes sense if you think about it; we assume we’re starting at the beginning, and we assume we’re ending at the end. Why do I bring this up? Because there’s one last element you can add to take a new slice out of array: the stride argument.
Whereas we’ve been taking some contiguous subset of the list, there’s nothing preventing us from skipping more than one number between every element, in effect taking every second, or every nth number.
>>> a[::2] [2, 5, 'hello']
Interestingly, this number doesn’t have to be positive either; if it’s negative it means we start at the end of the collection and work our way towards the front of the list:
>>> a[::-2] ['world', 6, 3]
Putting this all together then, one way to get the reverse of a list is to take a new slice out of it, taking the whole thing but backwards:
>>> a[::-1] ['world', 'hello', 6, 5, 3, 2]
(More advanced readers: an alternate way, and arguably easier, is to use a list comprehension and the reversed method:
>>> [i for i in reversed(a)] ['world', 'hello', 6, 5, 3, 2]
Hopefully you understand how to take slices out of a list now; you can read a whole lot more about slices at any number of sites, including this great introduction to Python.
But why did I start talking about lists? Weren’t we trying to reverse a string, not a list? Well, it turns out you can view a string as a list of individual letters (characters), and treat it exactly the same as we did for lists, including indexing and slicing.
>>> "hello" 'h' >>> "hello"[:3] 'hel' >>> "hello"[::-1] 'olleh'
So, the method for reversing a string (or really any subscriptable object, but that’s another issue) is
def reverseString(s): # Step size is -1, so start at the end and work backwards return s[::-1]
The only thing left to say in this regard is that if we want to convert a number to a string, this is accomplished by the str() method.
Iterate over a range of numbers
We want to test a whole range of temperatures, looking for those that yield the properties desired in the puzzle. Fortunately there is an easy way to generate a list of numbers in a given range in Python: the range command.
</div> >>> range(5) [0, 1, 2, 3, 4] >>> range(5,10) [5, 6, 7, 8, 9] <div>
>>> for x in range(5): ... print x ... 0 1 2 3 4
for temp in range(LOW_TEMP_FAHRENHEIT, HIGH_TEMP_FAHRENHEIT):
Where LOW_TEMP_FAHRENHEIT and HIGH_TEMP_FARENHEIT are two constants defined to limit the range of numbers we are looking at.
I’ve illustrated a brute-force solution to a recent puzzler. Despite being a fairly simple challenge, it illustrates some important features of Python, including range generation, list comprehension, slicing to reverse selections, and converting between different data types.
I’d love to see some other solutions to this problem, so post in the comments if you have ideas.