public static void main(String[] args) {
int num = 100;
int i=1;
int k=1;
while(k<num){
k=i*i;
i++;
System.out.println(k);
}

}

Sue D. Nymme2009-08-05 09:08

#!perl

sub lockers { return map $_**2, 1..sqrt shift }

neat2009-08-05 09:11

i don't have a method of solving this problem, but i can clearly see the pattern when it's done - closed lockers in runs of 2,4,6,8,10,12,14,16,18 with a single open locker between them

how delightful!

Obvious2009-08-05 09:14

Umm squares of 1 to 10?

Captcha "eros" .....I love you too!

Mark2009-08-05 09:16

Or to put it more simply- The open lockers are i^2 where i runs from 1-10.

Welbog2009-08-05 09:17

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

Savvy Business User2009-08-05 09:17

Paste this formula in Excel and use copy-down

=ROW(A1)^2

Addison2009-08-05 09:19

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

Somehow I think that makes it less fun.

anonym2009-08-05 09:23

vbs file, work in nearly any windows

a = inputbox("locker?")

for i = 1 to a
l = l+1
b = b & i & " "
i = i + (2*l)
next

msgbox b

Welbog2009-08-05 09:26

Addison:

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

Somehow I think that makes it less fun.

That's good because I don't find solving solved problems to be fun in the first place.

Florian Junker2009-08-05 09:28

Haskell:

lockers n = takeWhile (<= n) [x*x|x<-[1..]]

eliac2009-08-05 09:28

Looks like the most-toggled locker is the 96th one, with 12 toggles.

halcyon12342009-08-05 09:28

DOS, because I'm too lazy to SSH into my linux machine:

Edit.exe:

@ECHO OFF
SET /A LOCKERS = %1

IF %LOCKERS% LEQ 0 GOTO ERROR

SET /A COUNT = 1

:JOCKHACK

SET /A SQUARE = %COUNT%*%COUNT%

IF %SQUARE% GTR %LOCKERS% GOTO NERDSLAM

ECHO %SQUARE%

SET /A COUNT=%COUNT%+1
GOTO JOCKHACK

:NERDSLAM
ECHO Done
GOTO END

:ERROR
ECHO How can you have a negative amount of lockers? That's just silly.
GOTO END

:END
ECHO.

anonym2009-08-05 09:30

for me, I saw the pattern +3, +5 , +7, +9, +11, +13, +15, +17 and +19

not i^2

Daniel2009-08-05 09:33

neat:

i don't have a method of solving this problem, but i can clearly see the pattern when it's done - closed lockers in runs of 2,4,6,8,10,12,14,16,18 with a single open locker between them

how delightful!

I also noticed this pattern and it is trivial to code:

void lockers(int n)
{
int i, j, k;

for (i = 1, k = 2; i <= n;)
{
printf ("O")
i++;
for (j = 0; (i <= n) && (j < k); i++, k++)
printf ("X");
k = k+k;
}
}

From the explanation about the squares, we can deduce why this works:

(n+1)^2 = n^2 + 2n + 1

Anon2009-08-05 09:35

The header of the article shows up as white on white in chrome, maybe this category hasn't had a header color assigned to it yet?

That's good because I don't find solving solved problems to be fun in the first place.

So... Not having fun in your job as a programmer ?

steenbergh2009-08-05 09:37

neat:

i don't have a method of solving this problem, but i can clearly see the pattern when it's done - closed lockers in runs of 2,4,6,8,10,12,14,16,18 with a single open locker between them

how delightful!

Thanks for pointing out the rythm!

Classic ASP:

<%
function doLockers(numLocks)
dim Lockers()
redim Lockers(numLocks-1)
dim inc : inc = 1
dim lastOpened : lastOpened = 0
dim nextToOpen : nextToOpen = 0

' closing all lockers
for i = 0 to numLocks-1
Lockers(i) = 0
next

' Jocking through the corridor...
do while nextToOpen < numLocks
Lockers(nextToOpen) = 1 ' open locker
lastOpened = nextToOpen
inc = inc + 2 ' skip ahead
nextToOpen = lastOpened + inc
loop

' printing result
dim ret : ret = "Open lockers: "
for i = 0 to numLocks-1
if Lockers(i) = 1 then
ret = ret & "<br />" & cstr(i+1)
end if
next

(defun visit-door (doors doornum value1 value2)
"visits a door, swapping the value1 to value2 or vice-versa"
(let ((d (copy-list doors))
(n (- doornum 1)))
(if (eq (nth n d) value1)
(setf (nth n d) value2)
(setf (nth n d) value1))
d))

(defun visit-every (doors num iter value1 value2)
"visits every 'num' door in the list"
(if (> (* iter num) (length doors))
doors
(visit-every (visit-door doors (* num iter) value1 value2)
num
(+ 1 iter)
value1
value2)))

public List getLockers(int numLockers) {
(1..numLockers).collect{ it*it }
}

Any groovy programmers that want to show me better ways to do this, please point them out. :D

I AM NOT A GROOVY PROGRAMMER.

It looks like it will return the squares from 1 to numLockers**2, which might not be what you want.

daralick2009-08-05 10:00

SQL - though the use of numbers table may qualify as brute force...

create FUNCTION [dbo].[getOpenLockersList] ()

RETURNS @aReturnTable TABLE
( locker INT,
isOpen BIT,
myCount INT)
AS BEGIN

INSERT INTO @aReturnTable (locker, mycount)
SELECT locker, SUM(CASE WHEN locker%number = 0 THEN 1 ELSE 0 END)
FROM (SELECT number locker FROM numbers WHERE number <= 100) lcker
CROSS join
(SELECT number FROM numbers WHERE number <= 100) nbr
GROUP BY locker

return
END
GO
SELECT locker,
CASE WHEN mycount%2 = 1 THEN 'OPEN' ELSE 'closed' END lockerState ,
myCount
FROM dbo.getOpenLockersList()

SELECT SUM(mycount%2) FROM dbo.getOpenLockersList()
SELECT locker FROM dbo.getOpenLockersList()
WHERE mycount =
(SELECT MAX(mycount) FROM dbo.getOpenLockersList() )

Zecc2009-08-05 10:01

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

I don't see where it says n should be less than 100.

Welbog2009-08-05 10:02

Zecc:

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

I said factors. 24's factors are {1, 2, 3, 4, 6, 8, 12, 24}. There is an even number of them.

And the limit of 100 is irrelevant. That just gives us the maximum perfect square we care about.

Zecc2009-08-05 10:06

Welbog:

Zecc:

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

I said factors. 24's factors are {1, 2, 3, 4, 6, 8, 12, 24}. There is an even number of them.

Yeah, I was going to delete after posting, but it was to late.
I was thinking of a slight different problem, I guess; where you don't start toggling at the i-th locker for the i-th iteration.

Zecc2009-08-05 10:06

Welbog:

Zecc:

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

I said factors. 24's factors are {1, 2, 3, 4, 6, 8, 12, 24}. There is an even number of them.

Yeah, I was going to delete after posting, but it was too late.
I was thinking of a slight different problem, I guess; where you don't start toggling at the i-th locker for the i-th iteration.

Addendum (2009-08-05 10:12): Addendum: never mind. I guess I'm just not thinking straight about this.

Scot2009-08-05 10:08

The locker toggled the most is the locker whose prime factors can create the greatest number of combinations. (locker ... combinations ... get it?).

At first, I think 64 might be a good choice, but (2,2,2,2,2,2) creates only 6 combinations. If I replace a 2 with a 3, I describe locker 96, and I can now create 11 combinations. Applying my knowledge of cribbage, I see that I can replace three 2s with two 3s to describe locker 72 (2,2,2,3,3), which also creates 11 combinations.

Doug Graham2009-08-05 10:08

Wrote this quick in C#

Console.Write("How many lockers? ");
int lockers = Convert.ToInt32(Console.ReadLine());
int openlockers = 0;
int interval = 1;
Console.Write("Open Lockers: ");
while (openlockers + interval < lockers)
{
openlockers += interval;
Console.Write(openlockers + " ");
interval += 2;

}

Martin2009-08-05 10:10

Even worse is when the problem was already solved by Tom and Ray on Car Talk:

I would bet that Mr. Zargas was the coach of the football team. This challenge is EXTREMELY biased towards the jocks. I respectfully submit that in order to figure out the function, you HAVE to iterate (brute force) at SOME point in time.

SHENANIGANS!

Medinoc2009-08-05 10:12

Zecc:

Welbog:

The open lockers are perfect squares.
(snip)

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

24 can be divided by 1, 2, 3, 4, 6, 8, 12 and 24. That's 8 factors, or 6 if we exclude the extrema -> even

25 can be divided by 1, 5 and 25. That's 3 factors -> odd.

steenbergh2009-08-05 10:12

And a slightly smaller version in JS

<SCRIPT>
function doLockers(n)
{
var i = 1;
while((i*i)<=n)
{
document.write("<BR />" + i*i);
i++;
}
}
doLockers(100);
</SCRiPT>

BTW, I'm getting an awful lot of errors when posting lately...

Olav2009-08-05 10:12

#!/usr/bin/python
from math import sqrt
def getOpenLockers(n):
result = map(lambda x: x * x, range(1, (int)(sqrt(n)) + 1))
return result

Steve the Cynic2009-08-05 10:12

Re: "96 has the most"...

Other numbers not above 100 with 12 distinct factors:

simply - squares of prime numbers (or perfect squares)

I'm amazed with amount of i^2 solutions. Think a bit longer before posting.

Márton Balassa2009-08-05 10:14

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.

function Lockers(const Count: Integer): TIntegerDynArray;
var I, K: Integer;
begin SetLength(Result, Count);
for I := 1 to Count do begin Result[I - 1] := 0;
K := Count;
while K > 0 do begin if I mod K = 0 then Inc(Result[I - 1]);
Dec(K);
end;
end;
for I := 0 to Count - 1 do if Result[I] mod 2 = 0 then Result[I] := 0;
end;

pjt332009-08-05 10:15

Scot:

The locker toggled the most is the locker whose prime factors can create the greatest number of combinations. (locker ... combinations ... get it?).

At first, I think 64 might be a good choice, but (2,2,2,2,2,2) creates only 6 combinations. If I replace a 2 with a 3, I describe locker 96, and I can now create 11 combinations. Applying my knowledge of cribbage, I see that I can replace three 2s with two 3s to describe locker 72 (2,2,2,3,3), which also creates 11 combinations.

12, not 11 - you're probably failing to count 1.

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).

Daniel2009-08-05 10:15

Sinclair ZX81 / Timex TS100 (via emulator):

Rhombicosidodecahedron2009-08-05 10:15

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));
*/

Mamont2009-08-05 10:16

sub getOpenLockers {
my @opened;
my $last = 1;
my $total = shift;
my $skip = 2;

def testy (number):
skip = 3
sum = 3
step = 1
while True:
if number <= sum:
return step
skip += 2
sum += skip
step += 1

Tama2009-08-05 10:24

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.

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

double sqrts = Math.sqrt(Double.parseDouble(args[0]));
for (double i = 1; i <= sqrts; i++) {
System.out.print(new Double(Math.pow(i, 2.0)).intValue() + ",");
}
}
}

Tama2009-08-05 10:26

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

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.

BobbyBob2009-08-05 10:27

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

reallyAmazed2009-08-05 10:29

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)

RamÅ«ns2009-08-05 10:30

More JS:

function (n) {
if (n <= 0) {
return [];
}
var ret = [1];
for (var i = 4, plus = 5; i <= n; i += plus, plus += 2) {
ret[ret.length] = i;
}
return ret;
}

port2009-08-05 10:31

I'm really amazed you can't even use the demonstration at the top of the page before you start spouting off.

belgariontheking2009-08-05 10:35

It's all the square numbers. I've done this before, but with 1000 and only an imaginary hallway filled with lockers.

You're still wrong: 4 is not prime, but 16 remains open. Here's an optimized (O(sqrt(N)) solution:

def GetOpenLockersOsqrtn(n):
open_lockers = []
for v in xrange(int(sqrt(n))):
open_lockers.append((v+1) * (v+1))
return open_lockers

shane blake2009-08-05 10:44

some pretty simple sql... more brute force than nerdy, but it works...

declare @count int
set @count = 100
declare @lockers table( id int identity, state bit )
insert into @lockers ( state ) values ( 0 )
while ( (select max(id) from @lockers) < @count )
insert into @lockers ( state ) values ( 0 )
while ( @count > 0 )
begin
update @lockers set state = abs(state - 1) where id % @count = 0
set @count = @count - 1
end

for any natural power of a square of a prime number

(as an example 36 is 6*6 but it stays closed)

1,2,3,4,6,9,12,18,36
9 factors

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 non-zero real is well-defined.

MisterCheese2009-08-05 10:48

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...

Zack2009-08-05 10:48

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.

int main () {
// Excel was used to generate this part.
DoorColor<1>::print();
DoorColor<2>::print();
DoorColor<3>::print();
DoorColor<4>::print();
DoorColor<5>::print();
// ... you get the idea ...
DoorColor<96>::print();
DoorColor<97>::print();
DoorColor<98>::print();
DoorColor<99>::print();
DoorColor<100>::print();
return 0;
}

Addendum (2009-08-05 10:57): Edit: The 3rd struct should be

To enforce the 1st door to be open initially. Yeah, templates are crazy.

David Kowis2009-08-05 10:52

#!/usr/bin/ruby
#

def getOpenLockers(total)
open = []
(1..total).each do |num|
sqr = num ** 2
if(sqr <= total)
open << sqr
elsif sqr > total
break
end
end
open
end

puts "100: #{getOpenLockers(100)}"

There's a ruby solution. Works to find all the open lockers, will have to figure out which ones are opened most often.

Anonymous2009-08-05 10:52

I like the concept of coding challenges but so far they have all been the same - provide an algorithm to solve some well known mathematical problem. How about a challenge that consists of a bit more than just solving known equations?

Might be worth al least putting some form of color behind the title.

White-on-white doesn't work out too well...

egilhh2009-08-05 10:57

Ada (Quick and dirty, no validation of input)

with Command_Line;
with Ada.Text_IO;
with Ada.Numerics.Generic_Elementary_Functions;
procedure Lockers is
package Float_Numerics is
new Ada.Numerics.Generic_Elementary_Functions(Float);
Input : Integer := Integer'Value(Ada.Command_Line.Argument(1));
begin
for i in 1..Integer(Float_Numerics.Sqrt(Float(Input)) loop
Ada.Text_IO.Put(Integer'Image(i**2));
end loop;
end Lockers;

--
egilhh

jonnyq2009-08-05 10:59

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.

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 TI-89 (the only decent calculator) would be:

Prgm lsol(n)
For i,1,sqrt(n)
if i^2 <= n
Disp i^2
endif
EndFor
EndPrgm

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? )

amischiefr2009-08-05 11:11

The Java way to find the most toggled

private static ArrayList<Integer> toggledTheMost(int n) {
int arr[] = new int[n];
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 1; i <= n; i++) {
for(int j = i ; j <= n ; j = j + i) {
arr[j-1]++;
}
}

int toggled = 0;
for(int i = 0; i < arr.length ; ++i) {
if(arr[toggled] < arr[i])
toggled = i;
if(arr[i]%2 != 0)
list.add(i+1);
}
System.out.println("The locker that was toggled the most was locker: " + (toggled+1));

return list;
}

Miquel Fire2009-08-05 11:12

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.

azredwing2009-08-05 11:13

sub lockers{ push @_, $_**2 for 1..shift; return @_; }

Someone mentioned that doing the logic makes the programming "less fun" - they'd rather brute-force the program by actually flipping all 100 doors so many times - to make pretty code or something. The way I see it is if you can optimize a problem away beforehand, and your code ends up being an efficient one-liner, that's WAY better than trying to "beautifully" make a giant solution that somehow account for "edge cases" when it's clear there will never be any.

Anyone can program; not everyone can think logically, and that's the difference between mediocre and good programmers, or even good and great.

Matt Flowers2009-08-05 11:15

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.

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.

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:

#include <stdlib.h>
#include <stdio.h>

#define NUM_LOCKERS 100

int lockers[NUM_LOCKERS] = {0};
int i, j, *l = lockers - 1;

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

Anonymous Coward2009-08-05 11:28

status(n) = #divisors(n) % 2

Anonymous coward2009-08-05 11:28

a(n) = n^2

Kris2009-08-05 11:28

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.

nobody2009-08-05 11:29

At the end, the only lockers that would be opened are squares of numbers. That should make this easy.

DaveB2009-08-05 11:30

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]

Sorry for repost, its Python by the way, and I needed to sort out the indentation...teach me to preview first in future...

Way too much time on my hands2009-08-05 11:30

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

Char2009-08-05 11:32

function getLockers($tlockers) {
for ($i = 1; $i <= $tlockers; $i++) {
if (count(explode(".",(string)sqrt($i))) == 1) {
echo $i."<br>";
}
}
}

dtremain2009-08-05 11:32

print "Enter number of lockers (0 to exit) > ";
while (<>)
{
chomp;
exit if $_ == 0;
$lockerCnt = $_;
print "Locker Count = $lockerCnt\n";
@openLockers = {};
for ($i=1;($i**2)<=$lockerCnt;$i++)
{
push @openLockers, $i**2;
}
$openLockerCnt = @openLockers;
$openLockerCnt--;
for my $lockerNo (@openLockers[1..$openLockerCnt])
{
print "$lockerNo";
if ($lockerNo==@openLockers[$openLockerCnt]) {print "\n";} else {print ", ";}
}
print "Enter number of lockers (0 to exit) > ";
}

atrophic2009-08-05 11:32

Ruby:

require 'mathn'
puts "The open lockers would be #{(1..Math.sqrt(ARGV[0].to_i).floor).collect { |i| i*i }.inspect}"

reallyAmazed2009-08-05 11:32

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

Kleist2009-08-05 11:32

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:

function state = locker_toggle(count)
state = sqrt(1:count)==floor(sqrt(1:count));
end

Roland2009-08-05 11:33

in C#:

static int[] GetOpenLockers(int n)
{
List<int> res = new List<int>();

int root = (int)Math.Sqrt(n);
for(int i = 1; i <= root; i++)
{
res.Add(i*i);
}

return res.ToArray();
}

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

Kevin M2009-08-05 11:38

BJ Homer:

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)

I think that this solution best meets the spirit of the praxis (so far).

Once commenters watch the simulation, the two most common non-brute force solutions seem to be

1. print out the list of square numbers
2. print out the series created by successive additions of the odd numbers {1, 1+3, 1+3+5, 1+3+5+7, ...}

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>

Zac Boller2009-08-05 11:40

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.

simply - squares of prime numbers (or perfect squares)

I'm amazed with amount of i^2 solutions. Think a bit longer before posting.

Are you crazy! what kind of place would the intertubes be if people thought before posting...

kennytm2009-08-05 11:52

C++ again. Also brute force, but this version is cleaner ;)

#include <cstdio>

template<int Lock, int Run = Lock>
struct Door {
enum { State = (Lock >= Run && Lock % Run == 0) != Door<Lock, Run-1>::State };
static void print_this_and_previous_doors();
};

echo "Locker $i is $state.\n";
}
echo "The most toggled lockers where toggled $max_divisors times"
. "and are numbers " . implode(',', $most_toggled) . ".\n";

Brad2009-08-05 11:54

Delphi

{ Returns an array of integers, indicating the positions of open lockers. A
locker will be toggled on the n-th pass if, and only if, n is a factor of
the locker position. Lockers toggled an even number of times will be left
in the closed position, while lockers toggled an odd number of times will
be left open. If i is a factor of j, then so is j/i. Because of this, only
perfect squares will have an odd number of unique factors. (Where j = i*i,
i and j/i are not unique.) The lockers that will remain open are therefore
those at the positions indicated by perfect squares.
}
function GetOpenLockers(
lockerCount : Integer
) : TLockerArray;
var
i : Integer;
lockerNum : Integer;
resultCount : Integer;
begin
resultCount := 0;
SetLength( Result, resultCount );
i := 1;
lockerNum := i*i;
while lockerNum <= lockerCount do begin
SetLength( Result, resultCount + 1 );
Result[ resultCount ] := lockerNum;
Inc( resultCount );
Inc( i );
lockerNum := i*i;
end;
end;

zzo382009-08-05 11:55

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.)

Melvis2009-08-05 11:57

eliac:

Looks like the most-toggled locker is the 96th one, with 12 toggles.

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?

spence912009-08-05 11:57

python:

def lockJock(x):
flipper = lambda a: a==0 and 1 or a==1 and 0
a = [0 for i in range(x+1)]
for i in xrange(1,x+1):
for j in xrange(1,x+1):
if j % i == 0:
a[j] = flipper(a[j])
return a[1]

print lockJock(100)

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.

BoomWav2009-08-05 11:59

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.

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.

Torge2009-08-05 12:00

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

Herohtar2009-08-05 12:03

reallyAmazed:

simply - squares of prime numbers (or perfect squares)

I'm amazed with amount of i^2 solutions. Think a bit longer before posting.

reallyAmazed:

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)

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)

from math import floor, sqrt
def getOpen(numLockers):
openList = []
for i in range(1, floor(sqrt(numLockers))):
openList.append(i^2)
return openList

Diego Mijelshon2009-08-05 12:04

C#

IEnumerable<int> OpenLockers(int lockerCount)
{
var position = 1;
var gap = 0;
while (position <= lockerCount)
{
yield return position;
gap += 2;
position += gap + 1;
}
}

lolwut2009-08-05 12:06

I'm pretty sure this coforms to LOLCODE spec 2.0:

HAI
CAN HAS STDIO?
GIMMEH LOCKERZ
I HAS A NERDS ITZ 0
IN YR HALLS UPPIN YR NERDS TIL BOTH SAEM PRODUKT OF NERDS AN NERDS AN BIGGR OF PRODUKT OF NERDS AN NERDS AN LOCKERZ
VISIBLE PRODUKT OF NERDS AN NERDS
OUTTA YR HALLS
KTHXBYE

jstrayer2009-08-05 12:09

List<Integer> getOpenLockers(int numberOfLockers) {
List<Integer> openLockers = new ArrayList<Integer>();
if (numberOfLockers > 0) {
int skip = 3;
int locker = 1;
while (locker <= numberOfLockers) {
openLockers.add(locker);
locker += skip;
skip += 2;
}
}
return openLockers;
}

We nerds pooled our resources, and even optimized things a bit; The only lockers that will be open are perfect squares of integers. Fortunately, the jocks probably can't read the locker numbers.

Bim Job2009-08-05 12:34

Is there some way to devise a "programming praxis" that
* isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.)
* isn't trivially solvable by googling?
* actually requires a computer program?
* requires commenters to read, say, the first ten responses to see whether the problem has been solved?
* doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

Mind you, I liked the Befunge solution.

azredwing2009-08-05 12:37

Kevin M:

Once commenters watch the simulation, the two most common non-brute force solutions seem to be

1. print out the list of square numbers
2. print out the series created by successive additions of the odd numbers {1, 1+3, 1+3+5, 1+3+5+7, ...}

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.

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 non-perfect 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 1*24, 2*12, 3*8, 4*6. 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: 1*36, 2*18, 3*12, 4*9: 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 perfect-squares code after examining the underlying number theory, that's quite the opposite of cheating - it's recognizing the underlying math to simplify the problem.

Daniel Straight2009-08-05 12:38

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?

Daniel Straight2009-08-05 12:40

Wow. I can't believe the reason only squares have an odd number of factors didn't occur to me.

SumSoftwairGai2009-08-05 12:42

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)

If you look at it for long enough with your eyes crossed, You'll see the image of a locker.

Addendum (2009-08-05 12:49): Maybe.

markus2009-08-05 12:44

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.

Code Dependent2009-08-05 12:45

i^2 your locker are belong to us.

