Array-Vereinigung

24

Einführung

Betrachten Sie zwei Arrays gleicher Länge, sagen wir A = [0,1,0,2]und B = [-1,1,2,2]. Angenommen, wir wissen, dass ihr Inhalt in gewisser Weise Artikel für Artikel gleichwertig ist:

  • 0ist äquivalent zu -1,
  • 1ist äquivalent zu 1,
  • 0ist äquivalent zu 2, und
  • 2ist äquivalent zu 2.

Äquivalenz ist transitiv: -1und 0sind äquivalent und 0und 2sind äquivalent, also -1und 2sind auch äquivalent. Die Vereinheitlichung von Aund Bist das Array, in dem jedes Element von A(oder B) durch die größte entsprechende Zahl ersetzt wurde. In diesem Fall wäre die Vereinigung [2,1,2,2].

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die zwei nicht leere Ganzzahl-Arrays gleicher Länge verwendet und deren Vereinheitlichung ausgibt. Sie können auch eine der vorhandenen Eingaben ändern, anstatt sie zurückzugeben. Die niedrigste Byteanzahl gewinnt.

Testfälle

[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
quelle
3
Ich bin mir nicht ganz sicher, warum Sie diese Operation Vereinheitlichung genannt haben.
Fatalize
4
@Fatalize ich habe inspiriert Typ Vereinigung .
Zgarb

Antworten:

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={}))

Meine ursprüngliche Lösung war 90 Bytes:

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={}))

Obwohl alle bereitgestellten Testfälle bestanden wurden, schlägt dies beispielsweise fehl:

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

Testfälle

Code-Snippet anzeigen

Arnauld
quelle
Das ist eine Menge a.map...
ETHproductions
@ETHproductions Yup. Es könnte einen besseren Weg geben. Etwas interessantes Faktum: Die ersten beiden a.mapkönnen b.mapgenauso gut ersetzt werden.
Arnauld
Ich habe einen neuen Testfall für Ihre Situation hinzugefügt.
Zgarb
5

CJam , 27 Bytes

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

Probieren Sie es online! Testsuite.

Erläuterung

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
quelle
4

Python 2, 91 Bytes

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
quelle
4

Python, 86 Bytes

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])

Aktualisiert beide Listen gleichzeitig, indem jeder Wert in der ersten Liste durch das entsprechende Element in der zweiten Liste ersetzt wird, falls es größer ist. Die Ersetzung erfolgt mapnach der getMethode eines Wörterbuchs . Vertauscht dann die Listen und wiederholt sie, bis sie gleich sind.

xnor
quelle
2

Pyth, 13 Bytes

eMumS{s@#dGGC

Probieren Sie es online aus: Demonstration

Erläuterung:

Beginnen Sie mit jedem Paar. Erweitern Sie jedes Paar (Liste) iterativ mit überlappenden Listen, deduplizieren Sie die Elemente und sortieren Sie sie. Stoppen Sie, sobald dieser Prozess konvergiert. Drucken Sie das Maximum jeder Liste.

Jakube
quelle
2

Telefon 266 241 213 200 Bytes

Lösung:

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

Verwendung: u([1,2,3], [0,0,1]);Gibt das gewünschte Array zurück.

Nicht so golfen:

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
quelle
1

Mathematica, 56 Bytes

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

Java, 273 263 Bytes

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

Die Methode f(int[]a,int[]b)löst die Herausforderung.

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

}

Gehen Sie zuerst beide Arrays durch und notieren Sie sich die entsprechenden Zahlen. Ändern Sie dann jedes Element im ersten Array, damit die entsprechenden Nummern gespeichert werden.

Jack Ammo
quelle
0

Python, 522 Bytes

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)

Erläuterung

Erstellen Sie eine Wertetabelle für jedes einzelne Element in beiden Arrays ( aund bin diesem Fall). Zum Beispiel wenn

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

dann wäre der Tisch:

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

Wenden Sie dann zuerst die Tiefensuche an. Nehmen Sie also beispielsweise an, dass ich das am weitesten links stehende Element in adem Wert auswähle, der dann ist 0und 0die Äquivalenzen hat: 0und 2. Da 0wurde schon besucht, gehe zu 2. 2 hat die Äquivalenzen: 0. Das beste Ergebnis für die Auswahl des Elements ganz links in aist 2. Hier ist der Baum:

   0   
 /   \
0     2
       \
        0

und Sie möchten den größten Wert dort nehmen, also ist das Ergebnis 2.

Bobas_Pett
quelle
Willkommen bei PPCG! Beim Code-Golf ist es Ihr Ziel, die kürzestmögliche Bytecount in Ihrem Programm zu erzielen. Dies bedeutet, dass Funktions- und Variablennamen gekürzt und unnötige Leerzeichen in Ihrem Programm entfernt werden.
Kritixi Lithos
Sie sollten die beiden Arrays auch als Benutzereingabe verwenden, anstatt sie fest zu codieren.
Zgarb
0

PHP, 132 Bytes

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

Anonyme Funktion, die zwei Arrays annimmt.

Dies ist meine Einstellung, wie in der Ausgabe der Challenge angegeben, "eines der Arrays an Ort und Stelle ändern". Dies durchläuft jedes der beiden Arrays, zeichnet die Äquivalenz auf, wenn die aktuelle größer als die gespeicherte ist, durchläuft dann das erste Array und ersetzt alle Werte durch ihre größten Äquivalente. Das erste Array wird als Referenz genommen (daher das &$a), so dass das übergebene Array "an Ort und Stelle" geändert wird.

Xanderhall
quelle
0

Java, 170 Bytes

Golf gespielt

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

Ungolfed

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

Anonyme Funktion, die zwei int[]s als Argumente verwendet und ein zurückgibt int[].

Xanderhall
quelle