
Feature Articles
 Most Recent Articles
 The Wizard Algorithm
 The New Guy (Part II): Database Boogaloo
 The Manager Who Knew Everything
 Improv for Programmers: The Internet of Really Bad Things
 Improv for Programmers: When Harddrives Attack
 Passing Messages
 Improv for Programmers: Just for Transformers
 Business Driven Development
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best ofâ€¦
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
Pretty sure this is an Euler problem, but either way I decided to have some fun with it since standard C can be kind of boring.
This code is perfectly with the C89 spec (I checked to make sure), and will compile and run with no warnings on the IBM C89 compiler for System 390 (it's all I had available), enjoy:
Admin
from math import sqrt
def nerds(lockers): current, open = 1, [] while current <= sqrt(lockers): open.append(current*current) current = current + 1 return open
print nerds(100)
output: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
Admin
An espresso of Java:
int num = 100, c = 0; while( ++cc <= num) System.out.println(cc);
Admin
obviously the locker toggled the most is the one with the highest number of common divisors in 1n which are <= itself
Admin
In IDL:
For 100 lockers this prints:
IDL> jock_beater, 100 Open lockers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 Max toggles: locker(s) 60, 72, 84, 90, 96 with 12 toggles
Admin
status(n) = #divisors(n) % 2
Admin
a(n) = n^2
Admin
This isn't even that hard to figure out logically.
Each locker (N) can only be toggled when i is less than or equal to N. Also, logic tells you that you're only going to hit the locker when you're using a number that goes into it evenly, that is to say, its factors.
Only the perfect squares have an odd number of factors, resulting in the door staying open. Therefore, it's i^2 for every value of i < the maximum number of lockers.
Admin
At the end, the only lockers that would be opened are squares of numbers. That should make this easy.
Admin
Sorry for repost, its Python by the way, and I needed to sort out the indentation...teach me to preview first in future...
Admin
Is LOLcode acceptable?
HAI I HAS A COUNT CAN HAS STDIO? GIMMEH COUNT I HAS A VAR VAR IZ 1 IM IN YR LOOP UP COUNT!!1 IZ VAR PERFECTSQUARETHING IZ VAR BIGGER THAN COUNT? KTHXBYE IM OUTTA YR LOOP VISIBLE "I HAZ OPENED " VAR KTHXBYE
Admin
function getLockers($tlockers) { for ($i = 1; $i <= $tlockers; $i++) { if (count(explode(".",(string)sqrt($i))) == 1) { echo $i."
"; } } }
Admin
Admin
For irrational number of lockers?
Easy, that's all about quantum mechanics man! A bit of SchrĂ¶dinger equation peppered with uncertainty principle and just a hint of Fourier transform. Apply interference to taste. And here is what we get  people still fall for an obvious troll even after he's gone
Admin
For a locker to be left open it should have an uneven number of divisors. Only numbers with a whole square root has that, hence the solution:
Admin
in C#:
Reason: Every locker is touched for their divisors. The square numbered once have an uneven number of divisors (for example 16: 1,2,4,8,16) so they remain open while the others have an even number of divisors (for example number 6: 1,2,3,6) and stay closed at the end.
Greets Roland
Admin
Once commenters watch the simulation, the two most common nonbrute force solutions seem to be
But these are just really simpler versions of the brute force method: one knows what the solution looks like and then just writes code to create that appearance.
But as some have pointed out, the solution comes from the fact that any door with an odd number of factors will remain open. So the "real" solution is to factor a number into its prime factors, and then determine whether the number of prime factors is odd (even) to determine whether the door is open (closed). And to do it in O(n) time.
<Conspiracy hat on>This appears to be a sneaky attempt to get the WTF community to invent a fast integer factorization algorithm that can be used for cryptography!</Conspiracy hat off>
Admin
As I recall this exercise is straight out of the book 'Programming Interviews Exposed', so it's not anything new. For awhile Amazon (and like a few other companies) took many of their interview questions straight from the book.
Admin
$i = 1; $factor=2; while ($i<=$numlockers) { print $i." "; $i+=$factor+1;$factor+=2; } print "\n";
Admin
Admin
C++ again. Also brute force, but this version is cleaner ;)
Admin
Hey, that's the most elegant explanation I've seen so far.. nice..
Admin
A bit more PHP that works out the most toggled in a slightly brute force way.
define('SOME_FACTOR', 100); $max_divisors = 1; $most_toggled = array(); for($i = 1; $i <= SOME_FACTOR;$i++){ $these_divisors = array(); $no_of_divisors = 0; $sqrt_i = sqrt($i); for($ii = 1; $ii < $sqrt_i; $ii++){ if($i/$ii == round($i/$ii)){ $these_divisors[] = $ii; } $no_of_divisors = count($these_divisors) * 2; }
} echo "The most toggled lockers where toggled $max_divisors times" . "and are numbers " . implode(',', $most_toggled) . ".\n";
Admin
Delphi
Admin
Finding the pattern was easy (using the simulation).
Here's my code:
And if "Programming Praxis" has its own category, then maybe its own category should have its own color, too. ("Feature Articles" is blue, "CodeSOD" is red, "Error'd" is gray, "Tales from the Interview" is purple, "Alex's Soapbox" is brown, "Programming Praxis" is also red and should be changed to a different color that isn't blue or red or gray or purple or brown. Maybe green would do, since you don't have any green yet. Also, the old Programming Praxis articles should be moved to this category.)
Admin
How many factors does 96 have?
1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96 ==> 12!
So each door is toggled a number of times equal to its factors. I find it hard to believe the nerds never figured this out. Bogus story...
Captcha: damnum  need I say more?
Admin
python:
Completely Brute Force, but actually goes through the motions and will return an N sized array with 0 where a locker is shut and 1 if it is open.
Admin
Yay, I actually found it.
The fact is you'll always toggle them a 2 times unless it has an odd number of factor. The only number that has a impair number of factor are those that has 2 times the same one.
1  1 < 2  1 2 3  1 3 4  1 2 4 < 5  1 5 6  1 2 3 6
As you can see, only 1 and 4 as an odd number of factor. So to get a list of all the open locker, just do:
1^2, 2^2, 3^2, 4^2, 5^2, 6^2, 7^2, 8^2, 9^2, 10^2
You got all your lockers.
Admin
in PSEUDOCODE, using only "+" "<=" and a loop
current_odd=1 current_locker=1 while current_locker <= lockers do print current_locker current_odd := current_odd + 2 current_locker := current_locker + current_odd done
Admin
That's wrong; I just ran the demo and got the following open lockers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 Those are the squares of: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
The i^2 answers are indeed correct.
(Untested Python code)
Admin
C#
Admin
I'm pretty sure this coforms to LOLCODE spec 2.0:
Admin
Admin
Mathematica (consider it cheating)
Admin
This is similar to my first working solution. Then I saw the output and ended up with:
Admin
I missed the quote, obviously :(
Admin
Perl Golf: 54 characters.
perl e"print join', ',map{$*$}1..sqrt pop" 100
http://blogs.msdn.com/matthew_van_eerde/archive/2009/08/05/badperllockerproblem.aspx
Addendum (20090805 12:48): 48:
perl e"print map{$*$.$/}1..sqrt pop" 100
Addendum (20090805 13:02): 47:
perl e"map{print$*$.$/}1..sqrt pop" 100
I still think "say" is cheating but there are two 41character solutions with it:
perl E"map{say$*$}1..sqrt pop" 100 perl E"say$*$ for 1..sqrt pop" 100
Addendum (20090805 13:23): Someday I'll learn how to count. Counts above are off.
Anyway, 41 character sayless solution:
perl e"print$*$,$/for 1..sqrt pop" 100
37 with say: perl E"say$*$ for 1..sqrt pop" 100
Admin
Is there some way to devise a "programming praxis" that
Mind you, I liked the Befunge solution.
Admin
I disagree that the list of perfect squares is not a "real" solution.
By definition, a perfect square MUST have an odd number of factors. Think about any nonperfect square: for any prime number, there are exactly 2 factors: 1 and itself. For any composite number, there are still an even number of factors  you have to multiply two different numbers together to get a product. I.e., 24 can be made up of 124, 212, 38, 46. 8 factors for 4 pairs of numbers. (I'm not writing a formal proof of this.)
A perfect square, by definition, has a factor that can be multiplied by itself to get the product. Take 36: 136, 218, 312, 49: 8 factors, 4 pairs of numbers. But then we also have 6*6. Thus, 36 has 9 factors.
I suppose if someone wrote up the brute force code originally, then changed it after seeing the results, that would be "cheating". But if you wrote up the perfectsquares code after examining the underlying number theory, that's quite the opposite of cheating  it's recognizing the underlying math to simplify the problem.
Admin
The ones that remain open are the ones with an odd number of factors. I figured that out within the simulation time (running at 250 ms per toggle). What I didn't figure out is that only squares have an odd number of factors. What I still haven't figured out is WHY. Anyone?
Admin
Wow. I can't believe the reason only squares have an odd number of factors didn't occur to me.
Admin
Based on the results from the simulation above, here is a function that will give the same results in a far less brute force way (in php)
<?php function getOpenLockers ($numLockers) { $openLockers = array(); for($i = 1; $i <= floor(sqrt($numLockers)); $i++) { array_push($openLockers, $i * $i); } return $openLockers; } echo "The following lockers are open: "; foreach(getOpenLockers(100) as $num) { echo $num . " "; } ?>Admin
Patterns!
If you look at it for long enough with your eyes crossed, You'll see the image of a locker.
Addendum (20090805 12:49): Maybe.
Admin
could someone explain how this works in a really elementary way? I can't come up with a way to explain this problem. Thank you for helping me learn.
Admin
i^2 your locker are belong to us.
Admin
I think Mr. Zargus has his eye on the RSA prize... Isn't there a contest from RSA involving a way to calculate the factors of an arbitrarily large number?
Admin
The best part is setting the inputs to Alex's little simulation as 1000 lockers, 1 ms delay... then leaning back and letting your eyes defocus just a bit.
For the first few dozen cycles, you get some interesting Conway's Lifelike patterns, followed shortly by an impression of the old star field screensaver, and then meteors streaking and leaving trails across your screen. It finishes with a gradual, calming wipe across the screen.
I want this to be my new screen saver! Alex, make it so!
Admin
Because (n+1)^2 = n + (2n+1)