Jouez le jeu d'élimination

12

introduction

Dans ce défi, votre tâche consiste à simuler un certain type de jeu d'élimination. Dans le jeu, les participants se tiennent en cercle et tout le monde tient un entier. À chaque manche du jeu, chaque participant pointe du doigt la personne nqui s'éloigne, si tel nest le numéro qu'elle détient. Si nest positif, ils comptent à leur droite, s'ils nsont négatifs, ils comptent à leur gauche et s'ils nsont nuls, ils se désignent eux-mêmes. Tout participant qui a quelqu'un pointé sur lui est éliminé et quitte le cercle; ceci termine le tour. Les tours se poursuivent jusqu'à ce qu'il ne reste plus de participants.

Contribution

Votre entrée est une liste non vide d'entiers, dans n'importe quel format raisonnable. Il représente les numéros que détiennent les participants au jeu.

Production

Votre sortie est le nombre de tours qu'il faut jusqu'à la fin du jeu.

Exemple

Considérez la liste d'entrée [3,1,-2,0,8]. Au premier tour, les événements suivants se produisent:

  • La personne qui tient 3pointe droit sur la personne qui tient 0.
  • La personne qui tient 1pointe droit sur la personne qui tient -2.
  • La personne qui tient -2pointe vers la personne qui tient 3.
  • La personne qui se 0montre du doigt.
  • La personne qui tient 8pointe droit sur la personne qui tient -2(la liste représente un cercle, donc elle s'enroule aux extrémités).

Cela signifie que 0, -2et 3sont éliminés, donc le deuxième tour se fait avec la liste [1,8]. Ici, les 1points sur 8et les 8points sur eux-mêmes 8sont éliminés. Le troisième tour se fait avec la liste [1], où 1il se pointe simplement et est éliminé. Il a fallu trois tours pour éliminer tous les participants, donc la sortie correcte est 3.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites.

Cas de test

[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
Zgarb
la source
Êtes-vous sûr du dernier cas de test, j'en reçois 5?
flawr
@flawr Je peux vérifier mon implémentation de référence dans environ une heure (j'ai dû quitter mon ordinateur), mais cela devrait être correct.
Zgarb
Juste pour être clair: nest-ce le numéro que la personne détient?
Peter Taylor
@PeterTaylor Oui, ça l'est. Je clarifierai cela plus tard dans le défi.
Zgarb du

Réponses:

4

Pyth, 15 octets

f!=.DQ.e%+bklQQ

Suite de tests grâce à kirby

Utilise le même mécanisme d'itération que @orlp, mais détecte le nombre d'itérations en utilisant fla fonction "Répéter jusqu'à la fausse" pour détecter []une fois que nous avons terminé.

isaacg
la source
5

Matlab, 91 77 octets

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

Ancienne 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

C'est un défi où matlab brille, le cœur de ce code est la suppression des entrées du tableau: a(mod((1:l)+a-1,l)+1)=[]ce qui est assez élégant je pense.

flawr
la source
4

CJam, 21 octets

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

Suite de tests.

Prend en entrée une liste de style CJam, mais la suite de tests prend en charge la conversion du format dans le défi.

Explication

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.
Martin Ender
la source
Merci: eec'est presque exactement ce que je cherchais hier pour une autre question.
Peter Taylor
3

C #, 251 219 211 197 193 octets

Le langage non ésotérique le plus impassible frappe de nouveau.

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

Ce programme attend la séquence d'entrée comme arguments de ligne de commande. Par exemple, pour entrer la liste [5,5,5,6,6,6], appelez-la avec des arguments de ligne de commande 5 5 5 6 6 6.

Merci à Martin Büttner pour quelques conseils.

Je l'ai joué à 197 en réalisant que je peux réutiliser le argstableau même s'il s'agit d'un tableau de chaînes. J'ai seulement besoin de les analyser en un entier à un seul endroit.

Golfé à 193 en réalisant que .Where(...==x).Any()c'est plus court que .Select(...).Contains(x).

Non golfé

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);
    }
}
Timwi
la source
5
C # est le plus impassible? Vous devez certainement vous tromper; tout le monde sait que c'est Java. : P
Alex A.
@AlexA. Pfft, je suis avec Timwi sur celui-ci. J'ai souvent battu C # avec Java: P
Geobits
3
Vous vous trompez, Pyth ou CJam sont les plus inviolables, C # est le langage le plus impossible à gagner!
Beta Decay
2

R, 105 octets

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)

non golfé

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
Mutador
la source
2

Pyth, 17 octets

tl.u.DN.e%+kblNNQ

Par coïncidence, très similaire à la réponse de kirbyfan.

orlp
la source
2

Mathematica, 71 octets

Length@FixedPointList[#~Delete~Mod[Plus~MapIndexed~#,Length@#,1]&,#]-2&
alephalpha
la source
1
67:(i=0;#//.l:{__}:>l~Delete~Mod[++i;Plus~MapIndexed~l,Length@l,1];i)&
Martin Ender
1
C'est Plus~MapIndexed~#vraiment intelligent, mais je me demande s'il n'y a pas un moyen plus court d'utiliser l+Range@Length@l.
Martin Ender
1

STATA, 146 octets

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

Utilise la version payante de STATA. Suppose que l'entrée se trouve dans un fichier séparé par des sauts de ligne appelé a.. Limité aux situations où pas plus de 1023 tours sont nécessaires en raison d'un nombre maximum de variables autorisé (peut être fixé au coût de 10 octets). Il lit les données et exécute une boucle jusqu'à ce qu'il n'y ait plus d'observations. Dans chaque itération, créez une variable avec la valeur de l'index vers lequel elle pointe. Pour chaque observation, si une autre observation la pointe, définissez un indicateur pour supprimer la variable. Déposez ensuite toutes les observations avec cet indicateur et incrémentez le compteur. Après la boucle, imprimez le compteur.

bmarks
la source
1

Rubis, 78 74 octets

f=->a{b,i=[],0;(a.map{|e|b<<a[(e+i)%a.size]};a-=b;i+=1)while a.size>0;p i}
Peter Lenkefi
la source
1

awk, 66 octets

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

Utilise simplement mod length arraypour le garder à l'intérieur du tableau. Dans l'entrée, les nombres doivent être séparés par des espaces.

Exemple d'utilisation

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'

Voici tous les exemples d'entrée dans le format approprié

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
Cabbie407
la source
0

Python 2, 122 octets

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])
TFeld
la source