16
\$\begingroup\$

Your input is a non-empty set of non-empty sets of positive integers. For example:

{{1}, {2, 3}, {2,4}, {1,4}}

Your task is to output the maximal number of elements that can be picked from the sets with the following conditions:

  • You can only pick at most 1 element from a set
  • You can't pick the same element from 2 different sets

In this example you can pick 1 from the first set, 3 from the second set, 2 from the third set and 4 from the last set, for a total of 4 elements.

Io is flexible. You can take a list, instead of sets, etc.

There are no gaps in the numbers (eg. {{2,3},{3,4}} is not a valid input). Or in other words, the input flattened must contain all numbers [1,n] where n is the largest number in the input.

This is , so shortest code wins.

Examples

{{1}}
-> 1

{{1}, {2, 3}, {2,4}, {1,4}}
-> 4

{{1}, {2}, {1,2,3,4}}
-> 3

{{1}, {2}, {2,3}}
-> 3

{{1, 2, 3}, {2, 4, 5, 6}, {3, 5, 6, 7}, {1, 2}, {2, 3}, {1, 3}}
-> 5

{{1,2,3,4,5}, {1,2}, {2,3}, {1,3}}
-> 4

{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{5,6,7,8,9,10}}
-> 5

{{1,4}, {2,3}, {1,3}, {1,2,3}}
-> 4

Background

Recently @AnishSharma posted this question on Stack Overflow. This is a slightly modified version of that question

\$\endgroup\$
3
  • \$\begingroup\$ Is it acceptable to output a selection of the maximum number instead of the number? \$\endgroup\$
    – Wheat Wizard
    Jan 23 at 12:38
  • \$\begingroup\$ Do you mean like a set of picks? If so, the answer is no, just output the length of that set. \$\endgroup\$
    – AnttiP
    Jan 23 at 12:41
  • \$\begingroup\$ Is "3 from the second set, 2 from the second set" a typo for "3 from the second set, 2 from the third set"? \$\endgroup\$
    – aschepler
    Jan 24 at 0:21

12 Answers 12

7
\$\begingroup\$

Python 3, 66 bytes

lambda x:max(map(len,map(set,product(*x))))
from itertools import*

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Jelly, 6 bytes

ŒpQ€ẈṀ

Try It Online!

ŒpQ€ẈṀ    Main Link
Œp        Cartesian Product; get all possible selections
  Q€      Uniquify each
    Ẉ     Length of each
     Ṁ    Maximum result
\$\endgroup\$
5
\$\begingroup\$

Python 3, 63 bytes

f=lambda s,*v:s and max(f(s[1:],x,*v)for x in s[0])or len({*v})

Try it online!

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

JavaScript (ES6), 70 bytes

Expects an array of arrays.

f=([b,...a],s)=>b?Math.max(...b.map(v=>f(a,new Set(s).add(v)))):s.size

Try it online!

Commented

f = (              // f is a recursive function taking:
  [b,              //   b[] = next list
      ...a],       //   a[] = all remaining lists
  s                //   s = current set, initially undefined
) =>               //
b ?                // if b[] is defined:
  Math.max(        //   return the maximum of ...
    ...b.map(v =>  //     for each value v in b[]:
      f(           //       do a recursive call:
        a,         //         pass a[]
        new Set(s) //         create a new set from s
                   //         (an empty set if s is undefined)
        .add(v)    //         add v to it
      )            //       end of recursive call
    )              //     end of map()
  )                //   end of Math.max()
:                  // else:
  s.size           //   return the size of s
\$\endgroup\$
3
\$\begingroup\$

R, 55 54 bytes

Edit: -1 byte thanks to pajonk

function(x)max(lengths(apply(expand.grid(x),1,table)))

Try it online!

Test setup stolen from pajonk's R answer.
48 bytes using R ≥ 4.1 by exchanging function for \.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ TIL about lengths function. Thanks! \$\endgroup\$
    – pajonk
    Jan 23 at 16:47
  • 1
    \$\begingroup\$ @pajonk - You're welcome. It's quite disconcerting when you accidentally learn something potentially useful while deliberately trying to write difficult-to-understand code, isn't it? This has often happened to me, too... \$\endgroup\$ Jan 23 at 18:51
  • \$\begingroup\$ You're absolutely right... BTW, you "stole" the test setup from me, but not the table function (for -1) ;-) \$\endgroup\$
    – pajonk
    Jan 23 at 19:51
  • \$\begingroup\$ @pajonk - Dang, you're right! But if I use table instead of unique, it'd be the same as you using lengths instead of sapply(,length)... we should flip a coin somehow do decide who gets to use the other's function... \$\endgroup\$ Jan 23 at 22:19
  • 1
    \$\begingroup\$ "pajonk_guesses_heads" ends in letter st (by odd/even position). \$\endgroup\$ Jan 24 at 7:33
