introduction

Par définition, les identifiants uniques doivent être uniques. Le fait d'avoir plusieurs identifiants identiques entraîne la récupération de données inattendues. Mais avec des données provenant simultanément de plusieurs sources, il peut être difficile de garantir l'unicité. Écrivez une fonction qui unifie une liste d'identifiants.

C'est peut-être le pire casse-tête que j'ai écrit, mais vous avez l'idée.

Exigences

Étant donné une liste de zéro ou plusieurs entiers positifs, appliquez les règles suivantes à chaque nombre du premier au dernier:

• Si le numéro est le premier du genre, conservez-le.
• Si le nombre a déjà été rencontré, remplacez-le par l'entier positif le plus bas qui ne se trouve nulle part dans la liste d'entrée entière ou sur une sortie existante.

Pour la solution:

• La solution peut être un programme ou une fonction.
• L'entrée peut être une chaîne, un tableau, passé comme arguments ou une entrée au clavier.
• La sortie peut être une chaîne, un tableau ou imprimée à l'écran.
• Tous les nombres de la liste de sortie sont distincts.

Hypothèses

• La liste d'entrée est propre. Il ne contient que des entiers positifs.
• Un entier positif a une plage de 1 à 2 ³¹ -1.
• Moins de 256 Mo de mémoire sont disponibles pour les variables de votre programme. (Fondamentalement, aucun tableau à 2 147 483 648 éléments n'est autorisé.)

Cas de test

Input:  empty
Output: empty

Input:  5
Output: 5

Input:  1, 4, 2, 5, 3, 6
Output: 1, 4, 2, 5, 3, 6

Input:  3, 3, 3, 3, 3, 3
Output: 3, 1, 2, 4, 5, 6

Input:  6, 6, 4, 4, 2, 2
Output: 6, 1, 4, 3, 2, 5

Input:  2147483647, 2, 2147483647, 2
Output: 2147483647, 2, 1, 3

Notation

Juste un simple golf de code. Le nombre d'octets le plus bas à cette heure la semaine prochaine l'emporte.

Brachylog , 8 octets

{|∧ℕ₁}ᵐ≠

Essayez-le en ligne!

Explication

{    }ᵐ     Map on the Input:
              Input = Output…
 |            …or…
  ∧ℕ₁         …Output is in [1,+inf)
       ≠    All elements of the output must be different
            (Implicit labeling)

Java 8, 158 144 octets

a->{int m=0;String r="",c=",",b=r;for(int x:a)b+=x+c;for(int x:a)if(r.contains(x+c)){for(;(r+b).contains(++m+c););r+=m+c;}else r+=x+c;return r;}

• .contains(m+c);m++)pour .contains(++m+c);)enregistrer 1 octet et converti simultanément en Java 8 pour enregistrer 13 octets supplémentaires.

Explications:

Essayez ici.

a->{                      // Method with integer-array parameter and String return-type
  int m=0;                //  Lowest integer
  String r="",            //  Result-String
         c=",",           //  Comma delimiter for result String
         b=r;for(int x:a)b+=x+c;
                          //  Input array as String
  for(int x:a)            //  Loop (2) over the integers in the array
    if(r.contains(x+c)){  //   If the result already contains this integer
      for(;(r+b).contains(++m+c););
                          //    Inner (3) as long as either the result-String or array-String contains the lowest integer
                          //     and raise the lowest integer before every iteration by 1
      r+=m+c;             //    Append the result with this lowest not-present integer
    }else                 //   Else:
      r+=x+c;             //    Append the result-String with the current integer
                          //  End of loop (2) (implicit / single-line body)
  return r;               //  Return the result-String
}                         // End of method

JavaScript (ES6), 49 octets

a=>a.map(g=(e,i)=>a.indexOf(e)-i?g(++n,-1):e,n=0)

Rubis , 63 octets

->a{r=*0..a.size;r.map{|i|[a[i]]-a[0,i]==[]?a[i]=(r-a)[1]:0};a}

Essayez-le en ligne!

Explication

