13
\$\begingroup\$

There are N doors and K monkeys. Initially, all the doors are closed.

Round 1: The 1st monkey visits every door and toggles the door (if the door is closed, it gets opened it; if it is open, it gets closed).

Round 2: The 1st monkey visits every door and toggles the door. Then The 2nd monkey visits every 2nd door and toggles the door.

. . .

. . .

Round k: The 1st monkey visits every door and toggles the door . . . . . . . . . . The kth monkey visits every kth door and toggles the door.

Input : N K (separated by a single space)

Output: Door numbers which are open, each separated by a single space.

Example:

Input: 3 3

Output: 1 2

Constraints:

0< N<101

0<= K<= N

Note:

  • Assume N doors are numbered from 1 to N and K monkeys are numbered from 1 to K

  • The one with the shortest code wins. Also, display output for N=23, K=21

\$\endgroup\$
  • \$\begingroup\$ inspired by this puzzle? \$\endgroup\$ – Math chiller Oct 21 '13 at 15:47
  • \$\begingroup\$ I just have a question, if N=K, every prime number door is open, right? \$\endgroup\$ – Fabinout Oct 22 '13 at 15:07
  • \$\begingroup\$ @Fabinout no n=k=3 would output 1 2 so ur wrong... and 5 outputs 1 2 4 there is a pattern but its alot less obvious then that. \$\endgroup\$ – Math chiller Oct 25 '13 at 2:05
  • \$\begingroup\$ @Fabinout it follows a very weird type of Fibonacci number set, its very advanced abstract mathematics. \$\endgroup\$ – Math chiller Oct 25 '13 at 2:15
  • \$\begingroup\$ @tryingToGetProgrammingStraight you're right, my memories told me the answer was the list of prime numbers, when it was the list of square numbers. \$\endgroup\$ – Fabinout Oct 25 '13 at 8:00

11 Answers 11

14
\$\begingroup\$

APL, 32 28 26

{(2|+/(⍳⍺)∘.{+/0=⍺|⍨⍳⍵}⍳⍵)/⍳⍺}/⎕

⎕:
      23 21
 1 2 4 8 9 16 18 23 

Explaination

  • {+/0=⍺|⍨⍳⍵} is a function that returns the number of times door (left argument) is toggled on round (right argument), which equal the number of factors of that is ≤:

    • ⍳⍵ Generate numerical array from 1 to

    • ⍺|⍨ Calculate modulus each every item of that array

    • 0= Change to a 1 where there was a 0, and a 0 for every thing else

    • +/ Sum the resulting array

  • The outer function:

    • (⍳⍺) , ⍳⍵ Generate arrays from 1 to N and 1 to K

    • ∘.{...} For every pair of elements of the two arrays, apply the function. This gives a matrix of number of times toggled, each row represents a door and each column represents a round.

    • +/ Sum the columns. This gives an array of the number of times each door is toggled over all rounds.

    • 2| Modulus 2, so if a door is open, it's a 1; if it's closed, it's a 0.

    • (...)/⍳⍺ Finally, generate an array from 1 to N and select only the ones where there is a 1 in the array on the previous step.

  • /⎕ Finally, insert the function between the numbers from input.


EDIT

{(2|+⌿0=(,↑⍳¨⍳⍵)∘.|⍳⍺)/⍳⍺}/⎕
  • ,↑⍳¨⍳⍵ Generate all "monkeys" (If K=4, then this is 1 0 0 0 1 2 0 0 1 2 3 0 1 2 3 4)

    • ⍳⍵ Array from 1 to (K)

    • ⍳¨ For each of those, generate array from 1 to that number

    • ,↑ Convert the nested array into a matrix () and then unravel to a simple array (,)

  • (,↑⍳¨⍳⍵)∘.|⍳⍺ For each number from 1 to (N), mod it with each monkey.

  • 0= Change to a 1 where there was a 0, and a 0 for every thing else. This gives a matrix of toggles: Rows are each monkey on each round, columns are doors; 1 means a toggle, 0 means no toggle.

  • +⌿ Sum the rows to get an array of number of times each door is toggled

Other parts are not changed


EDIT

{(≠⌿0=(,↑⍳¨⍳⍵)∘.|⍳⍺)/⍳⍺}/⎕

