Play the elimination game

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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);
    }
}

Answer 5

Pyth, 21 bytes

[email protected]%+kblNNQ

Live demo with test cases.

Answer 6

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

Answer 7

Pyth, 17 bytes

tl.u.DN.e%+kblNNQ

Coincidentally very similar to kirbyfan's answer.

Answer 8

Mathematica, 71 bytes

Length@FixedPointList[#~Delete~Mod[Plus~MapIndexed~#,Length@#,1]&,#]-2&

Answer 9

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.

Answer 10

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}

Answer 11

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

Answer 12

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])