13
\$\begingroup\$

Introduction

In this challenge, your task is to simulate a certain type of elimination game. In the game, the participants stand in a circle, and everyone is holding an integer. On each round of the game, every participant points at the person n steps away, if n is the number they are holding. If n is positive, they count to their right, if n is negative, they count to their left, and if n is zero, they point at themselves. Every participant who has someone pointing at them is eliminated, and leaves the circle; this ends the round. The rounds continue until there are no participants left.

Input

Your input is a non-empty list of integers, in any reasonable format. It represents the numbers that the participants of the game are holding.

Output

Your output is the number of rounds it takes until the game ends.

Example

Consider the input list [3,1,-2,0,8]. On the first round, the following happens:

  • The person holding 3 points right at the person holding 0.
  • The person holding 1 points right at the person holding -2.
  • The person holding -2 points left at the person holding 3.
  • The person holding 0 points at themself.
  • The person holding 8 points right at the person holding -2 (the list represents a circle, so it wraps around at the ends).

This means that 0, -2 and 3 are eliminated, so the second round is done with the list [1,8]. Here, 1 points at 8, and 8 points at themself, so 8 is eliminated. The third round is done with the list [1], where 1 simply points at themself and is eliminated. It took three rounds to eliminate all participants, so the correct output is 3.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

[3] -> 1
[0,0,0] -> 1
[-2,-1,0,1,2,3,4,5,6,7] -> 2
[5,5,5,6,6,6] -> 2
[3,-7,-13,18,-10,8] -> 2
[-7,5,1,-5,-13,-10,9] -> 2
[4,20,19,16,8,-9,-14,-2,17,7,2,-2,10,0,18,-5,-5,20] -> 3
[11,2,7,-6,-15,-8,15,-12,-2,-8,-17,6,-6,-5,0,-20,-2,11,1] -> 4
[2,-12,-11,7,-16,9,15,-10,7,3,-17,18,6,6,13,0,18,10,-7,-1] -> 3
[18,-18,-16,-2,-19,1,-9,-18,2,1,6,-15,12,3,-10,8,-3,7,-4,-11,5,-15,17,17,-20,11,-13,9,15] -> 6
\$\endgroup\$
4
  • \$\begingroup\$ Are you sure about the last test case, I get 5? \$\endgroup\$
    – flawr
    Oct 16, 2015 at 15:55
  • \$\begingroup\$ @flawr I can check my reference implementation in about an hour (had to leave my computer), but it should be correct. \$\endgroup\$
    – Zgarb
    Oct 16, 2015 at 16:02
  • \$\begingroup\$ Just to be clear: n is the number the person is holding? \$\endgroup\$ Oct 16, 2015 at 16:08
  • \$\begingroup\$ @PeterTaylor Yes, it is. I'll clarify that later in the challenge. \$\endgroup\$
    – Zgarb
    Oct 16, 2015 at 16:18

12 Answers 12

5
\$\begingroup\$

Matlab, 91 77 bytes

function k=f(a);k=0;while a*0+1;l=numel(a);a(mod((1:l)+a-1,l)+1)=[];k=k+1;end

Old version:

function k=f(a);for k=1:numel(a);a(mod((1:l)+a-1,l)+1)=[];l=numel(a);if l==0;break;end;end

This is a challenge where matlab shines, the heart of this code is the deletion of the array entries: a(mod((1:l)+a-1,l)+1)=[] which is quite elegant I think.

\$\endgroup\$
4
\$\begingroup\$

Pyth, 15 bytes

f!=.DQ.e%+bklQQ

Test suite thanks to kirby

Uses the same iteration mechanism as @orlp, but detects the number of iterations using f, the "Repeat until falsy" function, to detect the [] once we're done.

\$\endgroup\$
4
\$\begingroup\$

CJam, 21 bytes