->a{                                    # Anonymous function with one argument
    r=*0..a.size;                       # Numbers from 0 to array size
    r.map{|i|                           # For all numbers in range:
        [a[i]]                          #  Get array with just a[i]
              -a[0,i]                   #  Remove elements from array that are
                                        #    also in a[0..i-1]
                    ==[]?               #  Check if result is an empty array
                        a[i]=           #  If true, set a[i] to:
                             (r-a)      #   Remove elements from number range
                                        #     that are also in input array
                                  [1]   #   Get second element (first non-zero)
                        :0};            #  If false, no-op
                            a}          # Return modified array

05AB1E , 17 16 18 octets

vy¯yåi¹gL¯K¹K¬}ˆ}¯

Essayez-le en ligne!

Explication

v                    # for each y in input
 y                   # push y
  ¯yåi               # if y exist in global list
      ¹gL            # push [1 ... len(input)]
         ¯K          # remove any number that is already in global list
           ¹K        # remove any number that is in the input
             ¬       # get the first (smallest)
              }      # end if
               ˆ     # add to global list
                }¯   # end loop, push and output global list

PHP, 121 octets

<?$n=array_diff(range(0,count($g=$_GET)),$g);sort($n);$r=[];foreach($g as$v)$r[]=in_array($v,$r)?$n[++$i]:$v;print_r($r);

Version en ligne

Étendu

$n=array_diff(range(0,count($g=$_GET)),$g); # create array of ascending values which are not in input array plus zero
sort($n); # minimize keys
$r=[];  # empty result array
foreach($g as$v) # loop input array
  $r[]=in_array($v,$r)?$n[++$i]:$v; # if value is not in result array add value else take new unique value skip zero through ++$i
print_r($r); # output result array

Python 2, 77 79 octets

a=input();u=[];j=1
for x in a:
 u+=[[x,j][x in u]]
 while j in u+a:j+=1
print u

Prend une saisie au clavier, comme [3, 3, 3, 3, 3, 3].

Gardez simplement une trace du plus petit entier positif jnon utilisé jusqu'à présent. Pour chaque élément xde l'entrée, la sortie xsi xn'a pas déjà été utilisée, sinon la sortie j. Enfin, mettez à jour jchaque fois que vous sortez quelque chose.

EDITED: pour corriger une erreur de gestion d'entrée de [6, 6, 4, 4, 2, 2]. Merci à @Rod d'avoir signalé l'erreur ainsi qu'un correctif. L'erreur était que, dans le cas d'une entrée en double, il produirait le plus petit nombre inutilisé à ce point de la liste, même si cette sortie apparaissait plus tard dans l'entrée. (C'était faux, comme expliqué dans le post et les commentaires, mais je l'ai quand même gâché d'une manière ou d'une autre.) Quoi qu'il en soit, le correctif consistait simplement à ajouter la liste d'entrée a, à l'ensemble de valeurs qui ne pouvaient pas être sorties dans ce cas.

Haskell , 79 76 octets

MODIFIER:

• -3 octets: @nimi a vu que cela headpourrait être remplacé par une correspondance de modèle.

([]#)est une fonction anonyme qui prend et renvoie une liste. Utilisez comme ([]#)[2147483647, 2, 2147483647, 2].

(?)=notElem
s#(x:y)|z:_<-[x|x?s]++filter(?(s++y))[1..]=z:(z:s)#y
_#n=n
([]#)

Essayez-le en ligne!

Comment ça marche

• ? est un opérateur abrégé pour vérifier si un élément est absent d'une liste.
• s#lgère la liste des entiers l, étant donné une liste sd'entiers déjà utilisés.
  • xest le prochain entier à regarder, yles autres.
  • zest l'entier choisi pour le point suivant. C'est xsi xn'est pas un élément de s, et le premier entier positif ni dans sni dans yautrement.
  • (z:s)#ypuis revient avec zajouté à la liste entière utilisée.
  • n est une liste vide, car les listes non vides ont été gérées dans la ligne précédente.
• La fonction principale ([]#)prend une liste et appelle #avec elle comme deuxième argument, et une liste vide pour le premier argument.

APL (Dyalog 16.0), 34 octets

(s↑v~⍨⍳⌈/v+s←+/b←(⍳≢v)≠⍳⍨v)@{b}v←⎕

Pyth , 21 20 octets

.b?} NPY@-UhlQQ=hZNQ._
m?}edPd@-SlQQ~hZed._

Suite de tests

J'ajouterai une explication quand j'aurai le temps.

C # , 135 octets

Golfé

(int[] i)=>{for(int x=1,v,m=0,l=i.Length,y;x<l;x++){v=i[x];for(y=0;y<l&&v==i[x]?y<x:y<l;y++)if(i[y]==v){v=++m;y=-1;}i[x]=v;}return i;};

Ungolfed

( int[] i ) => {
   for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {
      v = i[ x ];

      for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )
         if( i[ y ] == v ) {
            v = ++m;
            y = -1;
         }

      i[ x ] = v;
   }

   return i;
};

