9
\$\begingroup\$

Story

Martians have been observing Aussie rules football matches from space with great curiosity. Having totally fallen in love with the game, they have been inspired to start their very own football league. However, being dim-witted creatures, they are unable to comprehend the scoring system.*

We know that in Aussie rules, a goal is worth 6 points (\$G=6\$) and a behind is worth 1 point (\$B=1\$). The Martians are cluey enough to work out that there are two types of scores, but not smart enough to realise that they can deduce the point values of these scores by analysing match outcomes. Undeterred, the International Olympus Mons Committee decrees that in all Martian rules football matches, the point values for goals and behinds (i.e. \$G\$ and \$B\$) will be chosen at random.

'Perfect' scores

When \$G = 6\$ and \$B = 1\$ (as in Aussie rules), there are exactly four integer pairs \$[g,b]\$ such that a team with \$g\$ goals and \$b\$ behinds has a score of \$gb\$ points. We will refer to \$[g,b]\$ pairs that satisfy $$gG+bB=gb$$ as perfect scores. The four perfect scores in Aussie rules are \$[g,b]=[2,12]\$, \$[3,9]\$, \$[4,8]\$, and \$[7,7]\$.

Challenge

Given two strictly positive integers \$G\$ and \$B\$ representing the point values of goals and behinds in a Martian rules football match, write a program or function that determines all possible perfect scores for that match. Rules:

  • Input may be taken in any convenient format (pair of integers, list, string, etc.). You may not assume that \$G>B\$.
  • Output may also be in any format, provided that the \$[g,b]\$ pairs are unambiguously identifiable (e.g. successive elements in a list or string). The order of pairs does not matter. You may output pairs in \$[b,g]\$ order instead provided that you state this in your answer. You may not output the total scores (the products \$gb\$) instead, because in general there are multiple non-perfect ways to achieve the same total score.
  • Your program/function must terminate/return in finite time.

This is : the shortest submission (in bytes) in each language wins.

Test cases

Input -> Output

[6, 1] -> [[2, 12], [3, 9], [4, 8], [7, 7]]
[6, 2] -> [[3, 18], [4, 12], [5, 10], [6, 9], [8, 8], [14, 7]]
[1, 1] -> [[2, 2]]
[1, 6] -> [[7, 7], [8, 4], [9, 3], [12, 2]]
[7, 1] -> [[2, 14], [8, 8]]
[7, 5]  -> [[6, 42], [10, 14], [12, 12], [40, 8]]
[13, 8] -> [[9, 117], [10, 65], [12, 39], [16, 26], [21, 21], [34, 17], [60, 15], [112, 14]]

* This problem never, ever, occurs on Earth.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ This problem never, ever, occurs on Earth. That's bold of you to assert that statement... I'm Australian and I sometimes struggle to comprehend our own scoring methods. \$\endgroup\$
    – lyxal
    May 8, 2020 at 11:58
  • 1
    \$\begingroup\$ @Lyxal If you're Australian, do you know why they invented these incomprehensible scoring methods in the first place? \$\endgroup\$
    – user92069
    May 8, 2020 at 12:05
  • 1
    \$\begingroup\$ Absolutely not. No one really knows. \$\endgroup\$
    – lyxal
    May 8, 2020 at 12:07
  • 1
    \$\begingroup\$ However, being dim-witted creatures, they are unable to comprehend the scoring system. How are they dim-witted, given they've invented such a powerful telescope!? \$\endgroup\$
    – user92069
    May 8, 2020 at 12:11
  • 2
    \$\begingroup\$ @Lyxal , I can guess the complex rules were invented for the same reasons as the 'Offside' rule in soccer - so men can discuss about sports and their wifes don't understand it (men are not bothered as much by the fact that they don't really understand it - each one is sure he got it right). \$\endgroup\$
    – Aganju
    May 8, 2020 at 19:54

8 Answers 8

6
\$\begingroup\$

