Nerds, Jocks, and Lockers

  • Alex Papadimoulis 2009-08-05 00:37
    Programming Praxis has officially gotten its own category. Next up: perhaps adding a field for the programming language, so we can build an index.

    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.
  • jocks 2009-08-05 09:06
    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. Nymme 2009-08-05 09:08
    #!perl

    sub lockers { return map $_**2, 1..sqrt shift }
  • neat 2009-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!
  • Obvious 2009-08-05 09:14
    Umm squares of 1 to 10?

    Captcha "eros" .....I love you too!
  • Mark 2009-08-05 09:16
    Or to put it more simply- The open lockers are i^2 where i runs from 1-10.
  • Welbog 2009-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 User 2009-08-05 09:17
    Paste this formula in Excel and use copy-down

    =ROW(A1)^2
  • Addison 2009-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.
  • anonym 2009-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
  • Welbog 2009-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 Junker 2009-08-05 09:28
    Haskell:
    lockers n = takeWhile (<= n) [x*x|x<-[1..]]
  • eliac 2009-08-05 09:28
    Looks like the most-toggled locker is the 96th one, with 12 toggles.
  • halcyon1234 2009-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.

  • anonym 2009-08-05 09:30
    for me, I saw the pattern +3, +5 , +7, +9, +11, +13, +15, +17 and +19

    not i^2
  • Daniel 2009-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
  • Anon 2009-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?
  • halber_mensch 2009-08-05 09:37
    Not exactly awesome:

    import math; l=lambda x:map(lambda y: y**2,range(1,int(math.sqrt(x))+1))
  • moltonel 2009-08-05 09:37
    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 ?
  • steenbergh 2009-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

    doLockers = ret
    end function

    response.write "<HR />"
    response.write "<HR />" & doLockers(100)

    %>

  • Welbog 2009-08-05 09:39
    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.
  • Nerd 2009-08-05 09:40
    Thinking just shortly (1-2 min) about it, I'd say that exactly the square numbers stay open.
  • Frunobulax2099 2009-08-05 09:41
    input: totalLockerNum

    max = floor(sqrt(totalLockerNum))

    for i=1; i<=max; i++
    {
    result = i**2;
    add result to array
    }
    return array
  • Kris 2009-08-05 09:41
    anonym:
    for me, I saw the pattern +3, +5 , +7, +9, +11, +13, +15, +17 and +19

    not i^2


    Yes, that would be the pattern for perfect squares.
  • Nick 2009-08-05 09:45
    .NET Solution:


    public static IEnumerable Lockers(int numLockers)
    {
    for(int i = 1; i <= (int)Math.Sqrt(numLockers); i++) {
    yield return (i*i);
    }
    }

  • zbi 2009-08-05 09:45
    i just watched the example and i feel like a jock

    stupid nerds with their fancy "square" numbers, nobody needs em!
  • Anon 2009-08-05 09:46
    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.


    How sad :(
  • anonym 2009-08-05 09:46
    what with the brilliant paula being brillant?
  • seconddevil 2009-08-05 09:47
    Answer:

    perfect squares.

    using formulae:

    (let ((i 0))
    (mapcar (lambda (x)
    (if (zerop (mod (sqrt (incf i)) 1))
    "_"
    x))
    (make-list 100 :initial-element "#")))


    Brute force:

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

    (defun do-all-visits (doors cnt value1 value2)
    "Visits all doors changing the values accordingly"
    (if (< cnt 1)
    doors
    (do-all-visits (visit-every doors cnt 1 value1 value2)
    (- cnt 1)
    value1
    value2)))

    (defun print-doors (doors)
    "Pretty prints the doors list"
    (format T "~{~A ~A ~A ~A ~A ~A ~A ~A ~A ~A~%~}~%" doors))

    (defun start (&optional (size 100))
    "Start the program"
    (let* ((open "_")
    (shut "#")
    (doors (make-list size :initial-element shut)))
    (print-doors (do-all-visits doors size open shut))))

    Solved this ages ago for rosetta code: (http://rosettacode.org/wiki/100_doors#Common_Lisp)
  • esmo 2009-08-05 09:49
    Python:

    import math; def getOpenLockers(i): return [x**2 for x in range(1, 1+int(math.sqrt(i)))]
  • Drew 2009-08-05 09:53
    Using this excuse to practice some Groovy:

    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
  • Gabriel 2009-08-05 09:53
    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.

  • Jim 2009-08-05 09:57
    Yup, only one small change....


    groovy:000> public List getLockers( int numLockers ) {
    groovy:001> (1..Math.sqrt(numLockers)).collect { it*it }
    groovy:002> }
    ===> true
    groovy:000> getLockers(1)
    ===> [1]
    groovy:000> getLockers(100)
    ===> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    groovy:000> getLockers(30)
    ===> [1, 4, 9, 16, 25]
    groovy:000>

  • ponky 2009-08-05 09:57
    Might as well bandwagon on the languages thing:
       
    






























    You can download it here

    I'm getting eaten by the spam detector, uh oh.
  • Anonymous 2009-08-05 09:57
    Ah, I think I see the WTF here...

  • Steve the Cynic 2009-08-05 09:58
    Drew:
    Using this excuse to practice some Groovy:

    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.
  • daralick 2009-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() )
  • Zecc 2009-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.
  • Welbog 2009-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.
  • Zecc 2009-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.
  • Zecc 2009-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.
  • Scot 2009-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 Graham 2009-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;

    }
  • Martin 2009-08-05 10:10
    Even worse is when the problem was already solved by Tom and Ray on Car Talk:

    http://www.cartalk.com/content/puzzler/transcripts/200546/answer.html
  • Ozmo 2009-08-05 10:12
    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!
  • Medinoc 2009-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.
  • steenbergh 2009-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...
  • Olav 2009-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 Cynic 2009-08-05 10:12
    Re: "96 has the most"...

    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
  • reallyAmazed 2009-08-05 10:13
    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 Balassa 2009-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;

  • pjt33 2009-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).
  • Daniel 2009-08-05 10:15
    Sinclair ZX81 / Timex TS100 (via emulator):



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

  • Mamont 2009-08-05 10:16
    sub getOpenLockers {
    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;
    }
  • Welbog 2009-08-05 10:16
    reallyAmazed:
    simply - squares of prime numbers (or perfect squares)

    I'm amazed with amount of i^2 solutions. Think a bit longer before posting.
    16 is not the square of a prime number, yet it remains open. The i^2 solution is common because it's correct.
  • micksam7 2009-08-05 10:16
    Quicky crappy php using square-checking ~


    function locker($in) {
    $out="";
    for($t=1;$t<=$in;$t++)
    $out .= pow($t,.5) == round(pow($t,.5)) ? "{$t}, " : "";
    return substr($out,0,-2);
    }


    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
  • lolwtf 2009-08-05 10:19
    #include <stdio.h>

    int main(int argc, char **argv)
    {
    printf("4 9 16 25 36 49 64 81\n");
    return 0;
    }

    Totally optimized.
  • Tim 2009-08-05 10:20
    This Befunge program works OK on 2 and 10. Output is reversed though. I'm currently testing it on 100.


    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 <
    >00g1g.v ; #[#00]1 = 0 ;
    v <
    >00g0`v; } while (#00 > 0) ;
    v <
    ^_v
    v <
    >@ ; exit() ;



    ; ; denote pseudo-code, sort of
  • noway! 2009-08-05 10:22
    In BASICish (num being number of lockers):

    For i=1 to sqrt(num)
    print i*i
    next
  • Charles400 2009-08-05 10:24
    If I got this as an interview question, I'd go postal. Promise.
  • Børge N 2009-08-05 10:24
    Some ancient guy has already figured out the solution to the "number of toggles" question.
  • Nathon 2009-08-05 10:24
    Sorta brute force-ish...

    def testy (number):
    skip = 3
    sum = 3
    step = 1
    while True:
    if number <= sum:
    return step
    skip += 2
    sum += skip
    step += 1
  • Tama 2009-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.
  • MichaelM 2009-08-05 10:24

    #!/usr/bin/env ruby

    def getOpenLockers(lockers)
    (1..lockers).map {|locker| locker if(Math.sqrt(locker) % 1 == 0)}.compact
    end

    puts getOpenLockers(ARGV[0].to_i).join(', ')


    YAY!
  • Shoko 2009-08-05 10:26
    public class LockersApp {

    /**
    * @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() + ",");
    }
    }
    }
  • Tama 2009-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.
  • BobbyBob 2009-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
  • reallyAmazed 2009-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ūns 2009-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;
    }
  • port 2009-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.
  • belgariontheking 2009-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.
  • mpcube 2009-08-05 10:39
    A PHP Solution...

    <?php for($i=1;$i*$i<=100;$i++)echo($i*$i)."\n";?>
  • BobbyBob 2009-08-05 10:41
    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 blake 2009-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

    select * from @lockers where state = 1
  • Rob 2009-08-05 10:46
    Untested and messy php


    <?PHP
    function lockers( $n )
    {
    $ret = "1,";
    while ( $i = 2; $i^2 < $n; $i++ )
    {
    $ret .= "$i,";
    }
    return $ret;
    }

    print_r lockers(100);
    ?>
  • pjt33 2009-08-05 10:46
    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)

    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.
  • MisterCheese 2009-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...
  • Zack 2009-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.
  • kennytm 2009-08-05 10:50
    C++, by Brute force.


    #include <cstdio>
    #define DOORCOUNT 100

    template <int Lock, bool LockFrozen = true, int Run = DOORCOUNT>
    struct DoorColor {
    typedef typename DoorColor<Lock, (Lock<=Run)||(Lock%Run!=0), Run-1>::color color;
    typedef typename DoorColor<Lock, (Lock<=Run)||(Lock%Run!=0), Run-1>::anticolor anticolor;
    static void print();
    };

    template <int Lock, int Run>
    struct DoorColor<Lock, false, Run> {
    typedef typename DoorColor<Lock, (Lock<=Run)||(Lock%Run!=0), Run-1>::anticolor color;
    typedef typename DoorColor<Lock, (Lock<=Run)||(Lock%Run!=0), Run-1>::color anticolor;
    static void print();
    };

    template <int Lock>
    struct DoorColor<Lock, true, 0> {
    typedef char color;
    typedef struct { char x[256]; } anticolor;
    static void print();
    };

    template <int Lock>
    struct DoorColor<Lock, false, 0> {
    typedef char color;
    typedef struct { char x[256]; } anticolor;
    static void print();
    };

    template <int Lock, bool LockFrozen, int Run>
    void DoorColor<Lock,LockFrozen,Run>::print() {
    std::printf("Door %d is %s.\n", Lock, sizeof(typename DoorColor<Lock,LockFrozen,Run>::color) == 1 ? "closed" : "open");
    }

    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


    template <int Lock>
    struct DoorColor<Lock, true, 0> {
    typedef struct { char x[256]; } color;
    typedef char anticolor;
    static void print();
    };


    To enforce the 1st door to be open initially. Yeah, templates are crazy.
  • David Kowis 2009-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.
  • Anonymous 2009-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?

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

    <thinking>
    <thinking>
    <thinking>
    <don't worry, I'm getting there...>
  • John 2009-08-05 10:52
    Might be worth al least putting some form of color behind the title.

    White-on-white doesn't work out too well...
  • egilhh 2009-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

  • jonnyq 2009-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.

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

  • Fernando 2009-08-05 11:01
    Stupid short solution in PHP:
    <?php
    
    function getOpenLockers($lockers)
    {
    $openLockers = array();
    for ( $i = 0; $i < (int)sqrt($lockers);; $i++ ) $openLockers[] = pow( ($i + 1), 2 );
    return $openLockers;
    }
    ?>
  • dkf 2009-08-05 11:01
    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 admire your mathematical skills! Now do it for an irrational number of lockers, so that your reasoning powers can be truly matched...
  • BJ Homer 2009-08-05 11:04
    In Python:

    [code]
    count = int(sys.argv[1])

    open_lockers = []
    for i in range(1, count+1):
    factors = [j for j in range(1, i+1) if i%j == 0]
    if len(factors) % 2 == 1:
    open_lockers.append(i)

    print open_lockers
    [code]

    You know, just in case they decide to change the rules on square numbers or anything.
  • indrora 2009-08-05 11:09
    ok. This one is easy once you get the fact its a square system. the algorithm is simple:
    for(int l=1;l*l<=n;l++) {Console.WriteLine(" locker "+(l*l) + " is open" ); }

    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? )
  • amischiefr 2009-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 Fire 2009-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.
  • azredwing 2009-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 Flowers 2009-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.
  • DaveGamble 2009-08-05 11:15
    C, 66chars:

    void f(int l){for(int i=0,j=0;++i<=l;i+=(j+=2))printf("%d,",i);}

    I'm claiming extra credit for not using multiplication, and it being deeply, deeply ugly code.
  • monkey 2009-08-05 11:17
    Who is Paula and why is she brill(i)ant?
  • DaveGamble 2009-08-05 11:19
    Matt Flowers:

    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.


    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.
  • Capt. Obvious 2009-08-05 11:20
    I'm amazed at the number of brute force methods.

    I'm surprised at the nerds in the story as well. If you cannot solve a problem mathematically, optimize the numeric method. To wit, they could have used a bike to traverse the lockers. Or 100 boxes on a sheet of paper.
  • Reverend Gonzo 2009-08-05 11:20
    Groovy

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

    println getOpenLockers(100)
  • curtmack 2009-08-05 11:20
    That guy in Nethack is totally a jock.

    And may have a lot of identical twins.

    #!/usr/bin/perl
    

    $n = $ARGV[0];

    foreach $s (1..$n) {
    for ($i = $s-1; $i<$n; $i += $s) {
    $h[$i] = !$h[$i];
    }
    for ($i = 0; $i<$n; $i++) {
    print ($h[$i] ? "'" : "+");
    }
    print "\n";
    for ($i = 1; $i<=$n; $i++) {
    print (($i % $s || $i+1<$s) ? " " : "@");
    }
    print "\n\n";
    }


    This is what it looks like when run:

    curtmack@cardboardbox:~$ ./hall.pl 10
    
    ''''''''''
    @@@@@@@@@@

    '+'+'+'+'+
    @ @ @ @ @

    '+++'''+++
    @ @ @

    '++'''''++
    @ @

    '++'+'''+'
    @ @

    '++'++''+'
    @

    '++'+++'+'
    @

    '++'+++++'
    @

    '++'++++''
    @

    '++'++++'+
    @
  • pjt33 2009-08-05 11:20
    DaveGamble:
    C, 66chars:

    void f(int l){for(int i=0,j=0;++i<=l;i+=(j+=2))printf("%d,",i);}

    I'm claiming extra credit for not using multiplication, and it being deeply, deeply ugly code.

    Why not
    void f(int l){for(int i=1,j=1;i<=l;i+=(j+=2))printf("%d,",i);}
  • Guillaume 2009-08-05 11:22
    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 2009-08-05 11:22
    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 2009-08-05 11:24
    An espresso of Java:

    int num = 100, c = 0;
    while( ++c*c <= num) System.out.println(c*c);
  • Matt 2009-08-05 11:26
    obviously the locker toggled the most is the one with the highest number of common divisors in 1-n which are <= itself
  • MattyP 2009-08-05 11:28
    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 2009-08-05 11:28
    status(n) = #divisors(n) % 2
  • Anonymous coward 2009-08-05 11:28
    a(n) = n^2
  • Kris 2009-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.
  • nobody 2009-08-05 11:29
    At the end, the only lockers that would be opened are squares of numbers. That should make this easy.
  • DaveB 2009-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 hands 2009-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
  • Char 2009-08-05 11:32
    function getLockers($tlockers) {
    for ($i = 1; $i <= $tlockers; $i++) {
    if (count(explode(".",(string)sqrt($i))) == 1) {
    echo $i."<br>";
    }
    }
    }
  • dtremain 2009-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) > ";
    }
  • atrophic 2009-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}"

  • reallyAmazed 2009-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



  • Kleist 2009-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
  • Roland 2009-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 M 2009-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 Boller 2009-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.
  • maisnon 2009-08-05 11:44
    $i = 1; $factor=2;
    while ($i<=$numlockers) {
    print $i." ";
    $i+=$factor+1;$factor+=2;
    }
    print "\n";
  • seconddevil 2009-08-05 11:49
    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...

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

    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 2009-08-05 11:52
    Hey, that's the most elegant explanation I've seen so far.. nice..
  • Anon 2009-08-05 11:54
    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 2009-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;
  • zzo38 2009-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.)
  • Melvis 2009-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?
  • spence91 2009-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.
  • BoomWav 2009-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.

    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 2009-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
  • Herohtar 2009-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 Mijelshon 2009-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;
    }
    }
  • lolwut 2009-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

  • jstrayer 2009-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;
    }

  • kennytm 2009-08-05 12:13
    Mathematica (consider it cheating)


    {IntegerQ[Sqrt[#]], DivisorSigma[0, #]} & /@ Range[100]
  • Thomas Eyde 2009-08-05 12:20
    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 2009-08-05 12:21
    Thomas Eyde:
    This is similar to my first working solution. Then I saw the output and ended up with:


    I missed the quote, obviously :-(
  • Maurits 2009-08-05 12:26
    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 2009-08-05 12:32
    *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 2009-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.
  • azredwing 2009-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 Straight 2009-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 Straight 2009-08-05 12:40
    Wow. I can't believe the reason only squares have an odd number of factors didn't occur to me.
  • SumSoftwairGai 2009-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)

    <?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 . " ";
    }

    ?>
  • derula 2009-08-05 12:44
    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 2009-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 Dependent 2009-08-05 12:45
    i^2 your locker are belong to us.
  • James 2009-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 Bus 2009-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!
  • David 2009-08-05 12:49
    Because (n+1)^2 = n + (2n+1)
  • self 2009-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
  • DeepCerulean 2009-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
  • Anonymous 2009-08-05 12:52
    Way too much time on my hands:
    Is LOLcode acceptable?
    No it isn't. Ever. Now die.
  • Thuktun 2009-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).
  • aleph 2009-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-Paul 2009-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;
  • Maurits 2009-08-05 13:09
    Follow-up question: which lockers are toggled the LEAST?
  • Torge 2009-08-05 13:18
    Maurits:
    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


    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.
  • Brad 2009-08-05 13:21
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?

    Primes. Twice each.
  • Spectre 2009-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)))

  • tiller 2009-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++.
  • Anon 2009-08-05 13:24
    LabVIEW:



    Note: LabVIEW sucks
  • Ryan 2009-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 nerd 2009-08-05 13:26
    I don't believe that a bunch of football players could correctly determine what they had to do.
  • Dean 2009-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.
  • Anguirel 2009-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.
  • Dean 2009-08-05 13:32
    Actually scratch that, I meant factors not prime factors
  • gpan 2009-08-05 13:34
    Very simple. The lockers that stay open are the ones whose #'s are perfect squares.
    1,4,9,16,.....

  • rm5248 2009-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.
  • Me 2009-08-05 13:46
    Perl golf... here's 27 chars :)

    sub f{map$_**2,1..sqrt pop}
  • ircmaxell 2009-08-05 13:49
    The obligatory BrainFuck:

    ++++++++++[>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<[->+>+>+<<<]>>>[-<<<+>>>]<<[>[>+<-]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]<<<-]>>[->+>+<<]>>[-<<+>>]<[>++++++++++[->>+>+<<<]<[>>>[-<<<-[>]>>>>[<[>]>[---------->>]<++++++[-<++++++++>]<<[<->[->-<]]>->>>[>]+[<]<<[->>>[>]<+[<]<<]<>>]<<]<+>>[->+<<+>]>[-<+>]<<<<<]>>[-<<+>>]<<]>[-]>>>>>>[>]<[.[-]<]<<<<<<<>[-]>[-]+++ +[<+++ +++ +++ ++>-]<.>+ +++[<--->-]<.<<<<-]


    Output: 100, 81, 64, 49, 36, 25, 16, 9, 4, 1,
  • Davidm 2009-08-05 13:52
    Brute force Delphi:

    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.
  • Maurits 2009-08-05 13:53
    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?
  • Mrs MeChokemchild 2009-08-05 13:55
    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 MeChokemchild 2009-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.
  • Spectre 2009-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:


    most.toggled.brute <- function(n) (function(x) which(x == max(x))) (Reduce(
    '+', lapply(1:n, function(k) rep(c(rep(0, k-1),1), length.out=n))
    ))

  • Code Dependent 2009-08-05 14:06
    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.
    n is the number of lockers, not the number of toggles. The toggling takes place as described.
  • Steve 2009-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?
  • jmcnary 2009-08-05 14:35
    Here's my solution, without looking at comments.

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

    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;

    public class LockerChallenge {

    //No wonder the jocks always win, as this involvs prime factorizations of numbers
    //Introduce a memory to help speed things up;

    private static Map<Integer, Map<Integer, Integer>> numberFactorizations = new HashMap<Integer, Map<Integer, Integer>>();


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

    public static void main(String argv[]) {
    calculateAndDisplay(1);
    calculateAndDisplay(4);
    calculateAndDisplay(50);
    calculateAndDisplay(100);
    }

    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 void printHighCount(List<LockerState> lockerStates) {
    int highCount = lockerStates.get(0).toggles;
    System.out.print(" (" + highCount + "): " + lockerStates.get(0).lockerNumber);
    for(int index = 1; index < lockerStates.size() && lockerStates.get(index).toggles == highCount; index++) {
    System.out.print(" " + lockerStates.get(index).lockerNumber);
    }
    }

    private static void printOpenLockers(List<LockerState> lockerStates) {
    for(LockerState lockerState : lockerStates) {
    if(lockerState.isOpen()) {
    System.out.print(" " + lockerState.lockerNumber);
    }
    }

    }

    private static List<LockerState> calculateLockerStates(int numberOfLockers){
    List<LockerState> openLockers = new ArrayList<LockerState>();
    //Locker 1 is always open.
    openLockers.add(new LockerState(1, 1));
    for(int index = 2; index <= numberOfLockers; index++) {
    Map<Integer, Integer> factors = createPrimeFactorization(index);
    int toggles = 0;
    for(Integer exponents : factors.values()) {
    toggles += exponents;
    }
    //be sure to add one for the initial toggle -- the prime factorizations
    //only count additional toggles.
    openLockers.add(new LockerState(index, toggles+1));
    }

    return openLockers;
    }

    private static int integerSquareRoot(int number) {
    return (int) Math.sqrt(number);
    }

    private static Map<Integer, Integer> getPrimeFactorization(int number){
    if(numberFactorizations.containsKey(number)) {
    return numberFactorizations.get(number);
    } else {
    numberFactorizations.put(number, createPrimeFactorization(number));
    return numberFactorizations.get(number);
    }
    }

    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.

    Calculating for 100 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 51 54 55 56 57 58 60 62 64 65 69 74 77 81 82 84 85 86 87 88 90 91 93 94 95 96 100
    Lockers With highest Toggle Count (7): 64 96
    Calculation took 16 milliseconds.

  • B 2009-08-05 14:37
    Mrs MeChokemchild:
    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?

  • Kazan 2009-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
  • Shinobu 2009-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 Coward 2009-08-05 14:45
    In Befunge98:

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

  • DeadPanda 2009-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 Dependent 2009-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 Frankenstein 2009-08-05 15:00
    javascript:getPaula()
    (copy+paste in same window)... nuff said... for now.
  • zzo38 2009-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
  • Streeaker 2009-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...)
  • BCS 2009-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
  • czetts 2009-08-05 15:32
    perl -e "while($_**2<$ARGV[0]){$_++};print" 100
  • nonny nonny 2009-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!
  • atrophic 2009-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 }

    times_toggled = Hash.new([])
    toggles.each { |k,v| times_toggled[v] = times_toggled[v] + [k] }

    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 Kroske 2009-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)
  • jwd 2009-08-05 15:41
    ahh, my daily wtf: untested and excessively complicated
  • Two more options in JavaScript 2009-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);
    }
  • mikocs 2009-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üder 2009-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 N 2009-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. Obvious 2009-08-05 16:08
    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: 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. Obvious 2009-08-05 16:08
    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
  • Paul N 2009-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).
  • Prabhu 2009-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 of 2009-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
  • McLenin 2009-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 SHUN 2009-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;

    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 2009-08-05 16:54
    Brad:
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?

    Primes. Twice each.

    1. Only once
  • TheNewOne 2009-08-05 16:59
    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;
    ?>
  • Jordan Gray 2009-08-05 17:01
    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 2009-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)
  • Tim 2009-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!
  • McLenin 2009-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).
  • Avorntur 2009-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.net 2009-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.

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

  • DaveK 2009-08-05 17:18
    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 2009-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

  • Sebbe 2009-08-05 17:25
    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 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.
  • Maurits 2009-08-05 17:31
    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 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.
  • Maurits 2009-08-05 17:35
    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
  • Sebbe 2009-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.
  • McLenin 2009-08-05 17:40
    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 2009-08-05 17:42
    Add 3 new lines at the end.
  • Maurits 2009-08-05 17:49
    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?

    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 2009-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.
  • Ninjamobile 2009-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 Reigne 2009-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 Fouhy 2009-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 fuckwit 2009-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 Reigne 2009-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)
  • Mathamagician 2009-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 fuckwit 2009-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???
  • mmmkay 2009-08-05 18:32
    I've had this as an interview question. Didn't even get the job.
  • Wagout 2009-08-05 18:34
    monkey:
    Who is Paula and why is she brill(i)ant?


    You're Either New here or a troll!!!
  • Michael B. 2009-08-05 18:44
    Ruby:
    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.
  • Jimbo 2009-08-05 18:45
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?

    The Prime Numbers, of course. They are only toggled twice!!
  • Jabluki 2009-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>
  • Mad 2009-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 Shaney 2009-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 Shaney 2009-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.
  • zetetic 2009-08-05 19:42
    I don't understand this problem.
    What is the actual point of the problem?
    Doesn't make any sense.
  • devbanana 2009-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:

    (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 "<p>There are $numLockers lockers.</p>";

    echo "<p>" .
    count($corridor->getOpenedLockers()) .
    " lockers are opened, and " .
    count($corridor->getClosedLockers()) .
    " lockers are closed.</p>";

    $lockers = $corridor->getOpenedLockers();

    echo "<p>The following lockers are opened:</p>\n";

    echo "<ul>\n";
    foreach ($lockers as $locker)
    {
    echo "<li>" . $locker->getNumber() . "</li>";
    }
    echo "</ul>\n";

    $mostToggledLockers = $corridor->getMostToggledLockers();

    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!
  • Xythar 2009-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.

    Yeah, I'm no good at maths *or* brainteasers.
  • Shishberg 2009-08-05 20:00
    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 2009-08-05 20:09
    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 2009-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?
  • Jimbo 2009-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)
  • curtmack 2009-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.)
  • Sv3n 2009-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.
  • RogerInHawaii 2009-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.
  • ThatsALotOfGravy 2009-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 can be found at http://rmrf7.co.uk/locker.txt
    (Forum software thinks its spam. Pffft.)
  • Peter Kelley 2009-08-05 22:34
    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.
  • spiderlama 2009-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)]
  • Rand 2009-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).
  • Daniel 2009-08-05 23:01
    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
  • Daniel 2009-08-05 23:04
    There are 5 lockers that were toggled 12 times.

    Lockers 60, 72, 84, 90, and 96.
  • Richard 2009-08-05 23:17
    This first, it gets toggled only once, and remains open.
  • Bean 2009-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.
  • TR 2009-08-05 23:39
    Um...that's a WTF in itself. The only locker that is toggled
    only once: #1.
  • Ransom 2009-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
  • sokolomo 2009-08-05 23:55
    given BruteForce is O(1) this problem appears to have amazingly less to do with a ftw.
  • DaveGamble 2009-08-06 00:06
    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;
    }

  • zzo38 2009-08-06 00:54
    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.
  • Shriike 2009-08-06 01:03
    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))
  • Shriike 2009-08-06 01:06
    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))
  • Kane 2009-08-06 01:20
    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
  • Gonad the Barbarian 2009-08-06 02:04
    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...
  • Biff Tannen 2009-08-06 02:20
    OMFG you guys are the biggest nerds ever, see you in the locker room, get ready for atomic wedgies!
  • DaedalusRaistlin 2009-08-06 02:26
    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
  • Charlie 2009-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?
  • Tim 2009-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.
  • smartass 2009-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).
  • Charlie 2009-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...
  • CSK 2009-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.
  • Charlie 2009-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 Jonge 2009-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)

    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
  • noah Richards 2009-08-06 03:55
    Prime numbers - they'll only be toggled for 1 and themselves.
  • Rob G 2009-08-06 04:29
    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
  • k1 2009-08-06 04:39
    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
  • 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.Lawrence 2009-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.
  • JoeBar 2009-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.
  • Massimo 2009-08-06 05:04
    The first one, obviously. It's always toggled only one time.
  • VKS 2009-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...
  • Val 2009-08-06 05:12
    bool isOpen(int door)
    {
    return (floor(sqrt((double)door))==sqrt((double)door))
    }
  • VKS 2009-08-06 05:36
    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]
  • pjt33 2009-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/
  • 2ti6x 2009-08-06 05:54
    the first, duh!
  • k1 2009-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
  • k1 2009-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 Nameless 2009-08-06 06:49
    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"))

    }
  • ounos 2009-08-06 07:00
    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.
  • Mike 2009-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?"
  • Dave 2009-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)

    }
  • workmad3 2009-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 General 2009-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.

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

    * -10 for tortured translingual pun, I'm sure.
  • DanielT 2009-08-06 07:57
    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 :-/
  • pjt33 2009-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.
  • Hizard 2009-08-06 08:27
    1 will be toggled least :)
  • Hans 2009-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.
  • db2 2009-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.)
  • campkev 2009-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.
  • highphilosopher 2009-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;
    }
    }
    }
    }
  • Edmund 2009-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.
  • Errant 2009-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)
  • Bodestone 2009-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
  • Zed 2009-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
  • jmibanez 2009-08-06 10:27
    I did this same problem in Erlang, just because: http://people.orangeandbronze.com/~jmibanez/lockers.erl
  • jmibanez 2009-08-06 10:29
    And yes, it solves for squares at 100 elements.
  • Jorge 2009-08-06 10:43
    In Mathematica:

    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).
  • ADC Beast 2009-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.
  • Jorge 2009-08-06 11:11
    By the way, the proportion of toggled lockers follows an inverse square root,

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


  • A Gould 2009-08-06 11:15
    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.


    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).
  • metageek 2009-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.
  • calipygous 2009-08-06 11:36
    haskell:

    map (\x->x^2) [1..10]
  • Wongo 2009-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...
  • sirxnom 2009-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
  • Maurits 2009-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.
  • Indrora 2009-08-06 12:10
    Its interesting to see so many implementations in java, C, Haskell, etc. but only... 3 on calculators?!?!

    also, a correction to MY ti-89 function:

    :nsolv(n)
    :Prgm
    :For y,1,Sqrt(n)
    :If y^2<n+1:Disp y^2
    :EndFor
    :EndPrgm


    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.
  • pjt33 2009-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.
  • Ed 2009-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)
  • Martin 2009-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.
  • NotaProgrammer 2009-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).
  • WildCard 2009-08-06 13:18
    Easy answer: locker #1, it is toggled only during the first initial toggle and then never touched again.
  • KukkerMan 2009-08-06 13:22
    A not too pretty solution in piet:

  • Lithp 2009-08-06 13:49
    That was my initial solution as well. Technically, it was more along the lines of:
    print filter(lambda n:reduce(lambda d,k:d^(not n%k), range(n+1)), range(1,101))

    ...damn, I should learn OCaml.
  • Lithp 2009-08-06 13:50
    metageek:
    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 N 2009-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?
  • Maurits 2009-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.
  • Veggie 2009-08-06 14:22
    This would be a factorization problem, which is NP I believe...
  • Lithp 2009-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?

    Mind you, I liked the Befunge solution.
    Well, try http://projecteuler.org, but it may still be too "mathy" for you.
  • Ilya Ehrenburg 2009-08-06 14:46
    Lithp:
    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?

    Mind you, I liked the Befunge solution.
    Well, try http://projecteuler.org, but it may still be too "mathy" for you.

    It's http://projecteuler.net. For the lockers which are toggled the most, look at problems 108 and 110.
  • Paul N 2009-08-06 15:00
    Alex Papadimoulis:
    Programming Praxis has officially gotten its own category. Next up: perhaps adding a field for the programming language, so we can build an index.

    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.

    Will Programming Praxis get its own link under Content?
  • NotaProgrammer 2009-08-06 18:17
    Veggie:
    This would be a factorization problem, which is NP I believe...


    Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.
  • lateToTheParty 2009-08-06 18:54
    points-free Haskell:

    getOpenLockers = (enumFromTo 1) . floor . sqrt
  • Neil 2009-08-06 19:32
    For the first bit, in Python:

    (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.
  • Beaker 2009-08-06 19:37
    This just a high-school themed equivalent of the Sieve of Eratosthenes.
  • ðer 2009-08-06 20:08
    Boring Befunge version:
    1:>:*v
    ^> :
    + .
    @_1^ 4
    ` 4
    ^*4*<
  • Maurits 2009-08-06 20:10
    NotaProgrammer:
    Veggie:
    This would be a factorization problem, which is NP I believe...


    Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.


    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."
  • Lithp 2009-08-06 21:03
    Neil:
    For the first bit, in Python:
    (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.
    I can't resist, I'm afraid.
    >>> sorted(map(lambda n:(n,sum(not n%k for k in range(1,n+1))), range(101)), key=lambda (i,n):(-n,i))

    Ilya Ehrenburg:
    It's http://projecteuler.net. For the lockers which are toggled the most, look at problems 108 and 110.
    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 Gibbard 2009-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:


    divisorCount = product . map ((+1) . length) . group . factors


    and so we have another solution to the problem:


    toggleCount = map divisorCount [1..]


    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 = p_1^(2*k_1) * p_2^(2*k_2) * ... * p_m^(2*k_m)
    = (p_1^k_1 * ... * p_m^k_m)^2


    n is an arbitrary square of another number.

    Hence:


    openLockers = [k*k | k <- [1..]]
  • amaya 2009-08-06 23:18
    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
  • mol1111 2009-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



    Addendum (2009-08-07 16:04):
    You can try online by yourself if you have Java installed.
  • mol1111 2009-08-06 23:26
    TAP for emulator

    The SPAM detector is broken.
  • immibis 2009-08-06 23:53
    Prime numbered-ones.
  • Undefined 2009-08-07 00:23
    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).
  • babeshclow 2009-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;
    }
    }
  • babeshclow 2009-08-07 01:36
    Wikipediaing says its called the 'divisor function'.
  • k1 2009-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
  • Mike 2009-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?"
  • Jonas 2009-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
  • port 2009-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?
  • Alex 2009-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).

    Make sense?


    Good thinking :)
  • Stephan 2009-08-07 06:08

    function locker($amount) {
    $result = array();
    $resultString = '';
    for ($index = 1; $index <= $amount; $index++) {
    $root = sqrt($index);
    $result[$index] = floor($root) == $root;
    $resultString .= ';' . ($result[$index] ? '1' : '0');
    }
    echo substr($resultString, 1);
    return $result;
    }
  • troll 2009-08-07 08:09
    Has anyone figured out if there's some sort of pattern to the open doors?
  • Emanuele Sabellico 2009-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)))]
  • Daniel 2009-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...
  • Josh 2009-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 Muntz 2009-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 Bora 2009-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!
  • Gandalf 2009-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.
  • stangm 2009-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 Tim 2009-08-07 14:20
    The 60th locker gets toggled the most

    that's all I know.
  • greg 2009-08-07 15:09
    sorry, that's brute force. Try again. (hint, no loops allowed)
  • Beska 2009-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).
  • brigmar 2009-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)

  • Henkie 2009-08-07 19:15
    Most opend and closed is Locker#60 (12 times)
    least opend and closed is Locker#1 (1 times)
  • Grummel 2009-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.

  • Henkie 2009-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

  • Mike 2009-08-08 09:27
    All prime numbers but 1 (one is a prime number right? lol)...
  • Abatcher 2009-08-08 11:43
    Locker 1 duh :D
  • Joey 2009-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$_}
  • Babu 2009-08-08 15:50
    The primes
  • Fregas 2009-08-08 18:25
    the real wtf is that this is on the dailywtf.

    how the mighty have fallen. I miss the old days.
  • pjt33 2009-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 Kofler 2009-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)

    Proof: Basic algebra.

    Thus the function:
    unsigned *getOpenLockers(unsigned n)
    
    {
    unsigned i, i2, *b=calloc(n, sizeof(unsigned)), *p=b;
    for (i=1, i2=1; i2<=n; i2+=i, i++, i2+=i) {
    *(p++) = i2;
    }
    return b;
    }


    Test code:
    unsigned n=100;
    
    unsigned *p=getOpenLockers(n);
    unsigned i;
    for (i=0; i<n; i++) {
    if (!*p) break;
    printf("%u ", *(p++));
    }
    printf("\n");
  • Kevin Kofler 2009-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 Kofler 2009-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 nextOpenLocker(void)
    {
    i2 += i;
    i++;
    i2 += i;
    return (i2 > n) ? 0 : i2;
    }


    Test code:
    unsigned n=100;
    
    unsigned k=firstOpenLocker(n);
    do {
    printf("%u ", k);
    k = nextOpenLocker();
    } while (k);
    printf("\n");
  • RMB 2009-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 Troll 2009-08-09 12:46
    troll:
    Has anyone figured out if there's some sort of pattern to the open doors?
    Not yet. Keep reading.
  • Tom 2009-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
  • mol1111 2009-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.
  • Graysen 2009-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] << " // ";

    return 0;
    }

    void swap (int *p1){
    if (*p1 == false)
    *p1 = true;

    else
    *p1 = false;
    }

  • CrouchSoft 2009-08-10 05:17
    Requirements
    Counter-Strike:Source
    Eventscripts 1.5 installed on server

    Installation
    place script in the file
    \cstrike\addons\eventscripts\wtf_lockers\es_wtf_lockers.txt


    Usage
    Create local Counter-Strike:Source server
    Type the following in console:

    es_load wtf_lockers
    lockers 100
    nerds
    es_unload wtf_lockers


    The results will be the following:

    Nerds, Jocks, and Lockers loaded
    Number of Lockers = 100
    Toggling Lockers...
    1
    4
    9
    16
    25
    36
    49
    64
    81
    100
    Toggled Lockers!
    Nerds, Jocks, and Lockers unloaded


    Script
    es_wtf_lockers.txt:

    // Programming Praxis: Nerds, Jocks, and Lockers

    event load
    {
    es_xsetinfo num_lockers 0
    es_xsetinfo count 1
    es_xsetinfo square 0
    es_xsetinfo done 0

    es_regclientcmd lockers wtf_lockers/set_lockers
    es_regclientcmd nerds wtf_lockers/start

    es_xmsg #multi #greenNerds, Jocks, and Lockers loaded
    }

    event unload
    {
    es_xmsg #multi #greenNerds, Jocks, and Lockers unloaded
    }


    block set_lockers
    {
    es_getargv num_lockers 1
    es_msg Number of Lockers = server_var(num_lockers)
    }

    block start
    {
    es_xmsg #multi #greenToggling Lockers...
    es_doblock wtf_lockers/lockers
    }

    block lockers
    {
    es_setinfo square server_var(count)
    es_math square power 2
    if (server_var(square) greaterthan server_var(num_lockers)) do
    {
    es_xsetinfo done 1
    }

    if(server_var(done) equalto 0) do
    {
    es_msg server_var(square)
    es_math count add 1
    es_doblock wtf_lockers/lockers
    }
    else do
    {
    es_xmsg #multi #greenToggled Lockers!
    }
    }



  • onnie 2009-08-10 06:30
    This will probably segfault... but


    /* 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;
    }
  • midiwall 2009-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 Trader 2009-08-10 15:29
    Answer in Python:


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

    return answer

  • neried7 2009-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;
  • TopicSlayer 2009-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
  • neried7 2009-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.

    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;
  • fuffuf 2009-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.
  • mol1111 2009-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 ?
  • Gandalf 2009-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.
  • Moomoo 2009-08-11 07:58
    locker number 1....
  • Wintermute 2009-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).
  • Maurits 2009-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.

    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.
  • Gandalf 2009-08-11 11:13
    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
  • mol1111 2009-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.
  • Leilock 2009-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;
    }
  • Maurits 2009-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 Wilson 2009-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 Wilson 2009-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 :)
  • Dave 2009-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.

  • Dave 2009-08-12 04:25
    comparable cpu effort for 10^4 to 10^9 lockers
    (at least as reported)
  • Ed Gorcenski 2009-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ürgen 2009-08-13 06:17
    def least_toggled(n): return 1

  • Maurits 2009-08-13 20:48
    Ed Gorcenski:
    MATLAB code:


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

    (zeros(n) is an n x n matrix)
  • David 2009-08-15 18:28
    It's easy.
    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.
  • David 2009-08-15 18:30
    matlab? pfft. ;)

    You're still brutin' it.
  • quintopia 2009-08-16 07:48
    Without looking at previous comments:

    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.
  • quintopia 2009-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.
  • Minko 2009-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.
  • Minko 2009-08-17 17:46
    ooops forgot 12 is also a divider. It will actually be closed :)
  • Tama 2009-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".
  • Dan 2009-08-18 01:56
    Locker 1 and all primes are toggled least (twice).
  • Aaron M. 2009-08-18 03:39

    #!/bin/sh
    exec tclsh "$0" "$@"
    proc getOpenLockers {numToggled} {
    set numOpen [expr sqrt($numToggled)]
    for {set i 1} {$i <= $numOpen} {incr i} {
    lappend openLockers [expr pow($i,2)]
    }
    return $openLockers
    }


    For all you embedded geeks out there..
  • Eternal Density 2009-08-23 23:14
    Biff Tannen:
    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!
  • Anonerd 2009-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! (?)
  • AllanW 2009-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 Pyne 2009-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);

    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();
    }
    }
    }
  • Ethan 2009-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.
  • rjk 2009-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 McGavock 2009-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.
  • CS 2009-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
  • Cranberry 2009-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.
  • Christian 2009-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 Pockets 2009-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;
    }
    }
    }
    }

    $myCounter = 0;

    foreach $myNum (@myArray) {
    if ($myNum == 1) {
    print $myCounter . "\n";
    }
    $myCounter++;
    }
  • Ian 2009-10-14 03:43
    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).
  • Colin 2010-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
  • Joel 2010-05-13 17:52
    Prime numbers.
  • orange_batch 2010-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_batch 2010-08-25 19:34
    K, I didn't read the no brute force part. Whatever.
  • The loonly guy 2011-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
  • ac 2011-12-30 10:48
    The first locker is toggled exactly once. Prime-numbered lockers are toggled twice.
  • Smithd976 2014-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