7
\$\begingroup\$

The goal is to write a function or program which takes a set of integer arrays and returns a set of all possible arrays which meet the following criteria:

  • A valid array must contain at least one number from each of the input arrays.
  • A valid array cannot contain more than one number from a single input array.
  • A valid array cannot contain duplicate values.

Additional rules:

  • Order of the output does not matter.
  • Input/Output can be in any format you wish.
  • If no valid arrays exist, the result should be an empty array or blank string.

Examples:

input:
[[1,2],
 [2,1,0],
 [0,3,1]]

output:
[[2,3],
 [1]]
input:
[[1,3,4,7],
 [1,2,5,6],
 [3,4,8],
 [8,9]]

output:
[[6,7,8],
 [5,7,8],
 [2,7,8],
 [4,6,9],
 [4,5,9],
 [2,4,9],
 [3,6,9],
 [3,5,9],
 [2,3,9],
 [1,8]]
input:
[[1,2,3],
 [2,3,4],
 [1,4]]

output:
[]
\$\endgroup\$
  • \$\begingroup\$ Related: Helping the farmer \$\endgroup\$ – Peter Taylor Jun 23 '14 at 21:44
  • 1
    \$\begingroup\$ Some explanation of what do you mean with 'overlap array'? Or a link... \$\endgroup\$ – edc65 Jun 23 '14 at 23:31
  • \$\begingroup\$ @edc65 I've removed the term from the question to avoid confusion. They're just arrays. \$\endgroup\$ – nderscore Jun 24 '14 at 1:23
  • \$\begingroup\$ @edc65, it's exact set cover with some of the input implicit. So the input sets are the elements to cover, and for each element of their union there is a set consisting of those input sets which contain that element. \$\endgroup\$ – Peter Taylor Jun 24 '14 at 7:39
6
\$\begingroup\$

GolfScript, 36 characters

