A few times in the past months, someone's commented that they have no idea what
it's like to write a computer program, so I've been thinking about a sort of gentle
introduction to the fun ("joy" seems a bit overstated) of programming. Then it
happened—the puzzler from Car Talk was announced, and I thought it was perfect.
So in the next 45 minutes I want to write a program to solve last week's puzzler. It goes more or less like this:
Imagine a very long hall with 20,000 lights hanging from the ceiling, all off.
These lights are controlled by a pull-chain: pull it once, the light turns on; pull it
again and the light turns off.
Now someone comes through the hall and pulls every single chain. The lights are now
all on.
Person #2 comes through and pulls every 2nd chain, so that now lights 2, 4, 6, 8
and so on are now off. Person #3 comes through and pulls every 3rd chain,
thus changing the state of lights 3, 6, 9, 12 and so on; they turn some lights on and some off.
Person #4 comes through and flips lights 4, 8, 12, 16 and so on.
And so on, until person #20,000 comes through and only tugs on the chain of the 20,000th light.
Can you predict which lights will be on, and which will be off?
We'll use the programming language Python here. I briefly considered using something
like Ruby or OCaml, so we could go through the experience of learning a new programming
language together, but I'm long-winded enough that...
Right. So Python. Here's what we're going to do: We'll create a list representing
the state of each light fixture. And rather than forcing the program to do exactly 20,000
hanging lights, we'll provide a parameter to say how many lights there are.
The pattern will be obvious with as few as 100 lights, so let's start with that. Here's a
first partial whack at it.
# Adjust the following line to be however many lights you want
howevermanylights = 38
# "light_states" represents the states of howevermanylights
# Initialize it to have just some junk in element 0
light_states = ['junk']
# Add the states of however many lights
for a_light in range(howevermanylights):
light_states.append(True)
# We'll add code here to manipulate the lights' states
# Now show the state of each light
for a_light in light_states[1:]:
if a_light:
print '*',
else:
print ' ',
print
for a_light in range(howevermanylights):
# print last digit of a_light
print (a_light % 10),
print
and if I run the program (which I imaginatively called "ceiling") it does this:
$ python ceiling
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
$
(The bold blue text is what I typed in response to
my computer's prompt.)
This shows that light #0 is, oops... do you see that? I wanted to show
the state of light #1, #2, #3 etc., but for some reason the numbers are 0, 1, 2, etc.
I need to fix the digit printed. That last part will now read:
for a_light in range(howevermanylights):
# print last digit of a_light
print (a_light+1) % 10,
print
OK, that worked. Why did I have that "bug", or error? (Programmers call their mistakes
"bugs"; it sounds so much better to say "I had 5 bugs in my code" than "I made 5 mistakes
(or more) in my code.")
Well, actually I put it in on purpose. No, really; I wanted to mention that Python,
like Perl, starts its lists with index 0 rather than 1. This is why I wrote above
# Initialize it to have just some junk in element 0
light_states = ['junk']
if light_states has howevermanylights elements in it, they will be
numbered 0 up to howevermanylights-1.
Why do Python and Perl (and C and java too) start numbering lists/arrays at 0 rather
than 1? Well, it's for convenience. The first ten elements (or "decade" of elements) in
an array are numbered 0-9; the second ten are numbered 10-19. So you can tell which
"decade" we're in by looking at the tens digit.
This stands in contrast to our system of years, where the first century is years 1-100;
the second century is years 101-200... the 20th century is 1901-2000, and so on. See how
inconvenient this is? The 21st century started in 2001 (not 2000) so you can't tell just
by looking at the top digit. A computer scientist didn't come up with this
system for numbering years.
So a list of 5 elements (for example) has its elements numbered 0,1,2,3,4. Similarly
range(5) gives 5 numbers -- also numbered 0,1,2,3,4. To wit:
$ python
Python 2.6.5 (r265:79063, Jul 5 2010, 11:47:21)
[GCC 4.5.0 20100604 [gcc-4_5-branch revision 160292]] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> range(5)
[0, 1, 2, 3, 4]
>>>
Anyway, light_states starts at 0, and we number the ceiling lights starting at 1,
so I put some junk into element 0 of the list so element 1 could correspond to
ceiling light #1, etc.
OK, now let's put some more code in to deal with persons #2–howevermanylights.
# Adjust the following line to be however many lights you want
howevermanylights = 38
# "light_states" represents the states of howevermanylights
# Initialize it to have just some junk in element 0
light_states = ['junk']
# Add the states of however many lights
for a_light in range(howevermanylights):
light_states.append(True)
# Code to manipulate the lights' states
# We have person#2 upto and including howevermanylights.
for a_person in range(2, howevermanylights+1):
# Flip every "a_person"th light:
for a_light in range(a_person, howevermanylights+1, a_person):
light_states[a_light] = not light_states[a_light]
# Now show the state of each light
for a_light in light_states[1:]:
if a_light:
print '*',
else:
print ' ',
print
for a_light in range(howevermanylights):
# print last digit of a_light
print (a_light+1) % 10,
print
The new code is shown in this color and basically, um,
does what it says -- assigns the variable "a_person" all values from 2 upto and
including howevermanylights. And for each such person, flips every "a_person"th light.
When I run the program, it does this:
$ python ceiling
* * * * * *
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
$
Right, that's not 100 lights, and I've only printed the last digit of the light
number, but lights #1, 4, 9, 16, 25, 36 are left on. (If I make howevermanylights
much bigger than 38, then you won't be able to see the result on a single line.)
Time's up and you got the basic idea
OK, the above was 45 minutes' worth, but let me take a little more time to do two things:
And when we run it?
$ python ceiling
On: 1
On: 4
On: 9
On: 16
On: 25
On: 36
On: 49
On: 64
On: 81
On: 100
On: 121
On: 144
On: 169
On: 196
On: 225
On: 256
On: 289
On: 324
On: 361
On: 400
On: 441
On: 484
On: 529
On: 576
On: 625
On: 676
On: 729
On: 784
On: 841
On: 900
On: 961
$
Do you see the pattern there? Every number that's a perfect square is left on,
but composite numbers are off. Why perfect squares? That's an exercise left to the reader.
Anyway I hope that gives an idea of some of what it means to write a program.
Most of what "real programmers" do is quite a bit more complicated, but that ought
to give a flavor for at least some of the tasks. I hope that was fun reading for you;
it certainly was enjoyable for me to write.
Finishing(??) touches
OK, it's now the next morning and I wanted to sort of finish the program off,
and to give you the whole program in one snarf'n'barf-able blob so you can
tweak it yourself, if you've got the interest.
#!/usr/bin/python -utt
'''Program to solve cartalk puzzler
http://www.cartalk.com/content/puzzler/transcripts/201144/index.html
Basically this:
Imagine a very long hall with 20,000 lights hanging from the
ceiling, all off. These lights are controlled by a pull-chain:
pull it once, the light turns on; pull it again and the light
turns off.
Now someone comes through the hall and pulls every single chain.
The lights are now all on. Person #2 comes through and pulls
every 2nd chain, so that now lights 2, 4, 6, 8 and so on are
now off. Person #3 comes through and pulls every 3rd chain,
thus changing the state of lights 3, 6, 9, 12 and so on; they
turn some lights on and some off. Person #4 comes through and
flips lights 4, 8, 12, 16 and so on.
And so on, until person #20,000 comes through and only tugs on
the chain of the 20,000th light.
Can you predict which lights will be on, and which will be off?
The program calculates (not predicts) which lights will be on.
Provide the number of lights in a parameter (default 100)'''
import sys
def main(howevermanylights):
# "light_states" represents the states of howevermanylights
# Initialize it to have just some junk in element 0
light_states = ['junk']
# Add the states of however many lights
for a_light in range(howevermanylights):
light_states.append(True)
# Code to manipulate the lights' states
# We have person#2 upto and including howevermanylights.
for a_person in range(2, howevermanylights+1):
# Flip every "a_person"th light:
for a_light in range(a_person, howevermanylights+1, a_person):
light_states[a_light] = not light_states[a_light]
# Now show the state of each light
# Don't do that; just list out number of each light that's on
for a_num in range(1, howevermanylights+1):
if light_states[a_num]:
print 'On:', a_num
sys.exit(0)
if __name__ == '__main__':
try:
num_lights = int(sys.argv[1])
except:
num_lights = 100
main(num_lights)
So this does a few things beyond what I had last night:
- You can give a parameter and it'll do the calculation for the number
of lights provided
% ./ceiling.py 38
On: 1
On: 4
On: 9
On: 16
On: 25
On: 36
% ./ceiling.py 100
On: 1
On: 4
On: 9
On: 16
On: 25
On: 36
On: 49
On: 64
On: 81
On: 100
- It's got documentation:
% pydoc ceiling | cat
Help on module ceiling:
NAME
ceiling
FILE
/Users/collin/to-mail/ceiling.py
DESCRIPTION
Program to solve cartalk puzzler
http://www.cartalk.com/content/puzzler/transcripts/201144/index.html
Basically this:
Imagine a very long hall with 20,000 lights hanging from the
ceiling, all off. These lights are controlled by a pull-chain: (etc.)
- It's easier to debug (google "python debugger" for more info).
- It returns a "success!" code so the system thinks the program worked.
