Comment On Nerds, Jocks, and Lockers

Mr. Zargas was the zany math teacher at Cliffmont High that everyone seemed to love. Whether you were a nerd or a jock, he made mathematics interesting, challenging, and fun to learn. That, in and of itself, was impressive enough, but Mr. Zargus took it one step further. When it came time for his frequent "Mathematical Battle of Wits," he would let the jocks use their brawn instead of their brains. The nerds never stood a chance, especially when it came to his "locker challenge." [expand full text]
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9Next »

Re: Nerds, Jocks, and Lockers

2009-08-05 22:34 • by Peter Kelley (unregistered)
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.

Re: Nerds, Jocks, and Lockers

2009-08-05 22:46 • by spiderlama (unregistered)
Python:

from math import sqrt

from math import floor

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

Re: Nerds, Jocks, and Lockers

2009-08-05 22:49 • by Rand (unregistered)
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).

Re: Nerds, Jocks, and Lockers

2009-08-05 23:01 • by Daniel (unregistered)
281302 in reply to 281190
Lockers 1 was toggled once

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

Re: Nerds, Jocks, and Lockers

2009-08-05 23:04 • by Daniel (unregistered)
281303 in reply to 281026
There are 5 lockers that were toggled 12 times.

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

Re: Nerds, Jocks, and Lockers

2009-08-05 23:17 • by Richard (unregistered)
281304 in reply to 281190
This first, it gets toggled only once, and remains open.

Re: Nerds, Jocks, and Lockers

2009-08-05 23:19 • by Bean (unregistered)
"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.

Re: Nerds, Jocks, and Lockers

2009-08-05 23:39 • by TR (unregistered)
281306 in reply to 281190
Um...that's a WTF in itself. The only locker that is toggled
only once: #1.

Re: Nerds, Jocks, and Lockers

2009-08-05 23:52 • by Ransom (unregistered)
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

Re: Nerds, Jocks, and Lockers

2009-08-05 23:55 • by sokolomo (unregistered)
given BruteForce is O(1) this problem appears to have amazingly less to do with a ftw.

Re: Nerds, Jocks, and Lockers

2009-08-06 00:06 • by DaveGamble
Huh? No C++ Template Metaprogramming solution? Ok then:


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

template <int N>
struct Lockers
{
Lockers(vector<int> *vec) {
Lockers<N-1> head(vec);
int sq=sqrt(N);if (sq*sq==N) vec->push_back(N);
}
};

template<>
struct Lockers<1> {
Lockers(vector<int> *vec) {
vec->push_back(1);
}
};



int main (int argc, char * const argv[]) {
vector<int> lockers;
Lockers<100> dolockers(&lockers);

for (vector<int>::iterator i=lockers.begin();i!=lockers.end();i++) cout << *i << ", ";

return 0;
}

Re: Nerds, Jocks, and Lockers

2009-08-06 00:54 • by zzo38
281312 in reply to 281233
nonny nonny:
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!
Actually that's only one of the whole points, not all of them.

Re: Nerds, Jocks, and Lockers

2009-08-06 01:03 • by Shriike (unregistered)
I ran the simulation once, and saw the pattern, after you see it it's pretty easy.
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))

Re: Nerds, Jocks, and Lockers

2009-08-06 01:06 • by Shriike (unregistered)
281314 in reply to 281313
oops, messed up formatting and realized I made a mistake


def locker(n):
result = ""
c = 0
while (len(result) < n):
result += ("1"*c) + "0"
c += 2
return result[:n]
print (locker(100))

Re: Nerds, Jocks, and Lockers

2009-08-06 01:20 • by Kane (unregistered)
I glanced through the comments and couldn't find a SQL solution... So here it is.

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

Re: Nerds, Jocks, and Lockers

2009-08-06 02:04 • by Gonad the Barbarian (unregistered)
The very first locker gets opened the least...

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

Re: Nerds, Jocks, and Lockers

2009-08-06 02:20 • by Biff Tannen (unregistered)
OMFG you guys are the biggest nerds ever, see you in the locker room, get ready for atomic wedgies!

Re: Nerds, Jocks, and Lockers

2009-08-06 02:26 • by DaedalusRaistlin
Written in Myth


Var LockerCount 100
Call GetOpenLockers

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

Re: Nerds, Jocks, and Lockers

2009-08-06 02:58 • by Charlie (unregistered)
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?

Re: Nerds, Jocks, and Lockers

2009-08-06 03:20 • by Tim (unregistered)

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.

Re: Nerds, Jocks, and Lockers

2009-08-06 03:22 • by smartass (unregistered)
281326 in reply to 281190
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).

Re: Nerds, Jocks, and Lockers

2009-08-06 03:27 • by Charlie (unregistered)
281331 in reply to 281322
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...

Re: Nerds, Jocks, and Lockers

