• Alex Papadimoulis (cs)

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

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

    #!perl

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

  • neat (unregistered)

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

    Umm squares of 1 to 10?

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

  • Mark (unregistered) in reply to neat

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

  • Welbog (cs)

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

    Paste this formula in Excel and use copy-down

    =ROW(A1)^2

  • Addison (unregistered) in reply to Welbog
    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 (unregistered)

    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 (cs) in reply to Addison
    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 (unregistered)

    Haskell:

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

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

  • halcyon1234 (cs)

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

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

    not i^2

  • Daniel (unregistered) in reply to neat
    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 (unregistered)

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

    Not exactly awesome:

    import math; l=lambda x:map(lambda y: y**2,range(1,int(math.sqrt(x))+1))
    
  • moltonel (cs) in reply to Welbog
    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 (cs)
    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 & "
    " & cstr(i+1) end if next doLockers = ret end function response.write "
    " response.write "
    " & doLockers(100) %>
  • Welbog (cs) in reply to moltonel
    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 (unregistered)

    Thinking just shortly (1-2 min) about it, I'd say that exactly the square numbers stay open.

  • Frunobulax2099 (unregistered)

    input: totalLockerNum

    max = floor(sqrt(totalLockerNum))

    for i=1; i<=max; i++ { result = i**2; add result to array } return array

  • Kris (unregistered) in reply to anonym
    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 (unregistered)

    .NET Solution:

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

    i just watched the example and i feel like a jock

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

  • Anon (unregistered) in reply to Welbog
    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 (unregistered)

    what with the brilliant paula being brillant?

  • seconddevil (cs)

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

    Python:

    import math; def getOpenLockers(i): return [x**2 for x in range(1, 1+int(math.sqrt(i)))]
  • Drew (unregistered)

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

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

    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 (unregistered)
    Comment held for moderation.
  • Anonymous (unregistered)
    Comment held for moderation.
  • Steve the Cynic (unregistered) in reply to Drew
    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 (unregistered)
    Comment held for moderation.
  • Zecc (cs) in reply to Welbog
    Welbog:
    The open lockers are perfect squares.

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

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

    Make sense?

    What about numbers like 1234 = 24 or 2347 = 168 then?

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

  • Welbog (cs) in reply to Zecc
    Zecc:
    Welbog:
    The open lockers are perfect squares.

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

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

    Make sense?

    What about numbers like 1234 = 24 or 2347 = 168 then?
    I 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 (cs) in reply to Welbog
    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 1234 = 24 or 2347 = 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 (cs) in reply to Welbog
    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 1234 = 24 or 2347 = 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 (unregistered)

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

    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 (unregistered)
    Comment held for moderation.
  • Ozmo (unregistered)

    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 (unregistered) in reply to Zecc
    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 (cs) in reply to steenbergh

    And a slightly smaller version in JS

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

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

  • Olav (unregistered)
    #!/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 (unregistered)

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

    simply - squares of prime numbers (or perfect squares)

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

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

Log In or post as a guest

Replying to comment #:

« Return to Article