James2009-08-05 12:48

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?

North Bus2009-08-05 12:49

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 Life-like 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!

David2009-08-05 12:49

Because (n+1)^2 = n + (2n+1)

self2009-08-05 12:50

Casio calculator:

"Number of lockers"?->A
Int âˆšA->Dim List 1
For 1->B To âˆšA
B^2->List 1[B]
Next
List 1

DeepCerulean2009-08-05 12:50

Sweet...it would be cool if you would categorize the previous two entries so they show up in the category list

Anonymous2009-08-05 12:52

Way too much time on my hands:

Is LOLcode acceptable?

No it isn't. Ever. Now die.

Thuktun2009-08-05 12:54

A locker will remain open at the end if it's been touched an odd number of times. Each locker will be touched once for each of its integral factors, including 1 and itself.

For a given number n, any integral factor f (1 < f < n), there will be a complementary factor f' (1 < f < n). Collected together, the only way these factors will number evenly will be if f=f' and n=f^2.

Therefore, the resulting opened lockers will be squares of the numbers from 1..sqrt(n).

aleph2009-08-05 13:00

A more compact Funge solution (created using BeQunge). BeQunge seems to differ from the Funge-98 spec in terms of the directions produced by the 'w' instruction, so results may be incorrect with different interpreters.

Anyway, here's the code:

> v
v"Number of lockers: "<
>>,,,,,,,,,,,,,,,,,,,,&v
v 1 p01<
>::*: 10gv
^+1," ".<w@
^<

Output for n=100:
1 4 9 16 25 36 49 64 81 100

Jean-Paul2009-08-05 13:08

Function in Turbo Pascal

function lockers(n : integer) : string;
var cur : integer;
var mul : integer;
var s : string;
begin
s := '';
for cur := 1 to n do s := s + '0';
cur := 1;
mul := 1;
while cur < n do
begin
cur := mul * mul;
s[cur] := '1';
mul := mul + 1;
end;
lockers := s;
end;

Maurits2009-08-05 13:09

Follow-up question: which lockers are toggled the LEAST?

I still think "say" is cheating but there are two 41-character solutions with it:

perl -E"map{say$_*$_}1..sqrt pop" 100
perl -E"say$_*$_ for 1..sqrt pop" 100

since the call was for a function definition and the array is an acceptable return value, this can be golfed further to:

sub l{map{$_*$_}1..sqrt pop}

which has a golf count of 29 -- not counting the perl invocation
or:

perl -e 'sub l{map{$_*$_}1..sqrt pop}'

38 with the perl invocation but without an invocation of the function.

Brad2009-08-05 13:21

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Primes. Twice each.

Spectre2009-08-05 13:22

In R:

# the shortest one yet, no?
remaining <- function(n) (1:sqrt(n))^2

# generates a ton of warnings 8=[
most.toggled.brute <- function(n) which.max(Reduce('+',lapply(1:n, function(k) c(rep(0, n-k),1)), rep(0,n)))

tiller2009-08-05 13:22

Rob G:

An espresso of Java:

int num = 100, c = 0;
while( ++c*c <= num) System.out.println(c*c);

Are you sure that ++c*c works as expected in java? It would not work in c or c++.

Anon2009-08-05 13:24

LabVIEW:

Note: LabVIEW sucks

Ryan2009-08-05 13:26

List<int> getOpenLockers(int NumLockers)
{
List<int> OpenLockers = new List<int>();
int inc = 0;
for (int i = 0; i + inc + 1 <= NumLockers; i++)
{
OpenLockers.Add(i + inc + 1);
i += inc;
inc += 2;
}
return OpenLockers;
}

a nerd2009-08-05 13:26

I don't believe that a bunch of football players could correctly determine what they had to do.

Dean2009-08-05 13:29

Seems fairly simple. The state of each locker is just a property of the number of prime factors it has.

For example, 6 has prime factors of 1, 2 and 3. That's 3 prime factors. The 6th locker will be toggled 3 times and end up open.

Odd # of factors = open
Even = closed.

I find it hard to believe a bunch of nerds couldn't figure this out.

Anguirel2009-08-05 13:31

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Locker #1 only gets toggled once. Though I vote for the lockers in the next hall over. They don't get toggled at all during this experiment.

Dean2009-08-05 13:32

Actually scratch that, I meant factors not prime factors

gpan2009-08-05 13:34

Very simple. The lockers that stay open are the ones whose #'s are perfect squares.
1,4,9,16,.....

rm52482009-08-05 13:40

As it has been pointed out, the lockers that stay open are lockers that have an odd number of divisors. If you only know the number of the locker, you can somewhat brute force it by simply figuring out how many divisors it has.

public boolean[] getOpenLockers( int lockersIn ){
boolean[] lockers = new boolean[lockersIn];
//true = open, false = closed
for( int y = 1; y < lockers.length + 1; y++){
int count = 0;
for(int x = y; x > 0; x--){
if( y % x == 0 ){
//if the current locker has an
//odd number of divisors, it is open
count++;
}
}
if( count % 2 == 0){
lockers[y-1] = false;
}else{
lockers[y-1] = true;
}
}
return lockers;
}

Java code. I don't consider this "brute force" because it doesn't go thru each locker and toggle it several times. Although there are better ways to do this.

uses
SysUtils;
const
N = 100;
var
Lockers: set of 1..N;
i, Step: Integer;
begin
Lockers := [];
for Step := 1 to N do begin
i := Step;
repeat
if i in Lockers then
Exclude(Lockers, i)
else
Include(Lockers, i);
Inc(i, Step);
until i > N;
end;

for i in Lockers do
Write(i, ' ');
Writeln;
end.

Maurits2009-08-05 13:53

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Everybody failed this test. Have you read the problem?

Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.

It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door". The sample solutions for n=1 and n=4 are also wrong. It should be: f(1)={1} and f(4)={1;2;3;4}. So TDWTF failed its own test. The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

And your form is broken, it doesn't submit.

Mrs MeChokemchild2009-08-05 14:04

Mrs MeChokemchild:

it doesn't even say "after toggling every mth locker for m=1..n"

I meant to say "every 1..nth locker for n=1..100".

And your form is broken, it doesn't submit.

After adding the previous line, it did.

Spectre2009-08-05 14:05

Spectre:

# generates a ton of warnings 8=[
most.toggled.brute <- function(n) which.max(Reduce('+',lapply(1:n, function(k) c(rep(0, n-k),1)), rep(0,n)))

And it isn't even correct. Here's a better one, which doesn't generate any warnings and produces a list of the most toggled lockers:

Everybody failed this test. Have you read the problem?

Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.

It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door". The sample solutions for n=1 and n=4 are also wrong. It should be: f(1)={1} and f(4)={1;2;3;4}. So TDWTF failed its own test. The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

And your form is broken, it doesn't submit.

n is the number of lockers, not the number of toggles. The toggling takes place as described.

Steve2009-08-05 14:17

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Follow-up to Follow-up: What will the state of the lockers be after n steps of the brute force solution?

jmcnary2009-08-05 14:35

Here's my solution, without looking at comments.

/*
* Created on Aug 5, 2009
*/
package blueharvest.locker.channenge;

//A few minutes of reflection produces the following conjectures:
//Trip everything onece
//After than, Prime numbers will always be tripped one additional time.
//Other lockers tripped additional times equal to sum of exponents in their prime factorizations
//Odd additional trips are closed, even trips are open.
//Outlying case: 1 (neither prime nor composite) is always open
public static boolean isPrime(int number) {
/* //1st attempt:
//A number is prime if is not divisible by any prime numbes less than its square root

int squareRoot = LockerChallenge.integerSquareRoot(number);
for(int index = 2; index <= squareRoot; index++) {
if(isPrime(index)) {
if(number % index == 0) {
return false;
}
}
}
return true;
*/
//Use the prime facotrization memory Map for better results;
//A number if prime if itself is in the prime factorization list;
Map<Integer, Integer> primeFactors = getPrimeFactorization(number);
return primeFactors.containsKey(number);
}

private static void calculateAndDisplay(int number) {
if(number <= 0) {
System.out.println("Invalid integer. Use counting numbers only.");
return;
}
System.out.println("Calculating for " + number + " lockers");
long start = System.currentTimeMillis();
List<LockerState> states = calculateLockerStates(number);
long end = System.currentTimeMillis();
printResults(states);
System.out.println("Calculation took " + (end-start) + " milliseconds.");
System.out.println();
}

private static class LockerState{
public int lockerNumber;
public int toggles;

public LockerState(int number, int switches) {
lockerNumber = number;
toggles = switches;
}

//If a locker as been toggled an odd number of times, it is open.
public boolean isOpen() {
return toggles%2 == 1;
}
}

private static void printResults(List<LockerState> lockerStates) {
java.util.Collections.sort(lockerStates, new Comparator<LockerState>() {

public int compare(LockerState o1, LockerState o2) {
return new Integer(o1.lockerNumber).compareTo(o2.lockerNumber);
}});
System.out.print("Open lockers: ");
printOpenLockers(lockerStates);
System.out.println();
//This is a reverse sort!
java.util.Collections.sort(lockerStates, new Comparator<LockerState>() {

public int compare(LockerState o1, LockerState o2) {
int result = new Integer(o2.toggles).compareTo(o1.toggles);
if(result == 0) {
result = new Integer(o1.lockerNumber).compareTo(o2.lockerNumber);
}
return result;
}});

System.out.print("Lockers With highest Toggle Count ");
printHighCount(lockerStates);
System.out.println();
}

private static Map<Integer, Integer> createPrimeFactorization(int number){
Map<Integer, Integer> primeFactorization = null;
int squareRoot = LockerChallenge.integerSquareRoot(number);
//Skip 1, as that is out outlying case
for(int index = 2; index <= squareRoot; index++) {
if(isPrime(index)) {
if(number % index == 0) {
Map<Integer, Integer> baseFactorization = getPrimeFactorization(number / index);
primeFactorization = new HashMap<Integer, Integer>(baseFactorization);
Integer thisExp = primeFactorization.get(index);
if(thisExp == null) {
thisExp = 0;
}
thisExp = thisExp + 1;
primeFactorization.put(index, thisExp);

}
}
}
//This means that the number is prime;
if(primeFactorization == null) {
primeFactorization = new HashMap<Integer, Integer>();
primeFactorization.put(number, 1);
}
return primeFactorization;
}

private static class Factor {
int baseNumber;
int exponent;

public Factor(int base, int exp) {
this.baseNumber = base;
this.exponent = exp;
}
}
}

and Results

Calculating for 1 lockers
Open lockers: 1
Lockers With highest Toggle Count (1): 1
Calculation took 0 milliseconds.

Calculating for 4 lockers
Open lockers: 1 4
Lockers With highest Toggle Count (3): 4
Calculation took 0 milliseconds.

Calculating for 50 lockers
Open lockers: 1 4 6 9 10 14 15 16 21 22 24 25 26 33 34 35 36 38 39 40 46 49
Lockers With highest Toggle Count (6): 32 48
Calculation took 0 milliseconds.

The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

Umm... wasn't that the scenario given?

*doublechecks*

There should be one input to the function (number of lockers)

Why yes... yes it was. What problem were you thinking of?

Kazan2009-08-05 14:41

PS

for (int i=1; i*i < 100; ++i)
cout << i*i;

is more computationally efficient than using sqrt - a single multiply is much cheaper than a sqrt.

that's why many games use radius bounding spheres and use distance squared instead of distance - skip the unneeded and expensive sqrt

Shinobu2009-08-05 14:43

I think the solution is knowing the problem beforehand (which seems doable given the circumstances) and a) look up the solution and get some acting exercise to make solving it look believable, make a few mistakes at first and b) do something funny with the lockers and / or the corridor.

Anonymous Coward2009-08-05 14:45

In Befunge98:

