• self (unregistered)

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

    Sweet...it would be cool if you would categorize the previous two entries so they show up in the category list

  • Anonymous (unregistered) in reply to Way too much time on my hands
    Way too much time on my hands:
    Is LOLcode acceptable?
    No it isn't. Ever. Now die.
  • (cs)

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

  • (cs) in reply to Tim

    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@           
          ^<            </pre>

    Output for n=100:
1 4 9 16 25 36 49 64 81 100
  • Jean-Paul (unregistered)

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

    Follow-up question: which lockers are toggled the LEAST?

  • Torge (unregistered) in reply to Maurits
    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 (unregistered) in reply to Maurits
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?
    Primes. Twice each.
  • (cs)

    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)))
  • (cs) in reply to Rob G
    Rob G:
    An espresso of Java:

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

    Are you sure that ++c*c works as expected in java? It would not work in c or c++.

  • Anon (unregistered)

    LabVIEW:

    [image]

    Note: LabVIEW sucks

  • Ryan (unregistered)

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

    I don't believe that a bunch of football players could correctly determine what they had to do.

  • Dean (unregistered)

    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.

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

    Actually scratch that, I meant factors not prime factors

  • gpan (unregistered)

    Very simple. The lockers that stay open are the ones whose #'s are perfect squares. 1,4,9,16,.....

  • rm5248 (unregistered)

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

    Perl golf... here's 27 chars :)

    sub f{map$_**2,1..sqrt pop}

  • (cs)

    The obligatory BrainFuck:

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

    Output: 100, 81, 64, 49, 36, 25, 16, 9, 4, 1,

  • Davidm (unregistered)

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

  • Mrs MeChokemchild (unregistered)

    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 (unregistered) in reply to Mrs MeChokemchild
    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.
  • (cs) in reply to Spectre
    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))
))
  • (cs) in reply to Mrs MeChokemchild
    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 (unregistered)
    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 (unregistered)

    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 (unregistered) in reply to Mrs MeChokemchild
    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?
  • (cs)

    PS

    for (int i=1; ii < 100; ++i) cout << ii;

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

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

    In Befunge98:

    &19pv
v   <
1
>::*:19g`!v
^      +1._25*,@
  • DeadPanda (unregistered)

    Simple python solution with list comprehensions...

    get_lockers = lambda n: [(2*k) + pow(k,2) + 1 for k in range(0, floor(sqrt(n)))]
  • (cs) in reply to Shinobu

    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.

  • (cs)

    javascript:getPaula() (copy+paste in same window)... nuff said... for now.

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

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

    perl -e "while($**2<$ARGV[0]){$++};print" 100

  • nonny nonny (unregistered) in reply to Bim Job
    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!

  • (cs)

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

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

    ahh, my daily wtf: untested and excessively complicated

  • Two more options in JavaScript (unregistered)

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

    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 (unregistered) 
    def getOpenLockers(n):
    openLockers = []
    i = 1
    step = 3
    while i <= n:
        openLockers.append(i)
        i += step
        step += 2
    return openLockers
  • Paul N (unregistered)

    (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: 18 and 24. 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: 14 and 22. 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

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

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

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

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article