15
\$\begingroup\$

Given a non-empty set of strings and a list of strings, find out how many times the set occurs in the list, i.e. how many times you could create the set with items from the list. Every element from the list can only be used once.

Hint: a set is an unordered list of unique items.

Default input/output rules apply.

No external libraries allowed. Compiler/Interpreter standard libs are okay. This is code golf, so shortest solution counts.


Test cases:

["apple", "banana"], ["apple", "pear", "apple", "banana", "banana"] => 2

["apple", "banana"], ["apple", "pear", "apple", "banana", "apple"] => 1

["apple", "banana", "pear"], ["apple", "banana", "kiwi", "apple"] => 0

["coconut"], [] => 0

EDIT: removed a sentence stating that the input params are defined in local scope. This contradicts the default IO rules linked above.

\$\endgroup\$
12
  • \$\begingroup\$ Yes that clarifies it. However I am a little hung up on the third sentence. What do you mean by "doesn't handle objects"? \$\endgroup\$
    – Wheat Wizard
    Apr 20, 2017 at 18:45
  • \$\begingroup\$ @WheatWizard some languages are not object-oriented and don't know the concept of comparing arbitrary objects. \$\endgroup\$ Apr 20, 2017 at 18:47
  • 1
    \$\begingroup\$ You should probably change that to object-oriented because every language I am aware of does handle objects of some type even if objects are a closed class. I should also point out that there are a good deal of languages that also cannot handle strings at all. \$\endgroup\$
    – Wheat Wizard
    Apr 20, 2017 at 18:49
  • \$\begingroup\$ @WheatWizard okay, updated description. That paragraph was meant for languages such as C, Assembler or Maple. \$\endgroup\$ Apr 20, 2017 at 18:59
  • \$\begingroup\$ What languages are object oriented? What should they use if not strings? I think the easiest thing would be to restrict to just strings. Or, alternatively, only integers. See this advice on using the simplest type that suffices. \$\endgroup\$
    – xnor
    Apr 20, 2017 at 19:23

23 Answers 23

12
\$\begingroup\$

Python, 30 bytes

lambda s,l:min(map(l.count,s))

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Nice one. Didn't think about using map. You can save a little by using print instead of defining a lambda BTW. \$\endgroup\$ Apr 20, 2017 at 19:18
  • 1
    \$\begingroup\$ @HubertGrzeskowiak Changing the lambda to a print brings the byte count up to 37 because of the two input()s required. \$\endgroup\$
    – Wheat Wizard
    Apr 20, 2017 at 20:49
  • \$\begingroup\$ @WheatWizard as stated in the challenge, consider the inputs defined in local scope. You are NOT required to have the inputs explicitly defined, e.g. as function params or user inputs. \$\endgroup\$ Apr 21, 2017 at 5:45
  • \$\begingroup\$ @HubertGrzeskowiak if there is no good reason for it, you should not overwrite our defaults for taking input and output and our defaults for codegolf submissions \$\endgroup\$
    – ovs
    Apr 21, 2017 at 6:05
  • \$\begingroup\$ @ovs oh, I wasn't aware of that post. Thanks. \$\endgroup\$ Apr 21, 2017 at 6:15
6
\$\begingroup\$

Jelly, 4 bytes

⁼þSṂ

Try it online!

How?

⁼þSṂ - Main link: list theSet, list theList
 þ   - outer product using the dyadic operation:
⁼    -     is equal? (non-vectorising)
  S  - sum (vectorises) (yields the number of times each element of theSet appears in theList)
   Ṃ - minimum (can only make the minimum as a multiple)
\$\endgroup\$
6
\$\begingroup\$

Jelly, 6 5 4 bytes

ċ@€Ṃ

Try it online!

The first argument of the program is the set, and the second argument is the list.

Explanation

ċ@€Ṃ
ċ@   -- Create a link which finds the number of occurrences of 
          its left argument in its right argument (the list)
  €  -- Map this link over each element in the first argument
          of the program (the set)
   Ṃ -- Minimum value of this.

-1 byte thanks to @ETHproductions

-1 byte again thanks to @ETHproductions