&19pv
v <
1
>::*:19g`!v
^ +1._25*,@

DeadPanda2009-08-05 14:48

Simple python solution with list comprehensions...

get_lockers = lambda n: [(2*k) + pow(k,2) + 1 for k in range(0, floor(sqrt(n)))]

Code Dependent2009-08-05 14:50

In line with

Shinobu:

b) do something funny with the lockers and / or the corridor.

...and...

Steve:

What will the state of the lockers be after n steps of the brute force solution?

I would guess, several doors hanging by one hinge, at least a couple lying on the floor; papers, books, gym clothes and assorted high-school-type crap scattered willy-nilly; perhaps a jock or two moaning in pain after slipping on said crap.

Oh, wait... these lockers are unused. Forgot. Okay, switch halls, everybody.

Dr Frankenstein2009-08-05 15:00

javascript:getPaula()
(copy+paste in same window)... nuff said... for now.

zzo382009-08-05 15:07

Spectre:

In R:

# the shortest one yet, no?
remaining <- function(n) (1:sqrt(n))^2

There is two shorter ones, the Perl golf code is 29 and my code is 11

Streeaker2009-08-05 15:09

If the same hallway and rules were used for every "locker challenge" in the story, the best solution would have been to just remember the results from the last time. For bonus points, prank the teacher by putting stickers on the inside of the appropriate lockers saying This locker will be open.

(Captcha = paratus, latin for "ready". Hmm...)

BCS2009-08-05 15:09

- All lockers that are toggled an odd number of times
- All lockers with an odd number of divisors.
- Divisors pair so an odd number of divisors indicates that one occurs twice
- All square numbers

czetts2009-08-05 15:32

perl -e "while($_**2<$ARGV[0]){$_++};print" 100

nonny nonny2009-08-05 15:32

Bim Job:

* doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

I thought that was the whole point!

atrophic2009-08-05 15:33

Didn't notice the bonus points bit. Here's a Ruby implementation that sorts the lockers by the number of times they were toggled as well. (very inefficient divisor counter, but the efficient one is another dozen lines of code ;) )

Ruby:

require 'mathn'
puts "The open lockers would be #{(1..Math.sqrt(ARGV[0].to_i).floor).collect { |i| i*i }.inspect}"

toggles = Hash.new
(1..ARGV[0].to_i).each { |n| toggles[n] = (1..n).reject{|x| n % x !=0}.size }

puts "Here are the locker numbers sorted by the number of times they were toggled"
times_toggled.sort.reverse.each do |a|
puts "#{a[0]}:\t#{a[1].sort.inspect}"
end

Evan Kroske2009-08-05 15:36

I was pretty proud of myself with this one, until I realized all the numbers were perfect squares. Anyway, my function returns a list with the open open lockers = True and the rest = False.

def compute_open_lockers(numLockers):
lockers = []
for index in range(0, numLockers):
lockers.append(False)
for counter in range(0, numLockers):
for locker_index in range (counter, numLockers, counter + 1):
lockers[locker_index] = not lockers[locker_index]
return lockers

if __name__ == "__main__":
print compute_open_lockers(100)

jwd2009-08-05 15:41

ahh, my daily wtf: untested and excessively complicated

Two more options in JavaScript2009-08-05 15:41

Both are called as "getOpenLockers(100);"

function getOpenLockers(n) {
var x = 1;
var i = 1;
var result = '';

while (x <= n) {
result += (x > 1) ? ', ' + x : x;
x += i += 2;
}

return result;
}

or

function getOpenLockers(n, x, i) {
if (!x) i = (x = 1) + 2;
return (x > n) ? '' : ((x > 1) ? ', ' : '') + x + getOpenLockers(n, x + i, i + 2);
}

mikocs2009-08-05 15:54

I know it is not high programming:

put this in Excel to cell B1, and copy it to a 100x100 area :)
=IF(MOD(ROW(),COLUMN()-1)=0, IF(A1=0,1,0),A1)

Column CW is the solution itself

Can Berk Güder2009-08-05 15:56

def getOpenLockers(n):
openLockers = []
i = 1
step = 3
while i <= n:
openLockers.append(i)
i += step
step += 2
return openLockers

Paul N2009-08-05 16:05

(I haven't read the comments yet).

The solution is found by determining the number of factors.
1 has a single factor (1) and remains open.
2 has two factors (1,2) and is opened then closed.
3 has two factors (1,3) and is opened then closed.
4 has three factors (1,2,4) and is opened, closed, and reopened.

Each locker that is left open has an odd number of factors.
Factors come in pairs matched from outside in. For example 8 (1,2,4,8) has two pairs of factors: 1*8 and 2*4.
Odd numbers of factors also come in pairs matched from outside in, but the innermost number is used twice. For example 4 (1,2,4) has two pairs of factors: 1*4 and 2*2.
The odd number of factors are only found in numbers that are squares of one of the factors.

The easiest way to calculate the open lockers is to find the square numbers.

Answer in C#

private static List<int> NerdsJocksAndLockers(int numberOfLockers)
{
List<int> openLockers = new List<int>();
int number = 1;
int square = number * number;
while (square < numberOfLockers)
{
openLockers.Add(square);
number++;
square = number * number;
}
return openLockers;
}

CAPTCHA: damnum

Capt. Obvious2009-08-05 16:08

Maurits:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Toggles-
Zero: Lockers on a different hallway/outside range.
One: 1
Two: Primes
Three: Squares of Primes
Four: Product of two Primes; Cubes of Primes
Five: Product of three primes, exactly two of which are identical; Fourth powers of Primes
and so on in that manner

Edit: Utter fail on the five toggles. Fixed in posting below.

Capt. Obvious2009-08-05 16:08

Maurits:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Toggles-
Zero: Lockers on a different hallway/outside range.
One: 1
Two: Primes
Three: Squares of Primes
Four: Product of two Primes; Cubes of Primes
Five: Fourth powers of Primes
and so on in that manner

Paul N2009-08-05 16:19

Zecc:

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

What about numbers like 1*2*3*4 = 24 or 2*3*4*7 = 168 then?

I don't see where it says n should be less than 100.

All the numbers in 1*2*3*4 are factors of 24, but do not make up the complete list of factors.
24 has 8 factors: 1,2,3,4,6,8,12,24
These are matched in pairs: (1*24)(2*12)(3*8)(4*6).

Prabhu2009-08-05 16:20

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.

Anonymous, ... sort of2009-08-05 16:39

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

McLenin2009-08-05 16:41

Let's try a bit of Whitespace shall we? The instructions are
simple. Just
copy this code into a text editor. You should have some spaces and
some tabs
just ignore all the other words. There should be 51 lines if you
get 101
delete every even one (2, 4, 6, etc.). Than save the file and
interpret it
with a whitespace interpreter. With a bit of luck it should work. (Well
it worked
for me and I just hope that I have copied the code
100% OK).

End
here.

EX PLO SHUN2009-08-05 16:49

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!

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

sub getOpenLockers {
my $locker_count = shift;
# Keep track of open lockers
my @open_lockers;
# Which locker was the last to be kept open?
my $last_open_locker = 0;
# What was the locker count between the last two open lockers?
my $last_odd_number = -1;
foreach my $locker (1 .. $locker_count) {
# We're looking for the locker two beyond the last difference.
my $odd_check = $locker - $last_open_locker;
if($odd_check - 2 == $last_odd_number) {
$last_odd_number = $odd_check;
$last_open_locker = $locker;
push @open_lockers, $locker;
}
}
return \@open_lockers;
}

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.

Paul N2009-08-05 16:54

Brad:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Primes. Twice each.

1. Only once

TheNewOne2009-08-05 16:59

Code in PHP to determine the number of most commonly changed locker ($count is our locker count):

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.)

Paul N2009-08-05 17:02

Paul N:

private static List<int> NerdsJocksAndLockers(int numberOfLockers)
{
List<int> openLockers = new List<int>();
int number = 1;
int square = number * number;
while (square < numberOfLockers)
{
openLockers.Add(square);
number++;
square = number * number;
}
return openLockers;
}

Off by one error
should read

while (square <= numberOfLockers)

Tim2009-08-05 17:09

Ok, this one should display the white lockers.

v ;//00 - num lockers;
v ;//10 - current step;
v ;//20 - current locker;
v ;//x1 - locker: 0 if closed, 1 if open;

>25*:*00pv ; #00 = 100 ;
v <
>010pv ; #10 = 0 ;
v <
>v ; do { // set x1 to 0;
>00g1-00pv ; #00 -= 1 ;
v <
>000g1pv ; #[#00]1 = 0 ;
v <
>00g0`v; } while (#00 > 0) ;
v <
^_v
v <
>25*:*00pv ; #00 = 100 ;
v <
>v ; do { // b = 0 .. #00;
>10g1+10pv ; #10 += 1 ;
v <
>020pv ; #20 = 0 ;
v <
>v ; do { // c = 0, b, 2b .. #00;
>20g10g+20pv ; #20 += #10 ;
v <
>20g1g!20g1pv ; #[#20]1 = !#[#20]1 ;
v <
>00g20g`v; } while (#00 > #20) ;
v <
^_v
v <
>00g10g`v; } while (#00 > #10) ;
v <
^_v
v <
>v ; do { // print the results ;
>00g1-00pv ; #00 -= 1 ;
v <
>00g1g1-v ; if (!#[#00]1 != 1) ;
v <
v_v
v<
>00g.v ; print_num(#00) ;
v < ; } ;
>00g0`v; } while (#00 > 0) ;
v <
^_v
v <
>@ ; exit() ;

100% homebrewn befunge code made from some sort of pseudocode.

Non-brute force solution will come soon!

McLenin2009-08-05 17:12

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).

Avorntur2009-08-05 17:13

C#:

static List<long> getOpenLockers(long numberOfLockers)
{
List<long> openLockers = new List<long>();

for (long i = 1; i*i < numberOfLockers; i++)
{
openLockers.Add(i*i);
}
return openLockers;
}

John Evans, btradish@earthlink.net2009-08-05 17:16

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.

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?

Stephen2009-08-05 17:25

python:
def getOpenLockers(lockers):
import math
openLockers = []
for i in range(1,int(math.sqrt(lockers))+1):
openLockers.append(i*i)
return openLockers

Sebbe2009-08-05 17:25

Well, the lockers toggle once for each divisor in the number, so here's a Mathematica oneliner:

Toggles-
Zero: Lockers on a different hallway/outside range.
One: 1
Two: Primes
Three: Squares of Primes
Four: Product of two Primes; Cubes of Primes
Five: Fourth powers of Primes
and so on in that manner

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

Sebbe2009-08-05 17:38

Maurits:

Correct, with the caveat that the case n = 1 needs to be checked explicitly since the prime factorization is empty.

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.

McLenin2009-08-05 17:40

Just on update on my whitespace code (this time with comments):

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 (2009-08-05 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

ponky2009-08-05 17:53

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.

Ninjamobile2009-08-05 17:56

<Excel VBA Code>

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>

Timothy De La Reigne2009-08-05 18:14

Scot:

Applying my knowledge of cribbage

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.

John Fouhy2009-08-05 18:16

Maurits:

Follow-up question: which lockers are toggled the LEAST?

That's easy: Locker #1 :-)

(ok, gur cevzrf come second equal)

Mr.'; Drop Database --2009-08-05 18:20

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.

You are a fuckwit2009-08-05 18:22

reallyAmazed:

simply - squares of prime numbers (or perfect squares)

I'm amazed with amount of i^2 solutions. Think a bit longer before posting.

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)

Timothy De La Reigne2009-08-05 18:24

azredwing:

that's the difference between mediocre and good programmers, or even good and great.

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)

Mathamagician2009-08-05 18:26

Tama:

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.

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....

you are a fuckwit2009-08-05 18:29

reallyAmazed:

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)

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???

mmmkay2009-08-05 18:32

I've had this as an interview question. Didn't even get the job.

Follow-up question: which lockers are toggled the LEAST?

The Prime Numbers, of course. They are only toggled twice!!

Jabluki2009-08-05 18:55

Steve:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

Follow-up to Follow-up: What will the state of the lockers be after n steps of the brute force solution?

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>

Mad2009-08-05 18:58

Streeaker:

If the same hallway and rules were used for every "locker challenge" in the story, the best solution would have been to just remember the results from the last time. For bonus points, prank the teacher by putting stickers on the inside of the appropriate lockers saying This locker will be open.

(Captcha = paratus, latin for "ready". Hmm...)

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?

Mark V Shaney2009-08-05 19:14

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!

Mark V Shaney2009-08-05 19:15

Jimbo:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

The Prime Numbers, of course. They are only toggled twice!!

Nope. The locker 1 is only toggle once. Furthermore, it is not a prime locker.

zetetic2009-08-05 19:42

I don't understand this problem.
What is the actual point of the problem?
Doesn't make any sense.

devbanana2009-08-05 19:54

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:

x^a * y^b * z^c ...

Then the number of factors, and the number of times it has been toggled is:

public function __construct($number, $status)
{
if (!is_int($number))
{
throw new invalid_argument_exception('$number must be an integer.');
}
if ($number <= 0)
{
throw new invalid_argument_exception('$number must be a positive integer.');
}
if (!is_bool($status))
{
throw new invalid_argument_exception('$status must be a boolean.');
}

/**
* This function was inspired from the prime factorisation JavaScript calculator
* at http://www.btinternet.com/~se16/js/factor.htm
*/
function getPrimeFactors($number)
{
$primeFactors = array();

echo "<p>The following lockers have been toggled the most with " .
$mostToggledLockers[0]->getTimesToggled() . " toggles:</p>";
echo "<ul>\n";
foreach ($mostToggledLockers as $mostToggledLocker)
{
echo "<li>" .
$mostToggledLocker->getNumber() .
"</li>\n";
}
echo "</ul>";

$endTime = microtime(true);

$timespan = $endTime - $startTime;

echo "<p>Calculated in " .
number_format(round($timespan, 5), 5) .
" seconds. Take that, jocks!</p>";

// This script was for the programming practice at
// http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx

?>

Output:

There are 100 lockers.

10 lockers are opened, and 90 lockers are closed.

The following lockers are opened:

* 1
* 4
* 9
* 16
* 25
* 36
* 49
* 64
* 81
* 100

The following lockers have been toggled the most with 12 toggles:

* 60
* 72
* 84
* 90
* 96

Calculated in 0.00551 seconds. Take that, jocks!

Xythar2009-08-05 19:57

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.

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.

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 twenty-eighth 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

Bruno2009-08-05 20:11

Mark V Shaney:

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!

Why is it the slowest people always seem to think that their feats are impressive?

Jimbo2009-08-05 20:13

Mark V Shaney:

Jimbo:

Maurits:

Follow-up question: which lockers are toggled the LEAST?

The Prime Numbers, of course. They are only toggled twice!!

Nope. The locker 1 is only toggle once. Furthermore, it is not a prime locker.

WHOOPS - I realised that afterward (and kinda waondered how long before someone else would have a go)

curtmack2009-08-05 21:32

Wow. Your Befunge is way better than mine, Tim.

For what it's worth, here's my version. (It just prints out squares.)

&01p1 >::*01g`!#v_@
>1+^
^ ,*25.*::<

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.)

Sv3n2009-08-05 21:33

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.

RogerInHawaii2009-08-05 21:36

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.

ThatsALotOfGravy2009-08-05 21:48

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 depends on whether the locker number has an even or odd number of factors, even number = closed, odd number = open. Factors come in pairs unless the number is a square number where there is only a single factor multiplied by itself therefore if the number is a square then the locker is open otherwise closed. Simple really.

spiderlama2009-08-05 22:46

Python:

from math import sqrt
from math import floor

def getOpenLockers(lockerCount):
return [i * i for i in range(1, floor(sqrt(lockerCount)) + 1)]

Rand2009-08-05 22:49

I got this question in an interview at an Internet start-up. I solved in a few minutes (the previous poster stated the solution). I didn't get the job though, in part because they didn't like the -way- that I solved it :rolleyes. The whole thing was an Interview 2.0.

The "nerds" in these classes must have been real idiots to have never solved it faster than the jocks. I spent a few minutes on it, but even on paper you wouldn't get more than a couple iterations in, much less actually using physical lockers. I'm fairly intelligent, but even in high school I wasn't top of my class (~11 out of 250, though I was kinda lazy, that's why I like computers).

Lockers 12, 18, 20, 28, 32, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, and 99 were toggled 6 times

Lockers 64 was toggled 7 times

Lockers 24, 30, 40, 42, 54, 56, 66, 70, 78, and 88 were toggled 8 times

Lockers 36, and 100 were toggled 9 times

Lockers 48, and 80 were toggled 10 times

Lockers 60, 72, 84, 90, and 96 were toggled 12 times

Daniel2009-08-05 23:04

There are 5 lockers that were toggled 12 times.

Lockers 60, 72, 84, 90, and 96.

Richard2009-08-05 23:17

This first, it gets toggled only once, and remains open.

Bean2009-08-05 23:19

"The nerds never stood a chance, especially when it came to his "locker challenge.""
lol, it took me less than 5 minutes to figure out that it was perfect squares, and judging by this article, those nerds are unworthy of the title for having so much trouble figuring it out.

TR2009-08-05 23:39

Um...that's a WTF in itself. The only locker that is toggled
only once: #1.

Ransom2009-08-05 23:52

ruby makes me happy - so quick to write

def jocks(lockers, curr = nil, i = nil)
if curr.nil? && i.nil?
jocks(lockers, 1, 1)
else
if curr > lockers
return []
else
newcurr = curr + (i * 2) + 1
[curr].concat(jocks(lockers, newcurr, i+1))
end
end
end
puts jocks(100).inspect

sokolomo2009-08-05 23:55

given BruteForce is O(1) this problem appears to have amazingly less to do with a ftw.

DaveGamble2009-08-06 00:06

Huh? No C++ Template Metaprogramming solution? Ok then:

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

Private result Eval("'Open lockers: ' + #LockersOpen")
MsgBox #result
Stop

/* Params: LockerCount
* Return: LockersOpen
*/
Function GetOpenLockers:
Var LockersOpen ''
Private i 1
GOL_Loop:
Private Sqr Eval("%i * %i")
Var LockersOpen Eval("#LockersOpen + #Sqr")
Var LockersOpen Eval("#LockersOpen + ' '")
Private i Eval("%i + 1")
If Eval("%Sqr < 100") Goto GOL_Loop
EndFunction

Charlie2009-08-06 02:58

So... the number of times locker n is toggled is the number of divisors it has in the set of integers from 1 to 100. If locker n has an odd number of divisors (like that first locker does, having only one as a divisor) it ends up open. Otherwise, closed.

The teacher isn't really being very nice to the nerds here. If this had a really simple formula, wouldn't that mean we could easily do things like find primes and factor large numbers? You know, those things we base encryption on?

Tim2009-08-06 03:20

25*:*00p010p0>1+:10p:*:. v;
|`*:\g00:g01<
@

Ultra-compact Befunge, made from:

v ; // 00 - num lockers ;
v ; // 10 - current step ;
>25*:*00pv ; #00 = 100 ;
v <
>010pv ; #10 = 0 ;
v <
>v ; do { ;
>10g1+10pv ; #10 = #10 + 1 ;
v <
>10g:*.v ; print_num (#10 * #10) ;
v <
>00g10g:*`v ; } while (#00 > #10 * #10) ;
v <
^_v
v <
>@ ; exit();

This version contains 0% brute force.

smartass2009-08-06 03:22

Thats an easy one. There is only one locker that gets toggled only once. All others are toggled in the first round and in their round (at least).

Charlie2009-08-06 03:27

Wait, let me reason this out a little more.

Every number will have one and itself among its divisors. Except for locker 1, that's two free toggles for everybody, which cancel one another out as far as the final open/shut state goes.

For locker n, if n is prime, that's it. No more divisors and the locker will end up shut.

If n is a perfect square, the square root of n will be another factor, so in that case we'll add another toggle and call it open.

Of course, the perfect square can easily still have other divisors we haven't considered yet. 16 for example has 2 and 8. 100 has a bunch. Somehow we still need to show that there will be an even number of these... argh, it's late. Maybe I'll wake up seeing the obviousness of it...

CSK2009-08-06 03:27

Too tired to read through all the comments but I saw an awful lot of 1+3+5+7+9+11... stuff in there being used as arguments against the i^2 method.

It's the same thing.
using i as an iterator in F(i)
F(i) returns the i'th locker to end in an open state.
define F(1) = 1 (to make it explicit that i is not a zero based index)
d is the absolute difference between F(i) and F(i-1)
F(i)-F(i-1) = 2i - 1 as proven below.
i^2 - (i-1)^2 = d :
i^2 - (i^2 -2i + 1) = d :expand (i-1)^2
i^2 - i^2 + 2i -1 = d :extract terms from parenthesis
2i - 1 = d :cancel i^2 terms

So yes guys. the difference between two adjacent squares is double the larger root minus 1.

Given that modern processors can do multiplication in just as many clock cycles as addition, the i+d method requires more registers to run and is probably going to be slightly slower than the i^2 method. Additionally, i^2 is easier to understand and maintain later.

Charlie2009-08-06 03:33

Charlie:

Wait, let me reason this out a little more.

Every number will have one and itself among its divisors. Except for locker 1, that's two free toggles for everybody, which cancel one another out as far as the final open/shut state goes.

For locker n, if n is prime, that's it. No more divisors and the locker will end up shut.

If n is a perfect square, the square root of n will be another factor, so in that case we'll add another toggle and call it open.

Of course, the perfect square can easily still have other divisors we haven't considered yet. 16 for example has 2 and 8. 100 has a bunch. Somehow we still need to show that there will be an even number of these... argh, it's late. Maybe I'll wake up seeing the obviousness of it...

Oh wait... it is simple. If n isn't a perfect square, you can pair off all its factors with the one number they'll need to multiply in order to get n.

If n is a perfect square, its square root can pair only with itself. Our locker game doesn't let you count a factor twice this way. On our "10" round, locker 100 gets touched once.

That's basically the whole thing right there. Why all the code solutions anyway? That's little better than the jocks here.

Marc de Jonge2009-08-06 03:44

In Haskell, using prime factorization:

primes :: Int -> [Int]
primes n = 2: (sieve [3,5..n])
where
sieve (x:xs)
| x * x < n = x: (sieve $ filter (\y -> y `mod` x /= 0) xs)
| otherwise = (x:xs)

factorCount :: Int -> [Int]
factorCount x = count 0 x (primes 100)
where
count 0 1 _ = []
count c 1 _ = [c]
count 0 x (p:ps) = if x `mod` p == 0 then count 1 (x `div` p) (p:ps) else count 0 x ps
count c x (p:ps) = if x `mod` p == 0 then count (c + 1) (x `div` p) (p:ps) else c:(count 0 x ps)

timesTouched :: Int -> Int
timesTouched n = foldl addSum 1 $ factorCount n
where
addSum :: Int -> Int -> Int
addSum x y = x * (y + 1)

learn test $howMany {
if $howMany < 1 {
print "no lockers, no party..."
forward 20
exit
}
}

# algorithm:
# the locker is toggled if it is evenly divisible for a predecessor
# test it for every predecessor
learn getOpenLockers $nLockers {
test($nLockers)
# 1 is ever unlocked
print 1
forward 20
# we start from 3 because 2 is ever locked
for $currentLocker = 3 to $nLockers {
$thisLocker = $closed
for $prevLocker = 2 to ($currentLocker -1) {
# is evenly divisible, aka remainder is 0 ?
if ((round($currentLocker / $prevLocker)) * $prevLocker) == $currentLocker {
$thisLocker = toggle ($thisLocker)
}
}
# output
if $thisLocker == $opened {
print $currentLocker
forward 20
}
}
}

# now, for real :D
learn TR_getOpenLockers $nLockers {
test($nLockers)
for $i = 1 to round((sqrt($nLockers))-0.5) {
print $i * $i
forward 20
}
}

print "not really... :D "
forward 20
TR_getOpenLockers ($howmanyLockers)
print "_this_ is the end... :)"
forward 20

Repetition makes it right?2009-08-06 04:39

That sounds fine and dandy, but 36 doesn't stay closed... (see brute force js-implementation in original Praxis posting).

Have you tried the brute force approach or did you just come up with a fancy "solution" to a problem and want to advertise it even though it's incorrect?

P.M.Lawrence2009-08-06 04:59

In case anyone is interested, this problem (only, with light switches) is covered at http://www.math.hmc.edu/funfacts along with many others.

JoeBar2009-08-06 05:02

The principle is very simple. Count the divisors of any number, including 1 and itself, and you get the number of times it's switched. If it's odd then it remains open.

#! /usr/bin/ruby
# function to determine which lockers will be open at the end of
# http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx

def getOpenLockers(n)
lockers = Array.new
(1..n).each do |i|
open = true
(2..i).each do |j|
if (i%j == 0)
open = !open
end
end
if (open)
lockers << i
end
end
lockers
end

puts getOpenLockers(100)

The least switched number are of course the prime numbers, switched two times, and the 1, switched one time. The most switched are the numbers who have the greatest amount of divisors.

Massimo2009-08-06 05:04

The first one, obviously. It's always toggled only one time.

VKS2009-08-06 05:07

The 'most' and 'least' questions are trivial. The least triggered locker is the first one, which only gets triggered once. The most triggered locker is the sixtieth, because it's a Highly Composite Number.

(Lockers are triggered whenever the number that comes up in the list is a divisor of the locker's number.)

Come to think about it, a locker is left open if it is toggled an odd number of times. In other words, a locker is left open only if its number has an odd number of divisors. But for every divisor of a number, there is another number, lockerNumber/divisor, which is also a divisor. Divisors come in pairs, in other words, which means numbers have an even number of divisors. Unless the number is square, at which point lockerNumber/divisor = divisor for one and only one divisor, the square root, which means it doesn't form a pair. So only squares have odd numbers of divisors. So only square numbered lockers are left open. That makes ten of them, since only the numbers one through ten have squares between one and one hundred inclusive.

10

...

Alright, I'll make a code solution, just give me a minute...

getOpenLockers' n = map (\x->x*x) [1..(floor $ sqrt n)]

But the more normal solution is probably something along the lines of

factorList n = filter ((== 0) . (mod n)) [1..n]
getOpenLockers n = map fst $ filter (\(a,b)->odd $ length b) $ zip [1..n] $ map factorList [1..n]

pjt332009-08-06 05:54

Maurits:

Sebbe:

n will have distinct divisors

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?

Yes, but doing it efficiently is tricky.

To find the maximum number of divisors you need to find the largest highly composite number in the set - we'll call it n0 <= N. I don't know an easy way of generating highly composite numbers other than by filtering products of primorials. So

Step 1. Generate a list of primorials q_i <= N. This is easy - q_i is the product of the ith smallest primes (so q_0=1, q_1=2, q_2=2*3, q_3=2*3*5, q_4=2*3*5*7, q_5=2*3*5*7*11, etc.) We shall ignore q_0 subsequently, since it's not very helpful here.
Step 2. For each number formed by the product of powers of primorials which is <= N (that part is a bit messy) compute the number of divisors. This is again easy - you effectively already have the factorisation. Select the largest number of divisors, and call that d.
Step 3. Find all numbers <= N with d divisors: for every factorisation of derive a prime structure and use on small primes until you exceed N.

Worked example: N = 100.
Step 1: Primorials <= 100 are 2, 6, 30.
Step 2: Candidates are the primorials themselves (30 has 6 divisors), powers of two (64 has 7 divisors), powers of two multiplied by 6 (96 has 12 divisors), powers of two multiplied by 36 (72 has 12 divisors), and 2*30 = 60 (12 divisors). So d=12.
Step 3: 12 factors as 1*12, 2*6, 2*2*3, 3*4; the corresponding prime structures are p0^11, p0^5 * p1, p0^2 * p1 * p2, p0^3 * p1^2.
p0^11: No solutions <= 100
p0^5 * p1: 2^5 * 3 = 96
p0^2 * p1 * p2: 2^2 * 3 * 5 = 60, 2^2 * 3 * 7 = 84, 3^2 * 2 * 5 = 90
p0^3 * p1^2: 2^3 * 3^2 = 72

So the solution set is {96, 60, 84, 90, 72}.

Addendum (2009-08-06 06:02): s/for every factorisation of derive/for every factorisation of d, derive/

Addendum (2009-08-06 06:22): s/30 has 6 divisors/30 has 8 divisors/

2ti6x2009-08-06 05:54

the first, duh!

k12009-08-06 06:13

k1:

Logo (KTurtle)

for $currentLocker = 3 to $nLockers {
$thisLocker = $closed
for $prevLocker = 2 to ($currentLocker -1) {

Well, I've realized that the test can stop at the half of the current locker number/position. So...

[code]
for $prevLocker = 2 to (round($currentLocker/2)) {
[code]

And, yes, I've learned the use of the "code" tag ^_^;

CYA

k12009-08-06 06:16

k1:

[code]
for $prevLocker = 2 to (round($currentLocker/2)) {
[code]

And, yes, I've learned the use of the "code" tag ^_^;

D'OH! >_<;;;

.. ....'s Hospital for the Nameless2009-08-06 06:49

Though it is a brute-force way of doing it - at least it is a solution in R.

for me, I saw the pattern +3, +5 , +7, +9, +11, +13, +15, +17 and +19

not i^2

2nd derivative of x^2: 2
3rd derivative of x^3: 2 * 3
...
Nth derivative of x^N: N!

Pick any sequence of powers to the N, write the difference of subsequent powers, then write the difference of subsequent differences, N times (after that all differences are zero). The differences at the Nth level will always be N!.

This is a fun fact that made me happy as a kid.

Mike2009-08-06 07:05

Since that was such fun, how about this:

"A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

Dave2009-08-06 07:09

That is probably the least efficient algorithm for finding perfect squares I could think of.

Here's a better (still shitty) one that runs in O(logN) -ish time.

void find_open_lockers(char *lockers[], int num_lockers)
{
int i = 1;

do {
lockers[(i*i)-1] = 1;
i+=1;
if ((i*i) >num_lockers) return;
} while (1)

}

workmad32009-08-06 07:11

Looked at the comments too soon.

I was working through the problem (without the timer as I'm a coward ;)) and had gotten to the fact that it comes down to the number of factors (or rather the oddness/evenness of the number of factors). I hadn't made the step to the fact that only square numbers have an even number of factors though, so failed at the challenge :(

That said, here's a quick python solution anyway ;)

def lockers(no_of_lockers):
return [i**2 for i in range(1, int(no_of_lockers**0.5) + 1)]

Addendum (2009-08-06 07:33): Wow... looks like that's the shortest python solution so far.

Has everyone else posting python forgotten about list comprehensions, the built-in power operator and the fact that int() performs a floor? As shown, makes it a one-liner :)

Addendum (2009-08-06 07:35): Also, I meant in my original post that I hadn't noticed that only squares had odd numbers of factors, not even.

The General2009-08-06 07:49

Sv3n:

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.

Proof that without work, there's no Collatz.*

Actually this appears not to be the Collatz theorem (or really the Collatz conjecture) anyway - that's the one about the sequence of numbers generated by the rule "if N is even, halve it, else triple it and add 1". The Collatz conjecture is that if N starts as a positive integer, it always reaches the value 1.

This assumes that the ForEach extension-function for IEnumerable is defined, which in my projects it always is. But the Mofties forgot it somehow, so with plain .NET 3.5 you have to define it yourself or work around it like

new List<int>(Squares(100)).ForEach(Console.WriteLine);

Captcha: "validus", so I guess I have to provide the proof:
Every door is open that gets toggled an odd number of times.
The number of times each door is toggled is equal to its number of dividers (follows directly from the used algorithm).
If X is the number of doors, then for each divider N of X that is smaller than sqrt(X) there must be a number M greater than sqrt(X) such that N*M = X (else N wouldn't be a divider of X and if M <= sqrt(x) then N*M < sqrt(x)*sqrt(x) = X). So M is a divider of X, too, which makes the number of dividers even, except when sqrt(X) is itself an divider of X, which is true only for square-numbers.
So the open doors correspond to all square numbers (including 1) smaller or equal than X.

BTW: The Jocks still won in my case :-/

pjt332009-08-06 07:58

Mike:

Since that was such fun, how about this:

"A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

What's the graph of permitted movement between houses? K5? And is he allowed to visit the fifth house only once?

If my understanding of the problem is correct then the answer is 1, and he leaves 2 rabbits in each house. One way to accomplish this is to visit each house except the fifth twice.

Hizard2009-08-06 08:27

1 will be toggled least :)

Hans2009-08-06 08:37

Welbog:

moltonel:

Welbog:

That's good because I don't find solving solved problems to be fun in the first place.

So... Not having fun in your job as a programmer ?

Not particularly.

I've worked with guys like you: math background (right?), thinks of himself as much better than all those lowly computer scientists around him, hired as a programmer because there is zero money in math, but refuses to do menial work like actually programming because there's just no challenge in it for a genius like himself.

I've also seen the disorganized piles of shit that such people call code, after they had finally left. And then I'm grateful I don't work with them right now.

Anyway, I feel for you: living between all those stupid people, and chances are you will _never_ solve a new problem in your life. Happiness must be hard to reach under those conditions...

!?2009-08-06 08:41

Ozmo:

I would bet that Mr. Zargas was the coach of the football team. This challenge is EXTREMELY biased towards the jocks. I respectfully submit that in order to figure out the function, you HAVE to iterate (brute force) at SOME point in time.

SHENANIGANS!

And the jocks would never lose track of which locker they should toggle.... Yeah, right.

db22009-08-06 08:48

Here it is on an HP 48. Replace SQRT with the proper square root symbol.

<< SQRT IP -> L
<< 1 L
FOR C C SQ
NEXT L ->LIST
>>
>>

Compiles to 57.5 bytes on the calculator. (Yes, it uses half-byte addressing.)

campkev2009-08-06 09:12

Mrs MeChokemchild:

Everybody failed this test. Have you read the problem?

Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.

It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door". The sample solutions for n=1 and n=4 are also wrong. It should be: f(1)={1} and f(4)={1;2;3;4}. So TDWTF failed its own test. The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

And your form is broken, it doesn't submit.

No, you failed the reading test.

Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.

Thanks for playing though.

highphilosopher2009-08-06 09:16

public class LockerPicker
{
private int _numberOfLockers;
public Boolean[] _lockerArray;

public LockerPicker(int numberOfLockers)
{
_numberOfLockers = numberOfLockers;
_lockerArray = new Boolean[_numberOfLockers+1];
_lockerArray.Initialize();
for (int i = 1; i < _numberOfLockers; i++)
{
if ((i * i) > _numberOfLockers)
{
break;
}
else
{
_lockerArray[i * i] = true;
}
}
}
}

Edmund2009-08-06 09:28

Is it just me, or did the nerds at Cliffmont High really suck?

I mean, that took me about a minute to figure out that the open doors are square numbers - IN MY HEAD. Maybe I am being unrealistic about the quality of teaching offered by Mr Zargas, but I would hope that several members of the high school football team would have been able to figure it out.

Errant2009-08-06 09:33

This is more of a logic puzzle - you could sit and work it out mathematically or just apply simple logic and figure that the answer is that every 2xN locker in sequence.

Or:

# 1 must always remain open
# 2 is the first divider, by logic
diff = 2
open = [1]
last = 1
while last < 100:
last = last + diff
diff = diff * 2
open.append(last)
print "these are open",open

(the above is just made up - but it shgould work-ish)

Bodestone2009-08-06 10:01

SQL using a tally (or numbers) table

CREATE FUNCTION getOpenLockers(@lockerCount INT)
RETURNS TABLE
AS
RETURN
SELECT POWER(N,2) AS openLockers
FROM dbo.Tally
WHERE N BETWEEN 0 AND @lockerCount
AND POWER(N,2) <= @lockerCount

Zed2009-08-06 10:14

Maurits:

Follow-up question: which lockers are toggled the LEAST?

That's easy locker 1.. it's only toggled once.
--Zed

jmibanez2009-08-06 10:27

I did this same problem in Erlang, just because: http://people.orangeandbronze.com/~jmibanez/lockers.erl

More complicated would be to find the initial configuration, given a final one (actually, the algorithm is time invariant, so it is equivalent to beggining->end).

ADC Beast2009-08-06 11:00

> Follow-up question: which lockers are toggled the LEAST?

Once you've found the simple formula for whether any given locker ends up open or closed, your question is really easy to answer.

Locker number 1 is only toggled once, all the others are toggled at least twice. After that the lockers with prime numbers are toggled twice each, non-primes will be more than that.

Jorge2009-08-06 11:11

By the way, the proportion of toggled lockers follows an inverse square root,

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.

Depends - if the teacher asked the class not to repeat it, likely it wouldn't wander too much. (Possibly it gets mixed up a bit year to year as well). But full marks would be putting something in the lockers (little gnome saying "Open!"?), so that the jocks reveal the answer as they start.

Doesn't surprise me that the nerds had problems though - the obvious method is barred, and you're under both time and social pressure. Not the best conditions for thinking.

Also, 1sec/locker is very generous - I'd expect to see them moving much faster than that (considering you have multiple people, the first few iterations are easy to delegate).

metageek2009-08-06 11:26

So, the trick is to note that the number of times a locker gets toggled is the number of factors is has:

def numFactors(n):
count=0
for i in range(1,n):
if n%i==0:
count+=1
return count

def opened(n):
for i in range(1,n+1):
if numFactors(i)%2==0:
yield i

print list(opened(100))

I got this banged out before the simulated jocks finished their first pass.

calipygous2009-08-06 11:36

haskell:

map (\x->x^2) [1..10]

Wongo2009-08-06 11:48

Daniel:

Sinclair ZX81 / Timex TS100 (via emulator):

If I remember correctly, you could refactor lines 40 and 80 into "IF I>N THEN STOP", which would effectively:

1) save one byte inside each of those lines (for the adress byte)

and 2) remove line 160 altogether, which saves yet another byte.

This refactoring gives you three more bytes into which you can cram most anything you fancy: up to three instructions, or up to 24 bits of data, or any combination of the two! Las Vegas, baby!

Ahhh, good ole 1 KB RAM times...

sirxnom2009-08-06 11:59

Heres an implementation in ZOMBIE (Zombie Oriented Machine Being Interface Engine)

// Declare variables num, zombie1, zombie2,
num is a zombie
summon
remember 100
bind

zombie1 is a zombie
summon
remember 1
bind

zombie2 is a zombie
summon
remember 1
bind

//Declare variables for implementing multiplication through repeated addition.
//Since zombies can only hold one value a temp value must be declared to hold the result.

operandA is a zombie
summon
bind

operandB is a zombie
summon
bind

temp is a zombie
summon
bind

multiply is a zombie
summon
remember 0
shamble
temp remember moan temp moan operandA //Equivalent to temp=temp+operandA
remember moan 1 //Increments counter.
until remembering operandB //Stops counter when operandB has been reached.
bind

ToggleThem is a zombie
summon
shamble
operandA remember moan zombie1 //
operandB remember moan zombie1 // Squares zombie1 and stores in temp.
animate multiply //

zombie1 remember moan zombie1 moan zombie2 //Increments zombie1
say temp //outputs temp
until temp is greater than or equal to num //stops when temp (which is perfect squares,
//is greater then or equal to num.
animate

Maurits2009-08-06 12:03

pjt33:

Maurits:

Sebbe:

n will have distinct divisors

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?

Yes, but doing it efficiently is tricky.

To find the maximum number of divisors you need to find the largest highly composite number in the set - we'll call it n0 <= N. I don't know an easy way of generating highly composite numbers other than by filtering products of primorials. So

Step 1. Generate a list of primorials q_i <= N. This is easy - q_i is the product of the ith smallest primes (so q_0=1, q_1=2, q_2=2*3, q_3=2*3*5, q_4=2*3*5*7, q_5=2*3*5*7*11, etc.) We shall ignore q_0 subsequently, since it's not very helpful here.
Step 2. For each number formed by the product of powers of primorials which is <= N (that part is a bit messy) compute the number of divisors. This is again easy - you effectively already have the factorisation. Select the largest number of divisors, and call that d.
Step 3. Find all numbers <= N with d divisors: for every factorisation of derive a prime structure and use on small primes until you exceed N.

Worked example: N = 100.
Step 1: Primorials <= 100 are 2, 6, 30.
Step 2: Candidates are the primorials themselves (30 has 6 divisors), powers of two (64 has 7 divisors), powers of two multiplied by 6 (96 has 12 divisors), powers of two multiplied by 36 (72 has 12 divisors), and 2*30 = 60 (12 divisors). So d=12.
Step 3: 12 factors as 1*12, 2*6, 2*2*3, 3*4; the corresponding prime structures are p0^11, p0^5 * p1, p0^2 * p1 * p2, p0^3 * p1^2.
p0^11: No solutions <= 100
p0^5 * p1: 2^5 * 3 = 96
p0^2 * p1 * p2: 2^2 * 3 * 5 = 60, 2^2 * 3 * 7 = 84, 3^2 * 2 * 5 = 90
p0^3 * p1^2: 2^3 * 3^2 = 72

So the solution set is {96, 60, 84, 90, 72}.

Addendum (2009-08-06 06:02):
s/for every factorisation of derive/for every factorisation of d, derive/

Addendum (2009-08-06 06:22):
s/30 has 6 divisors/30 has 8 divisors/

Beautiful.

A suggested rewording of step 2:
Suppose the largest primorial <= N is 2*3*5*...pk

Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

Indrora2009-08-06 12:10

Its interesting to see so many implementations in java, C, Haskell, etc. but only... 3 on calculators?!?!

now if i really wanted to i could make it output a list. But thats more code, and its trivial to add stuff later :) Plus you're not a great nerd if you cant at least keep the first 20 squares in your head.

pjt332009-08-06 12:51

Maurits:

A suggested rewording of step 2:
Suppose the largest primorial <= N is 2*3*5*...pk

Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

From an implementation point of view that's almost certainly a more useful way of thinking about it, although the logs are mainly useful as documentation - it's almost certainly more efficient to stick to doing multiplication until you exceed N. I'm almost at the point of actually sitting down to write the code and then doing some profiling for N in the order of 10 million.

Ed2009-08-06 13:01

Interesting that the lockers remaining toggled are the squares of the first 10 digits (1^2=1,2^2=4,...,10^2=100)

Martin2009-08-06 13:10

Zack:

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.

Given that answer you suggested is totally wrong, it is perfectly possible that the nerds abide by your advice and still lose.

NotaProgrammer2009-08-06 13:17

Now a good follow up would be to solve for a more general case.

Let's say the inputs are toggle all the lockers for numbers between arbitrary limits (i.e. 100 lockers, toggle by 4-12).

WildCard2009-08-06 13:18

Easy answer: locker #1, it is toggled only during the first initial toggle and then never touched again.

KukkerMan2009-08-06 13:22

A not too pretty solution in piet:

Lithp2009-08-06 13:49

That was my initial solution as well. Technically, it was more along the lines of:

So, the trick is to note that the number of times a locker gets toggled is the number of factors is has (...)

(Was replying to this, erh.)

Paul N2009-08-06 13:55

Charlie:

Why all the code solutions anyway? That's little better than the jocks here.

Because that is the challenge:

The rules to your challenge are just as simple. Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above. There should be one input to the function (number of lockers) and one output (representation of which lockers remain open; string, array, etc).

Maybe you can write a mathmatical function with one input and one output instead?

Maurits2009-08-06 13:57

pjt33:

Maurits:

A suggested rewording of step 2:
Suppose the largest primorial <= N is 2*3*5*...pk

Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

From an implementation point of view that's almost certainly a more useful way of thinking about it, although the logs are mainly useful as documentation - it's almost certainly more efficient to stick to doing multiplication until you exceed N. I'm almost at the point of actually sitting down to write the code and then doing some profiling for N in the order of 10 million.

A rough sketch of an implementation, glossing over some steps which would be interesting problems themselves:

given N, find the set of lockers that are toggled the most times

find the smallest locker that was toggled the most times
- find the list of primes less than or equal to N (sieve of Eratosthenes, say)
- find largest primorial 2*3*5*...*p <= N
- note the largest prime, p
- e.g. if N = 100
- 2 = 2
- 2 * 3 = 6
- 2 * 3 * 5 = 30
- 2 * 3 * 5 * 7 = 210
- so the largest primorial <= 100 is 2 * 3 * 5
- note the largest prime is 5

- construct the set of numbers of the form
- - c = 2^n1 * 3^n2 * ... * p^nk
- (that "p" is the specific prime from the largest primorial <= N)
- where c <= N, and n1 >= n2 >= ... >= nk >= 0
- - for (n1 = floor(log2(N)); n1 > 0; n1--)
- - - for n2 = floor(log3(N/2^n1)); n2 >= 0; n2--)
- - - - ...
- (yes, it is possible to nest arbitrarily many loops - you just have to be clever)
- find the elements of the set that maximize the product (n1 + 1)(n2 + 1)...(nk + 1)
- THOSE ELEMENTS INCLUDE THE SMALLEST LOCKER
- and THE MAXIMUM PRODUCT IS THE NUMBER OF TOGGLES
- call the number of toggles t
- e.g. if N = 100
- c = 2^n1 * 3^n2 * 5^n3 - want to maximize (n1 + 1)(n2 + 1)(n3 + 1)
- n1 <= log2(100) = 6.6
- take n1 = 6 through 0 in turn
- n1 = 6:
- - 2^6 = 64 brings the residue of N down to 1.56 so n2 can only be 0
- - - 2^6 * 3^0 * 5^0 = 64: product = (6 + 1) = 7
- n1 = 5:
- - 2^5 = 32 brings the residue of N down to 3.125 so n2 can only be as high as 1
- - - 2^5 * 3^1 = 96 brings the residue of N down to 1.04 so n3 can only be 0
- - - - 2^5 * 3^1 * 5^0 = 96: product = (5 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST
- - - - 2^5 * 3^0 * 5^0 is dominated by 2^5 * 3^1 * 5^0
- n1 = 4:
- - 2^4 = 16 brings the residue of N down to 6.25 so n2 can only be as high as 1
- - - 2^4 * 3^1 = 48 brings the residue of N down to 2.1 so n3 can only be 0
- - - - 2^4 * 3^1 * 5^0 = 48: product = (4 + 1)(1 + 1) = 10
- - - - 2^4 * 3^0 * 5^0 is dominated by 2^4 * 3^1 * 5^0
- n1 = 3:
- - 2^3 = 8 brings the residue of N down to 12.5 so n2 can only be as high as 2
- - - 2^3 * 3^2 = 72 brings the residue of N down to 1.4 so n3 can only be 0
- - - - 2^3 * 3^2 * 5^0 = 72: product = (3 + 1)(2 + 1) = 12 TWELVE IS THE BIGGEST
- - - 2^3 * 3^1 = 24 brings the residue of N down to 4.1 so n3 can only be 0
- - - - 2^3 * 3^1 * 5^0 is dominated by 2^3 * 3^2 * 5^0
- - - 2^3 * 3^0 * 5^0 is dominated by 2^3 * 3^2 * 5^0
- n1 = 2:
- - 2^2 = 4 only brings the residue of N down to 25 so n2 is restricted only by n1
- - 2^2 * 3^2 = 36 brings the residue of N down to 2.7 so n3 can only be 0
- - - 2^2 * 3^2 * 5^0 = 36: product = (2 + 1)(2 + 1)(0 + 1) = 9
- - 2^2 * 3^1 = 12 brings the residue of N down to 8.3 so n3 is restricted only by n2
- - - 2^2 * 3^1 * 5^1 = 60: product = (2 + 1)(1 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST
- - - 2^2 * 3^1 * 5^0 is dominated by 2^2 * 3^1 * 5^1
- - 2^2 * 3^0 * 5^0 is dominated by 2^2 * 3^1 * 5^1
- n1 = 1:
- - these are all dominated by 2^2 * 3^1 * 5^1
- n1 = 0:
- - this is dominated by, um, everything
- smallest locker is in {60, 72, 96}, number of toggles is 12

find the set of lockers that are toggled t times
- find the prime factorization of t = p1^k1 p2^k2 ... pn^kn
- - construct the set F of distinct (not-necessarily-prime) factorizations of t
- - - { {f1, f2, ... fn}: fi > 1, f1*f2*...*fn = t }
- - - e.g. if t = 12, this would be { {2, 2, 3}, {3, 4}, {2, 6}, {12} }
- - construct the set of lockers as follows:
- - for each factorization f in F
- - - grab as many distinct primes pi <= N as there are elements in f
- - - subtract one from each element of f
- - - for each permutation of 1..n => i1...in
- - - - check if p1^(fi1-1)p2^(fi2-1)...pn^(fin-1) <= N
- - - - - if so, that's a locker... add it to the set
- - e.g., if t = 12 and N = 100:
- - - f = {2, 2, 3}
- - - - try primes 2, 3, and 5 first
- - - - - 5^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 60: FOUND!
- - - - - try permuting f:
- - - - - - 5^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 90: FOUND!
- - - - - - 5^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 150 is too big
- - - - try primes 2, 3, and 7 next
- - - - - 7^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 84: FOUND!
- - - - - try permuting f:
- - - - - - 7^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 126 is too big
- - - - - - 7^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 294 is too big
- - - - try primes 2, 5, and 7 next
- - - - - 7^(2 - 1)*5^(2 - 1)*2^(3 - 1) = 140 is too big
- - - - - don't bother permuting f
- - - - - - don't bother trying other primesets
- - - - - - they will only be bigger than 2, 5, 7, which came up empty
- - - f = {3, 4}
- - - - try primes 2 and 3 first
- - - - - 3^(3 - 1)*2^(4-1) = 72: FOUND!
- - - - - try permuting f:
- - - - - - 3^(4 - 1)*2^(3 - 1) = 108 is too big
- - - - try primes 2 and 5 next
- - - - - 5^(3 - 1)*2^(4-1) = 200 is too big
- - - - - don't bother permuting f
- - - - don't bother trying other primesets
- - - - they will only be bigger than 2, 5 which came up empty
- - - f = {2, 6}
- - - - try primes 2 and 3 first
- - - - - 3^(2 - 1)*2^(6 - 1) = 96: FOUND!
- - - - - try permuting f:
= - - - - - 3^(6-1)*2^(2-1) = 486 is too big
- - - - try primes 2 and 5
- - - - - 5^(2 - 1)*2(6 - 1) = 160 is too big
- - - - - don't bother permuting f
- - - - don't bother trying other primesets
- - - - they will only be bigger than 2, 5 which came up empty
- - - f = {12}
- - - - try prime 2 first
- - - - - 2 ^ (12 - 1) = 2048 is too big
- - - - don't bother trying only other primes
- - - - they will only be bigger than 2, which came up empty

print found lockers
e.g. Lockers that are toggled 12 times: 60, 72, 84, 90, 96
- Note that 84 and 90 weren't found in the first section
- This is because their prime factorizations don't have nonascending exponents
- 84 = 2^2*3^1*5^0*7^1; the exponent ascends from 0 to 1 going from base 5 to 7
- 90 = 2^1*3^2*5^1; the exponent ascends from 1 to 2 going from base 2 to 3

EDIT: The example should also try primeset 2, 3, 11 since 2, 3, 7 found something. 2, 3, 11 comes up empty, but the algorithm won't know that a priori.

Veggie2009-08-06 14:22

This would be a factorization problem, which is NP I believe...

Lithp2009-08-06 14:26

Bim Job:

Is there some way to devise a "programming praxis" that
* isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.)
* isn't trivially solvable by googling?
* actually requires a computer program?
* requires commenters to read, say, the first ten responses to see whether the problem has been solved?
* doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

Is there some way to devise a "programming praxis" that
* isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.)
* isn't trivially solvable by googling?
* actually requires a computer program?
* requires commenters to read, say, the first ten responses to see whether the problem has been solved?
* doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

Ah, my bad - I tend to mangle that URL most of the time. Thanks for the problem links, anyhow - those were fun to solve.

Cale Gibbard2009-08-06 21:14

(I did it in Haskell.)

Well, let's start with the straightforward answer before thinking about it too hard. We'll first define the sequence of how many times each locker will be toggled in the nth step:

s n = [if k `mod` n == 0 then 1 else 0 | k <- [1..]]

and then the number of times which each locker gets toggled after 100 steps is obtained by an easy fold:

toggleCount = foldr (zipWith (+)) (repeat 0) (map s [1..100])

and of course, lockers are open if they were toggled an odd number of times:

lockerPattern = map odd toggleCount

and we can get the indices at which these lockers occur easily enough:

openLockers = map (+1) . findIndices id $ lockerPattern

So, we've sort of solved the problem.

I managed this much before the jocks had finished opening the first 100 lockers.

There's just one distasteful thing in all that, which is the fact that we've limited ourselves to just 100 steps, even though our list of lockers is infinitely long. What if we wanted the process to continue forever? Naturally, any one locker will only be toggled a finite number of times, since on the nth step, the first locker to be toggled is the nth, and that is the last step on which that locker gets toggled.

Thinking a little more about the problem, each locker gets toggled once for each of its divisors. So, we'll start with prime factorisation:

primes = 2 : filter isPrime [3,5..]

isPrime n = all (\p -> n `mod` p /= 0)
. takeWhile (\p -> p*p <= n) $ primes

and then factoring a number into primes:

factors n | abs n <= 1 = []
| otherwise = p : factors (n `div` p)
where p = head . filter (\p -> n `mod` p == 0) $ primes

and then the number of divisors of n is the number of ways we can pick sub-multisets of its prime factorisation. If p^k is the largest multiple of p which divides n, then we can have any number of copies of p less than or equal to k in a divisor of n, which gives us k+1 possibilities. So for each prime, we count the number of times it occurs, add one, and multiply the results together to count the divisors:

Of course, looking at it from this perspective, the lockers which are open at the end are those with an odd number of divisors. In order to have an odd number of divisors, none of the numbers which we multiplied together in divisorCount can be even (or the product will be even). Each of those numbers was one more than the number of times that a given prime occurred. So in order for all those numbers to be odd, we need each prime to occur an even number of times:

there is a pattern that i am seeing here, it appears that the first one is open, then two are closed, one is open, then four are closed, then one is open, so the distance between the open lockers goes up by two after each open locker... this could seemingly be applied to as many lockers as you would like

mol11112009-08-06 23:23

Z80 Assembler

org 65100
MAIN:
ld c, 121
ld d, 0 ; counter
ld hl, RESULT ; result offset
; while a*a < c
START:
inc d
ld b, d
ld a, d
dec b
SQUARE:
add a, d
djnz SQUARE
cp c
ld (hl), a
inc hl
jp m, START ; jump if a < c
ret
RESULT: defs 100

Usage from ZX Spectrum BASIC:

10 CLEAR 65099
20 LET a=65100
40 POKE a, 14
50 LET a =a+1
55 INPUT "Number of lockers (1-121):", max
56 IF max<1 OR max>121 THEN GO TO 55
60 POKE a, max
70 LET a=a+1
80 READ n
90 POKE a, n
100 IF n<>201 THEN GO TO 70
110 REM 201 is RET
120 DATA 22, 0, 33, 97, 254
130 DATA 20, 66, 122, 5, 130
140 DATA 16, 253, 185, 119
150 DATA 35, 250, 83, 254, 201
154 LET d=USR 65100
155 LET a=a+1
160 LET n=PEEK a
170 IF n>max THEN STOP
180 PRINT n
190 LET a=a+1
200 IF n<max THEN GO TO 160
210 STOP

Admittedly I didn't let the simulation run to completion so I didn't see that it ended up with the perfect squares.

Alternative brute-force method that can be used for any arbitrary toggling instructions against lockers in any initial state:

1: Precompute all toggle rules for each pass against each locker (eg. first pass is 1=TOGGLE 2=TOGGLE 3=TOGGLE 4=TOGGLE etc, second pass is 1=SKIP 2=TOGGLE 3=SKIP 4=TOGGLE etc)

2: XOR together all toggle instructions for each locker to obtain an overall toggle instruction for that locker (eg. after the first two passes, first locker is TOGGLE XOR SKIP resulting in TOGGLE, second locker is TOGGLE XOR TOGGLE resulting in SKIP). For the XOR take TOGGLE=1 and SKIP=0.

3: Apply the single resulting toggle instruction to each locker as it is in the initial state (eg. after two passes Locker #1 is toggled but locker #2 is skipped).

babeshclow2009-08-07 01:26

Its the number of unique numbers the locker is divisible by then modd'd by 2.

1 is divisible only by 1 = 1 % 2 = 1 = open
2 is divisible by 1 and 2 = 2 % 2 = 0 = closed
3 is divisible by 1 and 3 = 2 % 2 = 0 = closed
4 is divisible by 1, 2, and 4 = 3 % 2 = 1 = open
5 is divisible by 1, and 5 = 2 % 2 = 0 = closed
6 is divisible by 1, 2, 3, and 6 = 4 % 2 = 0 = closed
etc...

int lockers[100]; // 0 for close 1 for open
for (int n = 1; n <= 100; n++) {
int c = 0;
for (int d = 1; d <= n; d++) {
int nd= n / d;
if (nd * d == n) {
c++;
}
lockers[n-1] = c % 2;
}
}

babeshclow2009-08-07 01:36

Wikipediaing says its called the 'divisor function'.

k12009-08-07 01:49

Mike:

Since that was such fun, how about this:

"A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

he start with (2^N)-1
2^N rabbits for each house

Mike2009-08-07 04:33

k1:

Mike:

Since that was such fun, how about this:

"A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

he start with (2^N)-1
2^N rabbits for each house

We has winner.

Now,
"In 3009, King Warren of Australia suspects the Earls of Akaron, Bairnsdale, Clearemont, Darlinghurst, Erina and Frankston are plotting a conspiracy against him.
He questions each in private and they tell him:
Akaroa: Frankston is loyal but Erina is a traitor
Bairnsdale: Akaroa is loyal.
Claremont: Frankston is loyal buy Bairnsdale is a traitor.
Darlinghurst: Claremont is loyal but Bairnsdale is a traitor.
Erina: Darlinghurst is a traitor.
Frankston: Akaroa is loyal.
Each traitor knows who the other traitors are, but will always give false information, accusing loyalists of being traitors and vice versa. Each loyalist tells the truth as he knows it, so his information on traitors can be trusted, but he may be wrong about those he claims to be loyal.
How many traitors are there?"

Jonas2009-08-07 05:01

Probably found before me, but here is my solution with recursion in python.
---------

def f(n):
if n == 1: return [1]
elif n == 4: return [1, 4]

tmp = f(n-1)
if n == (tmp[-1] - tmp[-2]) + res[-1] + 2:
tmp.append(n)

return tmp

port2009-08-07 05:19

This looks good but I can't get it to work in npiet. From the trace it seems to loop round, but it just outputs commas and never stops. The vertical light blue right of centre seems to be an OutC command. Which piet interpreter did you use?

Alex2009-08-07 05:45

Welbog:

The open lockers are perfect squares.

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Has anyone figured out if there's some sort of pattern to the open doors?

Emanuele Sabellico2009-08-07 08:24

In python:

import math
def getOpenLockers(n):
return [(x+1)**2 for x in range(0, math.floor(math.sqrt(n)))]

Daniel2009-08-07 10:25

If I remember correctly, you could refactor lines 40 and 80 into "IF I>N THEN STOP"

Well, why program in BASIC if you cannot abbuse GOTOs?

The truth is I as having a hard time in typing this program as the emulator follows the ZX81 keyboard layout. I was also too lazy to write it down on paper before entering or to find an image of the Z81 keyboard.

Btw, I bought the 16K expansion from the start, so I could waste a few bytes...

Josh2009-08-07 10:38

This is what the function looks like when you just simulate what the jocks are doing in c++ (and you, like myself, are at best a novice programmer). This includes counting the number of times the lockers are flipped and a simple output of the results:

int x, y, locker [100] = {0}, count [100] = {0};

for (x=1; x<=100; x++){
for (y=x-1; y<100; y=y+x){
count[y]++;
if (locker[y] == 0)
locker[y] = 1;
else locker[y] = 0;
}
}
cout<<"Current state: \n 0 = closed and 1 = open\n\n";
for (x=0; x<100; x++){
cout<<"Locker "<<setw(3)<<right<<(x+1)<<" : "<<locker[x]<<" | flipped "<<count[x]<<" times\n";
}

N Muntz2009-08-07 10:40

Maurits:

Follow-up question: which lockers are toggled the LEAST?

That's like asking the square root of a million. No one will ever know.

HA-ha.

Zach Bora2009-08-07 12:28

Gabriel:

Pretty simple :) after you watch the simulation...
getOpenLockers(n){open = 1;count = 3; while(open<=n) { print open; open += count;count += 2;} }
I'll leave the mathematical solution for somebody else.

Umm, the goal is to finish before the jockers!

Gandalf2009-08-07 12:53

There is no need to write code for this. For number, just think about by how many other numbers you can divide it. Note that the locker is opened/closed once for each of those. Obviously, it is important whether the locker number has an odd or an even number of such factors. Now, what numbers do have an odd number of factors? Hint: That depends on the prime factorization.

For each prime factor, take its exponent and add one. Then multiply the results. For example, 12 has 3 * 2 factors because 12 = 2^2 * 3^1. To get an odd result, each prime factor has to appear even times. That means, the locker number has to be a square number. Exactly then the locker will be open in the end.

CAPTCHA: genitus
because Gandalf is a genius... with a large genital.

stangm2009-08-07 14:05

which lockers are toggled the LEAST?
Locker 1, it is only toggled once, every other locker is toggled at least twice.

Vic Tim2009-08-07 14:20

The 60th locker gets toggled the most

that's all I know.

greg2009-08-07 15:09

sorry, that's brute force. Try again. (hint, no loops allowed)

Beska2009-08-07 17:45

The simple solution is floor(sqrt(n)) where n is the number of lockers (100 in this case.)

That's the easy way to determine how many perfect squares are between 1 and n (without looping).

brigmar2009-08-07 18:08

Mike:

Now,
"In 3009, King Warren of Australia suspects the Earls of Akaron, Bairnsdale, Clearemont, Darlinghurst, Erina and Frankston are plotting a conspiracy against him.
He questions each in private and they tell him:
Akaroa: Frankston is loyal but Erina is a traitor
Bairnsdale: Akaroa is loyal.
Claremont: Frankston is loyal buy Bairnsdale is a traitor.
Darlinghurst: Claremont is loyal but Bairnsdale is a traitor.
Erina: Darlinghurst is a traitor.
Frankston: Akaroa is loyal.
Each traitor knows who the other traitors are, but will always give false information, accusing loyalists of being traitors and vice versa. Each loyalist tells the truth as he knows it, so his information on traitors can be trusted, but he may be wrong about those he claims to be loyal.
How many traitors are there?"

Logic says that :

1: If somebody says somebody else is a Traitor, then they're in the other camp.

2: If two people call each other Loyalists, then they must be in the same camp (a Loyalist couldn't mistakenly identify a Traitor as Loyalist in this case, as the Traitor would identify the Loyalist as a Traitor).

3: If person1 from campX calls person2 from campY a Loyalist, person1 must be a mistaken Loyalist, campX must be Loyalist, and campY must be Traitors, as a traitor would identify a Loyalist as a Traitor.

From 1, it can be deduced that A,D,C fall into 1 group, and E,B fall into the other. A infers E infers D infers B. C infers B.

From 2, F falls into the same camp as A, giving A,D,C,F and E,B as the two groups.

From 3, B is a loyalist, and A is a traitor.

Therefore there are 2 loyalists (B,E) and 4 traitors (A,C,D,F)

Henkie2009-08-07 19:15

Most opend and closed is Locker#60 (12 times)
least opend and closed is Locker#1 (1 times)

Grummel2009-08-08 05:51

Maurits:

Follow-up question: which lockers are toggled the LEAST?

You are not thinking of prime numbers, aren't you?

The first is only toggled once, this seems pretty obvious.

Henkie2009-08-08 08:10

10000 times takes some time to calculate :)

"Most opend and closed is 64 times [lockers 7560, 9240]"
"Least openend and closed is 1 time [locker 1]"

100000 times some more :)

And 1 million times takes a whole lot longer :D

Mike2009-08-08 09:27

All prime numbers but 1 (one is a prime number right? lol)...

Abatcher2009-08-08 11:43

Locker 1 duh :D

Joey2009-08-08 13:22

Powershell

# 50 Bytes
# a function by the exact name which does this. Input gets passed as argument:
# getOpenLocker 100
function getOpenLockers($n){(1..$n|%{$_*$_})-le$n}

# 44 Bytes
# a filter by the same name which solves the problem. Input gets piped into the filter:
# 100 | getOpenLockers
filter getOpenLockers{(1..$_|%{$_*$_})-le$_}

# 39 Bytes
# A script block stored in a variable. Input gets passed from the pipeline via ForEach-Object:
# 100 | % $getOpenLockers
$getOpenLockers={(1..$_|%{$_*$_})-le$_}

Babu2009-08-08 15:50

The primes

Fregas2009-08-08 18:25

the real wtf is that this is on the dailywtf.

how the mighty have fallen. I miss the old days.

pjt332009-08-08 19:05

greg:

sorry, that's brute force. Try again. (hint, no loops allowed)

"Not brute force" doesn't mean "no loops allowed". The number of elements in the desired output is a monotonic increasing function of the size of the input, so it's impossible to give a correct solution without some form of loop.

Kevin Kofler2009-08-09 01:23

Lemma 1: Let the lockers be numbered starting from 1. Every locker is toggled as often as its number n's number of divisors.

Proof: Consider step k: it toggles lockers k, 2k etc., i.e. all the lockers m such that k divides m. So every k which toggles locker n is a divisor of n. Conversely, every divisor of n will toggle locker n, as all divisors of n are <= n and we run as many steps as there are lockers in total, and thus >= n steps.

Remark: This also answers the bonus questions: The more divisors a number n has, the more often the locker n will get toggled. The numbers which get toggled the least are, after 1 (1 divisor), the prime numbers (2 divisors).

Lemma 2: The locker remains closed if it is toggled an even number of times, it ends up opened if it is toggled an odd number of times.

Proof: By induction. If the locker is toggled 0 times, it remains closed. Let lemma 2 be true for k>0. If k is even, the locker is closed after the kth toggle, k+1 is odd and the locker will be open after the k+1st toggle. If k is odd, the locker is open after the kth toggle, k+1 is even and the locker will be closed after the k+1st toggle.

Lemma 3: The nth locker remains closed if n has an even number of divisors, it ends up opened if n has an odd number of divisors.

Proof: Follows from lemmas 1 and 2.

Theorem: Locker n will end up opened if and only if n is a perfect square.

Proof: Let k be a divisor of n such that k*k!=n. Then n/k!=k and n/k is also a divisor of n. It follows that any n which is not a perfect square has an even number of divisors, because k*k cannot equal n for a non-square and because n/(n/k)=k and thus (k,n/k) form pairs. By lemma 3, the locker will stay closed. Now let n be a perfect square and m be the square root of n. The number of divisors != m is even by the same reasoning as for non-square n. Thus, counting m too, the number of divisors is odd. By lemma 3, the locker will be open.

Lemma 4 (used in the implementation): (i+1)*(i+1)=i*i+2*i+1=i*i+i+(i+1)

unsigned n=100;
unsigned *p=getOpenLockers(n);
unsigned i;
for (i=0; i<n; i++) {
if (!*p) break;
printf("%u ", *(p++));
}
printf("\n");

Kevin Kofler2009-08-09 01:29

pjt33:

greg:

sorry, that's brute force. Try again. (hint, no loops allowed)

"Not brute force" doesn't mean "no loops allowed". The number of elements in the desired output is a monotonic increasing function of the size of the input, so it's impossible to give a correct solution without some form of loop.

Any loop which loops over all lockers is brute force. Look at my solution (maybe given by others first, I haven't read through all the comments), it only takes 1 loop iteration per open locker. (And no, you can't get the complexity down further as you need to produce the output, so you need at least 1 write per open locker.) I shall also remark that my solution requires no multiplication and definitely no square root.

Kevin Kofler2009-08-09 01:52

PS: The bottleneck in my C implementation is the calloc for the buffer. An elegant optimal solution would be using coroutines rather than a buffer. A less elegant way to do away with the buffer is to use an iterator-style API, which can easily be implemented in C:

static unsigned n, i, i2;

unsigned firstOpenLocker(unsigned N)
{
n = N;
i = i2 = 1;
return 1;
}

unsigned n=100;
unsigned k=firstOpenLocker(n);
do {
printf("%u ", k);
k = nextOpenLocker();
} while (k);
printf("\n");

RMB2009-08-09 11:18

import Array (assocs, accumArray)
main :: IO ()
main = let n = 100 in
print (map fst (filter snd (assocs
(accumArray (\x () -> not x) False (1,n)
[(k,())| m<-[1..n], k<-[m,2*m .. n]]) )))

Papa Troll2009-08-09 12:46

troll:

Has anyone figured out if there's some sort of pattern to the open doors?

Not yet. Keep reading.

Tom2009-08-09 13:16

Duh... the first one!

Some things I've noticed:

- on the i-th iteration, the i-th locker is in its final state

- each locker is toggled a number of times equal to the number of its factors, e.g.: every locker number has 1 as a factor hence they all get toggled at least once. Another e.g.: locker # 4 has 4,2,1 as factors (or divisors, or whatever you want to call them) so it's toggled thrice (yep, I said thrice)

- finally, (a bit obvious) lockers toggled odd number of times finish in the opposite state to which they started; even number of times: same as they started

mol11112009-08-09 14:54

There is bug somewhere. E.g. try input 16: the last one should be open but it's shown closed.

Addendum (2009-08-09 15:16): BTW I've put index online. Available from here.

Graysen2009-08-09 22:51

I'm VERY new to any programming (about 2 months), this is what I came up with in C++. If anyone has a suggestion to make the code better I would really appreciate it. This is based on open = True and closed = false. The correct lockers are open but I'm not sure of how to get rid of 0.

#include <iostream>

using namespace std;

void swap (int *p1);
int lockers[101];
int i, s;

int main()
{
for (s = 1; s < 101; s++){
for (i = s; i < 101; i = i + s){
swap (&lockers[i]);
cout << i << " - " << lockers[i] << " // ";
}
cout << "\n";
cout << "\n";
}

for (i = 0; i < 101; i++)
cout << i << " - " << lockers[i] << " // ";

/* it is the sqrt of the MAX_LOCKERS +1
#define DEF_MAX_LOCKERS 65 /* up to 4096 doors */
typedef struct lockers_s
{
uint32_t OpenLocks[DEF_MAX_LOCKERS];
uint32_t numOpenLocks;
} lockers_t;

lockers_t getOpenLockers(uint32_t lockerCount)
{
lockers_t lockers;
uint32_t tmp;
uint32_t count;
lockers.numOpenLocks = (uint32_t) sqrt(lockerCount);
if (lockers.numOpenLocks == 0)
return lockers;
/* only pure squares are left open */
for (count = 1; count <= lockers.numOpenLocks; count++)
{
lockers.OpenLocks[count-1] = count*count;
}
/* and the last one if not already in the list */
if (count*count != lockerCount)
{
lockers.OpenLocks[count] = lockerCount;
lockers.numOpenLocks++;
}
return lockers;
}

midiwall2009-08-10 15:05

I submit that while Mr. Zargas may have been "zany" he wasn't as whacked as his distant cousin Mr. Zargus whom it seems should have been the one to take it a step further, though it was actually "Mr. Zargas' locker challenge".

W. Craig Trader2009-08-10 15:29

Answer in Python:

def getOpenLockers( n ):
answer = []
i = 1
while ( i*i <= n ):
answer += [ i*i ]

return answer

neried72009-08-10 16:15

#!/usr/bin/perl

use warnings;
use strict;

sub lockers {

print "Enter a number of lockers: ";
chomp(my $n = <STDIN>);
my @lockers; #0 index will be ignored. So will 1 because those are all open to start.
if ($n == 1) {
@lockers = (1);
print @lockers;
return @lockers;
}

# 1 means open, 0 means closed. For $n > 1, the first round opens all lockers.

my ($i, $j);
for ($i=1; $i<=$n; $i++) {
for ($j=1; $j<=$n; $j++) {
if ($j % $i == 0) { # if the divisor i is a factor of j, there will be no remainder, and we toggle the locker.
if ($lockers[$j] == 1) {
$lockers[$j] = 0;
} else {
$lockers[$j] = 1
}
}
}
}

print "Final lockers: \n";
for ($i=1; $i<=$n; $i++) {
print "Locker $i: $lockers[$i] \n";
}
return @lockers;
}

&lockers;

TopicSlayer2009-08-10 16:27

Mike:

Now,
"In 3009, King Warren of Australia suspects the Earls of Akaron, Bairnsdale, Clearemont, Darlinghurst, Erina and Frankston are plotting a conspiracy against him.
He questions each in private and they tell him:
Akaroa: Frankston is loyal but Erina is a traitor
Bairnsdale: Akaroa is loyal.
Claremont: Frankston is loyal buy Bairnsdale is a traitor.
Darlinghurst: Claremont is loyal but Bairnsdale is a traitor.
Erina: Darlinghurst is a traitor.
Frankston: Akaroa is loyal.
Each traitor knows who the other traitors are, but will always give false information, accusing loyalists of being traitors and vice versa. Each loyalist tells the truth as he knows it, so his information on traitors can be trusted, but he may be wrong about those he claims to be loyal.
How many traitors are there?"

The easiest starting place is E, because he only names a single traitor.

E is either loyal or a traitor; let's assume he is a traitor.

If E is a traitor then he is lying about D being a traitor, in which case D must be loyal. Therefore, D's information about all traitors must be true (while his knowledge of loyalists may be wrong). If that is the case, then D must be correct about B being a traitor. If B was a traitor, then he is lying about A being loyal. Therefore A must be a traitor. If A were a traitor then he must be lying about E being a traitor, and therefore E must be loyal. However, this contradicts E being a traitor, and therefore E must be loyal. We have proven E must be a loyal by contradiction.

If E is loyal (and he must be) then D must be a traitor. If D is a traitor then he's lying about both B and C. Therefore, B must be loyal and C must be a traitor. If C is a traitor then he is lying about B and F. Therefore, B is loyal (we knew already) and F is a traitor. If F is a traitor then A is a traitor. If A is a traitor then E is loyal (we knew this) and F is a traitor (also known.).

So, in the order we figured it out:

Loyal: E, B
Traitors: D, C, F, A

neried72009-08-10 17:34

First was the brute version, here's the 'formulaic' version:

use warnings;
use strict;

sub lockers {

print "Enter a number of lockers: ";
chomp(my $n = <STDIN>);
my @lockers; #0 index will be ignored.

# 1 means open, 0 means closed. For $n > 1, the first round opens all lockers.
my ($i, $j);

#the ones that stay open are the perfect squares, because they end up with
#an odd number of toggles, and thus end up open (opposite of the starting state)

for ($j=1; $j<=$n; $j++) {

@lockers[$j] = 0;
}

my $root_n = sqrt $n;
print "Square root: $root_n";

for ($i=1; $i<=$root_n; $i++) {
$lockers[$i**2] = 1;
}

print "Final lockers: \n";
for ($j=1; $j<=$n; $j++) {
print "Locker $j : $lockers[$j] \n";
}
return @lockers;
}

&lockers;

fuffuf2009-08-10 17:38

In the simulation every opened locker adheres to the rule 2^n, except for #9.

I suspect there is a flaw in the simulation.

mol11112009-08-10 20:46

fuffuf:

In the simulation every opened locker adheres to the rule 2^n, except for #9.

I suspect there is a flaw in the simulation.

Oh, really? What about 25, 36, 49, 81, 100 ?

Gandalf2009-08-11 05:54

As I said before, exactly the lockers with a square number (i.e. n^2) get an odd number of toggles. That is because they have an odd number of divisors.

Obviously, locker 1 is toggled only once because 1 has only one divisor, itself.

To see which locker is toggled most times, consider which number has the highest number of divisors. For this, we only need to consider the prime factors 2, 3, and 5. (Otherwise, the number gets too large.)

So, the only real candidates are 64, 96, and 60. (If you don't understand this, go to a silent place and meditate about prime factors for some time.)

64 = 2^6 has 7 divisors
96 = 2^5 * 3^1 has 6*2 = 12 divisors
60 = 2^3 * 3 * 5 has 4*2*2 = 16 divisors

So 60 is toggled most often. 16 times.

Moomoo2009-08-11 07:58

locker number 1....

Wintermute2009-08-11 08:08

Gandalf:

60 = 2^3 * 3 * 5 has 4*2*2 = 16 divisors

So 60 is toggled most often. 16 times.

I'm not really sure about that. I did not check the math, though (wrong time of day for that).
From my point of view the divisors of 60 are 1,2,3,4,5,6,10,12,15,20,30 and 60, which makes 12. Did I miss any?
So most toggles have (according to my brute-force approach) 60,72,84,90 and 96 -> 12 toggles.

For 1.000.000 it's... 720.720 and four more (240 toggles).

Maurits2009-08-11 10:47

mol1111:

fuffuf:

In the simulation every opened locker adheres to the rule 2^n, except for #9.

I suspect there is a flaw in the simulation.

Oh, really? What about 25, 36, 49, 81, 100 ?

There are two perfectly good explanations for those, depending on what you think "^" does.

Uh, yeah, you are absolutely right, Wintermute. I accidentally counted the divisors of 120.

60 = 2^2 * 3 * 5 has 3*2*2 = 12 divisors

mol11112009-08-11 15:02

Maurits:

mol1111:

fuffuf:

In the simulation every opened locker adheres to the rule 2^n, except for #9.

I suspect there is a flaw in the simulation.

Oh, really? What about 25, 36, 49, 81, 100 ?

There are two perfectly good explanations for those, depending on what you think "^" does.

Explanation 1:

25 = 2^27
36 = 2^38
49 = 2^51
81 = 2^83

But if you mean XOR, than you can do:
9 = 2^11

In fact, for any x you can find y such as x=2 xor y, so it would not be any rule anyway.

Clear as mud.

I would say so.

Leilock2009-08-11 16:20

public static List<bool> BeatTheJocks(int numberOfLockers)
{
List<bool> lockers = new List<bool>();
for (int i = 0; i < numberOfLockers; i++)
lockers.Add(true);
for (int i = 2; i <= numberOfLockers; i++)
for (int j = i; j <= numberOfLockers; j = j+i)
lockers[j-1] = !lockers[j-1];
return lockers;
}

Maurits2009-08-11 16:50

mol1111:

In fact, for any x you can find y such as x=2 xor y, so it would not be any rule anyway.

y = x xor 2, in fact.

In fact, for any x and y you can find z such that x = y xor z (specifically, z = x xor y)

For my next trick, I will crack ROT13...

Sam Wilson2009-08-12 02:14

I'm not really a math geek (been years) but I think that a friend and I came up with a decent formula, but not sure how to express it :) after that, we realized that all squares are open lockers, so our "solution" became more a proof of why squares are open lockers

We initial figured that a locker "toggles" when a factor of the number is encountered. Then figured that an odd number of factors would leave the locker open. The formula is something like the sum of all instance from 1 to x (where in this case x is 100) where the number of factors of x is odd. So starting off:
1 has 1 (1 - odd)
2 has 2 (1 2 - even)
3 has 2 (1 3 - even)
4 has 3 (1 2 4 - odd)
5 has 2 (1 5 - even)
... and so on. Further down the locker line...
48 has 10 (1 2 3 4 6 8 12 16 24 48 - even)
49 has 3 (1 7 49 - odd)
50 has 6 (1 2 5 10 25 50 - even)
51 has 4 (1 3 17 51 - even)

Looking at this, we realize that squares are odd because we only count it's square factor once, when it multiplies itself.

As far as least toggled locker, locker #1 only once :) next in line, all prime number are toggled twice (1 and itself), naturally all being closed lockers

Sam

Sam Wilson2009-08-12 02:17

I just saw the 8 pages of comments, and realized that it's been solved already :( oh well, my last post stands, I figured it out while drinking beers :)

Dave2009-08-12 03:56

T-SQL (2005+)

Declare @n int
set @n = 100

; with locker (ID) AS (
SELECT Number
FROM master..spt_values --or any numbers function
WHERE Number > 0
AND Number < @N + 1
AND Name is null
)

SELECT locker.ID [locker], count(locker.ID) [toggles], count(locker.ID) % 2 [state]
FROM locker [locker]
JOIN locker [toggle] ON (locker.ID % toggle.ID) = 0
GROUP BY locker.ID
--Order by 2 asc

as a triangular CTE
optional order by if you want to see the least toggled.

Dave2009-08-12 04:25

comparable cpu effort for 10^4 to 10^9 lockers
(at least as reported)

Ed Gorcenski2009-08-12 17:08

MATLAB code:

n = 100;

L = zeros(1,n);
mask = 1:n;
toggle = zeros(n);

for i=1:n
toggle(i,:) = mod(mask,i)==0;
L = L + toggle(i,:);
L(find(L>1)) = 0;
end
L
t = sum(toggle);
least = find(t==min(t))
most = find(t==max(t))

Jürgen2009-08-13 06:17

def least_toggled(n): return 1

Maurits2009-08-13 20:48

Ed Gorcenski:

MATLAB code:

Make that
toggle = zeros(1, n);
or even just
toggle = L;

Open: Even powers of primes (1,4,9,16,25,49,64,81)
Closed: Everything else.

Most toggled: Whatever has the most prime factors (too lazy to figure it out, so I'm going to guess 60)

Least toggled: 1 (duh) and in second place, all primes.

quintopia2009-08-16 07:55

Yeah I got it wrong. All squares have an odd number of factors, not just even powers of primes. Oh well.

Minko2009-08-17 17:44

Simple: each locker with an index that is a prime number will be closed. All of these will be toggled just twice. For the rest they will be either open or closed depending on the number of unique dividers. For example 12 has 5 unique dividers 1, 2, 3, 4 and 6. It will be open.

Minko2009-08-17 17:46

ooops forgot 12 is also a divider. It will actually be closed :)

Tama2009-08-17 17:52

Mathamagician:

Tama:

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.

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....

I meant "perfect square" of course, not "perfect prime".

Dan2009-08-18 01:56

Locker 1 and all primes are toggled least (twice).

OMFG you guys are the biggest nerds ever, see you in the locker room, get ready for atomic wedgies!

See you in your car; get ready for a load of manure!

Anonerd2009-08-24 09:02

Nigl:

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 twenty-eighth 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

For extra points, do not assume English; support at least all languages spoken in the EU.

Seriously, Mrs MeChokemchild suggested a harder problem:

It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door".

Admittedly the simulator takes the number of lockers as input, not the number of togglings, but then the simulation was 'To Get Started' only.

Captcha: capio - I got it! (?)

AllanW2009-08-24 19:06

Uh... Maurits's "follow-up question" is much too easy: No mater how many lockers you have, locker #1 is only ever touched once.

Jeremy Pyne2009-08-28 09:51

Meh, generic C#...

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{

static bool[] doLockers(int size, int iteration)
{
bool[] data;

if (iteration == 1)
data = new bool[size];
else
data = doLockers(size, iteration - 1);

Console.WriteLine("Press any key to exit");
Console.ReadLine();
}
}
}

Ethan2009-08-29 07:56

locker #1 is toggled only once.
The prime number ones are toggled exactly twice, by one and the prime they represent.

rjk2009-08-31 13:28

Hmmmm... wonder if anyone has tried a Texas Instruments calculator version. Would like to see it run on my crappy TI-83 Plus!

Barett McGavock2009-09-02 20:42

Obviously, locker 1 is toggled only once. Lockers with prime numbers are toggled twice: once on the first iteration, and once for itself. For others, find the factors of the locker number. The number of factors equals the number of times it's toggled.

CS2009-09-04 17:50

The 1 followed by the primes are toggled the least. The number of toggles is based upon the number of factors.

1: 1 toggle
Primes: 2 toggles
Perfect Squares: Odd number of toggles, hence open
Other: Even number of toggles, hence closed

Cranberry2009-09-14 20:11

Prime numbered ones. They're toggled twice, one at the first step, and once at their own.

As a general rule, each locker is toggled a number of times equal to the number of possible unique groupings of its prime factors that are <= the number of lockers. So for example, take the 20th locker, with factors 2,2,5. It gets toggled:

On the 1st step.
On the 2nd step.
On the (2*2)th[4th] step.
On the 5th step.
On the (2*5)th[10th] step.
And of course on its own (20th) step.

If the number of swaps n is odd (that is, n mod 2 = 1), that locker is open, and if that number is even (n mod 2 = 0), the locker is closed. Thus, locker 20, with six toggles, is closed.

Christian2009-10-08 14:33

Easy. Locker number 1 (once), followed by any prime numbers (twice). From there, it's whatever numbers have exactly 3 factors (incl. themselves).

I'm fairly sure that 96 is the locker that would be toggled the most incidentally.

Gray Pockets2009-10-13 17:25

I lost by 27 seconds:

#!C:\Perl\bin\perl

for ($s=1; $s<=100; $s++) {
$myArray[$s] = 0;
}

for ($q=1; $q<=100; $q++) {
for ($i=1; $i<=100; $i++) {
if ($i%$q==0) {
if ($myArray[$i]==0) {
$myArray[$i] = 1;
} else {
$myArray[$i] = 0;
}
}
}
}

Locker one is toggled once. Otherwise, consider that factors ordinarily come in pairs, except in the case of perfect squares, where the squareroot lacks a partner (being its own).

Colin2010-04-21 13:42

Although I'm pretty late, I just had to beat the 29 character Perl solution in length. So here it goes:

*:>:i.%:100

(11 characters of J), or with precalculating the square root of 100, even shorter (and with it's 9 characters probably the shortest solution posted here):

*:>:i.10

Joel2010-05-13 17:52

Prime numbers.

orange_batch2010-08-25 19:32

The objective is to beat the jocks with the right answer, not how that answer is obtained, right?

In a lazy 7 minutes all I did was program what the jocks were doing.

DOS batch:

setlocal enabledelayedexpansion

for /l %%x in (1,1,100) do (
set locker%%x=0
for /l %%y in (1,1,100) do (
set /a remainder=%%x%%%%y
if !remainder!==0 if !locker%%x!==0 (set locker%%x=1) else set locker%%x=0
)
echo locker%%x: !locker%%x!
)

orange_batch2010-08-25 19:34

K, I didn't read the no brute force part. Whatever.

The loonly guy2011-11-12 07:52

Didn't anyone see the pattern???
Pattern:
(o=open c=closed)
occoccccocccccco (and so on)
Code:

/*
* ---Demo code for TDWTF (thedailywtf.com)---
* Code to work out the riddle at this url:
* URL: http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx
* May need some cleaning up...
* It works anyway
*
* How i got to this?
* Fill the calculator on that page and look how (in the end)
* the amount of closed lockers between the open ones increases...
*
* Keys:
* [ ] Open locker
* [X] Closed locker
*/
#include <stdio.h>

//Calculate and print a locker scheme as explained on the web-page
//Parameters: amount of lockers
void lockers(int amount)
{
//init vars
//the offset for open lockers starts at 1
int i, c = 0, l = 1, nc = 0;
//loop for each locker
for (i = 0; i < amount; i++)
{
//have we reached an open locker?
if (i == c)
{
//yes we did!

//set next open locker offset, our offset needs to increase each time
//our offset between open lockers grows with 2 each time
l += 2;
//add offset to counter for open lockers
c += l;
//print the open-locker symbol
printf("[ ]");
}
else
{
//this is an closed locker
printf("[X]");
}

//the next 6 lines of code (8 if you include comments)
// make this program's output look nice ;)
//it's not of any other use
nc++;
if (25 == nc)
{
nc = 0;
printf("\n");
}

} //end loop
} //end lockers (function)

int main()
{
//calculate (and print) the final locker scheme for 100 lockers
lockers(100);
return 0;
}

End code

Easy huh?
Strip the comments and you have a very small program, that works!!!
+ I'm not bruteforcing ;)'

I hope the graphical output isn't a problem.

Working sample + output:
http://codepad.org/GAk1EMki

ac2011-12-30 10:48

The first locker is toggled exactly once. Prime-numbered lockers are toggled twice.

Smithd9762014-05-25 12:38

Link exchange is nothing else but it is just placing the other persons weblog link on your page at proper place and other person will also do similar in support of you. fkkgfgcbbcebcgdb

As for last week's, there were some great solutions... some of the more interesting ones involved XSLT, ZX Spectrum BASIC version, Piet, and as a Minsky machine.

int num = 100;

int i=1;

int k=1;

while(k<num){

k=i*i;

i++;

System.out.println(k);

}

}

sub lockers { return map $_**2, 1..sqrt shift }

how delightful!

Captcha "eros" .....I love you too!

The reasoning is simple: non-perfect squares have an even number of factors. The jocks toggle a number for every factor it has. Therefore every door should be toggled an even number of times and should therefore end closed (the starting state).

However, perfect squares have an odd number of unique factors, because one of the factors is repeated. Because of this, perfect squares are toggled for their square root which has no pair to reverse the toggle, so the door ends up open (the opposite state it started in).

Make sense?

=ROW(A1)^2

Somehow I think that makes it less fun.

a = inputbox("locker?")

for i = 1 to a

l = l+1

b = b & i & " "

i = i + (2*l)

next

msgbox b

not i^2

I also noticed this pattern and it is trivial to code:

From the explanation about the squares, we can deduce why this works:

(n+1)^2 = n^2 + 2n + 1

So... Not having fun in your job as a programmer ?

Thanks for pointing out the rythm!

Classic ASP:

max = floor(sqrt(totalLockerNum))

for i=1; i<=max; i++

{

result = i**2;

add result to array

}

return array

Yes, that would be the pattern for perfect squares.

stupid nerds with their fancy "square" numbers, nobody needs em!

How sad :(

Answer:perfect squares.

using formulae:Brute force:Solved this ages ago for rosetta code: (http://rosettacode.org/wiki/100_doors#Common_Lisp)

public List getLockers(int numLockers) {

(1..numLockers).collect{ it*it }

}

Any groovy programmers that want to show me better ways to do this, please point them out. :D

getOpenLockers(n){open = 1;count = 3; while(open<=n) { print open; open += count;count += 2;} }

I'll leave the mathematical solution for somebody else.

You can download it here

I'm getting eaten by the spam detector, uh oh.

I AM NOT A GROOVY PROGRAMMER.

It looks like it will return the squares from 1 to numLockers**2, which might not be what you want.

create FUNCTION [dbo].[getOpenLockersList] ()

RETURNS @aReturnTable TABLE

( locker INT,

isOpen BIT,

myCount INT)

AS BEGIN

INSERT INTO @aReturnTable (locker, mycount)

SELECT locker, SUM(CASE WHEN locker%number = 0 THEN 1 ELSE 0 END)

FROM (SELECT number locker FROM numbers WHERE number <= 100) lcker

CROSS join

(SELECT number FROM numbers WHERE number <= 100) nbr

GROUP BY locker

return

END

GO

SELECT locker,

CASE WHEN mycount%2 = 1 THEN 'OPEN' ELSE 'closed' END lockerState ,

myCount

FROM dbo.getOpenLockersList()

SELECT SUM(mycount%2) FROM dbo.getOpenLockersList()

SELECT locker FROM dbo.getOpenLockersList()

WHERE mycount =

(SELECT MAX(mycount) FROM dbo.getOpenLockersList() )

I don't see where it says n should be less than 100.

And the limit of 100 is irrelevant. That just gives us the maximum perfect square we care about.

I was thinking of a slight different problem, I guess; where you don't start toggling at the i-th locker for the i-th iteration.

I was thinking of a slight different problem, I guess; where you don't start toggling at the i-th locker for the i-th iteration.

Addendum (2009-08-05 10:12):Addendum: never mind. I guess I'm just not thinking straight about this.

At first, I think 64 might be a good choice, but (2,2,2,2,2,2) creates only 6 combinations. If I replace a 2 with a 3, I describe locker 96, and I can now create 11 combinations. Applying my knowledge of cribbage, I see that I can replace three 2s with two 3s to describe locker 72 (2,2,2,3,3), which also creates 11 combinations.

Console.Write("How many lockers? ");

int lockers = Convert.ToInt32(Console.ReadLine());

int openlockers = 0;

int interval = 1;

Console.Write("Open Lockers: ");

while (openlockers + interval < lockers)

{

openlockers += interval;

Console.Write(openlockers + " ");

interval += 2;

}

http://www.cartalk.com/content/puzzler/transcripts/200546/answer.html

SHENANIGANS!

24 can be divided by 1, 2, 3, 4, 6, 8, 12 and 24. That's 8 factors, or 6 if we exclude the extrema -> even

25 can be divided by 1, 5 and 25. That's 3 factors -> odd.

BTW, I'm getting an awful lot of errors when posting lately...

Other numbers not above 100 with 12 distinct factors:

60: 1 2 3 4 5 6 10 12 15 20 30 60

72: 1 2 3 4 6 8 9 12 18 24 36 72

84: 1 2 3 4 6 7 12 14 21 28 42 84

I'm amazed with amount of i^2 solutions. Think a bit longer before posting.

12, not 11 - you're probably failing to count 1.

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).

{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));

*/

my @opened;

my $last = 1;

my $total = shift;

my $skip = 2;

for (my $i = 0; $i < $total; $i++) {

push @opened,$i+1;

$i = $i+$skip;

$skip = $skip+2;

}

return @opened;

}

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

int main(int argc, char **argv)

{

printf("4 9 16 25 36 49 64 81\n");

return 0;

}

Totally optimized.

; ; denote pseudo-code, sort of

For i=1 to sqrt(num)

print i*i

next

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.

YAY!

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

double sqrts = Math.sqrt(Double.parseDouble(args[0]));

for (double i = 1; i <= sqrts; i++) {

System.out.print(new Double(Math.pow(i, 2.0)).intValue() + ",");

}

}

}

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.

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

for any natural power of a square of a prime number

(as an example 36 is 6*6 but it stays closed)

declare @count int

set @count = 100

declare @lockers table( id int identity, state bit )

insert into @lockers ( state ) values ( 0 )

while ( (select max(id) from @lockers) < @count )

insert into @lockers ( state ) values ( 0 )

while ( @count > 0 )

begin

update @lockers set state = abs(state - 1) where id % @count = 0

set @count = @count - 1

end

select * from @lockers where state = 1

1,2,3,4,6,9,12,18,36

9 factors

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 non-zero real is well-defined.

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...

Addendum (2009-08-05 10:57):Edit: The 3rd struct should be

To enforce the 1st door to be open initially. Yeah, templates are crazy.

There's a ruby solution. Works to find all the open lockers, will have to figure out which ones are opened most often.

What's that? We can suggest our own programming challenges? Well OK then!

<thinking>

<thinking>

<thinking>

<don't worry, I'm getting there...>

White-on-white doesn't work out too well...

--

egilhh

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 =)

[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.

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 TI-89 (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? )

Someone mentioned that doing the logic makes the programming "less fun" - they'd rather brute-force the program by actually flipping all 100 doors so many times - to make pretty code or something. The way I see it is if you can optimize a problem away beforehand, and your code ends up being an efficient one-liner, that's WAY better than trying to "beautifully" make a giant solution that somehow account for "edge cases" when it's clear there will never be any.

Anyone can program; not everyone can think logically, and that's the difference between mediocre and good programmers, or even good and great.

Start with 1.

Add 3 to get 4

Add 5 to get 9

Add 7 to get 16

Add 9 to get 25

etc.

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.

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 - 2*1+1 = 3

2 - 2*2+1 = 5

3 - 2*3+1 = 7

as you'd expect.

That's the trick my horrific C experience uses.

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.

def getOpenLockers(int n) {

return (1..Math.sqrt(n)).collect {it**2}

}

println getOpenLockers(100)

And may have a lot of identical twins.

This is what it looks like when run:

Why not

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:

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]

int num = 100, c = 0;

while( ++c*c <= num) System.out.println(c*c);

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

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.

Sorry for repost, its Python by the way, and I needed to sort out the indentation...teach me to preview first in future...

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

for ($i = 1; $i <= $tlockers; $i++) {

if (count(explode(".",(string)sqrt($i))) == 1) {

echo $i."<br>";

}

}

}

