Happy Pi Day, everyone! (3/14, get it?) I got back from PyCon last night and have been trying to figure out how to integrate the energy and direction from the conference into my regular life here in Boston. It’s a challenge, but PyCon is always an invigorating experience, and I’m really glad to have gone.
In honor of Pi Day, I’ll present you with two puzzles I heard at PyCon, one as part of Google’s recruiting efforts, and one as part of a panel about Python in middle school.
Google’s puzzle: A number is a palindrome if the digits read the same backwards as forwards: 1, 88, 343, 234565432, and so on. What is the sum of the digits in the number of palindromes less than a googol (10100)? That is, count all the palindromes greater than zero and less than a googol, then sum all the digits in that number, not the sum of the digits in all the palindromes. What’s your answer? They actually posed it as “write a program to compute the sum of the digits, etc,” and were interested in the shortest program, but I prefer it as a pure math question.
The education question was a puzzle presented to middle-school kids, who were asked to write programs to find the answer. Imagine a set of stairs with n steps from bottom to top. You can walk up the stairs by taking every step, or by skipping a single step any time you want. You can’t skip more than one step at a time. How many different ways are there to walk up a flight of n steps? For example, representing a step as t and a skip as k, you could do a flight of 3 steps as ttt, tk, kt, and 4 steps could be tttt, ttk, tkt, ktt, or kk.
Update: I posted my solutions.