Python 2, 85 81 78 bytes

G,B=input()
R=range(~G*~B)
print[(g,b)for g in R for b in R if g*G+b*B==g*b>0]

Try it online! or Check all test cases!

A program that reads 2 integers G, B from STDIN, and prints to STDOUT all pairs of g,b.

The upper bounds of \$g\$ and \$b\$ are: $$g \leq B(G+1)$$ $$b \leq G(B+1)$$ or as used in the program: \$ g, b < (G+1)(B+1) \$

This is derived as follow:

$$ gG + bB = gb $$ $$ g(b-G) = bB $$ $$ \frac{g}{B} = \frac{b}{b-G} $$ $$ \frac{g}{B} = 1 + \frac{G}{b-G} \leq 1 + G $$ $$ g \leq B(1 + G) $$

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

05AB1E, 10 bytes

>PLãʒ*OyPQ

Try it online or verify all test cases.

Explanation:

>           # Increase both values in the (implicit) input-pair by 1
 P          # And take the product of those
  L         # Pop and push a list in the range [1, (G+1)*(B+1)]
   ã        # Create all possible pairs by taking the cartesian product with itself
    ʒ       # Filter those pairs [g,b] by:
     *      #  Multiply it with the (implicit) input-pair at the same positions:
            #   [G,B] * [g,b] will result in [Gg,Bb]
      O     #  Sum those: Gg+Bb
       yP   #  Take the product of the current pair: gb
         Q  #  And check that both values are the same: Gg+Bb == gb
            # (after which the result is output implicitly)

The last test case no longer times out by using an upper bound of \$(G+1)\times(B+1)\$ instead of my initial \$(2^G+2^B)\$ (byte count remains the same). Make sure to upvote @SurculoseSputum's Python answer for providing this mathematical upper bound.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 58 bytes

lambda G,B:[(i+B,G*B/i+G)for i in range(1,G<<B)if G*B%i<1]

Try it online!

We can write \$gG+bB=gb\$ as $$(g-B)(b-G)=GB,$$ that is, \$ij=GB\$ with $$g=i+B$$ $$b=j+G$$ So, the outputs \$(g,b)\$ are just the divisor pairs \$(i,j)\$ multiplying to \$GB\$, but shifted up by the input values:

$$(g,b)\in\{(i+B,j+G) \mid ij=GB; \thinspace i,j\in \mathbb{Z}^{+}\} $$

Note that negative \$(i,j)\$ are not included because they produce a negative \$g\$ or \$b\$.

The code is mostly straightforward, iterating over all potential factors \$i\$ of \$GB\$, taking those that are exact divisor, to produce the \$(g,b)\$ given by the formula. We could have looped over both \$i\$ and \$j\$ and take those with \$ij=GB\$, but the length of writing a second loop makes this unviable in Python, though other languages may prefer this option.

We need to test all potential divisors \$i\$ in the closed interval \$[1,GB]\$, excluding zero to avoid a modulo-by-zero error. For the half-open upper bound for range, we write G<<B to make some value strictly bigger than \$GB\$, noting that \$G \cdot 2^B \geq G(B+1) > GB \$. Despite this clunky range call, it seems longer to replace the iteration by a recursive function.

As a program:

Python 2, 60 bytes

G,B=input()
P=i=G*B
while i:
 if P%i<1:print i+B,P/i+G
 i-=1

Try it online!

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

Python 3.8 (pre-release), 59 bytes

A recursive port of the below.

def f(G,B,i=1):m=G*B;m%i or print(i+B,G+m/i);i<m<f(G,B,i+1)

Try it online!

Python 2, 64 60 bytes

Takes the two integers \$ G \$ and \$ B \$ as input, and outputs the integer solutions in \$ [g, b] \$ order, each on a new line.

G,B=input()
n=m=G*B
exec'if m%n<1:print n+B,G+m/n\nn-=1\n'*n

Try it online!

We first isolate \$ b \$, giving us:

