Array unifikasi

24

pengantar

Pertimbangkan dua array dengan panjang yang sama, katakan A = [0,1,0,2]dan B = [-1,1,2,2]. Misalkan kita tahu bahwa isinya setara dalam beberapa hal, item demi item:

  • 0setara dengan -1,
  • 1setara dengan 1,
  • 0setara dengan 2, dan
  • 2setara dengan 2.

Kesetaraan adalah transitif: -1dan 0setara, dan 0dan 2setara, demikian -1dan 2juga setara. The penyatuan dari Adan Badalah array di mana setiap item dari A(atau B) telah diganti dengan jumlah terbesar yang setara dengan itu. Dalam hal ini, penyatuan akan terjadi [2,1,2,2].

Tugas

Tulis program atau fungsi yang membutuhkan dua array integer non-kosong dengan panjang yang sama, dan output unifikasi mereka. Anda juga dapat memodifikasi salah satu input yang ada alih-alih mengembalikan. Hitungan byte terendah menang.

Uji kasus

[0] [0] -> [0]
[1] [2] -> [2]
[0,-1] [-1,-1] -> [0,0]
[0,1,0] [2,1,0] -> [2,1,2]
[1,2,3] [0,0,1] -> [3,3,3]
[0,1,0,2] [-1,1,2,2] -> [2,1,2,2]
[1,0,1,-4] [-3,-1,-2,2] -> [1,0,1,2]
[1,2,3,-2] [1,0,-3,-2] -> [1,2,3,-2]
[-3,-2,-1,0,1] [-1,-1,-1,-1,-1] -> [1,1,1,1,1]
[-3,-2,-1,0,1] [2,-1,0,1,-3] -> [2,2,2,2,2]
[-3,5,5,3,1] [4,2,3,1,2] -> [4,5,5,5,5]
[4,0,2,-5,0] [0,4,-5,3,5] -> [5,5,3,3,5]
[-2,4,-2,3,2,4,1,1] [-2,4,1,2,2,3,1,-2] -> [1,4,1,4,4,4,1,1]
[-10,-20,-11,12,-18,14,-8,-1,-14,15,-17,18,18,-6,3,1,15,-15,-19,-19] [-13,6,-4,3,19,1,-10,-15,-15,11,6,9,-11,18,6,6,-5,-15,7,-11] -> [-8,14,18,14,19,14,-8,-1,-1,15,14,18,18,18,14,14,15,-1,18,18]
[20,15,2,4,-10,-4,-19,15,-5,2,13,-3,-18,-5,-6,0,3,-6,3,-17] [-18,7,6,19,-8,-4,-16,-1,13,-18,8,8,-16,17,-9,14,-2,-12,7,6] -> [20,15,20,19,-8,-4,20,15,17,20,17,17,20,17,-6,14,15,-6,15,20]
code-golf array-manipulation Zgarb
sumber
3
Saya tidak yakin mengapa Anda menyebut unifikasi operasi.
Fatalkan
4
@Fatalize Saya terinspirasi oleh tipe unifikasi .
Zgarb

Jawaban:

6

JavaScript (ES6), 100 90 110 102 96 byte

a=>b=>a.map(v=>t[v],a.map((_,k)=>a.map((x,i)=>t[x]=t[y=b[i]]=Math.max(k?t[x]:x,k?t[y]:y)),t={}))

Solusi awal saya adalah 90 byte:

a=>b=>a.map(v=>t[v],a.map(_=>a.map((x,i)=>t[x]=t[y=b[i]]=Math.max(t[x]||x,t[y]||y)),t={}))

Meskipun melewati semua kasus uji yang disediakan, gagal untuk sesuatu seperti:

A = [0, -1], B = [-1, -1]

Uji kasus

Tampilkan cuplikan kode

Arnauld
sumber
Itu banyak a.map...
ETHproduksi
@ EHProduk Yup. Mungkin ada cara yang lebih baik. Fakta yang agak menarik: dua yang pertama a.mapbisa diganti b.mapjuga.
Arnauld
Saya menambahkan test case baru untuk situasi Anda.
Zgarb
5

CJam , 27 byte

l~_])\z_,*f{{_2$&,*|}/:e>}p

Cobalah online! Suite uji.

Penjelasan

l~       e# Read and evaluate input, dumping arrays A and B on the stack.
_        e# Copy B.
])\      e# Wrap in array, pull off B, swap. Gives B [A B] on the stack.
z        e# Transpose the [A B] matrix to get a list of all equivalent pairs.
_,*      e# Repeat this list by the number of pairs. This is to ensure that the
         e# following procedure is applied often enough to allow transitive
         e# equivalences to propagate.
