Pengidentifikasi Uniquify

31

pengantar

Menurut definisi, pengidentifikasi unik harus unik. Memiliki banyak pengidentifikasi yang sama menyebabkan seseorang untuk mengambil data yang tidak terduga. Tetapi dengan data yang tiba secara bersamaan dari berbagai sumber, mungkin sulit untuk memastikan keunikannya. Tulis fungsi yang menyatukan daftar pengidentifikasi.

Ini mungkin teka-teki terburuk yang pernah saya tulis, tetapi Anda mengerti.

Persyaratan

Diberikan daftar nol atau lebih bilangan bulat positif, terapkan aturan berikut untuk setiap angka dari pertama hingga terakhir:

  • Jika nomor tersebut adalah yang pertama dari jenisnya, pertahankan.
  • Jika nomor sebelumnya telah ditemukan, gantilah dengan bilangan bulat positif terendah yang tidak ditemukan di seluruh daftar input atau output yang ada.

Untuk solusinya:

  • Solusinya dapat berupa program atau fungsi.
  • Input dapat berupa string, array, diteruskan sebagai argumen, atau input keyboard.
  • Outputnya bisa berupa string, array, atau dicetak ke layar.
  • Semua angka dalam daftar keluaran berbeda.

Asumsi

  • Daftar input bersih. Ini hanya berisi bilangan bulat positif.
  • Bilangan bulat positif memiliki rentang 1 hingga 2 31 -1.
  • Memori kurang dari 256 MB tersedia untuk variabel program Anda. (Pada dasarnya, tidak ada array elemen 2.147.483.648 diizinkan.)

Uji Kasus

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

Mencetak gol

Hanya golf kode sederhana. Hitungan byte terendah saat ini menang minggu depan.

Makanan Tangan
sumber
4
Tambahkan test case: 6, 6, 1, 2, 3, 4, 56, 7, 1, 2, 3, 4, 5
Adám
2
@ Adam Sebaiknya tidak 6, 6, ...memberi 6, 1, ...?
xnor
5
@ Adám Saya pikir Anda benar tentang itu, tetapi kata-katanya bisa lebih jelas, Apakah "set" merujuk pada elemen yang ditemukan, semua elemen dari daftar input, atau elemen dalam daftar seperti yang sekarang ada?
xnor
3
@xnor Kasing 6, 6, 4, 4, 2, 2uji mengkonfirmasi interpretasi Adám: output yang diharapkan adalah 6, 1, 4, 3, 2, 5, dan tidak 6, 1, 4, 2, 3, 5.
Fatalkan
2
Apakah 0 dihitung sebagai bilangan bulat positif untuk tantangan ini?
Lukas

Jawaban:

11

Brachylog , 8 byte

{|∧ℕ₁}ᵐ≠

Cobalah online!

Penjelasan

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

Java 8, 158 144 byte

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++)untuk .contains(++m+c);)menyimpan 1 byte, dan secara bersamaan dikonversi ke Java 8 untuk menghemat 13 byte lagi.

Penjelasan:

Coba di sini.

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
sumber
7

JavaScript (ES6), 49 byte

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

Ruby , 63 byte

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

Cobalah online!

Penjelasan

->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
Nilai Tinta
sumber
6

05AB1E , 17 16 18 byte

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

Cobalah online!

Penjelasan

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
sumber
Saya mungkin harus menggunakan pengurangan alih-alih peta ... biarkan saya melihat apakah itu membantu
Leaky Nun
@LeakyNun: Mengurangi atau memetakan sering kali menjadi jalan :)
Emigna
3
Memberi [6, '1', '2', '3', '4', '5', '7']. Harus memberi [6, '7', '1', '2', '3', '4', '5'].
Adám
1
@ Adám: Terima kasih atas tangkapannya! Diperbaiki sekarang :)
Emigna
6

PHP, 121 Bytes

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

Versi Online

Diperluas

$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
sumber
5

Python 2, 77 79 byte

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

Mengambil input keyboard, misalnya [3, 3, 3, 3, 3, 3].

Catat bilangan bulat positif terkecil yang jtidak digunakan sejauh ini. Untuk setiap elemen xinput, output xjika xbelum pernah digunakan, jika tidak output j. Akhirnya, perbarui jsetiap kali Anda mengeluarkan sesuatu.

Diedit: untuk memperbaiki input penanganan kesalahan dari [6, 6, 4, 4, 2, 2]. Terima kasih kepada @Rod untuk menunjukkan kesalahan serta perbaikannya. Kesalahannya adalah, dalam hal entri duplikat, itu akan menghasilkan angka terkecil yang tidak digunakan ke titik itu dalam daftar, bahkan jika output itu muncul kemudian di input. (Ini salah, seperti yang diklarifikasi dalam posting dan komentar, tapi saya masih mengacaukannya entah bagaimana.) Lagi pula, perbaikannya adalah dengan hanya menambahkan daftar input a,, ke set nilai-nilai yang tidak bisa menjadi output dalam kasus itu.

