• Paul N (unregistered) in reply to Zecc
    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 1234 = 24 or 2347 = 168 then?

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

    All the numbers in 1234 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: (124)(212)(38)(4*6).

  • Prabhu (unregistered)

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

    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

  • McLenin (unregistered)
    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.
  • (cs) in reply to Alex Papadimoulis

    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;
    
    print Dumper getOpenLockers(1);
    print Dumper getOpenLockers(10);
    print Dumper getOpenLockers(100);
    print Dumper getOpenLockers(1000);
    print Dumper getOpenLockers(5000);
    
    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 N (unregistered) in reply to Brad
    Brad:
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?
    Primes. Twice each.
    1. Only once
  • TheNewOne (unregistered)

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

    <?php $num = 0; $count = 100; $x2 = $x = floor(log($count, 2)); $x3 = 0; while (($x2>=0) && ($x3>=0) && (($num/2*3)<=$count)) { $x2--; $x3++; $num = pow(2, $x2)*pow(3, $x3); } echo $num; ?>
  • (cs)

    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 N (unregistered) in reply to Paul N
    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)
    
  • Tim (unregistered)

    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!

  • McLenin (unregistered)

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

  • Avorntur (unregistered)

    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, [email protected] (unregistered)

    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.

    <?php
      for ($i = 1; $i <= 100; ++$i)
        echo "locker $i is " . (sqrt($i) == floor(sqrt($i)) ? "open" : "closed") . "\n";
    ?>
    
  • DaveK (unregistered)

    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?

  • Stephen (unregistered)

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

  • (cs)

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

    getOpenLockers[n_] := Select[
        ({#, Length@Divisors@#}) & /@ Range[n],
        ! EvenQ[#[[2]]] &
      ] /. {a_, _} -> a;

    Now, this lists all square numbers less than or equal to n, so naturally, a mathematical explanation would be nice.

    Let us assume we have a locker that is open afterwards, and let us call its position n.

    It must be that n has an odd number of divisors, for else the locker would be closed.

    Let [image] be the prime factorization of our integer, then n will have [image] distinct divisors; and this number will only be odd if all k's are even.

    Since all the powers are even, this number will be a square.

    That all squares make for an open locker follows from the above, as all steps are reversible.

  • (cs) in reply to Sebbe
    Sebbe:
    Well, the lockers toggle once for each divisor in the number, so here's a Mathematica oneliner:
    getOpenLockers[n_] := Select[
        ({#, Length@Divisors@#}) & /@ Range[n],
        ! EvenQ[#[[2]]] &
      ] /. {a_, _} -> a;

    Now, this lists all square numbers less than or equal to n, so naturally, a mathematical explanation would be nice.

    Let us assume we have a locker that is open afterwards, and let us call its position n.

    It must be that n has an odd number of divisors, for else the locker would be closed.

    Let [image] be the prime factorization of our integer, then n will have [image] distinct divisors; and this number will only be odd if all k's are even.

    Since all the powers are even, this number will be a square.

    That all squares make for an open locker follows from the above, as all steps are reversible.

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

  • (cs) in reply to Capt. Obvious
    Capt. Obvious:
    Maurits:
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?

    Anguriel: Locker #1 only gets toggled once... Brad: Primes. Twice each.

    Correct so far. What about three times? Four?

    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

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

  • McLenin (unregistered)

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

    I_toStack   	  	  	
    write	
    n_toStack   		 			
    write	
    p_toStack   			
    write u_toStack write t_toStack
    write space_toStack
    write n_toStack write u_toStack write m_toStack write b_toStack write e_toStack write r_toStack write colon_toStack write space_toStack
    write input_pos_toStack read_number temporary_position_toStack 1_toStack 1_toStack write

    lf_toStack   	 	 
    

    write cr_toStack write 1_to_temporary_position_on_Heap label

    temporary_position_toStack temporary_position_toStack fromHeap 1_toStack sum sum_to_temporary_position_on_Heap temporary_position_toStack fromHeap double_top_of_the_stack multiply
    double_top_of_the_stack

    write

    lf_toStack   	 	 
    

    write cr_toStack write input_pos_toStack

    fromHeapa subtract if_negativ_goto_label

    finish

  • McLenin (unregistered)

    Add 3 new lines at the end.

  • (cs) in reply to Maurits
    Sebbe:
    n will have [image] 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?

    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

  • ponky (unregistered) in reply to McLenin

    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.

  • Ninjamobile (unregistered)
    <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 Reigne (unregistered) in reply to Scot
    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 Fouhy (unregistered) in reply to Maurits
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?
    That's easy: Locker #1 :-)

    (ok, gur cevzrf come second equal)

  • Mr.'; Drop Database -- (unregistered)

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

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

  • Mathamagician (unregistered) in reply to Tama
    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 fuckwit (unregistered) in reply to reallyAmazed
    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???

  • mmmkay (unregistered) in reply to Charles400

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

  • Wagout (unregistered) in reply to monkey
    monkey:
    Who is Paula and why is she brill(i)ant?

    You're Either New here or a troll!!!

  • Michael B. (unregistered)

    Ruby: nlockers = ARGV[0].to_i 0.upto(nlockers).each { |n| puts n2 if n2 <= nlockers }

    I could have gone with a one liner, but meh.

  • Jimbo (unregistered) in reply to Maurits
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?
    The Prime Numbers, of course. They are only toggled twice!!
  • Jabluki (unregistered) in reply to Steve
    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>
  • Mad (unregistered) in reply to Streeaker
    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 Shaney (unregistered)

    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 Shaney (unregistered)
    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.

  • zetetic (unregistered)

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

  • devbanana (unregistered)

    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:

    (a+1) * (b + 1) * (c + 1) ...

    This is in PHP5, complete with classes.

    <?php
    class Corridor
    {
    
    private $lockers = array();
    private $mostToggledLockers = array();
    
    public function __construct($numLockers)
    {
    for ($i = 1; $i <= $numLockers; ++$i)
    {
    $sqrt = sqrt($i);
    if (intval($sqrt) == $sqrt)
    {
    array_push($this->lockers, new Locker($i, true));
    }
    else
    {
    array_push($this->lockers, new Locker($i, false));
    }
    }
    }
    
    public function getLockers()
    {
    return $this->lockers;
    }
    
    public function getOpenedLockers()
    {
    return array_values(
    array_filter($this->lockers, array($this, 'filterOpenedLockers'))
    );
    }
    
    public function getClosedLockers()
    {
    return array_values(
    array_filter($this->lockers, array($this, 'filterClosedLockers'))
    );
    }
    
    public function getMostToggledLockers()
    {
    $mostToggledLockers = array();
    
    foreach ($this->lockers as $locker)
    {
    if (empty($mostToggledLockers))
    {
    array_push($mostToggledLockers, $locker);
    }
    elseif ($locker->getTimesToggled() > $mostToggledLockers[0]->getTimesToggled())
    {
    $mostToggledLockers = array($locker);
    }
    elseif ($locker->getTimesToggled() == $mostToggledLockers[0]->getTimesToggled())
    {
    array_push($mostToggledLockers, $locker);
    }
    }
    
    return $this->mostToggledLockers = $mostToggledLockers;
    }
    
    private function filterOpenedLockers(Locker $locker)
    {
    return $locker->getStatus();
    }
    
    private function filterClosedLockers(Locker $locker)
    {
    return !$locker->getStatus();
    }
    
    }
    
    class Locker
    {
    
    private $number;
    private $status;
    private $timesToggled;
    
    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->number = $number;
    $this->status = $status;
    }
    
    public function getNumber()
    {
    return $this->number;
    }
    
    public function getStatus()
    {
    return $this->status;
    }
    
    public function gettimesToggled()
    {
    if ($this->timesToggled)
    {
    return $this->timesToggled;
    }
    
    $primeFactors = getPrimeFactors($this->number);
    
    $timesToggled = 1;
    foreach ($primeFactors as $primeFactor)
    {
    $timesToggled *= $primeFactor['exponent'] + 1;
    }
    
    return $this->timesToggled = $timesToggled;
    }
    
    }
    
    /**
     * This function was inspired from the prime factorisation JavaScript calculator
     * at http://www.btinternet.com/~se16/js/factor.htm
     */
    function getPrimeFactors($number)
    {
    $primeFactors = array();
    
    $factor = 2;
    $primeFactor = array();
    while (pow($factor, 2) <= $number)
    {
    if ($number % $factor == 0)
    {
    if (isset($primeFactor['factor']))
    {
    $primeFactor['exponent']++;
    }
    else
    {
    $primeFactor['factor'] = $factor;
    $primeFactor['exponent'] = 1;
    }
    $number /= $factor;
    }
    else
    {
    if (!empty($primeFactor))
    {
    array_push($primeFactors, $primeFactor);
    }
    $primeFactor = array();
    $factor++;
    }
    }
    
    if (!empty($primeFactor))
    {
    array_push($primeFactors, $primeFactor);
    }
    
    if ($number > 1)
    {
    $lastIndex = count($primeFactors) - 1;
    if ($lastIndex >= 0 && $primeFactors[$lastIndex]['factor'] == $number)
    {
    $primeFactors[$lastIndex]['exponent']++;
    }
    else
    {
    array_push(
    $primeFactors, array(
    'factor' => $number,
    'exponent' => 1
    ));
    }
    }
    
    return $primeFactors;
    }
    
    $startTime = microtime(true);
    
    $numLockers = isset($_GET['number'])
    ? $_GET['number']
    : mt_rand(50, 500);
    
    $corridor = new Corridor($numLockers);
    
    echo "

    There are $numLockers lockers.

    "; echo "

    " . count($corridor->getOpenedLockers()) . " lockers are opened, and " . count($corridor->getClosedLockers()) . " lockers are closed.

    "; $lockers = $corridor->getOpenedLockers(); echo "

    The following lockers are opened:

    \n"; echo "
      \n"; foreach ($lockers as $locker) { echo "
    • " . $locker->getNumber() . "
    • "; } echo "
    \n"; $mostToggledLockers = $corridor->getMostToggledLockers(); echo "

    The following lockers have been toggled the most with " . $mostToggledLockers[0]->getTimesToggled() . " toggles:

    "; echo "
      \n"; foreach ($mostToggledLockers as $mostToggledLocker) { echo "
    • " . $mostToggledLocker->getNumber() . "
    • \n"; } echo "
    "; $endTime = microtime(true); $timespan = $endTime - $startTime; echo "

    Calculated in " . number_format(round($timespan, 5), 5) . " seconds. Take that, jocks!

    "; // This script was for the programming practice at // http://thedailywtf.com/Articles/Nerds,-Jocks,-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!

  • Xythar (unregistered)

    The main thing I've learned from this is that the simulator is pretty to watch if you set it to like 1000 lockers and a 1ms delay.

    Yeah, I'm no good at maths or brainteasers.

  • Shishberg (unregistered)
    lambda n: filter(lambda i: len(filter(lambda j: i%j==0, range(1,n+1))) % 2 == 1, range(1,n+1))

    And yeah, they're all squares.

  • Nigl (unregistered) in reply to Mr.'; Drop Database --
    Mr.'; Drop Database --:
    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

  • Bruno (unregistered) in reply to Mark V Shaney
    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?

  • Jimbo (unregistered) in reply to Mark V Shaney
    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)

  • (cs) in reply to Tim

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

  • Sv3n (unregistered)

    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.

  • (cs) in reply to moltonel

    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.

  • ThatsALotOfGravy (unregistered)

    So many complicated, 'optimised' or esoteric solutions. Have people forgotten that compilers optimise your code FOR you? Here is the proper way to do it in VB.

    It can be found at http://rmrf7.co.uk/locker.txt (Forum software thinks its spam. Pffft.)

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

Log In or post as a guest

Replying to comment #:

« Return to Article