f{       e# Map this block over B, passing in the list of pairs each time...
  {      e#   For each pair...
    _2$  e#     Copy both the pair and the current value/list.
    &,   e#     Get the length of their intersection. If this is non-zero,
         e#     the current pair belongs to the current equivalence class.
    *    e#     Repeat the pair that many times.
    |    e#     Set union between the current value/list and the repeated pair.
         e#     This adds the pair to the current list iff that list already
         e#     contains one value from the pair.
  }/
  :e>    e#   Get the maximum value of this equivalence class.
}
p        e# Pretty print.
Martin Ender
sumber
4

Python 2, 91 byte

f=lambda a,b:[a<x>b.update(b&set(x)and x)and b or max(f(zip(a,b)*len(a),{x})[0])for x in a]
Mitch Schwartz
sumber
4

Python, 86 byte

f=lambda a,b:a*(a==b)or f(*[map({x:y for x,y in zip(a,b)if x<y}.get,x,x)for x in b,a])

Secara bersamaan memperbarui kedua daftar dengan mengganti setiap nilai di daftar pertama dengan elemen yang sesuai di daftar kedua jika lebih besar. Penggantian dilakukan dengan metode mapkamusget . Kemudian, swap daftar, dan ulangi sampai mereka sama.

Tidak
sumber
2

Pyth, 13 byte

