Arreglo de unificación

24

Introducción

Considere dos matrices de la misma longitud, digamos A = [0,1,0,2]y B = [-1,1,2,2]. Supongamos que sabemos que sus contenidos son equivalentes en algún sentido, elemento por elemento:

  • 0es equivalente a -1,
  • 1es equivalente a 1,
  • 0es equivalente a 2y
  • 2es equivalente a 2.

La equivalencia es transitiva: -1y 0son equivalentes, y 0y 2son equivalentes, por lo que -1y 2también son equivalentes. La unificación de Ay Bes la matriz donde cada elemento de A(o B) ha sido reemplazado por el número más grande que es equivalente a él. En este caso, la unificación sería [2,1,2,2].

La tarea

Escriba un programa o función que tome dos matrices enteras no vacías de igual longitud y genere su unificación. También puede modificar una de las entradas en su lugar en lugar de volver. El conteo de bytes más bajo gana.

Casos de prueba

[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
fuente
3
No estoy muy seguro de por qué llamaste a esa operación unificación.
Fatalize
44
@Fatalize Me inspiré en la unificación de tipos .
Zgarb

Respuestas:

6

JavaScript (ES6), 100 90 110 102 96 bytes

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

Mi solución inicial fue de 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={}))

Aunque está pasando todos los casos de prueba proporcionados, falla por algo como:

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

Casos de prueba

Mostrar fragmento de código

Arnauld
fuente
Eso es mucho a.map...
ETHproductions
@ETHproductions Sí. Puede haber una mejor manera. Hecho levemente interesante: los dos primeros a.mapse pueden reemplazar por b.mapigual.
Arnauld
Agregué un nuevo caso de prueba para su situación.
Zgarb
5

CJam , 27 bytes

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

Pruébalo en línea! Banco de pruebas.

Explicación

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

Simultáneamente actualiza ambas listas reemplazando cada valor en la primera lista por el elemento correspondiente en la segunda lista si es mayor. El reemplazo se realiza con mapel getmétodo de un diccionario . Luego, intercambia las listas y se repite hasta que sean iguales.

xnor
fuente
2

Pyth, 13 bytes

eMumS{s@#dGGC

Pruébelo en línea: demostración

Explicación:

Comience con cada par. Extiende iterativamente cada par (lista) con listas superpuestas, deduplica los elementos y ordena. Pare una vez que este proceso converja. Imprime el máximo de cada lista.

Jakube
fuente
2

Php, 266 241 213 200 bytes

Solución:

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

Uso: u([1,2,3], [0,0,1]);devuelve la matriz deseada.

No tan golfizado:

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

Mathematica, 56 bytes

#/.($|##->Max@##&@@@ConnectedComponents@Thread[#<->#2])&
alephalpha
fuente
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);}}

El método f(int[]a,int[]b)resuelve el desafío.

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

}

Primero revise ambas matrices y realice un seguimiento de los números equivalentes. Luego modifique cada elemento en la primera matriz para tener los números equivalentes almacenados.

Jack munición
fuente
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)

Explicación

Haga una tabla de valores correspondiente a cada elemento único en ambas matrices ( ay ben este caso). Por ejemplo si

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

entonces la tabla sería:

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

luego aplique primero la búsqueda de profundidad, así, por ejemplo, suponga que elijo el elemento más a la izquierda en ael valor es entonces 0y 0tiene las equivalencias: 0y 2. Como 0ya ha sido visitado, vaya a 2. 2 tiene las equivalencias: 0. Entonces, el mejor resultado para elegir el elemento más a la izquierda aes 2. Aquí está el árbol:

   0   
 /   \
0     2
       \
        0

y quieres tomar el mayor valor allí, entonces el resultado es 2.

Bobas_Pett
fuente
Bienvenido a PPCG! En code-golf , su objetivo es obtener el bytecount más corto posible en su programa. Esto significa acortar nombres de funciones y variables y eliminar espacios en blanco innecesarios en su programa.
Kritixi Lithos
También debe tomar las dos matrices como entrada del usuario en lugar de codificarlas.
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];}

Función anónima que toma dos matrices.

Esta es mi opinión sobre 'modificar una de las matrices en su lugar', como se especifica en la salida del desafío. Esto recorre cada una de las dos matrices, registra la equivalencia si la actual es más grande que la almacenada, luego recorre la primera matriz y reemplaza todos los valores con sus equivalentes más grandes. El primer conjunto se toma por referencia (de ahí el &$a), por lo que el conjunto pasado se modifica 'en su lugar'.

Xanderhall
fuente
0

Java, 170 bytes

Golfed

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

Sin golf

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

Función anónima que toma dos int[]s como argumentos y devuelve un int[].

Xanderhall
fuente