Ungolfed lisible

// Takes an array of Int32 objects ( 32-byte signed integers )
( int[] i ) => {

   // Cycles through each element on the array
   //   x: Scan position, starts at the 2nd element
   //   v: Value being processed
   //   m: The next minimum value to replace
   //   l: Size of the array, to save some byte count
   for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {

      // Hold the value
      v = i[ x ];

      // Re-scan the array for a duplicate value up the the current position ( 'x' ) IF
      //   ... the currently hold value hasn't been modified
      //   ... otherwise, re-scans the entire array to find a suitable value to replace
      for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )

         // Check if 'v' shares the same value with other element
         if( i[ y ] == v ) {

            // Set 'v' to the minimum value possible
            v = ++m;

            // Reset the scan position to validate the new value
            y = -1;
         }

      // Set the 'v' to the array
      i[ x ] = v;
   }

   // Return the array
   return i;
};

Code complet

using System;
using System.Collections.Generic;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
         Func<Int32[], Int32[]> f = ( int[] i ) => {
            for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {
               v = i[ x ];

               for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )
                  if( i[ y ] == v ) {
                     v = ++m;
                     y = -1;
                  }

               i[ x ] = v;
            }

            return i;
         };

         List<Int32[]>
            testCases = new List<Int32[]>() {
               new Int32[] { },
               new Int32[] { 5 },
               new Int32[] { 1, 4, 2, 5, 3, 6 },
               new Int32[] { 3, 3, 3, 3, 3, 3 },
               new Int32[] { 6, 6, 4, 4, 2, 2 },
               new Int32[] { 2147483647, 2, 2147483647, 2 },
            };

         foreach( Int32[] testCase in testCases ) {
            Console.WriteLine( $" Input: {String.Join( ",", testCase )}\nOutput: {string.Join( ",", f( testCase ) )}\n" );
         }

         Console.ReadLine();
      }
   }
}

Communiqués

• v1.0 - 135 bytes- Solution initiale.

Remarques

• Aucun

Python 2 , 101 octets

x=input()
for i,n in enumerate(x):x[i]=[n,list(set(range(1,len(x)+9))-set(x))[0]][n in x[:i]]
print x

Essayez-le en ligne! ou Essayez tous les cas de test

R , 39 46 octets

Crée un vecteur à partir de l'entrée, puis remplace les valeurs dupliquées par une plage de 1 à un million dont les valeurs d'entrée ont été supprimées. Renvoie un vecteur numérique. Aucune entrée ne renverra le vecteur vide numérique (0).

i[duplicated(i)]=(1:1e6)[-(i=scan())];i

Essayez-le en ligne!

Cela lancera un avertissement sur la longueur du vecteur de remplacement

                           i=scan()     # set i as input
                 (1:1e6)                # 1 to a million (could go higher)
                 (1:1e6)[-(i=scan())]   # without input values
  duplicated(i)                         # duplicate values in i
i[duplicated(i)]=(1:1e6)[-(i=scan())]   # set duplicate i values to reduced range vector
                                     ;i # return result

C 169 octets 133 octets

entrée = tableau a, sortie = tableau modifié a

