 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
Delphi solution. The function returns an array of integers. The Nth element of the array is 0 if the Nth locker is closed, and X if it's opened, where X was the number of toggles.
Admin
Also, the smallest number with 12 factors is 60 (and since it's the largest highly composite number smaller than 100, the next being 120, 12 factors is indeed the most possible).
Admin
public static IEnumerable<int> GetOpenLockers(int num0) {int num1=0,num2=1;while((num1+=num2+=2)<=num0)yield return num1;}
// You can use it like this /* foreach(int i in GetOpenLockers(100)) Console.WriteLine(i);
// Or with descending and using System.Linq;
Array.ForEach(GetOpenLockers(100).OrderByDescending(i => i).ToArray(), i => Console.WriteLine(i)); */
Admin
Admin
Quicky crappy php using squarechecking ~
locker(1000);
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961
Admin
#include <stdio.h>
int main(int argc, char **argv) { printf("4 9 16 25 36 49 64 81\n"); return 0; }
Totally optimized.
Admin
In BASICish (num being number of lockers):
For i=1 to sqrt(num) print i*i next
Admin
If I got this as an interview question, I'd go postal. Promise.
Admin
Sorta brute forceish...
Admin
Technically, this is incorrect; more than one factor may be repeated. To prove that a number has an odd number of factors if and only if it is a perfect prime:
Let x be an integer, x = x1^a1 * x2^a2 * ... * xn^an. For a given factor, there are (a1 + 1) ways to choose at what power x1 will be, (a2 + 1) ways to choose at what power x2 will be, and so on. The number of distinct factors for x is thus p = (a1 + 1) * (a2 + 1) * ... * (an + 1). Now, p is odd if and only if all of (a1 + 1), (a2 + 1), ..., (an + 1) are odd, or equivalently, if and only if a1, a2, ..., an are even. That last condition is equivalent to saying that x is a perfect prime.
Admin
YAY!
Admin
Technically, this is incorrect; more than one factor may be repeated. To prove that a number has an odd number of factors if and only if it is a perfect prime:
Let x be an integer, x = x1^a1 * x2^a2 * ... * xn^an. For a given factor, there are (a1 + 1) ways to choose at what power x1 will be, (a2 + 1) ways to choose at what power x2 will be, and so on. The number of distinct factors for x is thus p = (a1 + 1) * (a2 + 1) * ... * (an + 1). Now, p is odd if and only if all of (a1 + 1), (a2 + 1), ..., (an + 1) are odd, or equivalently, if and only if a1, a2, ..., an are even. That last condition is equivalent to saying that x is a perfect prime.
Admin
from math import sqrt
def IsSquare(n): if sqrt(n) == int(sqrt(n)): return True return False
def GetOpenLockers(n): open_lockers = [] for v in xrange(n): if IsSquare(v + 1): open_lockers.append(v + 1) return open_lockers
Admin
Ok ,sorry, i will state it a bit more clearly:
for any natural power of a square of a prime number
(as an example 36 is 6*6 but it stays closed)
Admin
More JS:
Admin
I'm really amazed you can't even use the demonstration at the top of the page before you start spouting off.
Admin
It's all the square numbers. I've done this before, but with 1000 and only an imaginary hallway filled with lockers.
Admin
A PHP Solution...
Admin
You're still wrong: 4 is not prime, but 16 remains open. Here's an optimized (O(sqrt(N)) solution:
Admin
Untested and messy php
Admin
Think about it this way: given integer n (> 0) find every pairwise factorisation (a,b) such that a <= b with a == b iff a^2 = n. Call the set of such factorisations S (so S = {(a,b)  ab = n && a <= b}).
Then the set of factors of n is F = {a  Exists b : (a,b) in S} U {b  Exists a : (a,b) in S}. That's a union of two sets which are the same size, so if the two sets are disjoint then F is even. The intersection of the two sets is the set of integers x such that Exists b : (x,b) in S and Exists a : (a,x) in S. By definition of S, xb = n and ax = n, so x = 0 (impossible since we said n > 0) or a=b. But, again by definition of S, x <= b and a <= x, so since b=a we have x <= a <= x, or x = a. Therefore the intersection of the two sets is the set of integers x such that x^2 = n.
Therefore if n is not a square number the two sets are disjoint and F is even. If n is a square number the two sets have sqrt(n) in common, and F is odd.
Edit: ok, I'm missing a step. I should also have shown that if (a,b) in S and (a,c) in S then b=c, and similarly if (a,b) in S and (c,b) in S then a=c. Trivial, since division by a nonzero real is welldefined.
Admin
I see... the ones that remain open have been hit by 1, themselves, and their square root, plus pairs of factors.
Eg 36 is hit by 1 and 36, 2 and 18, 3 and 12, 4 and 9, and 6.
The closed ones don't have a positive integer square root so are hit an even number of times.
Now I guess I need to work out how to extract my head from the toilet bowl...
Admin
Man, you would think the nerds from one year would notice the answer is all primes and tell the younger generation so they could show up the jocks next year and tell Zargus the answer while the jocks tired themselves out slamming lockers.
Admin
C++, by Brute force.
Addendum (20090805 10:57): Edit: The 3rd struct should be
To enforce the 1st door to be open initially. Yeah, templates are crazy.
Admin
There's a ruby solution. Works to find all the open lockers, will have to figure out which ones are opened most often.
Admin
Might be worth al least putting some form of color behind the title.
Whiteonwhite doesn't work out too well...
Admin
Ada (Quick and dirty, no validation of input)
 egilhh
Admin
In the same vein at the .NET IEnumerable, using Javascript 1.7 generators, and without brackets since that works too =)
You'll need a recent firefox with a special flag to the script tag to use generators.
function l(i) for(j = 1; j < Math.floor(Math.sqrt(i)); j++) yield i*i;
and getting it is fun too:
var opens = [i for each (i in l(100))];
javascript is fun =)
Admin
Stupid short solution in PHP:
Admin
Admin
In Python:
[code] count = int(sys.argv[1])
open_lockers = [] for i in range(1, count+1): factors = [j for j in range(1, i+1) if i%j == 0] if len(factors) % 2 == 1: open_lockers.append(i)
print open_lockers [code]
You know, just in case they decide to change the rules on square numbers or anything.
Admin
ok. This one is easy once you get the fact its a square system. the algorithm is simple:
C#: Given that n is an integer representing the number of lockers.
replace with your language of preferences form. Example, the basic syntax on a TI89 (the only decent calculator) would be:
its not brute force, and they can show it scales for however many lockers. :)
Simple, elegant, and in its own simple way a brute force. Captca: Esse (Hey, Esse you want some algorithms? )
Admin
The Java way to find the most toggled
Admin
I noticed an interesting pattern with the brute force method. When you get to the halfway mark, you're basically doing the single locker toggle.
Admin
A simple solution is to just sequentially add up all of the odd numbers. Each number in the series is an open locker.
Start with 1. Add 3 to get 4 Add 5 to get 9 Add 7 to get 16 Add 9 to get 25 etc.
Admin
C, 66chars:
void f(int l){for(int i=0,j=0;++i<=l;i+=(j+=2))printf("%d,",i);}
I'm claiming extra credit for not using multiplication, and it being deeply, deeply ugly code.
Admin
Who is Paula and why is she brill(i)ant?
Admin
Yep. What you're seeing is the identity:
(n+1)^2 = n^2 + 2n + 1
and you're subtracting off the n^2.
Hence you get: 1  21+1 = 3 2  22+1 = 5 3  2*3+1 = 7
as you'd expect.
That's the trick my horrific C experience uses.
Admin
I'm amazed at the number of brute force methods.
I'm surprised at the nerds in the story as well. If you cannot solve a problem mathematically, optimize the numeric method. To wit, they could have used a bike to traverse the lockers. Or 100 boxes on a sheet of paper.
Admin
Groovy
def getOpenLockers(int n) { return (1..Math.sqrt(n)).collect {it**2} }
println getOpenLockers(100)
Admin
That guy in Nethack is totally a jock.
And may have a lot of identical twins.
This is what it looks like when run:
Admin