Use XOR reduce (≠⌿) instead of sum and mod 2 (2|+⌿)

\$\endgroup\$
  • \$\begingroup\$ Was APL designed for golf script? ;-) \$\endgroup\$ – celtschk Jun 22 '14 at 14:12
  • \$\begingroup\$ @celtschk Yes, partly, in a way. It was designed to express algorithms concisely. \$\endgroup\$ – luser droog Jun 28 '14 at 6:03
  • \$\begingroup\$ Why do you use a dfn reduction {}/ instead of just taking N and K as arguments to the dfn? \$\endgroup\$ – Adám Jun 27 '17 at 13:45
  • \$\begingroup\$ @Adám Because 1) this is past me; 2) this question predates the "program or function" and I/O standardizations; 3) the OP specifically said "separated by a single space" \$\endgroup\$ – TwiNight Jun 27 '17 at 14:13
  • \$\begingroup\$ Fair enough, but at least you can save a byte with i←⍳⍺ \$\endgroup\$ – Adám Jun 27 '17 at 14:19
4
\$\begingroup\$

GolfScript, 33 characters

~:k;),1>{0\{1$)%!k@-&^}+k,/}," "*

If doors were numbered starting with zero it would save 3 characters.

Examples (online):

> 3 3
1 2

> 23 21
1 2 4 8 9 16 18 23
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 104 chars