while (<>)

{

chomp;

exit if $_ == 0;

$lockerCnt = $_;

print "Locker Count = $lockerCnt\n";

@openLockers = {};

for ($i=1;($i**2)<=$lockerCnt;$i++)

{

push @openLockers, $i**2;

}

$openLockerCnt = @openLockers;

$openLockerCnt--;

for my $lockerNo (@openLockers[1..$openLockerCnt])

{

print "$lockerNo";

if ($lockerNo==@openLockers[$openLockerCnt]) {print "\n";} else {print ", ";}

}

print "Enter number of lockers (0 to exit) > ";

}

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

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

Once commenters watch the simulation, the two most common non-brute force solutions seem to be

1. print out the list of square numbers

2. print out the series created by successive additions of the odd numbers {1, 1+3, 1+3+5, 1+3+5+7, ...}

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>

while ($i<=$numlockers) {

print $i." ";

$i+=$factor+1;$factor+=2;

}

print "\n";

Are you crazy! what kind of place would the intertubes be if people thought before posting...

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;

}

if($i/$sqrt_i == round($i/$sqrt_i)){

$no_of_divisors++;

$state = 'open';

} else {

$state = 'closed';

}

if($max_divisors <= $no_of_divisors) {

if($max_divisors < $no_of_divisors){

$most_toggled = array();

}

$max_divisors = $no_of_divisors;

$most_toggled[] = $i;

}

