11
\$\begingroup\$

You are the captain of a world-famous wrestling team. An Olympic-grade match is coming up, and you are determined not to let your team down. You also happen to be a competent programmer, so you are going to write a program to help your team win!

You have access to the strength ratings for each of your own team wrestlers, and each of the opponent wrestlers. A wrestler will win their match only when their strength rating is greater than their opponent's strength rating. You have to write a program that will calculate the optimum pairing for each of your own wrestlers against each of the opponent wrestlers, and then output the maximum number of matches that can be won as a result.

Input

Your program will take as input three strings:

  1. The number of members per team (there will be an equal number of wrestlers on each team)
  2. The strength rating of each of your team wrestlers, as a space-separated list
  3. The strength rating of each of the opponent wrestlers, as a space-separated list

Note:

  • You don't have to take the first number if you don't want to. It's there if you want it for help iterating through the list/array/string.
  • The strength rating is a number between 1 and 10.
  • You may input the strength ratings as a list or array instead of a string.

Output

Calculate the optimum pairing for each of your own wrestlers against each of the opponent wrestlers, and then output the maximum number of matches that can be won as a result.

Test cases

Test case 1:

5
2 4 6 2 6
3 10 6 7 7

Output: 1

Test case 2:

10
1 9 5 5 1 6 2 8 3 6
6 10 2 8 2 3 5 6 10 10

Output: 6

Bounties

I will upvote all answers that meet the requirements and that include an explanation, to encourage participation and to educate other code golfers on how your program works (this is my first post on CodeGolf.SE).

There will be no accepted answer since I want to encourage programs in all languages.

This is so be as creative as you can!

| improve this question | | | | |
New contributor
Aryan Beezadhur is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 4
    \$\begingroup\$ Hello, and welcome to CG&CC! In general when writing a new challenge you want to post it to the Sandbox first, to fix issues before answers can be submitted. The challenge itself seems fine (although I wouldn't be surprised if it's a duplicate), but the input format is stricter than is customary on this site and it would help to have outputs from the given test cases. \$\endgroup\$ – Unrelated String May 21 at 21:48
  • 1
    \$\begingroup\$ @Arnauld this is a completely original challenge \$\endgroup\$ – Aryan Beezadhur May 21 at 21:59
  • 1
    \$\begingroup\$ @mathjunkie I've added flexibility with the input format \$\endgroup\$ – Aryan Beezadhur May 21 at 22:00
  • 1
    \$\begingroup\$ @dingledooper I've calculated the output for each test case and added it \$\endgroup\$ – Aryan Beezadhur May 21 at 22:00
  • 3
    \$\begingroup\$ Do we have to take the first number? \$\endgroup\$ – Wezl May 21 at 22:47

12 Answers 12

11
\$\begingroup\$

Python 2, 59 57 bytes

-2 bytes thanks to @dingledooper!

lambda a,b:sum(b.sort()<b<[x]>b.pop(0)for x in sorted(a))

Try it online!

A function that takes 2 lists as arguments, and returns the maximum number of matches that can be won.

Approach

For each opponent (from weakest to strongest), match that opponent with the weakest available member of my team that can win.

For example, let's say the strength of 2 teams (sorted) are as follow:

No.       1  2  3  4  5
Me       [2, 2, 4, 5, 8]
Opponent [3, 6, 7, 7, 9]
  • The 1st opponent has strength 3, so we need to match that with our 3rd team member.
  • The 2nd opponent has strength 6, so we match that with our 5th.

We cannot win any more match. So in total we can win at most 2 matches.

Ungolfed code

a,b=map(sorted,input())  # sorted strength of my team and opponent team
s = 0                    # number of matches that can be won
for x in a:              # loop through my team, in order of increasing strength
  if x > b[0]:             # if current member can beat the weakest opponent left
    s += 1                   # then match those two
    b.pop(0)                 # and remove the weakest opponent
                           # (otherwise, current member is useless)