3
\$\begingroup\$

Haskell + hgl, 10 bytes

xMl<nb<<sQ

Works as of commit 4a9f6d27. Older version below.

Explanation

The functions involved are:

  • sQ can do many things but on lists it performs the cartesian product.
  • nb removes all duplicate lements from a list.
  • xMl gets the length of the longest list in a list of lists

So we get the Cartesian product, nub the results and then get the maximum of their lengths.

Haskell + hgl, 13 bytes

mx<l.^nb.^sQ

This no longer works in recent versions of hgl since (.^) was renamed to (<<). To test it run:

mx<l<<nb<<sQ

Explanation

This works the same as the new implementation above except we have to get all the lengths and then get the maximum separately. The new functions are:

  • l gets the length of a list
  • mx gets the maximum of a list.

So we get the Cartesian product, nub the results and then get the maximum of their lengths.

Reflections

  • First things first we don't have a set type. This is unfortunate and needs to be fixed at some point.
  • l<nb seems like something that would be useful to have a builtin for.
  • It would be nice to have some sort fold and sequence or fold and traverse combined function.
  • I could have used a "maxmap". If we wanted to get the actual choices we could have done, xB l<nb.^sQ to save two bytes. But xB returns the original list not the modified version. This has been fixed in newer versions with the function is called xM, but xMl was also added which saves another byte.
\$\endgroup\$
2
\$\begingroup\$

Factor, 42 bytes

[ [ members ] product-map longest length ]

Try it online!

Uniqueify the elements of the product sequence of the input, then find the longest length.

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

R, 60 bytes

Or R>=4.1, 53 bytes by replacing the word function with a \.

function(x)max(sapply(apply(expand.grid(x),1,table),length))

Try it online!


Solution shorter in R>=4.1:

R, 66 bytes

Or R>=4.1, 52 bytes by replacing two function occurrences with \s.

function(x)max(apply(expand.grid(x),1,function(a)sum(table(a)|1)))

Try it online!

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

Vyxal, 6 bytes

Πv‡ULG

Try it Online!

Π      # Cartesian product - get all possibilties
 v     # Over each...
  ‡--  # Do the next two elements
   U   # Uniquify 
    L  # Get length
     G # Maximum
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 32 bytes

I⌈EEΠEθLιEθ§λ÷ι∨ΠE…θμLν¹LΦι⁼μ⌕ιλ

Try it online! Link is to verbose version of code. Explanation:

      θ                             Input array
     E                              Map over lists
        ι                           Current list
       L                            Take the length
    Π                               Take the product
   E                                Map over implicit range
          θ                         Input array
         E                          Map over lists
            λ                       Current list
           §                        Cyclically indexed by
              ι                     Outer value
             ÷                      Integer divided by
                   θ                Input array
                  …                 Truncated to length
                    μ               Inner index
                 E                  Map over array
                      ν             Innermost list
                     L              Take the length
                Π                   Take the product
               ∨                    Logical Or
                       ¹            Literal integer `1`
  E                                 Map over lists
                          ι         Current list
                         Φ          Filtered where
                            μ       Inner index
                           ⁼        Equal to
                             ⌕      Index of
                               λ    Inner value
                              ι     In current list
                        L           Take the length
 ⌈                                  Take the maximum
I                                   Cast to string
                                    Implicitly print
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 10 bytes

.»âε¸˜Ùg}à

Try it online or verify all test cases.

Explanation:

.»     # (Left-)reduce the (implicit) input-list by:
  â    #  Cartesian product
ε      # Then map over each inner list:
 ¸     #  Wrap it into a list (workaround for input [[1]])
  ˜    #  Flatten it
   Ù   #  Uniquify it
    g  #  Pop and push the length
}à     # After the map: pop and push the maximum
       # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Julia, 55

J(l)=maximum(length.(Set.(Iterators.product(l...))[:]))

ATO

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