Unikaj identyfikatorów

31

Wprowadzenie

Z definicji unikalne identyfikatory powinny być unikalne. Posiadanie wielu identycznych identyfikatorów powoduje pobieranie nieoczekiwanych danych. Jednak przy równoczesnym napływaniu danych z wielu źródeł zapewnienie jednoznaczności może być trudne. Napisz funkcję, która ujednolica listę identyfikatorów.

To chyba najgorszy puch puzzli, jaki napisałem, ale masz pomysł.

Wymagania

Biorąc pod uwagę listę zerowych lub więcej dodatnich liczb całkowitych, zastosuj następujące reguły do ​​każdej liczby od pierwszej do ostatniej:

  • Jeśli numer jest pierwszym w swoim rodzaju, zachowaj go.
  • Jeśli liczba została wcześniej napotkana, zamień ją na najniższą dodatnią liczbę całkowitą, której nie znaleziono nigdzie na całej liście danych wejściowych ani na żadnym istniejącym wyjściu.

Dla rozwiązania:

  • Rozwiązaniem może być program lub funkcja.
  • Dane wejściowe mogą być łańcuchem, tablicą przekazywaną jako argumenty lub dane wejściowe z klawiatury.
  • Wynik może być łańcuchem, tablicą lub wydrukowany na ekranie.
  • Wszystkie liczby na liście wyników są różne.

Założenia

  • Lista wejściowa jest czysta. Zawiera tylko dodatnie liczby całkowite.
  • Dodatnia liczba całkowita ma zakres od 1 do 2 31 -1.
  • Mniej niż 256 MB pamięci jest dostępne na zmienne programu. (Zasadniczo niedozwolone są 2 147 483 648 elementów).

Przypadki testowe

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

Punktacja

Po prostu prosty golf. Najniższa liczba bajtów do tego czasu wygrywa w przyszłym tygodniu.

Hand-E-Food
źródło
4
Dodaj przypadek testowy: 6, 6, 1, 2, 3, 4, 56, 7, 1, 2, 3, 4, 5
Adám
2
@ Adám Nie powinieneś 6, 6, ...dawać 6, 1, ...?
xnor
5
@ Adám Myślę, że masz rację, ale sformułowanie może być jaśniejsze. Czy „zestaw” odnosi się do napotkanych elementów, wszystkich elementów listy wejściowej lub elementów na liście w obecnej postaci?
xnor
3
@xnor 6, 6, 4, 4, 2, 2Przypadek testowy potwierdza interpretację Adáma : oczekiwany wynik to 6, 1, 4, 3, 2, 5, a nie 6, 1, 4, 2, 3, 5.
Fatalize
2
Czy 0 jest liczone jako dodatnia liczba całkowita dla tego wyzwania?
Łukasz

Odpowiedzi:

11

Brachylog , 8 bajtów

{|∧ℕ₁}ᵐ≠

Wypróbuj online!

Wyjaśnienie

{    }ᵐ     Map on the Input:
              Input = Output…
 |            …or…
  ∧ℕ₁         …Output is in [1,+inf)
       ≠    All elements of the output must be different
            (Implicit labeling)
Fatalizować
źródło
8

Java 8, 158 144 bajtów

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++)aby .contains(++m+c);)zapisać 1 bajt i jednocześnie przekonwertować na Javę 8, aby zapisać 13 kolejnych bajtów.

Objaśnienia:

Wypróbuj tutaj.

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
Kevin Cruijssen
źródło
7

JavaScript (ES6), 49 bajtów

a=>a.map(g=(e,i)=>a.indexOf(e)-i?g(++n,-1):e,n=0)
Neil
źródło
7

Ruby , 63 bajty

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

Wypróbuj online!

Wyjaśnienie

->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
Wartość tuszu
źródło
6

05AB1E , 17 16 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

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
Emigna
źródło
Prawdopodobnie powinienem użyć zmniejszania zamiast mapy ... Zobaczę, czy to pomoże
Leaky Nun
@LeakyNun: Zmniejszenie lub mapa to często droga :)
Emigna
3
Daje [6, '1', '2', '3', '4', '5', '7']. Powinien dać [6, '7', '1', '2', '3', '4', '5'].
Adám
1
@ Adám: Dzięki za złapanie! Naprawiono teraz :)
Emigna
6

PHP, 121 bajtów

<?$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);

Wersja online

Rozszerzony

$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
Jörg Hülsermann
źródło
5

Python 2, 77 79 bajtów

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

Pobiera dane z klawiatury, jak [3, 3, 3, 3, 3, 3].

Śledź tylko najmniejszą dodatnią liczbę całkowitą, która dotychczas jnie była używana. Dla każdego elementu xwejścia wyprowadza dane wyjściowe, xjeśli xjeszcze nie zostały użyte, w przeciwnym razie dane wyjściowe j. Na koniec aktualizuj za jkażdym razem, gdy coś wypisujesz.

