24
\$\begingroup\$

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

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]
\$\endgroup\$
  • 3
    \$\begingroup\$ I'm not quite sure why you called that operation unification. \$\endgroup\$ – Fatalize Nov 11 '16 at 9:09
  • 4
    \$\begingroup\$ @Fatalize I got inspired by type unification. \$\endgroup\$ – Zgarb Nov 11 '16 at 9:14

12 Answers 12

6
\$\begingroup\$

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]

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That's a lot of a.map... \$\endgroup\$ – ETHproductions Nov 11 '16 at 15:31
  • \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Nov 11 '16 at 15:45
  • \$\begingroup\$ I added a new test case for your situation. \$\endgroup\$ – Zgarb Nov 11 '16 at 18:19
5
\$\begingroup\$

CJam, 27 bytes

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

Try it online! Test suite.

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.
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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);
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Dyalog APL, 29 28 bytes

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

Same idea as the Pyth solution.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 56 bytes

#/.($|##->Max@##&@@@ConnectedComponents@Thread[#<->#2])&
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\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 Nov 12 '16 at 13:29
  • \$\begingroup\$ You should also take the two arrays as user input instead of hard-coding them. \$\endgroup\$ – Zgarb Nov 12 '16 at 14:45
0
\$\begingroup\$

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'.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.