echo "Locker $i is $state.\n";

}

echo "The most toggled lockers where toggled $max_divisors times"

. "and are numbers " . implode(',', $most_toggled) . ".\n";

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.)

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?

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.

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.

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

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)

I missed the quote, obviously :-(

perl -e"print join', ',map{$_*$_}1..sqrt pop" 100

http://blogs.msdn.com/matthew_van_eerde/archive/2009/08/05/bad-perl-locker-problem.aspx

Addendum (2009-08-05 12:48):48:

perl -e"print map{$_*$_.$/}1..sqrt pop" 100

Addendum (2009-08-05 13:02):47:

perl -e"map{print$_*$_.$/}1..sqrt pop" 100

I still think "say" is cheating but there are two 41-character solutions with it:

perl -E"map{say$_*$_}1..sqrt pop" 100

perl -E"say$_*$_ for 1..sqrt pop" 100

Addendum (2009-08-05 13:23):Someday I'll learn how to count. Counts above are off.

Anyway, 41 character say-less solution:

perl -e"print$_*$_,$/for 1..sqrt pop" 100

37 with say:

perl -E"say$_*$_ for 1..sqrt pop" 100

*SPOILERS*The "100 doors" problem is fairly well known. Fortunately, there's a cheat sheet over at Rosetta Code

We nerds pooled our resources, and even optimized things a bit; The only lockers that will be open are perfect squares of integers. Fortunately, the jocks probably can't read the locker numbers.

* isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.)