\$\endgroup\$
4
  • \$\begingroup\$ Very nice! You can save a byte by combining the links into one line: ⁹ċ$€Ṃ I have a feeling that can be made shorter by using the implicit right argument in place of ... \$\endgroup\$ Apr 20, 2017 at 20:25
  • \$\begingroup\$ I think ċ@€Ṃ works to save another byte... (the @ reverses the arguments to ċ) \$\endgroup\$ Apr 20, 2017 at 20:45
  • \$\begingroup\$ @ETHproductions Works correctly as far as I have tested. \$\endgroup\$ Apr 20, 2017 at 20:52
  • \$\begingroup\$ It didn't exist until May 12 of last year, but in place of @€ (with reversed arguments to the program) saves yet another byte: Try it online! \$\endgroup\$ Nov 22, 2019 at 8:09
6
\$\begingroup\$

JavaScript (ES6), 56 bytes

f=(n,h)=>Math.min(...n.map(c=>h.filter($=>$==c).length))

Try it online

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Save 2 bytes by using an anonymous function and another by currying the parameters: n=>h=>Math.min(...n.map(c=>h.filter($=>$==c).length)) for 53 bytes \$\endgroup\$
    – Shaggy
    Apr 21, 2017 at 9:05
5
\$\begingroup\$

JavaScript (ES6), 64 bytes

(s,l)=>l.map(e=>m[s.indexOf(e)]++,m=s.map(e=>0))&&Math.min(...m)

Assumes both s and l are arrays of objects. Uses JavaScript strict equality for comparisons, so for instance [] === [] is false.

\$\endgroup\$
2
  • \$\begingroup\$ Very interesting solution. Please return or print the result. AFAIK this returns an anonymous function. \$\endgroup\$ Apr 20, 2017 at 19:19
  • 2
    \$\begingroup\$ @HubertGrzeskowiak The code as shown evaluates to an anonymous function. When called, the function returns the count as desired. \$\endgroup\$
    – Neil
    Apr 20, 2017 at 20:15
4
\$\begingroup\$

Haskell, 37 34 bytes

Thanks to @Laikoni for shaving off three bytes.

s#l=minimum[sum[1|y<-l,y==x]|x<-s]

Call with (set::[a]) # (list::[a]) where a is any type deriving Eq.

\$\endgroup\$
3
  • \$\begingroup\$ Instead of length[y|y<-l,y==x] you can use sum[1|y<-l,y==x]. \$\endgroup\$
    – Laikoni
    Apr 21, 2017 at 0:14
  • \$\begingroup\$ @Laikoni, are you sure about that? I think I would need to use something like sum[1|y<-l,y==x,_<-y], which comes out to two bytes longer—I could definitely be missing something there, though \$\endgroup\$ Apr 21, 2017 at 0:38
  • \$\begingroup\$ Never mind, you're definitely right. Good call. \$\endgroup\$ Apr 21, 2017 at 0:40
3
\$\begingroup\$

CJam, 11 bytes

q~f{\e=}:e<

Try it online!

Explanation

q~           e# Read and eval the input
  f{\e=}     e# Map each item in the set to the number of times it appears in the list
        :e<  e# Find the minimum of the resulting list
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 24 bytes