print s
| improve this answer | | | | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I like the idea with the b<[x]>b.pop(0). I think you can get 57 bytes with a function, though. \$\endgroup\$ – dingledooper May 21 at 22:55
  • \$\begingroup\$ @dingledooper Thanks! I was having trouble sorting b in a function, that's really clever. \$\endgroup\$ – Surculose Sputum May 21 at 22:58
  • \$\begingroup\$ This is very nice, and - annoyingly - the R ported version is shorter than my own first attempt (so I'm stealing it, with acknowledgement) \$\endgroup\$ – Dominic van Essen May 22 at 9:48
6
\$\begingroup\$

C (gcc) -zexecstack, 124 \$\cdots\$ 105 103 bytes

Saved a whopping 2 17 19 21 bytes thanks to ceilingcat!!!

#define q(x)qsort(x,i=n,4,L"\x62b078bǃ");
i;j;f(a,b,n)int*a,*b;{q(a)q(b)for(j=0;i--;j+=*a++>b[j]);i=j;}

Try it online!

How

Sorts the two teams from weakest to strongest. Then goes through our side, starting from weakest, comparing it to the \$j^{\text{th}}\$ member of the opponent's team starting at \$j=0\$, their weakest wrestler. If we are ever stronger than the \$j^{\text{th}}\$ member we increment \$j\$. After we go through all our wrestlers, \$j\$ will be the maximum number we can beat.

| improve this answer | | | | |
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for algorithm, now adapted to R with acknowledgement \$\endgroup\$ – Dominic van Essen May 22 at 10:14
4
\$\begingroup\$

Jelly, 5 bytes

Œ!>§Ṁ

Try it online!

The second test case times out on TIO, but I have verified it locally. Takes your lineup as the left argument and theirs as the right.

Œ!       Find every permutation of your lineups' strengths,
  >      compare each matchup for each permutation,
   §     sum your wins for each permutation,
    Ṁ    and return the maximum number of wins.
| improve this answer | | | | |
\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Extended), 16 bytes

(+/⊢≥⍋)0~⍨1⊥<\⍥∧

Try it online!

An almost direct port of Jonah's J answer. But unfortunately, I found that, despite having the same name "interval index", J's I. and APL's don't have the identical behavior; J finds the indices before identical elements, but APL does after them.

  • J: echo 1 3 5 I. 0 1 2 3 4 5 6 gives 0 0 1 1 2 2 3
  • APL: ⎕←1 3 5 ⍸ 0 1 2 3 4 5 6 gives 0 1 1 2 2 3 3

That makes hard to use for this problem, so I had to fall back to outer product (which is used in the previous version of Jonah's answer).

How it works

(+/⊢≥⍋)0~⍨1⊥<\⍥∧  ⍝ Left: opponent strengths, Right: ours
              ⍥∧  ⍝ Ascending sort both args
          1⊥<\    ⍝ Outer product by < and then sum;
                  ⍝ count the opponents who each of ours can win against
       0~⍨  ⍝ Remove zeros
(    ⍋)     ⍝ Grade up; this is identical to ⍳∘≢ here since the arg is sorted
   ⊢≥       ⍝ Check if each number is at least its index
 +/         ⍝ Sum; count ones
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ But am I screwing-up, or are there cases for which this doesn't work? \$\endgroup\$ – Dominic van Essen May 22 at 9:45
  • \$\begingroup\$ @Bubbler, He's correct (my error). See my update for a simple fix that ended up improving my score. \$\endgroup\$ – Jonah May 22 at 13:49
4
\$\begingroup\$

05AB1E, 5 bytes

Coincidental port of Unrelated String's Jelly answer.

œ€‹Oà

Try it online!

Explanation

œ     All permutations to your team's combination
 €‹   Does your team win at this position?
   O  Sum the resulting lists to get all wins
    à Return the largest item of the list
| improve this answer | | | | |
\$\endgroup\$
4
\$\begingroup\$

J, 25 22 20 bytes

0(]+>)/@|.@,I.&(/:~)

Try it online!

-3 bytes thanks to Bubbler

Thanks to Dominic van Essen for spotting a subtle bug (now fixed)


This could be shorter using brute force, but I wanted to see how short I could make an efficient solution.

Our team = right arg, their team = left arg.

Using 2nd test case an example:

