- 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
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]
Admin
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?
Admin
Good thinking :)
Admin
Admin
Has anyone figured out if there's some sort of pattern to the open doors?
Admin
In python:
import math def getOpenLockers(n): return [(x+1)**2 for x in range(0, math.floor(math.sqrt(n)))]
Admin
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...
Admin
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};
Admin
That's like asking the square root of a million. No one will ever know.
HA-ha.
Admin
Umm, the goal is to finish before the jockers!
Admin
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.
Admin
which lockers are toggled the LEAST? Locker 1, it is only toggled once, every other locker is toggled at least twice.
Admin
The 60th locker gets toggled the most
that's all I know.
Admin
sorry, that's brute force. Try again. (hint, no loops allowed)
Admin
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).
Admin
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)
Admin
Most opend and closed is Locker#60 (12 times) least opend and closed is Locker#1 (1 times)
Admin
The first is only toggled once, this seems pretty obvious.
Admin
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
Admin
All prime numbers but 1 (one is a prime number right? lol)...
Admin
Locker 1 duh :D
Admin
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$}
Admin
The primes
Admin
the real wtf is that this is on the dailywtf.
how the mighty have fallen. I miss the old days.
Admin
Admin
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 kk!=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 kk 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)=ii+2i+1=ii+i+(i+1)
Proof: Basic algebra.
Thus the function:
Test code:
Admin
Admin
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:
Test code:
Admin
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]]) )))
Admin
Admin
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
Admin
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.
Admin
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.
Admin
Requirements Counter-Strike:Source Eventscripts 1.5 installed on server
Installation place script in the file
Usage Create local Counter-Strike:Source server Type the following in console:
The results will be the following:
Script
Admin
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] = countcount; } /* and the last one if not already in the list / if (countcount != lockerCount) { lockers.OpenLocks[count] = lockerCount; lockers.numOpenLocks++; } return lockers; }
Admin
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".
Admin
Answer in Python:
Admin
#!/usr/bin/perl
use warnings; use strict;
sub lockers {
}
&lockers;
Admin
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
Admin
First was the brute version, here's the 'formulaic' version:
use warnings; use strict;
sub lockers {
}
&lockers;
Admin
In the simulation every opened locker adheres to the rule 2^n, except for #9.
I suspect there is a flaw in the simulation.
Admin
Oh, really? What about 25, 36, 49, 81, 100 ?
Admin
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 62 = 12 divisors 60 = 2^3 * 3 * 5 has 42*2 = 16 divisors
So 60 is toggled most often. 16 times.
Admin
locker number 1....
Admin
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).
Admin
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.
Admin
Uh, yeah, you are absolutely right, Wintermute. I accidentally counted the divisors of 120.
60 = 2^2 * 3 * 5 has 322 = 12 divisors
Admin
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.
I would say so.
Admin
Admin
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...