* isn't trivially solvable by googling?

* actually requires a computer program?

* requires commenters to read, say, the first ten responses to see whether the problem has been solved?

* doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

Mind you, I liked the Befunge solution.

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 non-perfect 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 1*24, 2*12, 3*8, 4*6. 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: 1*36, 2*18, 3*12, 4*9: 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 perfect-squares code after examining the underlying number theory, that's quite the opposite of cheating - it's recognizing the underlying math to simplify the problem.

<?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 . " ";

}

?>

If you look at it for long enough with your eyes crossed, You'll see the image of a locker.

Addendum (2009-08-05 12:49):Maybe.

For the first few dozen cycles, you get some interesting Conway's Life-like 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!

"Number of lockers"?->A

Int âˆšA->Dim List 1

For 1->B To âˆšA

B^2->List 1[B]

Next

List 1

For a given number n, any integral factor f (1 < f < n), there will be a complementary factor f' (1 < f < n). Collected together, the only way these factors will number evenly will be if f=f' and n=f^2.

Therefore, the resulting opened lockers will be squares of the numbers from 1..sqrt(n).

Anyway, here's the code:

Output for n=100:

1 4 9 16 25 36 49 64 81 100

since the call was for a function definition and the array is an acceptable return value, this can be golfed further to:

sub l{map{$_*$_}1..sqrt pop}

which has a golf count of 29 -- not counting the perl invocation

or:

perl -e 'sub l{map{$_*$_}1..sqrt pop}'

38 with the perl invocation but without an invocation of the function.

Primes. Twice each.

Are you sure that ++c*c works as expected in java? It would not work in c or c++.

Note: LabVIEW sucks

{

List<int> OpenLockers = new List<int>();

int inc = 0;

for (int i = 0; i + inc + 1 <= NumLockers; i++)

{

OpenLockers.Add(i + inc + 1);

i += inc;

inc += 2;

}

return OpenLockers;

}

For example, 6 has prime factors of 1, 2 and 3. That's 3 prime factors. The 6th locker will be toggled 3 times and end up open.

Odd # of factors = open

Even = closed.

I find it hard to believe a bunch of nerds couldn't figure this out.

Locker #1 only gets toggled once. Though I vote for the lockers in the next hall over. They don't get toggled at all during this experiment.

1,4,9,16,.....

Java code. I don't consider this "brute force" because it doesn't go thru each locker and toggle it several times. Although there are better ways to do this.

sub f{map$_**2,1..sqrt pop}

++++++++++[>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<[->+>+>+<<<]>>>[-<<<+>>>]<<[>[>+<-]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]<<<-]>>[->+>+<<]>>[-<<+>>]<[>++++++++++[->>+>+<<<]<[>>>[-<<<-[>]>>>>[<[>]>[---------->>]<++++++[-<++++++++>]<<[<->[->-<]]>->>>[>]+[<]<<[->>>[>]<+[<]<<]<>>]<<]<+>>[->+<<+>]>[-<+>]<<<<<]>>[-<<+>>]<<]>[-]>>>>>>[>]<[.[-]<]<<<<<<<>[-]>[-]+++ +[<+++ +++ +++ ++>-]<.>+ +++[<--->-]<.<<<<-]

Output: 100, 81, 64, 49, 36, 25, 16, 9, 4, 1,

Anguriel: Locker #1 only gets toggled once...

Brad: Primes. Twice each.

Correct so far. What about three times? Four?

Everybodyfailed this test. Have you read the problem?It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door". The sample solutions for n=1 and n=4 are also wrong. It should be: f(1)={1} and f(4)={1;2;3;4}. So TDWTF failed its own test. The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

And your form is broken, it doesn't submit.

After adding the previous line, it did.

And it isn't even correct. Here's a better one, which doesn't generate any warnings and produces a list of the most toggled lockers:

Follow-up to Follow-up: What will the state of the lockers be after n steps of the brute force solution?

and Results

Umm... wasn't that the scenario given?

*doublechecks*

Why yes... yes it was. What problem were you thinking of?

for (int i=1; i*i < 100; ++i)

cout << i*i;

is more computationally efficient than using sqrt - a single multiply is much cheaper than a sqrt.

that's why many games use radius bounding spheres and use distance squared instead of distance - skip the unneeded and expensive sqrt

Oh, wait... these lockers are unused. Forgot. Okay, switch halls, everybody.

(copy+paste in same window)... nuff said... for now.

every "locker challenge"in the story, the best solution would have been to just remember the results from the last time. For bonus points, prank the teacher by putting stickers on the inside of the appropriate lockers sayingThis locker will be open.(Captcha = paratus, latin for "ready". Hmm...)

- All lockers with an odd number of divisors.

- Divisors pair so an odd number of divisors indicates that one occurs twice

- All square numbers

I thought that was the whole point!

function getOpenLockers(n) {

var x = 1;

var i = 1;

var result = '';

while (x <= n) {

result += (x > 1) ? ', ' + x : x;

x += i += 2;

}

return result;

}

or

function getOpenLockers(n, x, i) {

if (!x) i = (x = 1) + 2;

return (x > n) ? '' : ((x > 1) ? ', ' : '') + x + getOpenLockers(n, x + i, i + 2);

}

put this in Excel to cell B1, and copy it to a 100x100 area :)

=IF(MOD(ROW(),COLUMN()-1)=0, IF(A1=0,1,0),A1)

Column CW is the solution itself

The solution is found by determining the number of factors.

1 has a single factor (1) and remains open.

2 has two factors (1,2) and is opened then closed.

3 has two factors (1,3) and is opened then closed.

4 has three factors (1,2,4) and is opened, closed, and reopened.

Each locker that is left open has an odd number of factors.

Factors come in pairs matched from outside in. For example 8 (1,2,4,8) has two pairs of factors: 1*8 and 2*4.

Odd numbers of factors also come in pairs matched from outside in, but the innermost number is used twice. For example 4 (1,2,4) has two pairs of factors: 1*4 and 2*2.

The odd number of factors are only found in numbers that are squares of one of the factors.

The easiest way to calculate the open lockers is to find the square numbers.

Answer in C#

CAPTCHA: damnum

Toggles-

Zero: Lockers on a different hallway/outside range.

One: 1

Two: Primes

Three: Squares of Primes

Four: Product of two Primes; Cubes of Primes

Five: Product of three primes, exactly two of which are identical; Fourth powers of Primes

and so on in that manner

Edit: Utter fail on the five toggles. Fixed in posting below.

Toggles-

Zero: Lockers on a different hallway/outside range.

One: 1

Two: Primes

Three: Squares of Primes

Four: Product of two Primes; Cubes of Primes

Five: Fourth powers of Primes

and so on in that manner

All the numbers in 1*2*3*4 are factors of 24, but do not make up the complete list of factors.

24 has 8 factors: 1,2,3,4,6,8,12,24

These are matched in pairs: (1*24)(2*12)(3*8)(4*6).

i.e. its unlocked if this number is odd, locked if its even

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.

1. Only once

<?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;

?>

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.)

Off by one error

should read

shoulddisplay the white lockers.100% homebrewn befunge code made from some sort of pseudocode.

Non-brute force solution will come soon!

static List<long> getOpenLockers(long numberOfLockers)

{

List<long> openLockers = new List<long>();

for (long i = 1; i*i < numberOfLockers; i++)

{

openLockers.Add(i*i);

}

return openLockers;

}

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.

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?

def getOpenLockers(lockers):

import math

openLockers = []

for i in range(1,int(math.sqrt(lockers))+1):

openLockers.append(i*i)

return openLockers

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 be the prime factorization of our integer, then n will have 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.

Correct, with the caveat that the case n = 1 needs to be checked explicitly since the prime factorization is empty.

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

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.

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 (2009-08-05 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

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>

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.

That's easy: Locker #1 :-)

(ok, gur cevzrf come second equal)

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)

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)

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....

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???