mathmandan
sumber
tidak bekerja untuk [6,6,4,4,2,2], Anda dapat (mungkin) memperbaikinya dengan menambahkan +ake while j in u:->while j in u+a:
Rod
@Rod Kau benar, kesalahanku. (Entah bagaimana saya masih mengacaukan ini meskipun ada komentar tentang ini - terima kasih telah memperhatikannya - dan saya juga tidak menguji solusi saya dengan baik terhadap kasus-kasus uji. Memalukan.) OK, saya telah memasukkan Anda yang sangat bagus perbaiki, dan verifikasi terhadap kasus uji. Terima kasih!
mathmandan
5

Haskell , 79 76 byte

EDIT:

  • -3 byte: @nimi saw yang headbisa diganti dengan pencocokan pola.

([]#)adalah fungsi anonim untuk mengambil dan mengembalikan daftar. Gunakan like ([]#)[2147483647, 2, 2147483647, 2].

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

Cobalah online!

Bagaimana itu bekerja

  • ? adalah operator yang disingkat untuk memeriksa apakah suatu elemen tidak ada dalam daftar.
  • s#lmenangani daftar bilangan bulat l, mengingat daftar sbilangan bulat yang sudah digunakan.
    • xadalah bilangan bulat berikutnya untuk dilihat, yyang tersisa.
    • zadalah bilangan bulat yang dipilih untuk tempat berikutnya. Ini xjika xbukan merupakan elemen dari s, dan bilangan bulat positif pertama tidak dalam satau ytidak sebaliknya
    • (z:s)#ykemudian berulang dengan zditambahkan ke daftar integer yang digunakan.
    • n adalah daftar kosong, karena daftar kosong telah ditangani di baris sebelumnya.
  • Fungsi utama ([]#)mengambil daftar, dan memanggilnya #sebagai argumen kedua, dan daftar kosong untuk argumen pertama.
Ørjan Johansen
sumber
|z:_<-[x|...]...
nimi
4

APL (Dyalog 16.0), 34 byte

(s↑v~⍨⍳⌈/v+s←+/b←(⍳≢v)≠⍳⍨v)@{b}v←⎕
Adm
sumber
2
Pasti ada cara yang lebih baik.
Adám
3

Pyth , 21 20 byte

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

Suite uji

Saya akan menambahkan penjelasan ketika saya punya waktu.

Biarawati Bocor
sumber
3

C # , 135 byte


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

Tidak disatukan

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

Tidak terbaca dibaca

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

Kode lengkap

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

Rilis

  • v1.0 - 135 bytes- Solusi awal.

Catatan

  • Tidak ada
auhmaan
sumber
3

R , 39 46 byte

Membuat vektor dari input, lalu menggantikan nilai yang digandakan dengan rentang dari 1 hingga satu juta yang memiliki nilai input dihapus. Mengembalikan vektor numerik. Tidak ada input yang akan mengembalikan angka vektor kosong (0).

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

Cobalah online!

Ini akan memberikan peringatan tentang panjang vektor pengganti

                           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
sumber
3

C, 169 byte 133 byte

input = array a, output = array yang dimodifikasi 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;}}

diformat

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

Terlalu banyak byte yang terbuang untuk loop ini. Adakah yang berpikir untuk mempersingkat kode dengan menciptakan algoritma baru (yang menggunakan lebih sedikit loop)? Saya sedang berpikir tetapi belum menemukannya.

hucancode
sumber
2

C # 7, 116 byte

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

Bertakuk

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

Dijelaskan

  • kemunculan pertama nomor selalu dibiarkan apa adanya
  • kejadian berurutan dari angka yang diambil [1, 2, 3, ...], melewatkan nilai yang ada di input.

Versi Online

pengguna1655772
sumber
2

Clojure, 72 byte

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

Pengurangan dasar. Jika iterkandung dalam daftar output sejauh ini, kami akan mengambil elemen ke-2 (1 ketika 0-diindeks) dari daftar bilangan bulat tak terbatas (range)dari mana kami telah menghapus angka-angka yang telah digunakan. Rentang dimulai dari nol sehingga kami tidak dapat mengambil elemen pertama selain elemen kedua.

NikoNyrh
sumber
1

R, 74 byte

membaca daftar dari stdin; mengembalikan NULL untuk input kosong.

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

penjelasan:

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) dapat digunakan karena kami dijamin tidak akan pernah membutuhkan pengganti dari luar kisaran itu.

Cobalah online!

Giuseppe
sumber
0

Aksioma, 169 byte

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 dan hasilnya

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
sumber