# Array unification

## Introduction

Consider two arrays of the same length, say A = [0,1,0,2] and B = [-1,1,2,2]. Suppose we know that their contents are equivalent in some sense, item by item:

• 0 is equivalent to -1,
• 1 is equivalent to 1,
• 0 is equivalent to 2, and
• 2 is equivalent to 2.

Equivalence is transitive: -1 and 0 are equivalent, and 0 and 2 are equivalent, so -1 and 2 are also equivalent. The unification of A and B is the array where each item of A (or B) has been replaced by the largest number that's equivalent to it. In this case, the unification would be [2,1,2,2].

Write a program or function that takes two non-empty integer arrays of equal length, and outputs their unification. You can also modify one of the inputs in place instead of returning. The lowest byte count wins.

## Test cases

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

• I'm not quite sure why you called that operation unification. – Fatalize Nov 11 '16 at 9:09
• @Fatalize I got inspired by type unification. – Zgarb Nov 11 '16 at 9:14

## JavaScript (ES6), 10090110102 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={}))


My initial solution was 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={}))


Although it's passing all provided test cases, it fails for something such as:

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


### Test cases

let f =

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

console.log(JSON.stringify(f([0])([0]))); // -> [0]
console.log(JSON.stringify(f([1])([2]))); // -> [2]
console.log(JSON.stringify(f([0,1,0])([2,1,0]))); // -> [2,1,2]
console.log(JSON.stringify(f([1,2,3])([0,0,1]))); // -> [3,3,3]
console.log(JSON.stringify(f([0,1,0,2])([-1,1,2,2]))); // -> [2,1,2,2]
console.log(JSON.stringify(f([1,0,1,-4])([-3,-1,-2,2]))); // -> [1,0,1,2]
console.log(JSON.stringify(f([1,2,3,-2])([1,0,-3,-2]))); // -> [1,2,3,-2]
console.log(JSON.stringify(f([-3,-2,-1,0,1])([-1,-1,-1,-1,-1]))); // -> [1,1,1,1,1]
console.log(JSON.stringify(f([-3,-2,-1,0,1])([2,-1,0,1,-3]))); // -> [2,2,2,2,2]
console.log(JSON.stringify(f([-3,5,5,3,1])([4,2,3,1,2]))); // -> [4,5,5,5,5]
console.log(JSON.stringify(f([4,0,2,-5,0])([0,4,-5,3,5]))); // -> [5,5,3,3,5]
console.log(JSON.stringify(f([-2,4,-2,3,2,4,1,1])([-2,4,1,2,2,3,1,-2]))); // -> [1,4,1,4,4,4,1,1]
console.log(JSON.stringify(f([-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]
console.log(JSON.stringify(f([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]
console.log(JSON.stringify(f([0,-1])([-1,-1]))); // -> [0,0]

• That's a lot of a.map... – ETHproductions Nov 11 '16 at 15:31
• @ETHproductions Yup. There might be a better way. Mildly interesting fact: the first two a.map can be replaced with b.map just as well. – Arnauld Nov 11 '16 at 15:45
• I added a new test case for your situation. – Zgarb Nov 11 '16 at 18:19

## CJam, 27 bytes

l~_])\z_,*f{{_2$&,*|}/:e>}p  ### Explanation 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.


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


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


Simultaneously updates both lists by replacing each value in the first list by the corresponding element in the second list if it's greater. The replacement is done with map on a dictionary's get method. Then, swaps the lists, and repeats until they are equal.

# Pyth, 13 bytes

eMumS{s@#dGGC


Try it online: Demonstration

### Explanation:

Start with each pair. Iteratively extend each pair (list) with overlapping lists, deduplicate the elements and sort. Stop once this process converges. Print the maximum of each list.

## Php, 266241213 200 bytes

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);}  Usage: u([1,2,3], [0,0,1]); returns the desired array. Not-so golfed: 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);
}


# Dyalog APL, 29 28 bytes

⌈/¨({∪¨,/∘.{⍵/⍨≢⍺∩⍵}⍨⍵}⍣≡,¨)

Same idea as the Pyth solution.

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


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


Anonymous function that takes two int[]s as arguments and returns an int[].