i=1,j,k,l;void f(int*a,int n){for(;i<n;i++)for(j=i-1;j>=0;j--)if(a[i]==a[j]){l=1;for(k=0;k<n;)if(l==a[k])k=l++?0:0;else k++;a[i]=l;}}

formaté

int i, j, k, l;
void f(int* a, int n)
{
    for (i = 1; i<n; i++)
        for (j = i - 1; j >= 0; j--)
            if (a[i] == a[j])
            {
                l = 1;
                for (k = 0; k<n;)
                    if (l == a[k])
                        k = l++ ? 0 : 0;
                    else
                        k++;
                a[i] = l;
            }
}

Trop d'octets gaspillés pour ces boucles. Quelqu'un pense-t-il à raccourcir le code en inventant un nouvel algorithme (qui utilise moins de boucle)? Je pensais, mais je n'en ai pas trouvé.

C # 7, 116 octets

int[]f(int[]c){int j=0;int h()=>c.Contains(++j)?h():j;return c.Select((e,i)=>Array.IndexOf(c,e)<i?h():e).ToArray();}

Dentelé

int[] f(int[] c)
{
    int j = 0;
    int h() => c.Contains(++j) ? h() : j;
    return c
        .Select((e, i) => Array.IndexOf(c, e) < i ? h() : e)
        .ToArray();
}

A expliqué

• la première occurrence d'un nombre est toujours laissée telle quelle
• les occurrences consécutives d'un nombre sont tirées de [1, 2, 3, ...], en ignorant les valeurs présentes dans l'entrée.

Version en ligne

Clojure, 72 octets

#(reduce(fn[r i](conj r(if((set r)i)(nth(remove(set r)(range))1)i)))[]%)

Une réduction de base. Si iest contenu dans la liste de sortie jusqu'à présent, nous prendrons le 2e élément (1 lorsqu'il est indexé à 0) de la liste infinie d'entiers (range)dont nous avons supprimé les nombres qui ont déjà été utilisés. La plage commence à zéro, nous ne pouvons donc pas prendre le premier élément mais le second.

R, 74 octets

lit la liste depuis stdin; renvoie NULL pour une entrée vide.

o=c();for(i in n<-scan())o=c(o,`if`(i%in%o,setdiff(1:length(n),o)[1],i));o

explication:

o=c()                                #initialize empty list of outputs
for(i in n<-scan())                  # loop through the list after reading it from stdin
    o=c(o,                           # set the output to be the concatenation of o and
      `if`(i%in%o,                   # if we've seen the element before
           setdiff(1:length(n),o)[1] # the first element not in 1,2,...
           ,i))                      # otherwise the element
o                                    # print the output

1:length(n) peut être utilisé car nous sommes garantis de ne jamais avoir besoin d'un remplacement de l'extérieur de cette gamme.

Essayez-le en ligne!

Axiome, 169 octets

f a==(r:List INT:=[];for i in 1..#a repeat(~member?(a.i,r)=>(r:=concat(r,a.i));for j in 1..repeat if~member?(j,r)and(~member?(j,a)or j=a.i)then(r:=concat(r,j);break));r)

ungolf et résultat

ff(a)==
  r:List INT:=[]
  for i in 1..#a repeat
      ~member?(a.i,r)=>(r:=concat(r,a.i))
      for j in 1.. repeat
            if~member?(j,r)and(~member?(j,a) or j=a.i)then(r:=concat(r,j);break)
  r

(3) -> f([])
   (3)  []
                                                       Type: List Integer
(4) -> f([5])
   (4)  [5]
                                                       Type: List Integer
(5) -> f([1,4,2,5,3,6])
   (5)  [1,4,2,5,3,6]
                                                       Type: List Integer
(6) -> f([3,3,3,3,3,3])
   (6)  [3,1,2,4,5,6]
                                                       Type: List Integer
(7) -> f([6, 6, 4, 4, 2, 2])
   (7)  [6,1,4,3,2,5]
                                                       Type: List Integer
(8) -> f([2147483647, 2, 2147483647, 2])
   (8)  [2147483647,2,1,3]
                                                       Type: List Integer