You may remember sudoku, where there can only be one of each number in each row, column and block of nine. The general idea is that if the array contains but one element, you can submit that as a deterministic solution. If there are already filtered arrays (by rows, columns and 3×3 blocks) the remainder can still be deterministic. Where

  • a=[1,2];
  • b=[1,3];
  • c=[2,3];
  • d=[1,2,3,4]

d should be reduced to [4] as it apparently cannot be anything else.


Provide a sniplet that compares n arrays. For every X, if only X numbers appear at least once in a set of X arrays, then all those X numbers should be removed from each array not in the set. The elements are integer numbers ranging [1, n].

Winning criterion

Lowest character count.

"I'm too young to die" version

9 arrays at most, 9 elements at most.

Test Cases

[1,2]; [2,3]; [1,3]; [1,2,3,4]
[1,2,3]; [2,3,4]; [1,5,6]; [2,3]; [1,4]; [1,2,3,4,6]

Test outputs

[1,2]; [2,3]; [1,3]; [4]
[1,2,3]; [2,3,4]; [5]; [2,3]; [1,4]; [6]

  • \$\begingroup\$ "the numerosity of elements of 1 to n arrays' union equals to the numerosity of arrays". Does this mean that there are n arrays in the input, and their union is exactly [1,2,...,n]? Also, I don't really understand the challenge. What should the output be in your example? \$\endgroup\$
    – Zgarb
    Commented Feb 6, 2015 at 11:10
  • \$\begingroup\$ The output should be in the above case [1,2]; [1,3]; [2,3] and [4]. The numerosity of arrays is not necessarily the same as the numerosity of their union's elements, the array reduction is a more general operation. \$\endgroup\$ Commented Feb 6, 2015 at 11:18
  • \$\begingroup\$ What is this about ""I'm too young to die" version"? The formatting suggests that it's part of the winning criterion, but that makes no sense. I think you probably want cascading deductions, but the question doesn't mention them: it should (either to say that they're required or that they aren't). \$\endgroup\$ Commented Feb 6, 2015 at 11:24
  • \$\begingroup\$ It would also be helpful to state whether the elements of the arrays are always integers, and if so whether they always fall within a given range. That could allow some answers to save bytes. \$\endgroup\$ Commented Feb 6, 2015 at 11:26
  • \$\begingroup\$ The "I'm too young to die" version is for lazy bums who don't want to test what they've written. Larger set combinatorics are a nasty thing. Anyways, the tests (sorry for the edit) fall within the bottleneck of 9 elements, 9 sets. \$\endgroup\$ Commented Feb 6, 2015 at 11:29

2 Answers 2


Pyth: 37 29 28 bytes


Input is a list of lists like [[1,2], [2,3], [1,3], [1,2,3,4]]. Try it online: Pyth Compiler/Executor


u                          Q  G = input array
u                       tyQQ  For each H in powerset(input):
 m                     G        G = [            ...        for d in G]
  ?d               -dsH             [d if ... else d-sum(H) for d in G] 
     -lHl{sH                        len(H)-len(set(sum(H)))!=0
    |                                     or
            smg{kdH                 sum(d is subset of k for k in H)>0
  • \$\begingroup\$ I love this. Clear, concise. \$\endgroup\$ Commented Feb 9, 2015 at 10:58

C# - 231 characters

static int[][] P(int[][]a){var m=a.GetUpperBound(0)+1;var j=0;for(var i=0;i<m;i++){var u=new List<int>();for(j=0;j<=i;j++)u=u.Union(a[j]).ToList();if(u.Count()==m)for(j=0;j<m;j++)if(i!=j)a[i]=a[i].Except(a[j]).ToArray();}return a;}

Ungolfed and harness

using System.Collections.Generic;
using System.Linq;

namespace ArrayCombCompar
    class Program
        static void Main(string[] args)
            var testArray1 = new int[][] {
                new int[] {1,2},
                new int[] {2,3},
                new int[] {1,3},
                new int[] {1,2,3,4}
            var testArray2 = new int[][] {
                new int[] {1,2,3},
                new int[] {2,3,4},
                new int[] {1,5,6},
                new int[] {2,3},
                new int[] {1,4},
                new int[] {1,2,3,4,6}
            var result1 = P(testArray1);
            var result2 = P(testArray2);
        } // Put breakpoint here to see results

        static int[][] P(int[][]a)
            var m = a.GetUpperBound(0) + 1;
            var j = 0;
            for (var i = 0; i < m; i++)
                var u = new List<int>();
                for (j = 0; j <= i; j++)
                    u = u.Union(a[j]).ToList();
                if (u.Count() == m)
                    for (j = 0; j < m; j++)
                        if (i != j) a[i] = a[i].Except(a[j]).ToArray();
            return a;


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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