6 10 2 8 2 3 5 6 10 10 f 1 9 5 5 1 6 2 8 3 6 
  • &(/:~) Sort both arguments:

    2 2 3 5 6 6 8 10 10 10
    1 1 2 3 5 5 6  6  8  9
    
  • I. Uses Interval Index to determine how many of their players each of our players beats:

    0 0 0 2 3 3 4 4 6 7
    
  • 0...|.@, Prepend a 0 and reverse:

    2 3 3 4 4 6 7
    
  • (]+>)/ Now reduce from the right as follows: Take the right arg ] (the running sum, seeded at 0), compare the two args using > (returns 1 if left arg is greater than running sum, 0 otherwise), and add the two.

    This means the running sum will increment exactly when "the number of opponents the current wrestler can beat" is greater than "opponents already beaten by other teammates".

    The final result will be the total number of players our team can beat.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ I.~&(/:~) (interval index) gives the same results as 1#.>/&(/:~), and you can remove ~ by swapping args. \$\endgroup\$ – Bubbler May 22 at 0:55
  • \$\begingroup\$ Nice observation! Tyvm. \$\endgroup\$ – Jonah May 22 at 1:02
  • \$\begingroup\$ But what about us: 1 2 3 3 5 5 6 6 7 9, them: 0 0 2 2 3 6 6 6 7 9 ? Our 1 beats their 0, 2 beats 0, 3 beats 2, 3 beats 2, 5 beats 3, 7 beats 6, and 9 beats 6, so total = 7. \$\endgroup\$ – Dominic van Essen May 22 at 9:40
  • \$\begingroup\$ @DominicvanEssen Great spot! I've fixed the problem which ended up leading to a solution that's 2 bytes shorter. \$\endgroup\$ – Jonah May 22 at 13:27
3
\$\begingroup\$

R, 58 54 bytes

function(a,b){for(i in sort(a))F=F+(i>sort(b)[F+1]);F}

Try it online!

Algorithm based on Noodle9's solution; this could be made shorter than my own original recursive solution 76 bytes or than one based on the elegant algorithm of Surculose Sputum 73 bytes in R

| improve this answer | | | | |
\$\endgroup\$
3
\$\begingroup\$

Io, 66 bytes

Algorithm based on Noodle9's solution.

method(x,y,F :=0;x sort map(i,F=F+if(i>y sort at(F+1),1,0))last+1)

Try it online!

Explanation

method(x, y,      // Take 2 arguments.
    F := 0        // Initialize the counter to 0.
    x sort map(i, // For every item in sorted x:
        F = F + if( // Add the counter by:
            i>y sort at(F+1), // if the current item is larger than sorted y at the same position
            1,0)    // converted to an integer
    ) last + 1)     // Add the last item of the map by 1
| improve this answer | | | | |
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 41 bytes

≔I⪪η η≔I⪪ζ ζWΦη›κ⌊櫧≔η⌕η⌊ι⁰§≔ζ⌕ζ⌊ζχ»I№η⁰

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

≔I⪪η η

Input the ratings of your wrestlers.

≔I⪪ζ ζ

Input the ratings of your opponents.

WΦη›κ⌊ζ«

Repeat while at least one of your wrestlers can beat one of your opponents.

§≔η⌕η⌊ι⁰

Set the strength of the weakest such wrestler to 0, so it will no longer be considered.

§≔ζ⌕ζ⌊ζχ

Similarly set the strength of its opponent to 10, so it will also no longer be considered.

»I№η⁰

Count and output the number of wins.

If the input was sorted, the calculation could be done in 19 bytes. Unfortunately it takes me 30 bytes to sort the input...

| improve this answer | | | | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 61 bytes

A shorter version inspired by @SurculoseSputum's answer.

a=>b=>(g=a=>a.sort((a,b)=>a-b))(a).map(x=>k+=x>g(b)[k],k=0)|k

Try it online!

That would be 31 bytes if the arrays were already sorted in ascending order:

a=>b=>a.map(x=>k+=x>b[k],k=0)|k

JavaScript (ES6),  85  75 bytes

Takes input as two lists of integers (team, opponents).

a=>b=>a.map(x=>(b[i=b.sort((a,b)=>b-a).findIndex(y=>x>y)]=a,~i&&++k),k=0)|k

Try it online!

| improve this answer | | | | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 48 bytes

Max[t=#2;Tr@Boole@Thread[#>t]&/@Permutations@#]&

Try it online!

Unnamed function taking two arguments as input (first our team, then their team), each as comma-separated lists such as {2,4,6,2,6}. Brute-force check over all Permutations of the input, taking the Max. Mathematica doesn't automatically compare lists elementwise, but Thread[#>t] forces it to; Boole converts Trues and Falses to 0s and 1s, respectively, so that Tr counts the number of wins. Mathematica is bad with currying when it's not programmed into the builtins, so I couldn't see a better way to handle the arguments than t=#2;.

| improve this answer | | | | |
\$\endgroup\$
1
\$\begingroup\$

Japt -h, 10 bytes

á Ëí>V xÃn

Try it

| improve this answer | | | | |
\$\endgroup\$

Your Answer

Aryan Beezadhur is a new contributor. Be nice, and check out our Code of Conduct.

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.