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:
0is equivalent to-1,1is equivalent to1,0is equivalent to2, and2is equivalent to2.
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].
The task
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]
-
3\$\begingroup\$ I'm not quite sure why you called that operation unification. \$\endgroup\$Fatalize– Fatalize2016年11月11日 09:09:13 +00:00Commented Nov 11, 2016 at 9:09
-
4\$\begingroup\$ @Fatalize I got inspired by type unification. \$\endgroup\$Zgarb– Zgarb2016年11月11日 09:14:34 +00:00Commented Nov 11, 2016 at 9:14
12 Answers 12
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={}))
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]-
\$\begingroup\$ That's a lot of
a.map... \$\endgroup\$ETHproductions– ETHproductions2016年11月11日 15:31:00 +00:00Commented Nov 11, 2016 at 15:31 -
\$\begingroup\$ @ETHproductions Yup. There might be a better way. Mildly interesting fact: the first two
a.mapcan be replaced withb.mapjust as well. \$\endgroup\$Arnauld– Arnauld2016年11月11日 15:45:43 +00:00Commented Nov 11, 2016 at 15:45 -
\$\begingroup\$ I added a new test case for your situation. \$\endgroup\$Zgarb– Zgarb2016年11月11日 18:19:43 +00:00Commented Nov 11, 2016 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, (削除) 266 (削除ここまで) (削除) 241 (削除ここまで) (削除) 213 (削除ここまで) 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.
Mathematica, 56 bytes
#/.($|##->Max@##&@@@ConnectedComponents@Thread[#<->#2])&
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);}}
The method f(int[]a,int[]b) solves the challenge.
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);
}
}
First go through both arrays and keep track of equivalent numbers. Then modify every element in the first array to have the equivalent numbers stored.
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)
Explanation
Make a table of values corresponding to each unique element in in both arrays (a and b in this case). For example if
a = [0,1,0]
b = [2,1,0]
then the table would be:
0:[0,2]
1:[1]
2:[0]
then apply depth first search, so, for example, assume I pick the leftmost element in a the value is then 0 and 0 has the equivalences: 0 and 2. Since 0 has already been visited, go to 2. 2 has the equivalences: 0. So the best result for choosing the leftmost element in a is 2.
Here's the tree:
0
/ \
0 2
\
0
and you want to take the largest value in there, so the result is 2.
-
\$\begingroup\$ Welcome to PPCG! In code-golf, you aim to get the shortest bytecount possible in your program. This means shortening function and variable names and removing unnecessary whitespace in your program. \$\endgroup\$user41805– user418052016年11月12日 13:29:44 +00:00Commented Nov 12, 2016 at 13:29
-
\$\begingroup\$ You should also take the two arrays as user input instead of hard-coding them. \$\endgroup\$Zgarb– Zgarb2016年11月12日 14:45:27 +00:00Commented Nov 12, 2016 at 14:45
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];}
Anonymous function that takes two arrays.
This is my take on 'modify one of the arrays in place', as specified in the output of the challenge. This loops through each of the two arrays, records the equivalence if the current one is bigger than the one stored, then loops through the first array and replaces all the values with their largest equivalents. The first array is taken by reference (hence the &$a), so the array passed in is modified 'in place'.
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[].