ZMIENIONO: aby naprawić błąd obsługi błędu [6, 6, 4, 4, 2, 2]. Dzięki @Rod za wskazanie błędu i poprawki. Błąd polegał na tym, że w przypadku zduplikowanego wpisu wyświetlałby najmniejszą liczbę nieużywaną do tego punktu na liście, nawet jeśli dane wyjściowe pojawiły się później na wejściu. (Było to błędne, jak wyjaśniono w poście i komentarzach, ale jakoś to pomieszałem). W każdym razie poprawką było po prostu dodanie listy danych wejściowych ado zestawu wartości, których nie można było w takim przypadku wygenerować.

Mathmandan
źródło
nie działa [6,6,4,4,2,2], możesz (prawdopodobnie) to naprawić, dodając +ado while j in u:->while j in u+a:
Rod
@Rod Masz rację, mój błąd. (Jakoś ciągle to pomieszałem pomimo komentarzy na ten temat - dziękuję za zwrócenie mi na to uwagi - a także nie przetestowałem mojego rozwiązania wystarczająco dobrze na testach. Zawstydzające.) OK, uwzględniłem twoje bardzo miłe napraw i zweryfikuj na podstawie przypadków testowych. Dzięki!
matmandan
5

Haskell , 79 76 bajtów

EDYTOWAĆ:

  • -3 bajty: zobaczyłem @nimi, które headmożna zastąpić dopasowaniem wzorca.

([]#)to anonimowa funkcja przyjmująca i zwracająca listę. Użyj jak ([]#)[2147483647, 2, 2147483647, 2].

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

Wypróbuj online!

Jak to działa

  • ? jest skróconym operatorem do sprawdzania, czy element jest nieobecny na liście.
  • s#lobsługuje listę liczb całkowitych l, biorąc pod uwagę listę sjuż użytych liczb całkowitych.
    • xjest następną liczbą całkowitą, na którą należy spojrzeć, ypozostałe.
    • zjest liczbą całkowitą wybraną dla następnego miejsca. To jest, xjeśli xnie jest elementem s, i pierwszą dodatnią liczbą całkowitą, ani w, sani w yinny sposób.
    • (z:s)#ynastępnie powtarza się z zdodaną do listy używanych liczb całkowitych.
    • n jest pustą listą, ponieważ niepuste listy były obsługiwane w poprzednim wierszu.
  • Główna funkcja ([]#)pobiera listę i wywołuje #ją jako drugi argument oraz pustą listę dla pierwszego argumentu.
Ørjan Johansen
źródło
|z:_<-[x|...]...
nimi
4

APL (Dyalog 16.0), 34 bajty

(s↑v~⍨⍳⌈/v+s←+/b←(⍳≢v)≠⍳⍨v)@{b}v←⎕
Adám
źródło
2
Musi być lepszy sposób.
Adám
3

Pyth , 21 20 bajtów

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

Zestaw testowy

Dodam wyjaśnienie, kiedy będę miał czas.

Leaky Nun
źródło
3

C # , 135 bajtów


Grał w golfa

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

Bez golfa

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

Nieczytelny czytelny

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

Pełny kod

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

Wydawnictwa

  • v1.0 - 135 bytes- Wstępne rozwiązanie.

Notatki

  • Żaden
auhmaan
źródło
3

R , 39 46 bajtów

Tworzy wektor z danych wejściowych, a następnie zastępuje zduplikowane wartości zakresem od 1 do miliona, z których usunięto wartości wejściowe. Zwraca wektor numeryczny. Żadne wejście nie zwróci pustego wektora liczbowego (0).

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

Wypróbuj online!

Spowoduje to wyświetlenie ostrzeżenia o długości wektora zastępczego

                           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
MickyT
źródło
3

C, 169 bajtów 133 bajty

input = tablica a, output = zmodyfikowana tablica 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;}}

sformatowany

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

Zbyt wiele bajtów zmarnowanych dla tych pętli. Czy ktoś myśli o skróceniu kodu poprzez wynalezienie nowego algorytmu (który wykorzystuje mniejszą liczbę pętli)? Myślałem, ale nie znalazłem.

hucancode
źródło
2

C # 7, 116 bajtów

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

Zębaty

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

Wyjaśnił

  • pierwsze wystąpienie liczby zawsze pozostaje niezmienne
  • losowane są kolejne wystąpienia liczby [1, 2, 3, ...], pomijając wartości obecne na wejściu.

Wersja online

użytkownik1655772
źródło
2

Clojure, 72 bajty

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

Podstawowa redukcja. Jeśli ido tej pory znajdował się na liście wyników, bierzemy drugi element (1, gdy indeksowany jest 0) z nieskończonej listy liczb całkowitych, (range)z których usunęliśmy te liczby, które zostały już użyte. Zakres zaczyna się od zera, więc nie możemy wziąć pierwszego elementu, ale drugi.

NikoNyrh
źródło
1

R, 74 bajty

czyta listę ze standardowego wejścia; zwraca NULL dla pustego wejścia.

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

wyjaśnienie:

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) mogą być używane, ponieważ gwarantujemy, że nigdy nie będziemy potrzebować wymiany spoza tego zakresu.

Wypróbuj online!

Giuseppe
źródło
0

Aksjomat, 169 bajtów

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)

golf i wynik

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
RosLuP
źródło