{n,k}=FromDigits/@StringSplit@InputString[];Select[Range@n,OddQ@DivisorSum[#,If[#>k,0,k+1-#]&]&]~Row~" "

Example:

In[1]:= {n,k}=FromDigits/@StringSplit@InputString[];Select[Range@n,OddQ@DivisorSum[#,If[#>k,0,k+1-#]&]&]~Row~" "

? 23 21

Out[1]= 1 2 4 8 9 16 18 23

\$\endgroup\$
  • 1
    \$\begingroup\$ You can knock another 15 characters off parsing the input by assuming an input stream, e.g.: {n,k}=%~Read~{Number,Number}. \$\endgroup\$ – Marcks Thomas Oct 21 '13 at 15:26
3
\$\begingroup\$

Ruby, 88

Based on @manatwork's answer.

gets;~/ /
$><<(1..$`.to_i).select{|d|(1..k=$'.to_i).count{|m|d%m<1&&(k-m+1)%2>0}%2>0}*$&

Those dodgy globals always break syntax highlighting!

\$\endgroup\$
  • \$\begingroup\$ Sorry, but the 90 chars (revision 2) and 86 chars (revision 3) seems to be buggy: a new number, 22, appeared in their results. \$\endgroup\$ – manatwork Oct 22 '13 at 7:47
  • \$\begingroup\$ @manatwork good call, I think I've fixed it now at the cost of two characters. I feel like that count bit could be improved further, I wish ruby had a built in #sum method for things like that :> \$\endgroup\$ – Paul Prestidge Oct 22 '13 at 12:11
  • \$\begingroup\$ Wow! Really impressed. \$\endgroup\$ – manatwork Oct 22 '13 at 12:20
3
\$\begingroup\$

Python 3, 97 84

If a monkey appears in an even number of rounds, that's no change at all. If a monkey appears in an even number of times, that's the same as in exactly one round.

Thus some monkeys can be left out, and the others just have to switch doors once.

N,K=map(int,input().split())
r=set()
while K>0:r^=set(range(K,N+1,K));K-=2
print(*r)

Output for 23 21:

1 2 4 8 9 16 18 23
\$\endgroup\$
  • \$\begingroup\$ Clever use of set operations! I think you can shorten range(2-K%2,K+1,2) to range(K,0,-2). \$\endgroup\$ – xnor Jun 21 '14 at 1:36
  • \$\begingroup\$ Or better yet, replace the for loop with a while loop: while K>0:r^=set(range(K,N+1,K));K-=2 \$\endgroup\$ – xnor Jun 21 '14 at 1:43
  • \$\begingroup\$ @xnor: thanks, that's great! \$\endgroup\$ – Reinstate Monica Jun 28 '14 at 2:17
2
\$\begingroup\$

R - 74

x=scan(n=2);cat(which(colSums((!sapply(1:x[1],`%%`,1:x[2]))*x[2]:1)%%2>0))

Simulation:

> x=scan(n=2);cat(which(colSums((!sapply(1:x[1],`%%`,1:x[2]))*x[2]:1)%%2>0))
1: 23 21
Read 2 items
1 2 4 8 9 16 18 23
\$\endgroup\$
2
\$\begingroup\$

javascript 148 127

function e(n,k){b=array(n);d=[];function a(c){for(i=0;i<n;i+=c)b[i]=!b[i];c<k&&a(c+1)}a(1);for(i in b)b[i]&&d.push(i);return d}

here is a (tiny bit) readable version:

function e(n, k) {     //define N and K
     b = array(n); //declare all doors as closed
     d = [];     //create array later used to print results

     function a(c) {   //(recursive) function that does all the work
         for (i = 0; i < n; i += c)  //increment by c until you reach N and...
              b[i] = !b[i];  //toggle said doors
         c < k && a(c + 1)  //until you reach k, repeat with a new C (next monkey)
     }
     a(1); //start up A

     for (i in b) b[i] && d.push(i); //convert doors to a list of numbers
     return d //NO, i refuse to explain this....
}   //closes function to avoid annoying errors

DEMO fiddle

i should note that it starts counting from 0 (technically a off-by-one error)

\$\endgroup\$
  • \$\begingroup\$ You can remove your 3rd line if you change the 2nd line to b=Array(n); This initializes your array as n length filled with undefined. !undefined is true, so the first monkey pass will turn it all into trues. \$\endgroup\$ – path411 Oct 24 '13 at 22:56
  • \$\begingroup\$ @path411 thank u very much! im surprised i forgot how "proper" array declaration works! you can feel free to +1 \$\endgroup\$ – Math chiller Oct 25 '13 at 1:35
  • \$\begingroup\$ Interesting. It seems yours is the only one I've seen so far that appears to get a similar answer as mine for N=23, K=21. The only difference being the off-by-one issue which includes 0 and excludes 23. \$\endgroup\$ – Iszi Nov 27 '13 at 5:38
  • \$\begingroup\$ Figured out what's wrong with mine, and this one has the same problem. For each round, you're only sending one monkey through all the doors. However, per the challenge specifications, there needs to be $i monkeys running through each round - where $i is the number of the round you're on. \$\endgroup\$ – Iszi Nov 27 '13 at 5:59
2
\$\begingroup\$

JavaScript, 153

(function(g){o=[],f=g[0];for(;i<g[1];i++)for(n=0;n<=i;n++)for(_=n;_<f;_+=n+1)o[_]=!o[_];for(;f--;)o[f]&&(l=f+1+s+l);alert(l)})(prompt().split(i=l=s=' '))

Output for N=23, K=21:

1 2 4 8 9 16 18 23  

Tested in Chrome, but doesn't use any fancy new ECMAScript features so should work in any browser!

I know I'll never win against the other entries and that @tryingToGetProgrammingStrainght already submitted an entry in JavaScript, but I wasn't getting the same results for N=23, K=21 as everyone else was getting with that so I thought I'd have a go at my own version.

Edit: annotated source (in looking over this again, I spotted places to save another 3 characters, so it can probably be improved still...)

(function(g) {
    // initialise variables, set f to N
    o = [], f = g[0];

    // round counter
    // since ++' ' == 1 we can use the same variable set in args
    for (; i < g[1]; i++)
        // monkey counter, needs to be reset each round
        for (n = 0 ; n <= i; n++)
            // iterate to N and flip each Kth door
            for (_ = n; _ < f; _ += n + 1)
                // flip the bits (as undef is falsy, we don't need to initialise)
                // o[_] = !~~o[_]|0; // flips undef to 1
                o[_] = !o[_]; // but booleans are fine
    // decrement f to 0, so we don't need an additional counter
    for (;f--;)
        // build string in reverse order
        o[f] && (l = f + 1 + s + l); // l = (f + 1) + ' ' + l
    alert(l)
    // return l // use with test
// get input from user and store ' ' in variable for use later
})(prompt().split(i = l = s = ' '))
// })('23 21'.split(i = l = s = ' ')) // lazy...

// == '1 2 4 8 9 16 18 23  '; // test
\$\endgroup\$
  • \$\begingroup\$ good work! if you would also provide a readable and commented version i would probably +1 \$\endgroup\$ – Math chiller Oct 25 '13 at 1:40
  • \$\begingroup\$ Answer updated! Since I can't comment on your answer, to add to @path411's comment, you could set b=[] and the empty indexes are still undefined and that saves you another 6 characters! \$\endgroup\$ – Dom Hastings Oct 25 '13 at 6:08
  • \$\begingroup\$ i did that already.... \$\endgroup\$ – Math chiller Oct 26 '13 at 19:47
1
\$\begingroup\$

Ruby - 65 characters

(1..n).each{|d|
t=0
(1..k).each{|m|t+=n-m+1 if d%m==0}
p d if t%2>0}

n = 23, k = 21 # => 1 2 4 8 9 16 18 23 

Here is the calculation, in pseudo-code:

  • Let s(d) be the number of times door d is touched after k rounds.
  • s(d) = sum(m=1..m=k)(d%m==0 ? (n-m+1): 0)
  • door d is open after k rounds if s(d) % 2 = 1 (or > 0)

If you are not convinced that the expression for s(d) is correct, look at it this way:

  • Let s(d,r) be the number of times door d is touched after r rounds.
  • s(d,k) - s(d,k-1) = sum(m=1,..,m=k)(d%m==0 ? 1 : 0)
  • s(d,k-1) - s(d,k-2) = sum(m=1,..,m=(k-1))(d%m==0 ? 1 : 0)
  • ...
  • s(d,2) - s(d,1) = d%2==0 ? 1 : 0
  • s(d,1) = 1
  • sum both sides to obtain the above expression for s(d), which equals s(d,k)
\$\endgroup\$
  • \$\begingroup\$ Very concise! Where do n and k come from, though? And the output seems to be separated by newlines rather than spaces. \$\endgroup\$ – Paul Prestidge Oct 28 '13 at 22:01
1
\$\begingroup\$

PowerShell: 132

Golfed Code:

$n,$k=(read-host)-split' ';0|sv($d=1..$n);1..$k|%{1..$_|%{$m=$_;$d|?{!($_%$m)}|%{sv $_ (!(gv $_ -Va))}}};($d|?{(gv $_ -Va)})-join' '

Un-Golfed, Commented Code:

# Get number of doors and monkeys from user as space-delimited string.
# Store number of doors as $n, number of monkeys as $k.
$n,$k=(read-host)-split' ';

# Store a list of doors in $d.
# Create each door as a variable set to zero.
0|sv($d=1..$n);

# Begin a loop for each round.
1..$k|%{

    # Begin a loop for each monkey in the current round.
    1..$_|%{

        # Store the current monkey's ID in $m.
        $m=$_;

        # Select only the doors which are evenly divisible by $m.
        # Pass the doors to a loop.
        $d|?{!($_%$m)}|%{

            # Toggle the selected doors.
            sv $_ (!(gv $_ -Va))
        }
    }
};

# Select the currently open doors.
# Output them as a space-delimited string.
($d|?{(gv $_ -Va)})-join' '

# Variables cleanup - don't include in golfed code.
$d|%{rv $_};rv n;rv d;rv k;rv m;

# NOTE TO SELF - Output for N=23 K=21 should be:
# 1 2 4 8 9 16 18 23
\$\endgroup\$
  • \$\begingroup\$ Oh, I see what my problem is. I misunderstood the question - this is not the 100 Lockers problem. It's that, taken up a notch! This will require a bit more work... \$\endgroup\$ – Iszi Nov 27 '13 at 5:46
  • 1
    \$\begingroup\$ Sweet! Fixing it to meet the challenge requirements properly only netted a gain of 6 characters in the end. \$\endgroup\$ – Iszi Nov 27 '13 at 7:12
0
\$\begingroup\$

Powershell, 66 bytes

Based on Cary Swoveland's answer.

param($n,$k)1..$n|?{$d=$_
(1..$k|?{($n-$_+1)*!($d%$_)%2}).Count%2}

Test script:

$f = {

param($n,$k)1..$n|?{$d=$_
(1..$k|?{($n-$_+1)*!($d%$_)%2}).Count%2}

}

@(
    ,(3, 3   , 1,2)
    ,(23, 21 , 1, 2, 4, 8, 9, 16, 18, 23)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$("$result"-eq"$expected"): $result"
}

Output:

True: 1 2
True: 1 2 4 8 9 16 18 23
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.