eMumS{s@#dGGC

Cobalah online: Demonstrasi

Penjelasan:

Mulailah dengan masing-masing pasangan. Memperpanjang setiap pasangan (daftar) secara bergantian dengan daftar yang tumpang tindih, menduplikasi elemen dan mengurutkan. Hentikan begitu proses ini bertemu. Cetak maksimum setiap daftar.

Jakube
sumber
2

Php, 266 241 213 200 byte

Larutan:

function u($x,$y){foreach($x as$i=>$j){$k[$y[$i]][]=$j;$k[$j][]=$y[$i];}$h=function($c,&$w)use($k,&$h){$w[]=$c;foreach($k[$c]as$u)!in_array($u,$w)&&$h($u,$w);return max($w);};return array_map($h,$x);}

Penggunaan: u([1,2,3], [0,0,1]);mengembalikan array yang diinginkan.

Tidak bermain golf:

function unify($x, $y)
{
    foreach($x as $i=>$j) {
        $k[$y[$i]][] = $j;
        $k[$j][] = $y[$i];
    }

    $h = function ($c, &$w=[]) use ($k, &$h) {
        $w[] = $c;
        foreach($k[$c] as $u)
            !in_array($u, $w) && $h($u, $w);
        return max($w);
    };

    return array_map($h, $x);
}
Progrock
sumber
1

Mathematica, 56 byte

#/.($|##->Max@##&@@@ConnectedComponents@Thread[#<->#2])&
alephalpha
sumber
0

Java, 273 263 byte

interface Z{int z(int x);default Z g(int m,int n){return x->{for(int t;x!=(t=x==m?z(n):z(x));)x=t;return x;};}static void f(int[]a,int[]b){Z y=x->x;int i=0,v;for(int u:a){u=y.z(u);v=y.z(b[i++]);if(u<v)y=y.g(u,v);if(v<u)y=y.g(v,u);}i=0;for(int u:a)a[i++]=y.z(u);}}

Metode ini f(int[]a,int[]b)memecahkan tantangan.

interface Z{

  //should return an "equivalent" integer
  int z(int x);

  //return a Z lambda where the 1st arg is "equivalent" to the 2nd arg
  default Z g(int m,int n){
    return x->{
      for(int t;x!=(t=x==m?z(n):z(x));) //always find the last equivalent number for x
        x=t;
      return x;
    };
  }

  //solve the challenge
  static void f(int[]a,int[]b){
    Z y=x->x; //start off with all numbers only equivalent only to themselves
    int i=0,v;
    for(int u:a){
      u=y.z(u); //get a's element's equivalent number
      v=y.z(b[i++]); //get b's element's equivalent number
      if(u<v)y=y.g(u,v); //if a's was smaller than b's, make a's equivalent to b's
      if(v<u)y=y.g(v,u); //if b's was smaller than a's, make b's equivalent to a's
    }
    i=0;
    for(int u:a) //overwrite a with each element's equivalent value
      a[i++]=y.z(u);
  }

}

Pertama melalui kedua array dan melacak angka-angka yang setara. Kemudian, modifikasi setiap elemen dalam array pertama untuk menyimpan angka-angka yang setara.

Jack Ammo
sumber
0

Python, 522 byte

a = [-2,4,-2,3,2,4,1,1]
b = [-2,4,1,2,2,3,1,-2]
m = {}
visited = {}
for i in range(len(a)):
    if a[i] in m:
        if b[i] not in m[a[i]]:
            m[a[i]].append(b[i])
    else:
        l = []
        l.append(b[i])
        m[a[i]] = l
    if b[i] in m:
        if a[i] not in m[b[i]]:
            m[b[i]].append(a[i])
    else:
        l = []
        l.append(a[i])
        m[b[i]] = l

def dfs(v, maximum):
    if v > maximum:
        maximum = v
    visited[v] = True
    for n in m[v]:
        if not visited[n]:
            d = dfs(n, maximum)
            if d > v:
                maximum = d
    return maximum

result = []
for k in range(len(a)):
    for q in m:
        visited[q] = False
    result.append(max(dfs(a[k], a[k]), dfs(b[k], b[k])))

print(result)

Penjelasan

Buat tabel nilai yang sesuai dengan setiap elemen unik di dalam kedua array ( adan bdalam hal ini). Misalnya jika

a = [0,1,0] 
b = [2,1,0]

maka tabelnya adalah:

0:[0,2]
1:[1]
2:[0]

kemudian menerapkan pencarian kedalaman pertama, jadi, misalnya, anggap saya memilih elemen paling kiri dalam anilai kemudian 0dan 0memiliki kesetaraan: 0dan 2. Karena 0sudah dikunjungi, buka 2. 2 memiliki ekuivalensi: 0. Jadi hasil terbaik untuk memilih elemen paling kiri aadalah 2. Ini pohonnya:

   0   
 /   \
0     2
       \
        0

dan Anda ingin mengambil nilai terbesar di sana, jadi hasilnya 2.

Bobas_Pett
sumber
Selamat datang di PPCG! Dalam kode-golf , Anda bertujuan untuk mendapatkan bytecount sesingkat mungkin dalam program Anda. Ini berarti memperpendek fungsi dan nama variabel dan menghapus spasi yang tidak perlu dalam program Anda.
Kritixi Lithos
Anda juga harus menggunakan dua array sebagai input pengguna alih-alih mengkodekannya.
Zgarb
0

PHP, 132 byte

function(&$a,$b){for(;$i<count($a);$i++){$r=$a[$i];$s=$b[$i];$r<$c[$s]?:$c[$s]=$r;$s<$c[$r]?:$c[$r]=$s;}foreach($a as&$v)$v=$c[$v];}

Fungsi anonim yang mengambil dua array.

Ini adalah pendapat saya tentang 'modifikasi salah satu array di tempat', sebagaimana ditentukan dalam output dari tantangan. Ini loop melalui masing-masing dari dua array, mencatat kesetaraan jika yang sekarang lebih besar dari yang disimpan, kemudian loop melalui array pertama dan mengganti semua nilai dengan setara terbesar mereka. Array pertama diambil dengan referensi (maka itu &$a), sehingga array yang lewat diubah 'di tempat'.

Xanderhall
sumber
0

Java, 170 byte

Golf

(a,b)->{int[]d=a.clone();for(int i=0,y;i<d.length;i++){y=0;for(int j=0;j<a.length;j++)if(a[j]==d[i]||b[j]==d[i])y=Integer.max(y,Integer.max(a[j],b[j]));d[i]=y;}return d;}

Tidak disatukan

(a, b) -> {                                        // Two argument lambda
    int[] d = a.clone();                           // We clone our first array for modification
    for (int i = 0,y; i < d.length; i++) {         // Going through the elements of d...
        y = 0;                                     // We initialize our 'highest' equivalent
        for (int j = 0; j < a.length; j++) {       // Going through each of our arrays (a and b)...
            if (a[j] == d[i] || b[j] == d[i]) {    // If either of them is the number we're trying to match for equivalence...
                y = Integer.max(y, Integer.max(a[j], b[j])); // We see if the new number is bigger than the largest we've found.
            }
        }
        d[i] = y;                                  // We then assign the largest equivalent number for the current position in our output array.
    }
    return d; // And return!
}

Fungsi anonim yang mengambil dua int[]s sebagai argumen dan mengembalikan sebuah int[].

Xanderhall
sumber