:I[[]]\{{{|$}+1$/}%|}/{I{1$&,(},!*},

Input/output is standard GolfScript arrays, see in this example.

:I              # save input to variable I

# part 1: generate all possible sets with zero or one numbers from each array
# (zero or one is one char shorter than exactly one which would work also)
[[]]\           # push the set with an empty set
{               # iterate over all input sets
  {             #   iterate over the numbers in the current set
    {|$}+1$/    #     add this number to any set in the result
  }%
  |             #   join with the result set
}/

# part 2: filter for valid sets (i.e. exactly one number from each array)
{               # start of filter block
  I{            #   filter the input array of sets
    1$&         #     calculate overlap of the current set with the input set
    ,(          #     remove if length is equal to one
  },
  !             #   is the list empty? (i.e. all input matched the filter criterion)
  *             #   get rid of the second item on the stack
},              # end of filter block
\$\endgroup\$
5
\$\begingroup\$

CJam, 35 bytes

q~:Q{m*{(+$_&}%}*_&{Q{1$&,(},,*!},p

Input is a list of list like:

[[1 3 4 7] 
 [1 2 5 6] 
 [3 4 8] 
 [8 9]]

and output is the list of unique lists that match all conditions, like for above input,

[[1 8] [2 3 9] [3 5 9] [3 6 9] [2 4 9] [4 5 9] [4 6 9] [2 7 8] [5 7 8] [6 7 8]]

How it works:

q~:Q                                 "Evaluate the input and store it in Q";
    {          }*                    "Run this block for each adjacent pair in the array";
     m*                              "Calculate Cartesian product of the pair";
       {     }%                      "Map each cartesian product with the code block";
        (+$                          "Flatten the array and sort it";
           _&                        "Make the array unique";
                 _&                  "Only take unique cartesian products";
                   {            },   "Filter the cartesian products based on the code block";
                    Q{     },        "Put Q on stack and run it through this filter";
                      1$&            "Take ∩ of the input array with the cartesian product";
                         ,(          "Check that length of the ∩ should be greater than 1";
                             ,*!     "Now we have all the lists from the input list of list"
                                     "which matched more than 1 element from this cartesian"
                                     "product. So if this list is non empty, discard this"
                                     "cartesian product";
                                  p  "Print the filtered out valid unique arrays";

Try it online here

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 135 84 72 bytes

f=Cases[Union/@Tuples@#,l_/;!MemberQ[#,k_/;Length@Intersection[k,l]>1]]&

Less golf:

f = Cases[
   Union /@ Tuples@#,
   l_ /; ! MemberQ[#, k_ /; Length@Intersection[k, l] > 1]
] &

This defines a function f that expects the input as a plain Mathematica list of lists, e.g.

f[{{1, 2}, {2, 1, 0}, {0, 3, 1}}]

Basically, I'm creating a list of all lists that fulfil conditions 1 and 3, and then I'm filtering out those that violate conditions 2. There might be a shortcut for one of the two, which I'll have to think about in more depth tomorrow. Found that shortcut!

\$\endgroup\$
2
\$\begingroup\$

ruby, 143 114

Now shorter thanks to @Ventero.

h={};i=eval$*[0];v=i.flatten.uniq
loop{h[a=v.sample(1+rand(v.size)).sort]||=h[a]||i.any?{|o|(o&a).size!=1}?1:p(a)}

Usage:

ruby uniq_arr.rb '[[1,3,4,7],[1,2,5,6],[3,4,8],[8,9]]'
[2, 3, 9]
[6, 7, 8]
[3, 5, 9]
[1, 8]
[2, 7, 8]
[4, 6, 9]
[5, 7, 8]
[2, 4, 9]
[3, 6, 9]
[4, 5, 9]

Making it stop (eventually) is easy, but requires some code. It stops one h contains 2**l-1 elements, l being the number of unique elements in i, i.flatten.uniq.size

http://ideone.com/zTlXZw

\$\endgroup\$
  • \$\begingroup\$ Some general improvements: $* is short for ARGV and allows dropping the whitespace after eval, loop{...} is a shorter infinite loop, rand is the same as Random.rand and p is a shorter way than $_ to get nil (the function does nothing and returns nil if called without arguments). Also, I think your reduce can be replaced with i.any?{|o|(o&a).size!=1}. \$\endgroup\$ – Ventero Jun 24 '14 at 8:14
2
\$\begingroup\$

Ruby — 80 73 characters

@Howard knocks off 7 characters:

f=->a{a[0].product(*a).map(&:uniq).uniq.select{|l|a.all?{|x|(l&x).one?}}}

Some sample input:

a = [[1, 2], [2, 1, 0], [0, 3, 1]]
b = [[1,3,4,7], [1,2,5,6], [3,4,8], [8,9]]
c = [[1,2,3], [2,3,4], [1,4]]
d = [[]]
e = [[1,2]]

Output:

f[a] # => [[1], [2, 3]]
f[b] # => [[1, 8], [3, 2, 9], [3, 5, 9], [3, 6, 9], [4, 2, 9], [4, 5, 9], [4, 6, 9], [7, 2, 8], [7, 5, 8], [7, 6, 8]]
f[c] # => []
f[d] # => []
f[e] # => [[1], [2]]

Haskell — 90 characters

I'm just learning Haskell, so I imagine this can be vastly improved. Same basic strategy as my Ruby solution.

import Data.List
f a=[l|l<-nub.map nub$sequence a,all(\x->length x==1)(map(intersect l)a)]
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can also use the shorter version .product(*a) since the invalid solutions are filtered afterwards anyways. \$\endgroup\$ – Howard Jun 25 '14 at 12:34
1
\$\begingroup\$

Python, 157 characters

This is a straightforward brute-force implementation.

from itertools import*
a=input()
v=set(chain(*a))
print[x for x in chain(*[combinations(v,r)for r in range(len(v))])if all(1==len(set(x)&set(y))for y in 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.