Introdução

Neste desafio, sua tarefa é simular um certo tipo de jogo de eliminação. No jogo, os participantes ficam em círculo e todos estão segurando um número inteiro. Em cada rodada do jogo, cada participante aponta para a pessoa nque se afasta, se né o número que está segurando. Se né positivo, conta à direita, se né negativo, conta à esquerda e, se nfor zero, aponta para si. Todo participante que tem alguém apontando para eles é eliminado e sai do círculo; isso termina a rodada. As rodadas continuam até que não haja mais participantes.

Entrada

Sua entrada é uma lista não vazia de números inteiros, em qualquer formato razoável. Representa os números que os participantes do jogo estão segurando.

Resultado

Sua saída é o número de rodadas necessárias até o final do jogo.

Exemplo

Considere a lista de entrada [3,1,-2,0,8]. Na primeira rodada, acontece o seguinte:

• A pessoa que está segurando 3aponta diretamente para a pessoa que está segurando 0.
• A pessoa que está segurando 1aponta diretamente para a pessoa que está segurando -2.
• A pessoa que mantém -2pontos deixados na pessoa que está segurando 3.
• A pessoa que 0aponta para si mesma.
• A pessoa que está segurando 8aponta diretamente para a pessoa que está segurando -2(a lista representa um círculo, de modo que envolve as extremidades).

Isso significa que 0, -2e 3são eliminados, a segunda rodada é feita com a lista [1,8]. Aqui, 1aponta para 8, e 8aponta para si mesmo, então 8é eliminado. A terceira rodada é feita com a lista [1], onde 1simplesmente aponta para si mesma e é eliminada. Foram necessárias três rodadas para eliminar todos os participantes, portanto a saída correta é 3.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Casos de teste

[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

Pitão, 15 bytes

f!=.DQ.e%+bklQQ

Suíte de teste graças a Kirby

Usa o mesmo mecanismo de iteração que o @orlp, mas detecta o número de iterações usando fa função "Repetir até falsidade", para detectar a []vez que terminarmos.

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

Versão antiga:

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

Esse é um desafio no qual o matlab brilha, o coração desse código é a exclusão das entradas da matriz: o a(mod((1:l)+a-1,l)+1)=[]que é bastante elegante, eu acho.

CJam, 21 bytes

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

Suíte de teste.

Recebe entrada como uma lista de estilos CJam, mas a suíte de testes cuida da conversão do formato no desafio.

Explicação

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.

C #, 251 219 211 197 193 bytes

A linguagem não esotérica mais ingovernável ataca novamente.

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

Este programa espera a sequência de entrada como argumentos da linha de comandos. Por exemplo, para inserir a lista [5,5,5,6,6,6], chame-a com argumentos de linha de comando 5 5 5 6 6 6.

Obrigado a Martin Büttner por algumas dicas.

Aumentou para 197 ao perceber que eu posso reutilizar a argsmatriz, mesmo que seja uma série de seqüências de caracteres. Eu só preciso analisá-los em um número inteiro em um só lugar.

Golfou para 193 ao perceber que .Where(...==x).Any()é menor que .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);
    }
}

Pitão, 21 bytes

[email protected]%+kblNNQ

Demonstração ao vivo com casos de teste.

R, 105 bytes

código

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)

destroçado

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

Pitão, 17 bytes

tl.u.DN.e%+kblNNQ

Coincidentemente muito semelhante à resposta de Kirbyfan.

Mathematica, 71 bytes

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

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

Usa a versão paga do STATA. Supõe que a entrada esteja em um arquivo separado por nova linha chamado a.. Limitado a situações em que não são necessárias mais de 1023 rodadas devido a um número máximo de variáveis ​​permitido (pode ser corrigido ao custo de 10 bytes). Ele lê os dados e executa um loop até que não haja mais observações. Em cada iteração, faça uma variável com o valor do índice para o qual aponta. Para cada observação, se outra observação apontar para ela, defina um indicador para descartar a variável. Em seguida, descarte todas as observações com esse indicador e aumente o contador. Após o loop, imprima o contador.

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}

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

Simplesmente usa mod length arraypara mantê-lo dentro da matriz. Na entrada, os números precisam ser separados por espaços.

Exemplo de uso

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'

Aqui estão todos os exemplos de entrada no formato apropriado

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

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