 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
Here it is on an HP 48. Replace SQRT with the proper square root symbol.
Compiles to 57.5 bytes on the calculator. (Yes, it uses halfbyte addressing.)
Admin
No, you failed the reading test.
Thanks for playing though.Admin
Admin
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.
Admin
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 workish)
Admin
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
Admin
That's easy locker 1.. it's only toggled once. Zed
Admin
I did this same problem in Erlang, just because: http://people.orangeandbronze.com/~jmibanez/lockers.erl
Admin
And yes, it solves for squares at 100 elements.
Admin
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).
Admin
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, nonprimes will be more than that.
Admin
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}]
[image]Admin
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).
Admin
So, the trick is to note that the number of times a locker gets toggled is the number of factors is has:
I got this banged out before the simulated jocks finished their first pass.
Admin
haskell:
map (\x>x^2) [1..10]
Admin
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...
Admin
Heres an implementation in ZOMBIE (Zombie Oriented Machine Being Interface Engine)
Admin
Beautiful.
A suggested rewording of step 2: Suppose the largest primorial <= N is 235*...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.
Admin
Its interesting to see so many implementations in java, C, Haskell, etc. but only... 3 on calculators?!?!
also, a correction to MY ti89 function:
Admin
Admin
Interesting that the lockers remaining toggled are the squares of the first 10 digits (1^2=1,2^2=4,...,10^2=100)
Admin
Given that answer you suggested is totally wrong, it is perfectly possible that the nerds abide by your advice and still lose.
Admin
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 412).
Admin
Easy answer: locker #1, it is toggled only during the first initial toggle and then never touched again.
Admin
A not too pretty solution in piet:
[image]Admin
That was my initial solution as well. Technically, it was more along the lines of:
...damn, I should learn OCaml.
Admin
Admin
Admin
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 235*...*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
(that "p" is the specific prime from the largest primorial <= N)
where c <= N, and n1 >= n2 >= ... >= nk >= 0
(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:
n1 = 5:
n1 = 4:
n1 = 3:
n1 = 2:
n1 = 1:
n1 = 0:
smallest locker is in {60, 72, 96}, number of toggles is 12
find the set of lockers that are toggled t times
print found lockers e.g. Lockers that are toggled 12 times: 60, 72, 84, 90, 96
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.
Admin
This would be a factorization problem, which is NP I believe...
Admin
Admin
Admin
Admin
Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.
Admin
pointsfree Haskell:
Admin
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 oneliner for the second part.
Admin
This just a highschool themed equivalent of the Sieve of Eratosthenes.
Admin
Boring Befunge version: 1:>:*v ^> :
Admin
Sometimes, although a general problem is NPcomplete, specializations of them are not NPcomplete.
See the Monty Python "Mastermind" sketch, where a guest claimed that is specialty was "complicated mathematical problems to which the answer is two."
Admin
Admin
(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:
and then the number of times which each locker gets toggled after 100 steps is obtained by an easy fold:
and of course, lockers are open if they were toggled an odd number of times:
and we can get the indices at which these lockers occur easily enough:
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:
and then factoring a number into primes:
and then the number of divisors of n is the number of ways we can pick submultisets 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:
and so we have another solution to the problem:
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 is an arbitrary square of another number.
Hence:
Admin
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
Admin
Z80 Assembler
Usage from ZX Spectrum BASIC:
Admin
TAP for emulator
The SPAM detector is broken.
Admin
Prime numberedones.
Admin
Admittedly I didn't let the simulation run to completion so I didn't see that it ended up with the perfect squares.
Alternative bruteforce 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).
Admin
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[n1] = c % 2; } }
Admin
Wikipediaing says its called the 'divisor function'.
Admin
he start with (2^N)1 2^N rabbits for each house
Admin
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?"