• Guillaume (unregistered)

    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;

int main()
{
   for(i = j = !j; j < NUM_LOCKERS; *(l + j) = 1, ++i, j = i * i);
   *(l + NUM_LOCKERS) = 1;
   printf("Open Lockers: ");
   for(i = 0, l = lockers; i < NUM_LOCKERS; ++l) *l ? printf("%d ", ++i) : i++;
   printf("\n");
}
  • DaveB (unregistered)

    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]

  • Rob G (unregistered)

    An espresso of Java:

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

  • Matt (unregistered)

    obviously the locker toggled the most is the one with the highest number of common divisors in 1-n which are <= itself

  • MattyP (unregistered)

    In IDL:

    pro jock_beater, num_lockers

  num_toggles = INTARR(num_lockers)
  
  for stride = 1L, num_lockers do begin
    num_toggles[stride-1:*:stride] += 1
  endfor
  
  print, 'Open lockers:',  STRCOMPRESS(STRJOIN(WHERE((num_toggles MOD 2) EQ 1) + 1, ", "))
  
  max_toggles = MAX(num_toggles)
  print, 'Max toggles: locker(s)',                                           $
         STRCOMPRESS(STRJOIN(WHERE(num_toggles EQ max_toggles) + 1, ", ")),  $
         ' with', STRCOMPRESS(max_toggles), ' toggles'

end

    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

  • Anonymous Coward (unregistered)

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

  • Anonymous coward (unregistered)

    a(n) = n^2

  • Kris (unregistered)

    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.

  • nobody (unregistered)

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

  • DaveB (unregistered) in reply to DaveB
    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 hands (unregistered) in reply to Alex Papadimoulis

    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

  • Char (unregistered)

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

  • dtremain (unregistered)

    print "Enter number of lockers (0 to exit) > "; while (<>) { chomp; exit if $_ == 0; $lockerCnt = $_; print "Locker Count = $lockerCnt\n"; @openLockers = {}; for ($i=1;($i2)<=$lockerCnt;$i++) { push @openLockers, $i2; } $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) > "; }

  • (cs)
    Ruby:
    require 'mathn'
puts "The open lockers would be #{(1..Math.sqrt(ARGV[0].to_i).floor).collect { |i| i*i }.inspect}"
  • reallyAmazed (unregistered) in reply to dkf

    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

  • Kleist (unregistered) in reply to Alex Papadimoulis

    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
  • Roland (unregistered)

    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 M (unregistered) in reply to BJ Homer
    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 Boller (unregistered)

    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.

  • maisnon (unregistered) in reply to Alex Papadimoulis

    $i = 1; $factor=2; while ($i<=$numlockers) { print $i." "; $i+=$factor+1;$factor+=2; } print "\n";

  • (cs) in reply to reallyAmazed
    reallyAmazed:
    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...

    [image]
  • (cs)

    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();
};

template<int Lock>
struct Door<Lock, 0> {
	enum { State = false };
	static void print_this_and_previous_doors();
};

template<int Lock, int Run>
void Door<Lock, Run>::print_this_and_previous_doors() {
	if (Lock > 1)
		Door<(Lock > 1 ? Lock-1 : 1), Run>::print_this_and_previous_doors();
	printf("Door %d is %s\n", Lock, Door<Lock, Run>::State ? "open" : "closed");
}

int main () {
	Door<100>::print_this_and_previous_doors();
	return 0;
}
  • Gadi (unregistered) in reply to MisterCheese

    Hey, that's the most elegant explanation I've seen so far.. nice..

  • Anon (unregistered)

    A bit more PHP that works out the most toggled in a slightly brute force way.

    define('SOME_FACTOR', 100); $max_divisors = 1; $most_toggled = array(); for($i = 1; $i <= SOME_FACTOR;$i++){ $these_divisors = array(); $no_of_divisors = 0; $sqrt_i = sqrt($i); for($ii = 1; $ii < $sqrt_i; $ii++){ if($i/$ii == round($i/$ii)){ $these_divisors[] = $ii; } $no_of_divisors = count($these_divisors) * 2; }

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

  • Brad (unregistered)

    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;
  • (cs)

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

  • Melvis (unregistered) in reply to eliac
    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?

  • spence91 (unregistered)

    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.

  • BoomWav (unregistered)

    Yay, I actually found it.

    The fact is you'll always toggle them a 2 times unless it has an odd number of factor. The only number that has a impair number of factor are those that has 2 times the same one.

    1 - 1 <-- 2 - 1 2 3 - 1 3 4 - 1 2 4 <-- 5 - 1 5 6 - 1 2 3 6

    As you can see, only 1 and 4 as an odd number of factor. So to get a list of all the open locker, just do:

    1^2, 2^2, 3^2, 4^2, 5^2, 6^2, 7^2, 8^2, 9^2, 10^2

    You got all your lockers.

  • Torge (unregistered)

    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

  • Herohtar (unregistered) in reply to reallyAmazed
    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 Mijelshon (unregistered)

    C#

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

    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
  • (cs) 
    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;
}
  • (cs)

    Mathematica (consider it cheating)

    {IntegerQ[Sqrt[#]], DivisorSigma[0, #]} & /@ Range[100]
  • Thomas Eyde (unregistered) in reply to jstrayer

    This is similar to my first working solution. Then I saw the output and ended up with:

        internal class LockerToggler
    {
        public static int[] OpenLockers(int count)
        {
            return EnumerateSquaresUpTo(count)
                .TakeWhile(i => i <= count)
                .ToArray();
        }
        private static IEnumerable<int> EnumerateSquaresUpTo(int count)
        {
            for (var i = 1; i <= count; i++) yield return i*i;
        }
    }
  • Thomas Eyde (unregistered) in reply to Thomas Eyde
    Thomas Eyde:
    This is similar to my first working solution. Then I saw the output and ended up with:

    I missed the quote, obviously :-(

  • (cs)

    Perl Golf: 54 characters.

    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

  • Michael Mol (unregistered) in reply to Alex Papadimoulis

    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.

  • Bim Job (unregistered)

    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.

  • azredwing (unregistered) in reply to Kevin M
    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 124, 212, 38, 46. 8 factors for 4 pairs of numbers. (I'm not writing a formal proof of this.)

    A perfect square, by definition, has a factor that can be multiplied by itself to get the product. Take 36: 136, 218, 312, 49: 8 factors, 4 pairs of numbers. But then we also have 6*6. Thus, 36 has 9 factors.

    I suppose if someone wrote up the brute force code originally, then changed it after seeing the results, that would be "cheating". But if you wrote up the 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 Straight (unregistered)

    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 Straight (unregistered) in reply to azredwing

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

  • SumSoftwairGai (unregistered)

    Based on the results from the simulation above, here is a function that will give the same results in a far less brute force way (in php)

    <?php function getOpenLockers ($numLockers) { $openLockers = array(); for($i = 1; $i <= floor(sqrt($numLockers)); $i++) { array_push($openLockers, $i * $i); } return $openLockers; } echo "The following lockers are open: "; foreach(getOpenLockers(100) as $num) { echo $num . " "; } ?>
  • (cs)

    Patterns!

    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.

  • markus (unregistered)

    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.

  • (cs)

    i^2 your locker are belong to us.

  • James (unregistered)

    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?

  • (cs)

    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!

  • David (unregistered) in reply to anonym

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

Leave a comment on “Nerds, Jocks, and Lockers”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article