You're Either New here or a troll!!!

nlockers = ARGV[0].to_i

0.upto(nlockers).each { |n|

puts n**2 if n**2 <= nlockers

}

I could have gone with a one liner, but meh.

The Prime Numbers, of course. They are only toggled twice!!

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 ofour 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>

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?

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!

Nope. The locker 1 is only toggle once. Furthermore, it is not a prime locker.

What is the actual point of the problem?

Doesn't make any sense.

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.

Output:

Yeah, I'm no good at maths *or* brainteasers.

And yeah, they're all squares.

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 twenty-eighth 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

Why is it the slowest people always seem to think that their feats are impressive?

WHOOPS - I realised that afterward (and kinda waondered how long before someone else would have a go)

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.)

it's called the collatz theorem.

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.

It can be found at http://rmrf7.co.uk/locker.txt

(Forum software thinks its spam. Pffft.)

The "nerds" in these classes must have been real idiots to have never solved it faster than the jocks. I spent a few minutes on it, but even on paper you wouldn't get more than a couple iterations in, much less actually using physical lockers. I'm fairly intelligent, but even in high school I wasn't top of my class (~11 out of 250, though I was kinda lazy, that's why I like computers).

Lockers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97 were toggled twice

Lockers 4, 9, 25, and 49 were toggled 3 times

Lockers 6, 8, 10, 14, 15, 21, 22, 26, 27, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, and 95 were toggled 4 times

Lockers 16, and 81 were toggled 5 times

Lockers 12, 18, 20, 28, 32, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, and 99 were toggled 6 times

Lockers 64 was toggled 7 times

Lockers 24, 30, 40, 42, 54, 56, 66, 70, 78, and 88 were toggled 8 times

Lockers 36, and 100 were toggled 9 times

Lockers 48, and 80 were toggled 10 times

Lockers 60, 72, 84, 90, and 96 were toggled 12 times

Lockers 60, 72, 84, 90, and 96.

lol, it took me less than 5 minutes to figure out that it was perfect squares, and judging by this article, those nerds are unworthy of the title for having so much trouble figuring it out.

only once: #1.

0 is open 1 is closed.

def locker(n):

result = ""

c = 0

while (len(result) < n):

result += ("1"*c) + "0"

c += 2

return result

print (locker(100))

-- drop table #LockerChallenge

create table #LockerChallenge

( LockerDoor int null,

OpenClosed bit null,

Toggled int null )

declare @i int

select @i = 0

while @i < 100

begin

select @i = @i + 1

insert into #LockerChallenge

( LockerDoor,

OpenClosed,

Toggled )

select @i, -- LockerDoor

0, -- OpenClosed

0 -- Toggled

end

declare @DoorNo int,

@Increment int

select @DoorNo = 0,

@Increment = 0

while @Increment < 100

begin

select @Increment = @Increment + 1

while @DoorNo <= 100

begin

select @DoorNo = @DoorNo + @Increment

update #LockerChallenge

set OpenClosed = 1 - OpenClosed,

Toggled = Toggled + 1

where LockerDoor = @DoorNo

end

select @DoorNo = 0

end

Every other locker gets opened at least twice, once for the very first run, then for the nth run, where n is its locker number...

The teacher isn't really being very nice to the nerds here. If this had a really simple formula, wouldn't that mean we could easily do things like find primes and factor large numbers? You know, those things we base encryption on?

Ultra-compact Befunge, made from:

This version contains 0% brute force.

Every number will have one and itself among its divisors. Except for locker 1, that's two free toggles for everybody, which cancel one another out as far as the final open/shut state goes.

For locker n, if n is prime, that's it. No more divisors and the locker will end up shut.

If n is a perfect square, the square root of n will be another factor, so in that case we'll add another toggle and call it open.

Of course, the perfect square can easily still have other divisors we haven't considered yet. 16 for example has 2 and 8. 100 has a bunch. Somehow we still need to show that there will be an even number of these... argh, it's late. Maybe I'll wake up seeing the obviousness of it...

It's the same thing.

using i as an iterator in F(i)

F(i) returns the i'th locker to end in an open state.

define F(1) = 1 (to make it explicit that i is not a zero based index)

d is the absolute difference between F(i) and F(i-1)

F(i)-F(i-1) = 2i - 1 as proven below.

i^2 - (i-1)^2 = d :

i^2 - (i^2 -2i + 1) = d :expand (i-1)^2

i^2 - i^2 + 2i -1 = d :extract terms from parenthesis

2i - 1 = d :cancel i^2 terms

So yes guys. the difference between two adjacent squares is double the larger root minus 1.

Given that modern processors can do multiplication in just as many clock cycles as addition, the i+d method requires more registers to run and is probably going to be slightly slower than the i^2 method. Additionally, i^2 is easier to understand and maintain later.

Oh wait... it is simple. If n isn't a perfect square, you can pair off all its factors with the one number they'll need to multiply in order to get n.

If n is a perfect square, its square root can pair only with itself. Our locker game doesn't let you count a factor twice this way. On our "10" round, locker 100 gets touched once.

That's basically the whole thing right there. Why all the code solutions anyway? That's little better than the jocks here.

The result it quite predictable. The only times when the number of changes is odd is when each of the prime factorizations has an even power. So:

1 (with no factorizations)

2^2 -> 4

3^2 -> 9

2^4 -> 16

5^2 -> 25

2^2 * 3^2 -> 36

7^2 -> 49

2^6 -> 64

9^2 -> 81

2^2 * 5^2 -> 100

How does it work in c or c++? I'd assume it would do this:

num := 100

c := 0

enter_while_loop

enter_while_condition

c := c + 1

compare:

c*c = 1

lte

num = 100

end_compare

false: exit_while

true: continue

enter_while_body

sysout:

c*c = 1

loop_while

exit_program

(no readed the previous comments, this is all my fault :D )

now for the code:

---------------------------------------------

# no costants?

$opened = 1

$closed = 0

learn toggle $X {

$X1 = $closed

if $X == $closed {

$X1 = $opened

}

return $X1

}

learn test $howMany {

if $howMany < 1 {

print "no lockers, no party..."

forward 20

exit

}

}

# algorithm:

# the locker is toggled if it is evenly divisible for a predecessor

# test it for every predecessor

learn getOpenLockers $nLockers {

test($nLockers)

# 1 is ever unlocked

print 1

forward 20

# we start from 3 because 2 is ever locked

for $currentLocker = 3 to $nLockers {

$thisLocker = $closed

for $prevLocker = 2 to ($currentLocker -1) {

# is evenly divisible, aka remainder is 0 ?

if ((round($currentLocker / $prevLocker)) * $prevLocker) == $currentLocker {

$thisLocker = toggle ($thisLocker)

}

}

# output

if $thisLocker == $opened {

print $currentLocker

forward 20

}

}

}

reset

penup

$howmanyLockers = ask "How many lockers?"

print "Start"

forward 20

getOpenLockers ($howmanyLockers)

print "End"

forward 20

# now, for real :D

learn TR_getOpenLockers $nLockers {

test($nLockers)

for $i = 1 to round((sqrt($nLockers))-0.5) {

print $i * $i

forward 20

}

}

print "not really... :D "

forward 20

TR_getOpenLockers ($howmanyLockers)

print "_this_ is the end... :)"

forward 20

Have you tried the brute force approach or did you just come up with a fancy "solution" to a problem and want to advertise it even though it's incorrect?

The least switched number are of course the prime numbers, switched two times, and the 1, switched one time. The most switched are the numbers who have the greatest amount of divisors.

