Unification des baies

24

introduction

Considérez deux tableaux de même longueur, disons A = [0,1,0,2]et B = [-1,1,2,2]. Supposons que nous sachions que leur contenu est équivalent dans un certain sens, article par article:

  • 0est équivalent à -1,
  • 1est équivalent à 1,
  • 0est équivalent à 2, et
  • 2est équivalent à 2.

L'équivalence est transitive: -1et 0sont équivalentes, et 0et 2sont équivalentes, donc -1et 2sont également équivalentes. L' unification de Aet Best le tableau où chaque élément de A(ou B) a été remplacé par le plus grand nombre qui lui est équivalent. Dans ce cas, l'unification serait [2,1,2,2].

La tâche

Écrivez un programme ou une fonction qui prend deux tableaux entiers non vides de longueur égale et génère leur unification. Vous pouvez également modifier l'une des entrées en place au lieu de revenir. Le nombre d'octets le plus bas gagne.

Cas de test

[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
la source
3
Je ne sais pas trop pourquoi vous avez appelé cette opération unification.
Fatalize
4
@Fatalize Je me suis inspiré de l' unification des types .
Zgarb

Réponses:

6

JavaScript (ES6), 100 90 110 102 96 octets

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

Ma solution initiale était de 90 octets:

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

Bien qu'il passe tous les cas de test fournis, il échoue pour quelque chose comme:

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

Cas de test

Afficher l'extrait de code

Arnauld
la source
Ça fait beaucoup de a.map...
ETHproductions
@ETHproductions Yup. Il pourrait y avoir une meilleure façon. Fait légèrement intéressant: les deux premiers a.mappeuvent également être remplacés par b.map.
Arnauld
J'ai ajouté un nouveau cas de test pour votre situation.
Zgarb
5

CJam , 27 octets

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

Essayez-le en ligne! Suite de tests.

Explication

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
la source
4

Python 2, 91 octets

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
la source
4

Python, 86 octets

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

Met à jour simultanément les deux listes en remplaçant chaque valeur de la première liste par l'élément correspondant dans la deuxième liste s'il est supérieur. Le remplacement se fait avec mapla getméthode d' un dictionnaire . Ensuite, échange les listes et répète jusqu'à ce qu'elles soient égales.

xnor
la source
2

Pyth, 13 octets

eMumS{s@#dGGC

Essayez-le en ligne: Démonstration

Explication:

Commencez avec chaque paire. Étendez itérativement chaque paire (liste) avec des listes qui se chevauchent, dédupliquez les éléments et triez. Arrêtez une fois que ce processus converge. Imprimez le maximum de chaque liste.

Jakube
la source
2

Php, 266 241 213 200 octets

Solution:

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

Utilisation: u([1,2,3], [0,0,1]);retourne le tableau souhaité.

Pas si 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
la source
1

Mathematica, 56 octets

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

Java, 273 263 octets

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

La méthode f(int[]a,int[]b)résout le défi.

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

}

Parcourez d'abord les deux tableaux et gardez une trace des nombres équivalents. Modifiez ensuite chaque élément du premier tableau pour stocker les nombres équivalents.

Jack Ammo
la source
0

Python, 522 octets

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)

Explication

Créez un tableau de valeurs correspondant à chaque élément unique dans les deux tableaux ( aet bdans ce cas). Par exemple si

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

alors le tableau serait:

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

puis appliquer la recherche en profondeur en premier, donc, par exemple, supposons que je prenne l'élément le plus à gauche dans ala valeur est alors 0et 0a les équivalences: 0et 2. Depuis 0a déjà été visité, allez à 2. 2 a les équivalences: 0. Le meilleur résultat pour choisir l'élément le plus à gauche aest donc 2. Voici l'arbre:

   0   
 /   \
0     2
       \
        0

et vous voulez y prendre la plus grande valeur, donc le résultat est 2.

Bobas_Pett
la source
Bienvenue chez PPCG! En code-golf , vous visez à obtenir le bytecount le plus court possible dans votre programme. Cela signifie raccourcir les noms de fonction et de variable et supprimer les espaces inutiles dans votre programme.
Kritixi Lithos du
Vous devez également prendre les deux tableaux comme entrée utilisateur au lieu de les coder en dur.
Zgarb
0

PHP, 132 octets

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

Fonction anonyme qui prend deux tableaux.

C'est mon point de vue sur «modifier l'un des tableaux en place», comme spécifié dans la sortie du défi. Cela parcourt chacun des deux tableaux, enregistre l'équivalence si le courant est plus grand que celui stocké, puis parcourt le premier tableau et remplace toutes les valeurs par leurs plus grands équivalents. Le premier tableau est pris par référence (d'où le &$a), donc le tableau transmis est modifié «sur place».

Xanderhall
la source
0

Java, 170 octets

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

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

Fonction anonyme qui prend deux int[]s comme arguments et retourne un int[].

Xanderhall
la source