Min[#/.Rule@@@Tally@#2]&

Pure function taking two lists as arguments in the suggested order and returning a nonnegative integer. Tally counts how many occurrences of every symbol occur in the input list, and #/.Rule@@@ converts each element of the input set into the corresponding number of occurrences.

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

T-SQL, 62 59 bytes

Previous version didn't work for sets with no matches

select top 1(select count(*)from l where l=s)from s order by 1

With s and l as tables and columns named the same as the table

select top 1         -- return only the first result
    (select count(*) -- count of rows
     from l          -- from table l
     where l=s)      -- for each l equal
from s               -- to each from s
order by 1           -- sort by count ascending
\$\endgroup\$
3
\$\begingroup\$

Swift, 39 bytes

s.map{w in l.filter{$0==w}.count}.min()

explanation:

s.map{} goes through each word in s and will produce an array of counts

w in names the mapped word for use in the next filter

l.filter{} aplies a filter to the l array

$0==w is the filter condition matching word w

.count gives the number of elements of l that met the condition

.min() returns the lowest count in the mapped result

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to PPCG! I've added code formatting for your solution. You can do this by prepending 4 spaces to lines that contain code. \$\endgroup\$
    – user45941
    Apr 21, 2017 at 5:48
3
\$\begingroup\$

APL (Dyalog), 9 bytes

⌊/+/⎕∘.≡⎕

Try it online!

 get evaluated input (list of strings)

⎕∘.≡ get evaluated input (non-empty set of strings) and create equivalency table

+/ add across

⌊/ minimum across

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

Perl 6,  37  18 bytes

37

{+(($_=@^a⊍@^b)≽@a)&&.values.min}

Try it

Expanded:

{
  +( # turn into a 0 if False

    (
      $_ =        # store into $_ the result of
        @^a ⊍ @^b # use the baggy multiplication operator
    ) ≽ @a        # is that the baggy superset of the set
  )

  &&          # if that is True

  .values.min # get the minimum value from the Bag in $_
}

See Sets, Bags, and Mixes for more information.


18

{@^b.Bag{@^a}.min}

Try it

Explanation:

@^b.Bag create a Bag from the values
{@^a} key into that Bag (returns a list of counts)
.min get the minimum value of the resulting list


\$\endgroup\$
6
  • \$\begingroup\$ Neat answers, but neither of these look like functions / complete programs \$\endgroup\$ Apr 21, 2017 at 2:37
  • \$\begingroup\$ @JulianWolf I was under the impression that snippets were allowed based on the statements “Consider both inputs being defined in the current scope as s and l.” and “You don't need to define a function.” I went and edited it anyway. \$\endgroup\$ Apr 21, 2017 at 3:44
  • \$\begingroup\$ Ah, you're completely right. That must've been edited into the question after I read it. In any case, I like the aesthetic of this version even more than the last—Perl's syntax will always be a mystery to me. \$\endgroup\$ Apr 21, 2017 at 3:46
  • \$\begingroup\$ @JulianWolf This isn't really a good example of Perl 6 code. I would recommend seeing Ovid's 1hr talk Perl 6 — Why People Are So Excited, or looking at the Resources tab on Perl6.org. \$\endgroup\$ Apr 21, 2017 at 4:08
  • \$\begingroup\$ Yeah, sorry for the confusion. This is my first chllenge and I didn't know there already are rules for input and output. I changed it because most answers were using these rules even while it wasn't required. \$\endgroup\$ Apr 21, 2017 at 6:51
2
\$\begingroup\$

Axiom, 42 bytes

f(a,b)==reduce(min,[count(x,b)for x in a])

test code and results

(28) -> f(["1","2"], ["1", "2", "1", "1", "7"])
   (28)  1
                                                    Type: PositiveInteger
(29) -> f(["apple","banana"],["apple","pear","apple","banana","banana"])
   (29)  2
                                                    Type: PositiveInteger
(30) -> f(["apple","banana"],["apple","pear","apple","banana","apple"])
   (30)  1
                                                    Type: PositiveInteger
(31) -> f(["apple","banana","pear"],["apple","banana","kiwi","apple"])
   (31)  0
\$\endgroup\$
2
\$\begingroup\$

C++, 203 201 bytes

Thanks to @Quentin for saving two bytes!

#import<vector>
#import<string>
using T=std::vector<std::string>;
int f(T S,T L){for(int j,b,i=0;;++i)for(auto s:S){for(b=j=0;j<L.size();++j)if(L[j]==s){b=1;L.erase(begin(L)+j);break;}if(!b)return i;}}

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ L.begin() -> begin(L) saves one byte :) \$\endgroup\$
    – Quentin
    Apr 21, 2017 at 9:26
  • \$\begingroup\$ Also, using T=std::vector<std::string>; saves another! Who knew modern pretty syntax could also help golfing. \$\endgroup\$
    – Quentin
    Apr 21, 2017 at 17:10
  • \$\begingroup\$ @Quentin I tried that at first. Probably there was some simple typo I didn't notice. \$\endgroup\$
    – Steadybox
    Apr 21, 2017 at 23:39
  • \$\begingroup\$ Suggest j<L.size()&!b;++j)if(b=L[j]==s)L.erase(begin(L)+j); instead of j<L.size();++j)if(L[j]==s){b=1;L.erase(begin(L)+j);break;} \$\endgroup\$
    – ceilingcat
    Jul 13, 2020 at 4:56
1
\$\begingroup\$

PHP, 74 Bytes

<?foreach($_GET[0]as$v)$t[]=array_count_values($_GET[1])[$v];echo+min($t);

