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:
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:- First, let's change this line to say 1000 instead:
howevermanylights = 1000
- And let's just list out which lights are on, rather than printing out the
state of all the lights:
# 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
$ 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.
No comments:
Post a Comment