q~{__ee{~+0t}/0-}h],(

Test suite.

Takes input as a CJam style list, but the test suite takes care of the conversion from the format in the challenge.

Explanation

q~     e# Read and evaluate the input.
{      e# While the array is non-empty...
  _    e#   Copy the array. The original is left on the stack so that we can use the
       e#   stack depth to count the number of iterations later.
  _ee  e#   Make another copy and enumerate it, which means that each element is replaced
       e#   by a pair containing the element and its index in the array.
  {    e#   For each such pair...
    ~+ e#     Add the value to the index, giving the index it points at.
    0t e#     Set the value in the original array at the pointed-at index to 0.
       e#     This works without giving false positives because all 0s point to themselves.
  }/
  0-   e#   Remove all 0s from the array.
}h
],(    e# Wrap the stack in an array, get its length and decrement it to determine how
       e# many iterations this process took.
\$\endgroup\$
1
  • \$\begingroup\$ Thanks: ee is almost exactly what I was looking for yesterday for a different question. \$\endgroup\$ Oct 16, 2015 at 20:13
3
\$\begingroup\$

C#, 251 219 211 197 193 bytes

The most ungolfable non-esoteric language strikes again.

using System.Linq;class X{static void Main(string[]a){int i=0,c;for(;(c=a.Length)>0;i++)a=a.Where((e,x)=>!a.Where((f,y)=>((int.Parse(f)+y)%c+c)%c==x).Any()).ToArray();System.Console.Write(i);}}

This program expects the input sequence as command-line arguments. For example, to input the list [5,5,5,6,6,6], call it with command-line arguments 5 5 5 6 6 6.

Thanks to Martin Büttner for some tips.

Golfed it to 197 by realizing that I can reuse the args array even though it’s an array of strings. I only need to parse them into an integer in one place.

Golfed to 193 by realizing that .Where(...==x).Any() is shorter than .Select(...).Contains(x).

Ungolfed

using System.Linq;
class X
{
    static void Main(string[] args)
    {
        var iterations = 0, count;

        // In the golfed version, this is a `for` loop instead.
        while ((count = args.Length) > 0)
        {
            // Create a new args array containing the items to be kept.
            args = args.Where((item, index) =>
            {
                // Should the item at index `index` be deleted?
                var deleteThisIndex = args.Where((item2, index2) =>
                    // Modulo that works with negative numbers...
                    ((int.Parse(item2) + index2) % count + count) % count
                        == index);

                return !deleteThisIndex.Any();

            }).ToArray();

            iterations++;
        }

        System.Console.Write(iterations);
    }
}
\$\endgroup\$
3
  • 5
    \$\begingroup\$ C# is the most ungolfable? Surely you must be mistaken; everyone knows that's Java. :P \$\endgroup\$
    – Alex A.
    Oct 16, 2015 at 17:23
  • \$\begingroup\$ @AlexA. Pfft, I'm with Timwi on this one. I've beaten C# with Java plenty of times :P \$\endgroup\$
    – Geobits
    Oct 16, 2015 at 17:26
  • 3
    \$\begingroup\$ You're wrong, Pyth or CJam are the most ungolfable, C# is the most unwinnable language! \$\endgroup\$
    – Beta Decay
    Oct 16, 2015 at 17:57
2
\$\begingroup\$

Pyth, 21 bytes

[email protected]%+kblNNQ

Live demo with test cases.

\$\endgroup\$
2
\$\begingroup\$

R, 105 bytes

code

l=scan();o=c();z=0;while((n=length(l))>0){for(i in 1:n)o=c(o,(i+l[i]-1)%%n+1);l=l[-o];o=c();z=z+1};cat(z)

ungolfed

l <- scan()                  # get input as a 'l' vector from user
o <- c()                     # create a empty vector
z=0                          # create a counter starting at 0   
while((n=length(l))>0){      # while the length of the input is more than 0
  for(i in 1:n){             # iterate through the vector
    o=c(o,(i+l[i]-1)%%n+1)   # add the index that will be deleted to the 'o' vector
  }
  l=l[-o]                    # remove the 'o' vector indexes from 'l'
  o=c()                      # empty 'o'
  z=z+1                      # add 1 to counter
}
cat(z)                       # print the counter
\$\endgroup\$
0
2
\$\begingroup\$

Pyth, 17 bytes

tl.u.DN.e%+kblNNQ

Coincidentally very similar to kirbyfan's answer.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 71 bytes

Length@FixedPointList[#~Delete~Mod[Plus~MapIndexed~#,Length@#,1]&,#]-2&
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 67: (i=0;#//.l:{__}:>l~Delete~Mod[++i;Plus~MapIndexed~l,Length@l,1];i)& \$\endgroup\$ Oct 17, 2015 at 16:13
  • 1
    \$\begingroup\$ The Plus~MapIndexed~# is really clever, but I wonder if there isn't a shorter way using l+Range@Length@l. \$\endgroup\$ Oct 17, 2015 at 16:14
1
\$\begingroup\$

STATA, 146 bytes

inf a using a.
gl b=0
qui while _N>0{
g q$b=0
g c$b=mod(_n+a-1,_N)+1
forv y=1/`=_N'{
replace q$b=1 if _n==c$b[`y']
}
drop if q$b
gl b=$b+1
}
di $b

Uses the paid version of STATA. Assumes the input is in a newline separated file called a.. Limited to situations where no more than 1023 rounds are required due to a maximum number of variables allowed (can be fixed at the cost of 10 bytes). It reads the data and runs a loop until there are no more observations. In each iteration, make a variable with the value of the index it points to. For each observation, if another observation points to it, set an indicator to drop the variable. Then drop all observations with that indicator and increment the counter. After the loop, print the counter.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 78 74 bytes

f=->a{b,i=[],0;(a.map{|e|b<<a[(e+i)%a.size]};a-=b;i+=1)while a.size>0;p i}
\$\endgroup\$
1
\$\begingroup\$

awk, 66 bytes

{for(;n=split($0=$0,a);++r)for(i in a)$((i+a[i]%n+n-1)%n+1)=X}$0=r

Simply uses mod length array to keep it inside the array. In the input the numbers need to be separated by spaces.

Usage example

echo "-2 -1 0 1 2 3 4 5 6 7" | awk '{for(;n=split($0=$0,a);++r)for(i in a)$((i+a[i]%n+n-1)%n+1)=X}$0=r'

Here's all the input examples in the appropriate format

3
0 0 0
-2 -1 0 1 2 3 4 5 6 7
5 5 5 6 6 6
3 -7 -13 18 -10 8
-7 5 1 -5 -13 -10 9
4 20 19 16 8 -9 -14 -2 17 7 2 -2 10 0 18 -5 -5 20
11 2 7 -6 -15 -8 15 -12 -2 -8 -17 6 -6 -5 0 -20 -2 11 1
2 -12 -11 7 -16 9 15 -10 7 3 -17 18 6 6 13 0 18 10 -7 -1
18 -18 -16 -2 -19 1 -9 -18 2 1 6 -15 12 3 -10 8 -3 7 -4 -11 5 -15 17 17 -20 11 -13 9 15
\$\endgroup\$
0
\$\begingroup\$

Python 2, 122 bytes

def f(l):
 if not l:return 0
 L=len(l);x=[1]*L
 for i in range(L):x[(i+l[i])%L]=0
 return 1+e([v for i,v in zip(x,l)if i])
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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