Testcases

PHP, 108 Bytes

<?[$x,$y]=$_GET;echo($a=array_intersect)($x,$y)==$x?min(($a._key)(array_count_values($y),array_flip($x))):0;

Testcases

\$\endgroup\$
1
\$\begingroup\$

Pyth, 5 bytes

hS/LF

Takes the list first and the set second. Test suite.

Explanation:

    F  Expand the input into l and s (not literally, 
                  since those are function names in Pyth, but...)
   L   for d in s:
  /        Count instances of d in l
   L   Package all the results as a list
 S     Sort the results smallest-first
h      grab the smallest element
\$\endgroup\$
1
\$\begingroup\$

C#, 36 bytes

f=(n,h)=>n.Min(c=>h.Count(x=>x==c));

n and h are string[] and the output is an int.

Try it online!

This answer is inspire by @ovs and @Alberto Rivera's logic. Thank you!

\$\endgroup\$
1
\$\begingroup\$

Java, 135 bytes

int f(List<String> s,List<String> l){int n=0,i=0;while(i<s.size()){if(!l.remove(s.get(i++)))break;if(i==s.size()){n++;i=0;}};return n;}

This is my first code golf challenge and answer, so not sure about the format. Does it need to be a full compiling program? Do I need to define the parameters? Suggestions appreciated.

EDIT: wrapped code in a function. Thanks @Steadybox

\$\endgroup\$
1
1
\$\begingroup\$

05AB1E, 7 bytes

v²y¢})W

Try it online!

v   }   # For each item in the first list...
 ²y¢    # Count the occurances in the second list.
     )W # Take the minimum occurrence count, return.
\$\endgroup\$
1
\$\begingroup\$

Java, 114 Bytes

<T>int a(Set<T>b,List<T>c){int m=2e32;b.stream().map(i->{int j=java.util.Collections.frequency(c,i);m=j<m?j:m;});return m;}

Tio coming soon

Explanation

  • creates local variable m.

  • maps the set to a stream.

  • for each element, if the number of occurances of the element in the list is less than m, m is set to that value.

  • returns m, which is the number of complete versions of the set

\$\endgroup\$
0
\$\begingroup\$

R 54 Bytes

f<-function(s,l) min(table(factor(l[l%in%s],levels=s)))

Explanation: creating a table of the counts of only the values in the list that also appear in the sublist.

I then turn the variable into a factor in order to generate zeros if a value that appears in the sublist does not appear in the list. Finally, I take the minimum of the counts.

\$\endgroup\$
0
\$\begingroup\$

R, 61 57 44 bytes

print(min(sapply(s,function(x)sum(l%in%x))))

Anonymous function. Apparently you don't have to define a function for this challenge. Saved 13 bytes thanks to count.

Explanation:

sum(l%in%x)) returns the number of times a string in s is found in l.

lapply(s,function(x)) applies that to each string in s separately and returns a list of sums.

min() returns the smallest from that list.

\$\endgroup\$
3
  • \$\begingroup\$ Could be brought down to 40 Bytes with a for-loop: z=c();for(i in s)z[i]=sum(l%in%i);min(z) \$\endgroup\$
    – count
    Apr 21, 2017 at 9:18
  • \$\begingroup\$ Or even further to 37 bytes with sapply: min(sapply(s,function(x)sum(l%in%x))) \$\endgroup\$
    – count
    Apr 21, 2017 at 9:23
  • \$\begingroup\$ Brilliant, I always forget you can sum booleans. I'll edit that in later. I've been told I need that print() if it's not a function. \$\endgroup\$
    – BLT
    Apr 21, 2017 at 14:08
0
\$\begingroup\$

JavaScript (ES6), 59 bytes

a=>b=>a.reduce((x,y)=>(l=b.filter(s=>s==y).length)>x?x:l)|0

Try it

f=

a=>b=>a.reduce((x,y)=>(l=b.filter(s=>s==y).length)>x?x:l)|0

console.log(f(["apple","banana"])(["apple","pear","apple","banana","banana"]))
console.log(f(["apple","banana"])(["apple", "pear", "apple", "banana", "apple"]))
console.log(f(["apple","banana","pear"])(["apple","banana","kiwi","apple"]))
console.log(f(["coconut"])([]))

\$\endgroup\$

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.