 Feature Articles
 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
Admin
The nerds should win and fairly comfortably too...there are a total of 4245 toggles to be made and in the challenge clock, it would take 4245 secs for the jocks or 70.xx minutes...thats way too much time for the nerds to whip out the solution.
Admin
am i missing something or is every locker just toggled the number of its divisors in {1,...,n}? i.e. its unlocked if this number is odd, locked if its even
Admin
Admin
I didn't get past Algebra 1, so figuring out the formula is beyond me. But hey, I'd may as well and see if any patterns emerge, right?
I ran the simulation for a thousand lockers. 1, 4, 9, 16, 25... and 100, 400, and 900. It repeats! Hm, but not at 40 or 90.
Like most good geeks, I can make up for not knowing something myself by knowing who or what knows it instead. Say, Wolfram Alpha, what produces the sequence 1, 4, 9, 16, 25, 36, 49, 64?
I have honestly no clue whatsoever about those formulas, but it did show me the blindingly obvious differences in count between each locker.
So!
I'm sure it could be optimized further, and I'm sure that others will already have done so, but I haven't looked at any of the comments beyond looking to see if someone'd already used Wolfram Alpha. My submission, therefore, is mundane and possibly cheating, but who cares. ;)
Edit: Hahaha, beaten by post number two. Awesome. You may, therefore, look at this submission in the light of someone that couldn't math themselves out of a paper bag.
Admin
Admin
Code in PHP to determine the number of most commonly changed locker ($count is our locker count):
<?php $num = 0; $count = 100; $x2 = $x = floor(log($count, 2)); $x3 = 0; while (($x2>=0) && ($x3>=0) && (($num/2*3)<=$count)) { $x2; $x3++; $num = pow(2, $x2)*pow(3, $x3); } echo $num; ?>Admin
This isn't so hard if you think about it for a minute. The only lockers that will be left open are those that are "toggled" an odd number of times—in other words, those with an odd number of unique factors. This is always, and only, true when n = x * x for some integer x, i.e. where n is a perfect square.
Of course, if I were given this in high school I may have been too busy enjoying the sight of sweaty jocks to apply myself seriously to the problem…
(Dagnamit, I'm always late to these praxis parties! Of course someone got there first.)
Admin
Admin
Ok, this one should display the white lockers.
100% homebrewn befunge code made from some sort of pseudocode.
Nonbrute force solution will come soon!
Admin
S... is should read the instructions better. I just output the number if open closets at the end <hits his head at the wall>. As for the follow up question. It's obviously the first closet (it just gets opened and nobody touches it ever again).
Admin
C#:
static List<long> getOpenLockers(long numberOfLockers) { List<long> openLockers = new List<long>();
}
Admin
A locker is toggled for each of its divisors, including itself and 1. So, if the number of divisors is even, closed; if odd, open.
However, these divisors always come in pairs; 2 * 8 = 16. UNLESS the number is a perfect square, in which case the square root factor "overlaps" and is only counted once, making a pair "by itself"; 4 * 4 = 16.
Thus, a locker has an odd number of factors (is open) if and only if it's a perfect square.
Admin
That was interesting and quite fun used as a learning break but it's my observation [primarily because it was a little vague in the defining parameters] that if NumToggles <> NumLockers then the whole solution falls to pieces.
Is there a simplified mathematical formula which could be derived if both NumToggles and NumLockers were variable or is brute force the only remaining solution?
Admin
python: def getOpenLockers(lockers): import math openLockers = [] for i in range(1,int(math.sqrt(lockers))+1): openLockers.append(i*i) return openLockers
Admin
Well, the lockers toggle once for each divisor in the number, so here's a Mathematica oneliner:
Now, this lists all square numbers less than or equal to n, so naturally, a mathematical explanation would be nice.
Let us assume we have a locker that is open afterwards, and let us call its position n.
It must be that n has an odd number of divisors, for else the locker would be closed.
Let [image] be the prime factorization of our integer, then n will have [image] distinct divisors; and this number will only be odd if all k's are even.
Since all the powers are even, this number will be a square.
That all squares make for an open locker follows from the above, as all steps are reversible.
Admin
Correct, with the caveat that the case n = 1 needs to be checked explicitly since the prime factorization is empty.
Admin
Yup. I carried it out to eight before I (independently) hit on the (k1 + 1)(k2 + 1)(...)(kn + 1) calculation above:
Once: 1: 1 Twice: p: 1 <> p Three times: p^2: 1 <> p^2, p Four times: p^3: 1 <> p^3, p <> p^2 pq: 1 <> pq, p <> q Five times: p^4: 1 <> p^4, p <> p^3, p^2 Six times: p^5: 1 <> p^5, p <> p^4, p^2 <> p^3 p^2q: 1 <> p^2q, p <> pq, q <> p^2 Seven times: p^6: 1 <> p^6, p <> p^5, p^2 <> p^4, p^3 Eight times: p^7: 1 <> p^7, p <> p^6, p^2 <> p^5, p^3 <> p^4 p^3q: 1 <> p^3q, p <> p^2q, p^2 <> pq, p^3 <> q pqr: 1 <> pqr, p <> qr, q <> pr, r <> pq
Admin
Well, in the case n = 1, both of the products would be the empty product, so the net effect would still be an odd number of divisors.
Admin
Just on update on my whitespace code (this time with comments):
Admin
Add 3 new lines at the end.
Admin
Ooh... an answer to the "which ones are toggled the most" and in a tantalizing form. Is there a way for a given N to find the set of numbers {n: 1 <= n <= N} which maximize that expression?
Addendum (20090805 18:01): Hopefully in a more elegant fashion than:
most_so_far = 1 for i (1 .. N) { factorization = prime_factorization_of(i) divisors = do_product_trick(factorization) if (divisors > most_so_far) { most_so_far = divisors; answers = { i } } else if (divisors == most_so_far) { answers.add(i) } }
print answers
Admin
Hooray, whitespace!! I did a whitespace on page 1 but I don't think anyone noticed. I don't know why not, the code was right there for them to read.
Admin
Sub MarkSet() For j = 1 To 100 Mark (j) Next End Sub
Sub Mark(increment As Integer) For i = increment To 100 Step increment If (Sheet1.Cells(i, 1).Value = "Open") Then Sheet1.Cells(i, 1).Value = "Closed" Else Sheet1.Cells(i, 1).Value = "Open" End If Next End Sub
</Excel VBA Code>
Admin
It may already have been said, I haven't read all eight billion comments yet, and I probably won't, but class, man. Pure class. very few people can put knowledge of cribbage into use in the real world, and you have crossed that boundary. it will do you no good, in "the real world", but don't let that get you down.
one for his nob.
Admin
(ok, gur cevzrf come second equal)
Admin
Would it be too much to ask to have a challenging problem? This is The Daily WTF; it's supposed to attract people with some actual coding ability.
Admin
It has nothing to do with which lockaers are toggled the least  rather which lockers are toggled an odd number of times > i^2 is the solution, not p^2 (where p is prime)
Gees...THINK before you post!!!
(BTW: There is a generator provided on the original page where you could have verified your result before making an idiot of yourself)
Admin
nope. the difference between mediocre and good programmers is beard length. it is left as an exercise to the grokker which is wrong and which is right (hint: you've got seventy years left, tops, so don't worry too much)
Admin
uhm...no
36 has factors 1, 2, 3, 4, 6, 9, 18, 36 (7 of them) does this mean 36 is prime?? It has an even number of prime factors (2 and 3) which might be what you meant....
Admin
I'm sure someone else will have posted this by now....
"36 stays open WHY DON'T YOU TRY IT OUT ON THE SIMULATOR THAT WAS QUITE KINDLY PROVIDED ON THE FIRST PAGE???
Admin
I've had this as an interview question. Didn't even get the job.
Admin
You're Either New here or a troll!!!
Admin
Ruby: nlockers = ARGV[0].to_i 0.upto(nlockers).each { n puts n2 if n2 <= nlockers }
I could have gone with a one liner, but meh.
Admin
Admin
This is why some people consider the 'squares' answer a cheat... It solves the problem exactly as written, but if the problem is changed slightly the entire algorithm would need to be rewritten.
I don't for a minute (well maybe just a minute) suggest that looking for underlying patterns and shortcuts is a bad thing, but I think it is equally as important to think about whether a problem might one day need to be expanded/changed and whether any optimisations we make might significantly impair our ability to easily adapt the problem later.
The most efficient answer is not always the best  especially where we can see that a minor change to the requirements will result in a major code change because of our optimisation. I know many will say "Nothing is lost because the original change was far quicker than planned, and the later change can then swallow some of the time saved earlier", but I think those who work in the industry will realise that time saved in the first release will never be made available for subsequent releases.
</rant>Admin
Are these combination locks or key locks? If combination, how do the jocks remember 100 combinations If key, I assume the keys are left in the locks during the exercise?
Admin
Sorry guys, it took me 25 seconds to come up with the solution (seriously).
Let's take any locker. It is toggled each time we use a toggling sequence that is one of his divisor. Locker #24 will be toggle by the 1 and 24 sequence, the 2 and 12, the 3 and 8, the 4 and 6 sequences.
All numbers have an even number of divisors, unless it is a perfect square (the divisor in the middle is only counted once): Locker #36 is toggle by sequence 1 and 36, 2 an 18, 3 and 9, 4 and 9, and 6 ALONE.
Hence all the perfect square will remain open.
Very nice riddle, I didn't knew it. Of course, nobody will beleive me, but it really took 20 seconds. Yoooo!
Admin
Nope. The locker 1 is only toggle once. Furthermore, it is not a prime locker.
Admin
I don't understand this problem. What is the actual point of the problem? Doesn't make any sense.
Admin
This code is quite long, but I'm wordy like that.
Any perfect square is an opened locker.
For the most toggled, I just had to figure out how many factors each number had.
After calculating the prime factors in the form:
Then the number of factors, and the number of times it has been toggled is:
This is in PHP5, complete with classes.
\n"; foreach ($lockers as $locker) { echo " " . $locker>getNumber() . "
";
}
echo "
\n"; $mostToggledLockers = $corridor>getMostToggledLockers(); echo "The following lockers have been toggled the most with " . $mostToggledLockers[0]>getTimesToggled() . " toggles:
"; echo "\n"; foreach ($mostToggledLockers as $mostToggledLocker) { echo " " .
$mostToggledLocker>getNumber() .
"
\n";
}
echo "
"; $endTime = microtime(true); $timespan = $endTime  $startTime; echo "Calculated in " . number_format(round($timespan, 5), 5) . " seconds. Take that, jocks!
"; // This script was for the programming practice at // http://thedailywtf.com/Articles/Nerds,Jocks,andLockers.aspx ?>Output:
Admin
The main thing I've learned from this is that the simulator is pretty to watch if you set it to like 1000 lockers and a 1ms delay.
Yeah, I'm no good at maths or brainteasers.
Admin
And yeah, they're all squares.
Admin
I agree  rather than having fairly simple problem whose answers are widely published on the 'net, can't we have some more like something from ProjectEuler (though some of their puzzles have simple underlying math, implementations of said math haven't always been published all over the net)?
There was one I found on an IT companies site, which was basically "if you can solve this, send us your resume". Though the solution can be found online, it is more difficult to search for than most of the standard ones  and though it is long, the solution requires a fair bit of programming ability. The problem went something like:
Write a program that alphabetically sorts the numbers from one to a billion (we will exclude spaces and 'and' so 4567 would be fourthousandfivehundredsixtyseven). Counting characters in this sorted list, we see that the twentyeighth letter is the end of eighteenmillion (only eight and eighteen precede it)). the 51 billionth letter also happens to be the last letter of a spelt out number  What is the number, and what is the sum of the integers up to that point?
Granted this particular question may be too complex for this sort of forum, but it serves a good example because it requires very little knowledge other than data structures and algorithms...
I'm Kent Brockman
Admin
Why is it the slowest people always seem to think that their feats are impressive?
Admin
WHOOPS  I realised that afterward (and kinda waondered how long before someone else would have a go)
Admin
Wow. Your Befunge is way better than mine, Tim.
For what it's worth, here's my version. (It just prints out squares.)
Also, Befunge implementations differ on how big a cell is, so it may not work on inputs greater than 127. (It will exit before printing out anything.)
Admin
I wrote a program that solves in the brute force way in fortran 90 for my comp class last semester. In the end, the only lockers that are open are powers. 1,4,9,16,etc.
it's called the collatz theorem.
Admin
Programming can be quite intellectually challenging and rewarding, though not often "fun".
But, really now, how often does professional programming require solving problems like this? Practically never. So it raises the question as to why this kind of problem is ever presented in programming courses.
Admin
So many complicated, 'optimised' or esoteric solutions. Have people forgotten that compilers optimise your code FOR you? Here is the proper way to do it in VB.
It can be found at http://rmrf7.co.uk/locker.txt (Forum software thinks its spam. Pffft.)