$$ gG + bB = gb $$ $$ gG = gb - bB $$ $$ gG = b(g - B) $$ $$ \frac{gG}{g - B} = b $$

All we need to do now is find values of \$ g \$ that produce a positive integer solution when plugged into the formula. We also get that \$ g \leq B + GB \$ from Surculose Sputum's answer, and that \$ B < g \$, otherwise it would produce a negative solution because of the denominator.

One thing which I did in my program is subtract \$ B \$ from \$ g \$. The formula then becomes

$$ \frac{(g + B)G}{g} $$

and the inequality becomes \$ 0 < g \leq GB \$. This change turned out to slightly improve the byte count.

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

C (gcc), 84 bytes

b;g;f(B,G){for(b=0;++b<~B*~G;)for(g=0;++g<~B*~G;b*B+g*G-b*g||printf("%d %d ",b,g));}

Try it online!

Prints out the values of \$b\$ and \$g\$ separated by spaces.

Uses the upper bounds for \$b\$ and \$g\$ as calculated by Surculose Sputum in his Python answer.

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

Charcoal, 32 30 27 bytes

IEΦΠθ¬﹪Πθ⊕ι⟦⁺⊕ι§θ¹⁺÷Πθ⊕ι§θ⁰

Try it online! Link is to verbose version of code. Takes input as a list. I converted my 30 byte version (below) to take input as a list, which ends up making it behave like @xnor's answer. Explanation:

   Πθ                       G*B
  Φ                         Filter over implicit range
         ⊕ι                 g-B
     ¬﹪                     Divides
       Πθ                   G*B=G*g-G*(g-B)
 E                          Map over filtered values
           ⟦                Tuple of
            ⁺⊕ι§θ¹          (g-B)+B=g
                  ⁺÷Πθ⊕ι§θ⁰ G*B/(g-B)+G=G*g/(g-B)=b
I                           Cast to string
                            Implicitly print

Previous 30-byte version:

NθNηIEΦ…·¹×ηθ¬﹪×ηθι⟦⁺ιη÷×⁺ιηθι

Try it online! Link is to verbose version of code. The lower bound for g is B+1 and the upper bound (as independently calculated by @SurculoseSputum) is B(G+1) so it simply remains to calculate those values where b is an integer. Explanation:

NθNη

Input G and B.

IEΦ…·¹×ηθ

Loop i from 1 to BG. This is equivalent to looping g from B+1 to B(G+1), where g=i+B.

¬﹪×ηθι

Filter on b being an integer. Edit: Saved 2 bytes by checking whether i divides GB rather than whether b=gB/i=(G+i)B/i is an integer.

⟦⁺ιη÷×⁺ιηθι

Output g and b.

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

Pyth, 17 bytes

fq*FTs*VTQ^Sy*FQ2

Try it online!

Port of @KevinCruijssen's 05AB1E Answer, with a few modifications to make it more suitable for Pyth.

In particular, the upper bounds of

$$g \leq B(G+1)$$ $$b \leq G(B+1)$$

from @SurculoseSputum's answer have been used to derive that:

$$g,b \leq 2GB$$

fq*FTs*VTQ^Sy*FQ2
            y*FQ    Multiply G and B, then multiply by 2
           S        Range( 1, 2*GB )
          ^     2   Cartesian product of that range with itself
f                   Filter for elements (g,b) satisfying:
  *FT                g*b
 q                    equals
     s*VTQ            G*g + B*b

Bonus: Port of @xnor's Python answer (21 bytes)

AQVSJ*GHI!%JN+NH+G/JN

Try it online!

Outputs each pair g,b on two separate lines. I find this solution amusing because it contains only uppercase letters and operators.

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

Erlang (escript), 61 bytes

Boring port of the Python answer. (To get me started.)

f(G,B)->[[I+B,G*B/I+G]||I<-lists:seq(1,G bsl B),G*B rem I<1].

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.