N Doors, K Monkeys

Question

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

Answer 1

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|+⌿)

Answer 2

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

Answer 3

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

Answer 4

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!

Answer 5

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

Answer 6

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

Answer 7

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)

Answer 8

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

Answer 9

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)

Answer 10

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

Answer 11

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