2009-08-06 03:27 • by CSK (unregistered)
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 03:33 • by Charlie (unregistered)
281333 in reply to 281331
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 03:44 • by Marc de Jonge (unregistered)
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)

main :: IO ()
main = print $ map fst $ filter (\(x, y) -> odd y) $ map (\x -> (x, timesTouched x)) [1..100]


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

Re: Nerds, Jocks, and Lockers

2009-08-06 03:55 • by noah Richards (unregistered)
281335 in reply to 281190
Prime numbers - they'll only be toggled for 1 and themselves.

Re: Nerds, Jocks, and Lockers

2009-08-06 04:29 • by Rob G (unregistered)
281337 in reply to 281194
tiller:
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++.


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

Re: Nerds, Jocks, and Lockers

2009-08-06 04:39 • by k1 (unregistered)
Logo (KTurtle)

(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

Re: Nerds, Jocks, and Lockers

2009-08-06 04:39 • by Repetition makes it right? (unregistered)
281339 in reply to 281085
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?

Re: Nerds, Jocks, and Lockers

2009-08-06 04:59 • by P.M.Lawrence (unregistered)
In case anyone is interested, this problem (only, with light switches) is covered at http://www.math.hmc.edu/funfacts along with many others.

Re: Nerds, Jocks, and Lockers

2009-08-06 05:02 • by JoeBar (unregistered)
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 05:04 • by Massimo (unregistered)
281342 in reply to 281190
The first one, obviously. It's always toggled only one time.

Re: Nerds, Jocks, and Lockers

2009-08-06 05:07 • by VKS (unregistered)
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...

Re: Nerds, Jocks, and Lockers

2009-08-06 05:12 • by Val (unregistered)
bool isOpen(int door)
{
return (floor(sqrt((double)door))==sqrt((double)door))
}

Re: Nerds, Jocks, and Lockers

2009-08-06 05:36 • by VKS (unregistered)
In bad Haskell...

Well, the 'clever' solution is

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]

Re: Nerds, Jocks, and Lockers

2009-08-06 05:54 • by pjt33
281347 in reply to 281268
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/

Re: Nerds, Jocks, and Lockers

2009-08-06 05:54 • by 2ti6x (unregistered)
281348 in reply to 281190
the first, duh!

Re: Nerds, Jocks, and Lockers

2009-08-06 06:13 • by k1 (unregistered)
281350 in reply to 281338
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

Re: Nerds, Jocks, and Lockers

2009-08-06 06:16 • by k1 (unregistered)
281351 in reply to 281350
k1:


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

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



D'OH! >_<;;;

Re: Nerds, Jocks, and Lockers

2009-08-06 06:49 • by .. ....'s Hospital for the Nameless (unregistered)
Though it is a brute-force way of doing it - at least it is a solution in R.

This problem immediately remembered me of the Sieve of Eratosthenes.


locker_toggling <- function(n_lockers) {
lockers <- rep("closed",length=n_lockers)
show(data.frame(lockers))

for (i in 1:n_lockers) {
for (j in 1:n_lockers) {

if (j %% i == 0) {

if (lockers[j] == "open") {
lockers[j] <- "closed"
}

else {
lockers[j] <- "open"
}

}

}

show(data.frame(lockers))

}

show("open lockers:")
show(which(lockers == "open"))
show("closed lockers:")
show(which(lockers == "closed"))

}

Re: Nerds, Jocks, and Lockers

2009-08-06 07:00 • by ounos
281353 in reply to 281028
anonym:
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 07:05 • by Mike (unregistered)
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?"

Re: Nerds, Jocks, and Lockers

2009-08-06 07:09 • by Dave (unregistered)
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)

}

Re: Nerds, Jocks, and Lockers

2009-08-06 07:11 • by workmad3
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 07:49 • by The General
281358 in reply to 281296
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.

http://en.wikipedia.org/wiki/Collatz_conjecture

* -10 for tortured translingual pun, I'm sure.

Re: Nerds, Jocks, and Lockers

2009-08-06 07:57 • by DanielT (unregistered)
C# 3.5:

static IEnumerable<int> Squares(int max)
{
var i = 0;
while (++i*i <= max)
{
yield return i*i;
}
}

static void Main()
{
Squares(100).ForEach(Console.WriteLine);
}

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 :-/

Re: Nerds, Jocks, and Lockers

2009-08-06 07:58 • by pjt33
281360 in reply to 281355
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.

Re: Nerds, Jocks, and Lockers

2009-08-06 08:27 • by Hizard (unregistered)
281361 in reply to 281190
1 will be toggled least :)

Re: Nerds, Jocks, and Lockers

2009-08-06 08:37 • by Hans (unregistered)
281362 in reply to 281034
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...


Re: Nerds, Jocks, and Lockers

2009-08-06 08:41 • by !? (unregistered)
281363 in reply to 281061
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.
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9Next »

Add Comment