Array unification

Question

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]

I'm not quite sure why you called that operation unification. — Fatalize, Commented Nov 11, 2016 at 9:09

Arnauld · Accepted Answer · 2016-11-11 15:53:25Z

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]

@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, Commented Nov 11, 2016 at 15:45

Martin Ender · Accepted Answer · 2016-11-11 08:31:50Z

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.

Mitch Schwartz · Accepted Answer · 2016-11-12 07:12:54Z

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]

edited Nov 12, 2016 at 7:12

answered Nov 11, 2016 at 15:59

Mitch Schwartz

5,8891 gold badge27 silver badges26 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:12Z

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

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.

edited Apr 13, 2017 at 12:39

CommunityBot

1

answered Nov 12, 2016 at 8:32

xnor

147k26 gold badges279 silver badges652 bronze badges

Add a comment |

Jakube · Accepted Answer · 2016-11-12 09:12:17Z

2

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.

answered Nov 12, 2016 at 9:12

Jakube

21.9k3 gold badges27 silver badges108 bronze badges

Add a comment |

Progrock · Accepted Answer · 2016-11-12 11:54:49Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Dyalog APL, 29 28 bytes

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

Same idea as the Pyth solution.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 12, 2016 at 12:12

ngn

15.3k2 gold badges43 silver badges87 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2016-11-12 10:40:41Z

1

Mathematica, 56 bytes

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

answered Nov 12, 2016 at 10:40

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Jack Ammo · Accepted Answer · 2016-11-14 04:08:41Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

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:

and you want to take the largest value in there, so the result is 2.

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. — user41805, Commented Nov 12, 2016 at 13:29
You should also take the two arrays as user input instead of hard-coding them. — Zgarb, Commented Nov 12, 2016 at 14:45

Xanderhall · Accepted Answer · 2016-12-19 16:55:47Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Stack Exchange Network

Array unification

Introduction

The task

Test cases

12 Answers 12

JavaScript (ES6), 100 90 110 102 96 bytes

Test cases

CJam, 27 bytes

Explanation

Python 2, 91 bytes

Python, 86 bytes

Pyth, 13 bytes

Explanation:

Php, 266 241 213 200 bytes

Dyalog APL, 29 28 bytes

Mathematica, 56 bytes

Java, 273 263 bytes

Python, 522 bytes

PHP, 132 bytes

Java, 170 bytes

Golfed

Ungolfed

Your Answer

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

Linked

Hot Network Questions

Array unification

Introduction

The task

Test cases

12 Answers 12

JavaScript (ES6), 100 90 110 102 96 bytes

Test cases

CJam, 27 bytes

Explanation

Python 2, 91 bytes

Python, 86 bytes

Pyth, 13 bytes

Explanation:

Php, 266 241 213 200 bytes

Dyalog APL, 29 28 bytes

Mathematica, 56 bytes

Java, 273 263 bytes

Python, 522 bytes

PHP, 132 bytes

Java, 170 bytes

Golfed

Ungolfed

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

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