(Lockers are triggered whenever the number that comes up in the list is a divisor of the locker's number.)

Come to think about it, a locker is left open if it is toggled an odd number of times. In other words, a locker is left open only if its number has an odd number of divisors. But for every divisor of a number, there is another number, lockerNumber/divisor, which is also a divisor. Divisors come in pairs, in other words, which means numbers have an even number of divisors. Unless the number is square, at which point lockerNumber/divisor = divisor for one and only one divisor, the square root, which means it doesn't form a pair. So only squares have odd numbers of divisors. So only square numbered lockers are left open. That makes ten of them, since only the numbers one through ten have squares between one and one hundred inclusive.

10

...

Alright, I'll make a code solution, just give me a minute...

{

return (floor(sqrt((double)door))==sqrt((double)door))

}

Well, the 'clever' solution is

But the more normal solution is probably something along the lines of

Yes, but doing it efficiently is tricky.

To find the maximum number of divisors you need to find the largest highly composite number in the set - we'll call it n0 <= N. I don't know an easy way of generating highly composite numbers other than by filtering products of primorials. So

Step 1. Generate a list of primorials q_i <= N. This is easy - q_i is the product of the ith smallest primes (so q_0=1, q_1=2, q_2=2*3, q_3=2*3*5, q_4=2*3*5*7, q_5=2*3*5*7*11, etc.) We shall ignore q_0 subsequently, since it's not very helpful here.

Step 2. For each number formed by the product of powers of primorials which is <= N (that part is a bit messy) compute the number of divisors. This is again easy - you effectively already have the factorisation. Select the largest number of divisors, and call that d.

Step 3. Find all numbers <= N with d divisors: for every factorisation of derive a prime structure and use on small primes until you exceed N.

Worked example: N = 100.

Step 1: Primorials <= 100 are 2, 6, 30.

Step 2: Candidates are the primorials themselves (30 has 6 divisors), powers of two (64 has 7 divisors), powers of two multiplied by 6 (96 has 12 divisors), powers of two multiplied by 36 (72 has 12 divisors), and 2*30 = 60 (12 divisors). So d=12.

Step 3: 12 factors as 1*12, 2*6, 2*2*3, 3*4; the corresponding prime structures are p0^11, p0^5 * p1, p0^2 * p1 * p2, p0^3 * p1^2.

p0^11: No solutions <= 100

p0^5 * p1: 2^5 * 3 = 96

p0^2 * p1 * p2: 2^2 * 3 * 5 = 60, 2^2 * 3 * 7 = 84, 3^2 * 2 * 5 = 90

p0^3 * p1^2: 2^3 * 3^2 = 72

So the solution set is {96, 60, 84, 90, 72}.

Addendum (2009-08-06 06:02):s/for every factorisation of derive/for every factorisation of d, derive/

Addendum (2009-08-06 06:22):s/30 has 6 divisors/30 has 8 divisors/

Well, I've realized that the test can stop at the half of the current locker number/position. So...

[code]

for $prevLocker = 2 to (round($currentLocker/2)) {

[code]

And, yes, I've learned the use of the "code" tag ^_^;

CYA

D'OH! >_<;;;

This problem immediately remembered me of the Sieve of Eratosthenes.

2nd derivative of x^2: 2

3rd derivative of x^3: 2 * 3

...

Nth derivative of x^N: N!

Pick any sequence of powers to the N, write the difference of subsequent powers, then write the difference of subsequent differences, N times (after that all differences are zero). The differences at the Nth level will always be N!.

This is a fun fact that made me happy as a kid.

"A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

Here's a better (still shitty) one that runs in O(logN) -ish time.

void find_open_lockers(char *lockers[], int num_lockers)

{

int i = 1;

do {

lockers[(i*i)-1] = 1;

i+=1;

if ((i*i) >num_lockers) return;

} while (1)

}

I was working through the problem (without the timer as I'm a coward ;)) and had gotten to the fact that it comes down to the number of factors (or rather the oddness/evenness of the number of factors). I hadn't made the step to the fact that only square numbers have an even number of factors though, so failed at the challenge :(

That said, here's a quick python solution anyway ;)

Addendum (2009-08-06 07:33):Wow... looks like that's the shortest python solution so far.

Has everyone else posting python forgotten about list comprehensions, the built-in power operator and the fact that int() performs a floor? As shown, makes it a one-liner :)

Addendum (2009-08-06 07:35):Also, I meant in my original post that I hadn't noticed that only squares had

oddnumbers of factors, not even.Proof that without work, there's no Collatz.*

Actually this appears not to be the Collatz theorem (or really the Collatz conjecture) anyway - that's the one about the sequence of numbers generated by the rule "if N is even, halve it, else triple it and add 1". The Collatz conjecture is that if N starts as a positive integer, it always reaches the value 1.

http://en.wikipedia.org/wiki/Collatz_conjecture

* -10 for tortured translingual pun, I'm sure.

This assumes that the ForEach extension-function for IEnumerable is defined, which in my projects it always is. But the Mofties forgot it somehow, so with plain .NET 3.5 you have to define it yourself or work around it like

Captcha: "validus", so I guess I have to provide the proof:

Every door is open that gets toggled an odd number of times.

The number of times each door is toggled is equal to its number of dividers (follows directly from the used algorithm).

If X is the number of doors, then for each divider N of X that is smaller than sqrt(X) there must be a number M greater than sqrt(X) such that N*M = X (else N wouldn't be a divider of X and if M <= sqrt(x) then N*M < sqrt(x)*sqrt(x) = X). So M is a divider of X, too, which makes the number of dividers even, except when sqrt(X) is itself an divider of X, which is true only for square-numbers.

So the open doors correspond to all square numbers (including 1) smaller or equal than X.

BTW: The Jocks still won in my case :-/

What's the graph of permitted movement between houses? K5? And is he allowed to visit the fifth house only once?

If my understanding of the problem is correct then the answer is 1, and he leaves 2 rabbits in each house. One way to accomplish this is to visit each house except the fifth twice.

I've worked with guys like you: math background (right?), thinks of himself as much better than all those lowly computer scientists around him, hired as a programmer because there is zero money in math, but refuses to do menial work like actually programming because there's just no challenge in it for a genius like himself.

I've also seen the disorganized piles of shit that such people call code, after they had finally left. And then I'm grateful I don't work with them right now.

Anyway, I feel for you: living between all those stupid people, and chances are you will _never_ solve a new problem in your life. Happiness must be hard to reach under those conditions...

And the jocks would never lose track of which locker they should toggle.... Yeah, right.

Compiles to 57.5 bytes on the calculator. (Yes, it uses half-byte addressing.)

No,

youfailed the reading test. Thanks for playing though.I mean, that took me about a minute to figure out that the open doors are square numbers - IN MY HEAD. Maybe I am being unrealistic about the quality of teaching offered by Mr Zargas, but I would hope that several members of the high school football team would have been able to figure it out.

Or:

# 1 must always remain open

# 2 is the first divider, by logic

diff = 2

open = [1]

last = 1

while last < 100:

last = last + diff

diff = diff * 2

open.append(last)

print "these are open",open

(the above is just made up - but it shgould work-ish)

CREATE FUNCTION getOpenLockers(@lockerCount INT)

RETURNS TABLE

AS

RETURN

SELECT POWER(N,2) AS openLockers

FROM dbo.Tally

WHERE N BETWEEN 0 AND @lockerCount

AND POWER(N,2) <= @lockerCount

That's easy locker 1.. it's only toggled once.

--Zed

locker[n_] := Select[Range[n], IntegerQ[Sqrt[#]] &];

More complicated would be to find the initial configuration, given a final one (actually, the algorithm is time invariant, so it is equivalent to beggining->end).

Once you've found the simple formula for whether any given locker ends up open or closed, your question is really easy to answer.

Locker number 1 is only toggled once, all the others are toggled at least twice. After that the lockers with prime numbers are toggled twice each, non-primes will be more than that.

Show[DiscretePlot[Dimensions[locker[n]][[1]]/n, {n, 1000},

PlotStyle -> Thickness[0.003]],

Plot[n^(-1/2), {n, 1, 1000},

PlotStyle -> {Thickness[0.003], Red, Dashing[0.03]}],

ImageSize -> {800, 600}]

Depends - if the teacher asked the class not to repeat it, likely it wouldn't wander too much. (Possibly it gets mixed up a bit year to year as well). But full marks would be putting something in the lockers (little gnome saying "Open!"?), so that the jocks reveal the answer as they start.

Doesn't surprise me that the nerds had problems though - the obvious method is barred, and you're under both time and social pressure. Not the best conditions for thinking.

Also, 1sec/locker is very generous - I'd expect to see them moving much faster than that (considering you have multiple people, the first few iterations are easy to delegate).

I got this banged out before the simulated jocks finished their first pass.

map (\x->x^2) [1..10]

If I remember correctly, you could refactor lines 40 and 80 into "IF I>N THEN STOP", which would effectively:

1) save one byte inside each of those lines (for the adress byte)

and 2) remove line 160 altogether, which saves yet another byte.

This refactoring gives you three more bytes into which you can cram most anything you fancy: up to three instructions, or up to 24 bits of data, or any combination of the two! Las Vegas, baby!

Ahhh, good ole 1 KB RAM times...

Beautiful.

A suggested rewording of step 2:

Suppose the largest primorial <= N is 2*3*5*...pk

Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

also, a correction to MY ti-89 function:

Result:

...(cant read above this line!)

16

25

36

49

64

81

100

now if i really wanted to i could make it output a list. But thats more code, and its trivial to add stuff later :) Plus you're not a great nerd if you cant at least keep the first 20 squares in your head.

From an implementation point of view that's almost certainly a more useful way of thinking about it, although the logs are mainly useful as documentation - it's almost certainly more efficient to stick to doing multiplication until you exceed N. I'm almost at the point of actually sitting down to write the code and then doing some profiling for N in the order of 10 million.

Given that answer you suggested is totally wrong, it is perfectly possible that the nerds abide by your advice and still lose.

Let's say the inputs are toggle all the lockers for numbers between arbitrary limits (i.e. 100 lockers, toggle by 4-12).

...damn, I should learn OCaml.

Because that is the challenge:

Maybe you can write a mathmatical function with one input and one output instead?

A rough sketch of an implementation, glossing over some steps which would be interesting problems themselves:

given N, find the set of lockers that are toggled the most times

find the smallest locker that was toggled the most times

- find the list of primes less than or equal to N (sieve of Eratosthenes, say)

- find largest primorial 2*3*5*...*p <= N

- note the largest prime, p

- e.g. if N = 100

- 2 = 2

- 2 * 3 = 6

- 2 * 3 * 5 = 30

- 2 * 3 * 5 * 7 = 210

- so the largest primorial <= 100 is 2 * 3 * 5

- note the largest prime is 5

- construct the set of numbers of the form

- - c = 2^n1 * 3^n2 * ... * p^nk

- (that "p" is the specific prime from the largest primorial <= N)

- where c <= N, and n1 >= n2 >= ... >= nk >= 0

- - for (n1 = floor(log2(N)); n1 > 0; n1--)

- - - for n2 = floor(log3(N/2^n1)); n2 >= 0; n2--)

- - - - ...

- (yes, it is possible to nest arbitrarily many loops - you just have to be clever)

- find the elements of the set that maximize the product (n1 + 1)(n2 + 1)...(nk + 1)

- THOSE ELEMENTS INCLUDE THE SMALLEST LOCKER

- and THE MAXIMUM PRODUCT IS THE NUMBER OF TOGGLES

- call the number of toggles t

- e.g. if N = 100

- c = 2^n1 * 3^n2 * 5^n3 - want to maximize (n1 + 1)(n2 + 1)(n3 + 1)

- n1 <= log2(100) = 6.6

- take n1 = 6 through 0 in turn

- n1 = 6:

- - 2^6 = 64 brings the residue of N down to 1.56 so n2 can only be 0

- - - 2^6 * 3^0 * 5^0 = 64: product = (6 + 1) = 7

- n1 = 5:

- - 2^5 = 32 brings the residue of N down to 3.125 so n2 can only be as high as 1

- - - 2^5 * 3^1 = 96 brings the residue of N down to 1.04 so n3 can only be 0

- - - - 2^5 * 3^1 * 5^0 = 96: product = (5 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST

- - - - 2^5 * 3^0 * 5^0 is dominated by 2^5 * 3^1 * 5^0

- n1 = 4:

- - 2^4 = 16 brings the residue of N down to 6.25 so n2 can only be as high as 1

- - - 2^4 * 3^1 = 48 brings the residue of N down to 2.1 so n3 can only be 0

- - - - 2^4 * 3^1 * 5^0 = 48: product = (4 + 1)(1 + 1) = 10

- - - - 2^4 * 3^0 * 5^0 is dominated by 2^4 * 3^1 * 5^0

- n1 = 3:

- - 2^3 = 8 brings the residue of N down to 12.5 so n2 can only be as high as 2

- - - 2^3 * 3^2 = 72 brings the residue of N down to 1.4 so n3 can only be 0

- - - - 2^3 * 3^2 * 5^0 = 72: product = (3 + 1)(2 + 1) = 12 TWELVE IS THE BIGGEST

- - - 2^3 * 3^1 = 24 brings the residue of N down to 4.1 so n3 can only be 0

- - - - 2^3 * 3^1 * 5^0 is dominated by 2^3 * 3^2 * 5^0

- - - 2^3 * 3^0 * 5^0 is dominated by 2^3 * 3^2 * 5^0

- n1 = 2:

- - 2^2 = 4 only brings the residue of N down to 25 so n2 is restricted only by n1

- - 2^2 * 3^2 = 36 brings the residue of N down to 2.7 so n3 can only be 0

- - - 2^2 * 3^2 * 5^0 = 36: product = (2 + 1)(2 + 1)(0 + 1) = 9

- - 2^2 * 3^1 = 12 brings the residue of N down to 8.3 so n3 is restricted only by n2

- - - 2^2 * 3^1 * 5^1 = 60: product = (2 + 1)(1 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST

- - - 2^2 * 3^1 * 5^0 is dominated by 2^2 * 3^1 * 5^1

- - 2^2 * 3^0 * 5^0 is dominated by 2^2 * 3^1 * 5^1

- n1 = 1:

- - these are all dominated by 2^2 * 3^1 * 5^1

- n1 = 0:

- - this is dominated by, um, everything

- smallest locker is in {60, 72, 96}, number of toggles is 12

find the set of lockers that are toggled t times

- find the prime factorization of t = p1^k1 p2^k2 ... pn^kn

- - construct the set F of distinct (not-necessarily-prime) factorizations of t

- - - { {f1, f2, ... fn}: fi > 1, f1*f2*...*fn = t }

- - - e.g. if t = 12, this would be { {2, 2, 3}, {3, 4}, {2, 6}, {12} }

- - construct the set of lockers as follows:

- - for each factorization f in F

- - - grab as many distinct primes pi <= N as there are elements in f

- - - subtract one from each element of f

- - - for each permutation of 1..n => i1...in

- - - - check if p1^(fi1-1)p2^(fi2-1)...pn^(fin-1) <= N

- - - - - if so, that's a locker... add it to the set

- - e.g., if t = 12 and N = 100:

- - - f = {2, 2, 3}

- - - - try primes 2, 3, and 5 first

- - - - - 5^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 60: FOUND!

- - - - - try permuting f:

- - - - - - 5^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 90: FOUND!

- - - - - - 5^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 150 is too big

- - - - try primes 2, 3, and 7 next

- - - - - 7^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 84: FOUND!

- - - - - try permuting f:

- - - - - - 7^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 126 is too big

- - - - - - 7^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 294 is too big

- - - - try primes 2, 5, and 7 next

- - - - - 7^(2 - 1)*5^(2 - 1)*2^(3 - 1) = 140 is too big

- - - - - don't bother permuting f

- - - - - - don't bother trying other primesets

- - - - - - they will only be bigger than 2, 5, 7, which came up empty

- - - f = {3, 4}

- - - - try primes 2 and 3 first

- - - - - 3^(3 - 1)*2^(4-1) = 72: FOUND!

- - - - - try permuting f:

- - - - - - 3^(4 - 1)*2^(3 - 1) = 108 is too big

- - - - try primes 2 and 5 next

- - - - - 5^(3 - 1)*2^(4-1) = 200 is too big

- - - - - don't bother permuting f

- - - - don't bother trying other primesets

- - - - they will only be bigger than 2, 5 which came up empty

- - - f = {2, 6}

- - - - try primes 2 and 3 first

- - - - - 3^(2 - 1)*2^(6 - 1) = 96: FOUND!

- - - - - try permuting f:

= - - - - - 3^(6-1)*2^(2-1) = 486 is too big

- - - - try primes 2 and 5

- - - - - 5^(2 - 1)*2(6 - 1) = 160 is too big

- - - - - don't bother permuting f

- - - - don't bother trying other primesets

- - - - they will only be bigger than 2, 5 which came up empty

- - - f = {12}

- - - - try prime 2 first

- - - - - 2 ^ (12 - 1) = 2048 is too big

- - - - don't bother trying only other primes

- - - - they will only be bigger than 2, which came up empty

print found lockers

e.g. Lockers that are toggled 12 times: 60, 72, 84, 90, 96

- Note that 84 and 90 weren't found in the first section

- This is because their prime factorizations don't have nonascending exponents

- 84 = 2^2*3^1*5^0*7^1; the exponent ascends from 0 to 1 going from base 5 to 7

- 90 = 2^1*3^2*5^1; the exponent ascends from 1 to 2 going from base 2 to 3

EDIT: The example should also try primeset 2, 3, 11 since 2, 3, 7 found something. 2, 3, 11 comes up empty, but the algorithm won't know that

a priori.It's http://projecteuler.net. For the lockers which are toggled the most, look at problems 108 and 110.

Will Programming Praxis get its own link under Content?

Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.

(lambda lockers: [n for n in lockers if sum([1 for i in lockers if n % i == 0]) % 2 != 0])(range(1, K))

where K is the number of lockers. Still thinking about the best one-liner for the second part.

1:>:*v

^> :

+ .

@_1^ 4

` 4

^*4*<

Sometimes, although a general problem is NP-complete, specializations of them are not NP-complete.

See the Monty Python "Mastermind" sketch, where a guest claimed that is specialty was "complicated mathematical problems to which the answer is two."

Ah, my bad - I tend to mangle that URL most of the time. Thanks for the problem links, anyhow - those were fun to solve.

Well, let's start with the straightforward answer before thinking about it too hard. We'll first define the sequence of how many times each locker will be toggled in the nth step:

and then the number of times which each locker gets toggled after 100 steps is obtained by an easy fold:

and of course, lockers are open if they were toggled an odd number of times:

and we can get the indices at which these lockers occur easily enough:

So, we've sort of solved the problem.

I managed this much before the jocks had finished opening the first 100 lockers.

There's just one distasteful thing in all that, which is the fact that we've limited ourselves to just 100 steps, even though our list of lockers is infinitely long. What if we wanted the process to continue forever? Naturally, any one locker will only be toggled a finite number of times, since on the nth step, the first locker to be toggled is the nth, and that is the last step on which that locker gets toggled.

Thinking a little more about the problem, each locker gets toggled once for each of its divisors. So, we'll start with prime factorisation:

and then factoring a number into primes:

and then the number of divisors of n is the number of ways we can pick sub-multisets of its prime factorisation. If p^k is the largest multiple of p which divides n, then we can have any number of copies of p less than or equal to k in a divisor of n, which gives us k+1 possibilities. So for each prime, we count the number of times it occurs, add one, and multiply the results together to count the divisors:

and so we have another solution to the problem:

Of course, looking at it from this perspective, the lockers which are open at the end are those with an odd number of divisors. In order to have an odd number of divisors, none of the numbers which we multiplied together in divisorCount can be even (or the product will be even). Each of those numbers was one more than the number of times that a given prime occurred. So in order for all those numbers to be odd, we need each prime to occur an even number of times:

So:

n is an arbitrary square of another number.

Hence:

Usage from ZX Spectrum BASIC:

Addendum (2009-08-07 16:04):You can try online by yourself if you have Java installed.

The SPAM detector is broken.

Alternative brute-force method that can be used for any arbitrary toggling instructions against lockers in any initial state:

1: Precompute all toggle rules for each pass against each locker (eg. first pass is 1=TOGGLE 2=TOGGLE 3=TOGGLE 4=TOGGLE etc, second pass is 1=SKIP 2=TOGGLE 3=SKIP 4=TOGGLE etc)

2: XOR together all toggle instructions for each locker to obtain an overall toggle instruction for that locker (eg. after the first two passes, first locker is TOGGLE XOR SKIP resulting in TOGGLE, second locker is TOGGLE XOR TOGGLE resulting in SKIP). For the XOR take TOGGLE=1 and SKIP=0.

3: Apply the single resulting toggle instruction to each locker as it is in the initial state (eg. after two passes Locker #1 is toggled but locker #2 is skipped).

1 is divisible only by 1 = 1 % 2 = 1 = open

2 is divisible by 1 and 2 = 2 % 2 = 0 = closed

3 is divisible by 1 and 3 = 2 % 2 = 0 = closed

4 is divisible by 1, 2, and 4 = 3 % 2 = 1 = open

5 is divisible by 1, and 5 = 2 % 2 = 0 = closed

6 is divisible by 1, 2, 3, and 6 = 4 % 2 = 0 = closed

etc...

int lockers[100]; // 0 for close 1 for open

for (int n = 1; n <= 100; n++) {

int c = 0;

for (int d = 1; d <= n; d++) {

int nd= n / d;

if (nd * d == n) {

c++;

}

lockers[n-1] = c % 2;

}

}

he start with (2^N)-1

2^N rabbits for each house

We has winner.

Now,

"In 3009, King Warren of Australia suspects the Earls of Akaron, Bairnsdale, Clearemont, Darlinghurst, Erina and Frankston are plotting a conspiracy against him.

He questions each in private and they tell him:

Akaroa: Frankston is loyal but Erina is a traitor

Bairnsdale: Akaroa is loyal.

Claremont: Frankston is loyal buy Bairnsdale is a traitor.

Darlinghurst: Claremont is loyal but Bairnsdale is a traitor.

Erina: Darlinghurst is a traitor.

Frankston: Akaroa is loyal.

Each traitor knows who the other traitors are, but will always give false information, accusing loyalists of being traitors and vice versa. Each loyalist tells the truth as he knows it, so his information on traitors can be trusted, but he may be wrong about those he claims to be loyal.

How many traitors are there?"

---------

def f(n):

if n == 1: return [1]

elif n == 4: return [1, 4]

tmp = f(n-1)

if n == (tmp[-1] - tmp[-2]) + res[-1] + 2:

tmp.append(n)

return tmp

Good thinking :)

import math

def getOpenLockers(n):

return [(x+1)**2 for x in range(0, math.floor(math.sqrt(n)))]

Well, why program in BASIC if you cannot abbuse GOTOs?

The truth is I as having a hard time in typing this program as the emulator follows the ZX81 keyboard layout. I was also too lazy to write it down on paper before entering or to find an image of the Z81 keyboard.

Btw, I bought the 16K expansion from the start, so I could waste a few bytes...

int x, y, locker [100] = {0}, count [100] = {0};

for (x=1; x<=100; x++){

for (y=x-1; y<100; y=y+x){

count[y]++;

if (locker[y] == 0)

locker[y] = 1;

else locker[y] = 0;

}

}

cout<<"Current state: \n 0 = closed and 1 = open\n\n";

for (x=0; x<100; x++){

cout<<"Locker "<<setw(3)<<right<<(x+1)<<" : "<<locker[x]<<" | flipped "<<count[x]<<" times\n";

}

That's like asking the square root of a million. No one will ever know.

HA-ha.

Umm, the goal is to finish before the jockers!

For each prime factor, take its exponent and add one. Then multiply the results. For example, 12 has 3 * 2 factors because 12 = 2^2 * 3^1. To get an odd result, each prime factor has to appear even times. That means, the locker number has to be a square number. Exactly then the locker will be open in the end.

CAPTCHA: genitus

because Gandalf is a genius... with a large genital.

Locker 1, it is only toggled once, every other locker is toggled at least twice.

that's all I know.

That's the easy way to determine how many perfect squares are between 1 and n (without looping).

Logic says that :

1: If somebody says somebody else is a Traitor, then they're in the other camp.

2: If two people call each other Loyalists, then they must be in the same camp (a Loyalist couldn't mistakenly identify a Traitor as Loyalist in this case, as the Traitor would identify the Loyalist as a Traitor).

3: If person1 from campX calls person2 from campY a Loyalist, person1 must be a mistaken Loyalist, campX must be Loyalist, and campY must be Traitors, as a traitor would identify a Loyalist as a Traitor.

From 1, it can be deduced that A,D,C fall into 1 group, and E,B fall into the other. A infers E infers D infers B. C infers B.

From 2, F falls into the same camp as A, giving A,D,C,F and E,B as the two groups.

From 3, B is a loyalist, and A is a traitor.

Therefore there are 2 loyalists (B,E) and 4 traitors (A,C,D,F)

least opend and closed is Locker#1 (1 times)

You are not thinking of prime numbers, aren't you?

The first is only toggled once, this seems pretty obvious.

"Most opend and closed is 64 times [lockers 7560, 9240]"

"Least openend and closed is 1 time [locker 1]"

100000 times some more :)

And 1 million times takes a whole lot longer :D

Powershell# 50 Bytes

# a function by the exact name which does this. Input gets passed as argument:

# getOpenLocker 100

function getOpenLockers($n){(1..$n|%{$_*$_})-le$n}

# 44 Bytes

# a filter by the same name which solves the problem. Input gets piped into the filter:

# 100 | getOpenLockers

filter getOpenLockers{(1..$_|%{$_*$_})-le$_}

# 39 Bytes

# A script block stored in a variable. Input gets passed from the pipeline via ForEach-Object:

# 100 | % $getOpenLockers

$getOpenLockers={(1..$_|%{$_*$_})-le$_}

how the mighty have fallen. I miss the old days.

"Not brute force" doesn't mean "no loops allowed". The number of elements in the desired output is a monotonic increasing function of the size of the input, so it's impossible to give a correct solution without some form of loop.

Proof: Consider step k: it toggles lockers k, 2k etc., i.e. all the lockers m such that k divides m. So every k which toggles locker n is a divisor of n. Conversely, every divisor of n will toggle locker n, as all divisors of n are <= n and we run as many steps as there are lockers in total, and thus >= n steps.

Remark: This also answers the bonus questions: The more divisors a number n has, the more often the locker n will get toggled. The numbers which get toggled the least are, after 1 (1 divisor), the prime numbers (2 divisors).

Lemma 2: The locker remains closed if it is toggled an even number of times, it ends up opened if it is toggled an odd number of times.

Proof: By induction. If the locker is toggled 0 times, it remains closed. Let lemma 2 be true for k>0. If k is even, the locker is closed after the kth toggle, k+1 is odd and the locker will be open after the k+1st toggle. If k is odd, the locker is open after the kth toggle, k+1 is even and the locker will be closed after the k+1st toggle.

Lemma 3: The nth locker remains closed if n has an even number of divisors, it ends up opened if n has an odd number of divisors.

Proof: Follows from lemmas 1 and 2.

Theorem: Locker n will end up opened if and only if n is a perfect square.

Proof: Let k be a divisor of n such that k*k!=n. Then n/k!=k and n/k is also a divisor of n. It follows that any n which is not a perfect square has an even number of divisors, because k*k cannot equal n for a non-square and because n/(n/k)=k and thus (k,n/k) form pairs. By lemma 3, the locker will stay closed. Now let n be a perfect square and m be the square root of n. The number of divisors != m is even by the same reasoning as for non-square n. Thus, counting m too, the number of divisors is odd. By lemma 3, the locker will be open.

Lemma 4 (used in the implementation): (i+1)*(i+1)=i*i+2*i+1=i*i+i+(i+1)

Proof: Basic algebra.

Thus the function:

Test code:

Any loop which loops over all lockers is brute force. Look at my solution (maybe given by others first, I haven't read through all the comments), it only takes 1 loop iteration per

openlocker. (And no, you can't get the complexity down further as you need to produce the output, so you need at least 1 write per open locker.) I shall also remark that my solution requiresnomultiplication and definitelyno square root.Test code:

main :: IO ()

main = let n = 100 in

print (map fst (filter snd (assocs

(accumArray (\x () -> not x) False (1,n)

[(k,())| m<-[1..n], k<-[m,2*m .. n]]) )))

Some things I've noticed:

- on the i-th iteration, the i-th locker is in its final state

- each locker is toggled a number of times equal to the number of its factors, e.g.: every locker number has 1 as a factor hence they all get toggled at least once. Another e.g.: locker # 4 has 4,2,1 as factors (or divisors, or whatever you want to call them) so it's toggled thrice (yep, I said thrice)

- finally, (a bit obvious) lockers toggled odd number of times finish in the opposite state to which they started; even number of times: same as they started

Addendum (2009-08-09 15:16):BTW I've put index online. Available from here.

RequirementsCounter-Strike:Source

Eventscripts 1.5 installed on server

Installationplace script in the file

UsageCreate local Counter-Strike:Source server

Type the following in console:

The results will be the following:

Script/* it is the sqrt of the MAX_LOCKERS +1

#define DEF_MAX_LOCKERS 65 /* up to 4096 doors */

typedef struct lockers_s

{

uint32_t OpenLocks[DEF_MAX_LOCKERS];

uint32_t numOpenLocks;

} lockers_t;

lockers_t getOpenLockers(uint32_t lockerCount)

{

lockers_t lockers;

uint32_t tmp;

uint32_t count;

lockers.numOpenLocks = (uint32_t) sqrt(lockerCount);

if (lockers.numOpenLocks == 0)

return lockers;

/* only pure squares are left open */

for (count = 1; count <= lockers.numOpenLocks; count++)

{

lockers.OpenLocks[count-1] = count*count;

}

/* and the last one if not already in the list */

if (count*count != lockerCount)

{

lockers.OpenLocks[count] = lockerCount;

lockers.numOpenLocks++;

}

return lockers;

}

whom it seems should have been the one to take it a step further, though it was actually "Mr.Zargus' locker challenge".Zargasuse warnings;

use strict;

sub lockers {

print "Enter a number of lockers: ";

chomp(my $n = <STDIN>);

my @lockers; #0 index will be ignored. So will 1 because those are all open to start.

if ($n == 1) {

@lockers = (1);

print @lockers;

return @lockers;

}

# 1 means open, 0 means closed. For $n > 1, the first round opens all lockers.

my ($i, $j);

for ($i=1; $i<=$n; $i++) {

for ($j=1; $j<=$n; $j++) {

if ($j % $i == 0) { # if the divisor i is a factor of j, there will be no remainder, and we toggle the locker.

if ($lockers[$j] == 1) {

$lockers[$j] = 0;

} else {

$lockers[$j] = 1

}

}

}

}

print "Final lockers: \n";

for ($i=1; $i<=$n; $i++) {

print "Locker $i: $lockers[$i] \n";

}

return @lockers;

}

&lockers;

The easiest starting place is E, because he only names a single traitor.

E is either loyal or a traitor; let's assume he is a traitor.

If E is a traitor then he is lying about D being a traitor, in which case D must be loyal. Therefore, D's information about all traitors must be true (while his knowledge of loyalists may be wrong). If that is the case, then D must be correct about B being a traitor. If B was a traitor, then he is lying about A being loyal. Therefore A must be a traitor. If A were a traitor then he must be lying about E being a traitor, and therefore E must be loyal. However, this contradicts E being a traitor, and therefore E must be loyal. We have proven E must be a loyal by contradiction.

If E is loyal (and he must be) then D must be a traitor. If D is a traitor then he's lying about both B and C. Therefore, B must be loyal and C must be a traitor. If C is a traitor then he is lying about B and F. Therefore, B is loyal (we knew already) and F is a traitor. If F is a traitor then A is a traitor. If A is a traitor then E is loyal (we knew this) and F is a traitor (also known.).

So, in the order we figured it out:

Loyal: E, B

Traitors: D, C, F, A

use warnings;

use strict;

sub lockers {

print "Enter a number of lockers: ";

chomp(my $n = <STDIN>);

my @lockers; #0 index will be ignored.

if ($n == 1) {

@lockers = (1);

print @lockers;

return @lockers;

}

# 1 means open, 0 means closed. For $n > 1, the first round opens all lockers.

my ($i, $j);

#the ones that stay open are the perfect squares, because they end up with

#an odd number of toggles, and thus end up open (opposite of the starting state)

for ($j=1; $j<=$n; $j++) {

@lockers[$j] = 0;

}

my $root_n = sqrt $n;

print "Square root: $root_n";

for ($i=1; $i<=$root_n; $i++) {

$lockers[$i**2] = 1;

}

print "Final lockers: \n";

for ($j=1; $j<=$n; $j++) {

print "Locker $j : $lockers[$j] \n";

}

return @lockers;

}

&lockers;

I suspect there is a flaw in the simulation.

Oh, really? What about 25, 36, 49, 81, 100 ?

Obviously, locker 1 is toggled only once because 1 has only one divisor, itself.

To see which locker is toggled most times, consider which number has the highest number of divisors. For this, we only need to consider the prime factors 2, 3, and 5. (Otherwise, the number gets too large.)

So, the only real candidates are 64, 96, and 60. (If you don't understand this, go to a silent place and meditate about prime factors for some time.)

64 = 2^6 has 7 divisors

96 = 2^5 * 3^1 has 6*2 = 12 divisors

60 = 2^3 * 3 * 5 has 4*2*2 = 16 divisors

So 60 is toggled most often. 16 times.

I'm not really sure about that. I did not check the math, though (wrong time of day for that).

From my point of view the divisors of 60 are 1,2,3,4,5,6,10,12,15,20,30 and 60, which makes 12. Did I miss any?

So most toggles have (according to my brute-force approach) 60,72,84,90 and 96 -> 12 toggles.

For 1.000.000 it's... 720.720 and four more (240 toggles).

There are two perfectly good explanations for those, depending on what you think "^" does.

Explanation 1:

25 = 2^27

36 = 2^38

49 = 2^51

81 = 2^83

Explanation 2:

25 = 2^4.64

36 = 2^5.17

49 = 2^5.615

81 = 2^6.34

Clear as mud.

60 = 2^2 * 3 * 5 has 3*2*2 = 12 divisors

But if you mean XOR, than you can do:

9 = 2^11

In fact, for any x you can find y such as x=2 xor y, so it would not be any rule anyway.

I would say so.

y = x xor 2, in fact.

In fact, for any x and y you can find z such that x = y xor z (specifically, z = x xor y)

For my next trick, I will crack ROT13...

We initial figured that a locker "toggles" when a factor of the number is encountered. Then figured that an odd number of factors would leave the locker open. The formula is something like the sum of all instance from 1 to x (where in this case x is 100) where the number of factors of x is odd. So starting off:

1 has 1 (1 - odd)

2 has 2 (1 2 - even)

3 has 2 (1 3 - even)

4 has 3 (1 2 4 - odd)

5 has 2 (1 5 - even)

... and so on. Further down the locker line...

48 has 10 (1 2 3 4 6 8 12 16 24 48 - even)

49 has 3 (1 7 49 - odd)

50 has 6 (1 2 5 10 25 50 - even)

51 has 4 (1 3 17 51 - even)

Looking at this, we realize that squares are odd because we only count it's square factor once, when it multiplies itself.

As far as least toggled locker, locker #1 only once :) next in line, all prime number are toggled twice (1 and itself), naturally all being closed lockers

Sam

Declare @n int

set @n = 100

; with locker (ID) AS (

SELECT Number

FROM master..spt_values --or any numbers function

WHERE Number > 0

AND Number < @N + 1

AND Name is null

)

SELECT locker.ID [locker], count(locker.ID) [toggles], count(locker.ID) % 2 [state]

FROM locker [locker]

JOIN locker [toggle] ON (locker.ID % toggle.ID) = 0

GROUP BY locker.ID

--Order by 2 asc

as a triangular CTE

optional order by if you want to see the least toggled.

(at least as reported)

n = 100;

L = zeros(1,n);

mask = 1:n;

toggle = zeros(n);

for i=1:n

toggle(i,:) = mod(mask,i)==0;

L = L + toggle(i,:);

L(find(L>1)) = 0;

end

L

t = sum(toggle);

least = find(t==min(t))

most = find(t==max(t))

Make that

toggle = zeros(1, n);

or even just

toggle = L;

(zeros(n) is an n x n matrix)

1*1 = 1

2*2 = 4

3*3 = 9

4*4 = 16

5*5 = 25

6*6 = 36

7*7 = 49

8*8 = 64

9*9 = 81

10*10=100

done.

You're still brutin' it.

Open: Even powers of primes (1,4,9,16,25,49,64,81)

Closed: Everything else.

Most toggled: Whatever has the most prime factors (too lazy to figure it out, so I'm going to guess 60)

Least toggled: 1 (duh) and in second place, all primes.

I meant "perfect square" of course, not "perfect prime".

For all you embedded geeks out there..

For extra points, do not assume English; support at least all languages spoken in the EU.

Seriously, Mrs MeChokemchild suggested a harder problem:

It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door".

Admittedly the simulator takes the number of lockers as input, not the number of togglings, but then the simulation was 'To Get Started' only.

Captcha: capio - I got it! (?)

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

static bool[] doLockers(int size, int iteration)

{

bool[] data;

if (iteration == 1)

data = new bool[size];

else

data = doLockers(size, iteration - 1);

for (int count = iteration - 1; count < size; count = count + iteration)

data[count] = !data[count];

return data;

}

static void Main(string[] args)

{

Console.Write("Enter a number of lockers to toggle: ");

int count = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Results: ");

foreach (bool item in doLockers(count, count))

Console.Write(item ? "1" : "0");

Console.WriteLine();

Console.WriteLine("Press any key to exit");

Console.ReadLine();

}

}

}

The prime number ones are toggled exactly twice, by one and the prime they represent.

1: 1 toggle

Primes: 2 toggles

Perfect Squares: Odd number of toggles, hence open

Other: Even number of toggles, hence closed

As a general rule, each locker is toggled a number of times equal to the number of possible unique groupings of its prime factors that are <= the number of lockers. So for example, take the 20th locker, with factors 2,2,5. It gets toggled:

On the 1st step.

On the 2nd step.

On the (2*2)th[4th] step.

On the 5th step.

On the (2*5)th[10th] step.

And of course on its own (20th) step.

If the number of swaps n is odd (that is, n mod 2 = 1), that locker is open, and if that number is even (n mod 2 = 0), the locker is closed. Thus, locker 20, with six toggles, is closed.

I'm fairly sure that 96 is the locker that would be toggled the most incidentally.

#!C:\Perl\bin\perl

for ($s=1; $s<=100; $s++) {

$myArray[$s] = 0;

}

for ($q=1; $q<=100; $q++) {

for ($i=1; $i<=100; $i++) {

if ($i%$q==0) {

if ($myArray[$i]==0) {

$myArray[$i] = 1;

} else {

$myArray[$i] = 0;

}

}

}

}

$myCounter = 0;

foreach $myNum (@myArray) {

if ($myNum == 1) {

print $myCounter . "\n";

}

$myCounter++;

}

*:>:i.%:100

(11 characters of J), or with precalculating the square root of 100, even shorter (and with it's 9 characters probably the shortest solution posted here):

*:>:i.10

In a lazy 7 minutes all I did was program what the jocks were doing.

DOS batch:

setlocal enabledelayedexpansion

for /l %%x in (1,1,100) do (

set locker%%x=0

for /l %%y in (1,1,100) do (

set /a remainder=%%x%%%%y

if !remainder!==0 if !locker%%x!==0 (set locker%%x=1) else set locker%%x=0

)

echo locker%%x: !locker%%x!

)

Pattern:

(o=open c=closed)

occoccccocccccco (and so on)

Code:

End code

Easy huh?

Strip the comments and you have a very small program, that works!!!

+ I'm not bruteforcing ;)'

I hope the graphical output isn't a problem.

Working sample + output:

http://codepad.org/GAk1EMki