3
\$\begingroup\$

Introduction

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.

Challenge

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]

\$\endgroup\$
  • \$\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 Feb 6 '15 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\$ – user3819867 Feb 6 '15 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\$ – Peter Taylor Feb 6 '15 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\$ – Peter Taylor Feb 6 '15 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\$ – user3819867 Feb 6 '15 at 11:29
2
\$\begingroup\$

Pyth: 37 29 28 bytes

um?d|-lHl{sHsmg{kdH-dsHGtyQQ

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

Explanation:

um?d|-lHl{sHsmg{kdH-dsHGtyQQ
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
\$\endgroup\$
  • \$\begingroup\$ I love this. Clear, concise. \$\endgroup\$ – user3819867 Feb 9 '15 at 10:58
0
\$\begingroup\$

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

     }
}
\$\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.