[PyAR2] Car Talk Puzzler (The Hall of Lights)

Chris Nestrud ccn at panix.com
Thu Nov 3 19:17:25 CET 2011


Here's the method that I used to initially solve the problem.

#Begin
from collections import defaultdict
max_lights = 20000
lights=defaultdict(bool) # defaults to False
for i in xrange(1,max_lights+1,1):
    for j in xrange(i,max_lights+1,i):
        lights[j] = not lights[j]
print("Lights on: %s" % (', '.join((str(l) for l in
xrange(1,max_lights+1,1) if lights[l]))))
#End

Here's the method after realizing the pattern.

#Begin
from math import sqrt
max_lights = 20000
print("Lights on: %s" % (', '.join((str(l*l) for l in
xrange(1,int(sqrt(max_lights)+1),1)))))
#End

I'm going for minimum number of lines rather than "Readability counts."

Chris

Greg Lindstrom wrote:
> The Car Talk "Puzzler" this week is a classic (I've heard it
> opening/closing lockers):
>
> *RAY:* This puzzler is from my "ceiling light" series. Imagine, if you
> will, that you have a long, long corridor that stretches out as far as the
> eye can see. In that corridor, attached to the ceiling are lights that are
> operated with a pull cord.
>
> There are gazillions of them, as far as the eye can see. Let's say there
> are 20,000 lights in a row.
>
> They're all off. Somebody comes along and pulls on each of the chains,
> turning on each one of the lights. Another person comes right behind, and
> pulls the chain on every second light.
>
> *TOM:* Thereby turning off lights 2, 4, 6, 8 and so on.
>
> *RAY:* Right. Now, a third person comes along and pulls the cord on every
> third light. That is, lights number 3, 6, 9, 12, 15, etcetera. Another
> person comes along and pulls the cord on lights number 4, 8, 12, 16 and so
> on. Of course, each person is turning on some lights and turning other
> lights off.
>
> If there are 20,000 lights, at some point someone is going to come
> skipping
> along and pull every 20,000th chain.
>
> When that happens, some lights will be on, and some will be off. Can you
> predict which lights will be on?
>
> I wrote a Python program to "solve" this is 8 (non-blank) lines long,
> including one line, "MAX_LIGHTS = 20000" used to adjust the number of
> lights for debugging/testing.  Let's see how YOU would do it (I'll post
> mine in a couple days).
>
> O'Reilly accidentally sent me an "extra" case of books to give away at
> PyArkansas (the arrived after the conference).  If Marsee will let me give
> them away, the entry judged "best" will win one of the titles.  "Best" is
> totally subjective but will include (1) Correct Solution and (2) Elegance
> (is it Pythonic/Understandable?).  Python 2 or 3.
>
> --greg
> _______________________________________________
> PyAR2 mailing list
> PyAR2 at python.org
> http://mail.python.org/mailman/listinfo/pyar2
>




More information about the PyAR2 mailing list