Largest monetary amount impossible to make with two types of coin

19

2

Suppose we have two different types of coin which are worth relatively prime positive integer amounts. In this case, it is possible to make change for all but finitely many quantities. Your job is to find the largest amount that cannot be made with these two types of coin.

Task

Input: A pair of relatively prime integers \$(a,b)\$ such that \$1<a<b\$.

Output: The largest integer that cannot be expressed as \$ax+by\$ where \$x\$ and \$y\$ are nonnegative integers.

Scoring:

This is code golf so shortest answer in bytes wins.

Example:

Input \$(3,11)\$

\$4\cdot 3- 1\cdot 11=1\$, so if \$n\geq 22\$ we can write \$n=q\cdot 3 + 2\cdot 11 +r\$ where \$q\$ is the quotient and \$r\in\{0,1,2\}\$ the remainder after dividing \$n-22\$ by \$3\$. The combination \$(q+4r)\cdot 3 + (2-r)\cdot 11 = n\$ is a nonnegative combination equal to \$n\$. Thus the answer is less than \$22\$. We can make \$21=7\cdot 3\$ and \$20=3\cdot 3 + 1\cdot 11\$ but it's impossible to make \$19\$ so the output should be \$19\$.

Test Cases:

[ 2,  3] => 1

[ 2,  7] => 5

[ 3,  7] => 11

[ 3, 11] => 19

[ 5,  8] => 27

[ 7, 12] => 65

[19, 23] => 395

[19, 27] => 467

[29, 39] => 1063

[ 1,  7] => error / undefined behavior (inputs not greater than one)

[ 6, 15] => error / undefined behavior (not relatively prime).

[ 3,  2] => error / undefined behavior (3 > 2)

[-3,  7] => error / undefined behavior (-3 < 0)

Hood

Posted 2020-01-11T00:46:56.077

Reputation: 1 437

2I remember seeing this challenge before, but I'm not coming up with it on searching. – xnor – 2020-01-11T03:13:58.420

@xnor I thought there was a good chance it would be a duplicate but I also failed to find it when I searched. – Hood – 2020-01-11T03:39:58.717

2There is a problem for any number of coins. But I don't think it is a duplicate, because most answers here do not work for the case with more than 2 coins. – alephalpha – 2020-01-11T04:26:44.903

Are you the same Hood that has written poker software? – Jonah – 2020-01-11T05:39:51.067

2Here's a proof for the formula by one of the diamond mods of Math.SE. – Jyrki Lahtonen – 2020-01-12T15:11:27.753

2@Jonah I am not. I am a mathematician (I study algebra, specifically homotopy theory) and hobbyist programmer. – Hood – 2020-01-12T18:30:46.670

shouldn't your "reasoning" contain 21= 73 instead of 21=83 which is obviously false – eagle275 – 2020-01-13T14:07:31.773

@eagle275 Oops fixed. – Hood – 2020-01-13T19:40:20.320

Answers

16

J, 7,6 3 bytes

-1 byte thanks to FrownyFrog !

-3 bytes thanks to Grimmy!

*-+

Try it online!

     -    subtract
      +   the sum of the arguments
    *     from their product

Galen Ivanov

Posted 2020-01-11T00:46:56.077

Reputation: 13 815

2

3 bytes with *-+

– Grimmy – 2020-01-11T11:10:13.707

@Grimmy Great - this is much better! Thanks! – Galen Ivanov – 2020-01-11T11:57:09.087

2Seeing answers like this in J make me glad to lurk. – cole – 2020-01-12T20:38:23.677

2fails on the "not relative prime"-Example 6 f 15 which results in 69 – eagle275 – 2020-01-13T14:12:13.907

and 69 is wrong as it is 64+153 ^^ – eagle275 – 2020-01-13T14:23:58.400

1@@eagle275 it is undefined behavior, as stated in the OP – Galen Ivanov – 2020-01-13T14:50:24.763

well shouldn't J then show this - if you try the 05AB1E example - likewise 3 bytes , its working "correctly" by not giving a result for the 6,15 pair – eagle275 – 2020-01-13T15:36:45.810

@eagle275 6,15

– Galen Ivanov – 2020-01-13T15:42:53.500

10

Husk, 4 bytes

←¤*←

Try it online!

Explanation

As proved in lots of places, the answer for inputs a and b is ab-a-b = (a-1)(b-1)-1. ¤ is the 'combine' combinator, so ¤*← is a function that applies ← (decrement) to each argument and 'combines' the results by multiplication. Then I decrement the result to get the final output.

Sophia Lechner

Posted 2020-01-11T00:46:56.077

Reputation: 1 200

9

alephalpha

Posted 2020-01-11T00:46:56.077

Reputation: 23 988

9Because of course there's a builtin for that. – randomdude999 – 2020-01-11T10:36:32.557

6Is there a language that just has all the Mathematica builtins but as single characters? – Sam Dean – 2020-01-13T09:04:41.383

@SamDeann How would that be possible, assuming that the number of builtins is more than the number of characters? – Acccumulation – 2020-01-14T06:39:12.937

7

05AB1E, 3 bytes

<P<

Try it online!

<         # decrement both inputs
 P        # product
  <       # decrement

Grimmy

Posted 2020-01-11T00:46:56.077

Reputation: 12 521

4

Perl 6, 43 13 bytes

(*-1)*(*-1)-1

Try it online!

Turns out there's a much shorter way to calculate the answer.

Perl 6, 43 bytes

->\a,\b{max ^(a*b)∖((a X*^b)X+(^a X*b)):}

Try it online!

Jo King

Posted 2020-01-11T00:46:56.077

Reputation: 38 234

4

Python 3, 18 bytes

lambda a,b:a*b-a-b

Try it online!

Mukundan

Posted 2020-01-11T00:46:56.077

Reputation: 1 188

4

APL (Dyalog Unicode), 3 bytes

×-+

Try it online!

Dyadic train where a f b computes (a×b)-(a+b).

Jelly, 3 bytes

×_+

Try it online!

Dyadic link that takes two numbers a and b as left and right arguments. Works the same as the APL version, just with the symbol _ instead of - to represent subtraction.

Bubbler

Posted 2020-01-11T00:46:56.077

Reputation: 16 616

3

C (clang), 31 22 bytes

f(a,b){return~-a*b-a;}

Try it online!

Saved 9 bytes thanks to ceilingcat!!!

Noodle9

Posted 2020-01-11T00:46:56.077

Reputation: 2 776

3

Jelly, 3 bytes

P_S

Try it online!

A monadic link taking a pair of integers. Same method as most other answers (product minus sum).

Nick Kennedy

Posted 2020-01-11T00:46:56.077

Reputation: 11 829

3

Pyth, 5 bytes

-*FQs

Try it online!

Product minus sum.

t*FtM

Try it online!

a,b -> (a-1)*(b-1)-1

isaacg

Posted 2020-01-11T00:46:56.077

Reputation: 39 268

2

Pyth, 8 7 bytes

t*thQte

Try it online!

Uses the formula (a-1)(b-1) - 1. Takes input as a Python array of 2 integers.

-1 by using implicit appended Q

randomdude999

Posted 2020-01-11T00:46:56.077

Reputation: 789

@FryAmTheEggman: isaacg already posted that as a separate solution, so I don't think it's worth editing this one, given how it's a rather different approach. – randomdude999 – 2020-01-13T17:58:04.650

Ah, didn't see that, sorry! – FryAmTheEggman – 2020-01-13T19:04:26.620

2

C (gcc), 18 bytes

f(a,b){a=~-a*b-a;}

Noodle9's answer except using a= instead of return.

Try it online!

girobuz

Posted 2020-01-11T00:46:56.077

Reputation: 391

2

Java 8, 13 bytes

a->b->a*b-a-b

Try it online.

Explanation:

Similar as most other answers, it calculate the product minus the sum:

a->b->         // Method with two integer parameters and integer return-type
      a*b      //  Return the two parameters multiplied by each other,
         -a-b  //  after we've also subtracted both parameters from this product

Kevin Cruijssen

Posted 2020-01-11T00:46:56.077

Reputation: 67 575

2

Whitespace, 59 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Duplicate_input][S N
S _Duplicate_input][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
S _Duplicate_input][S T S S T   S N
_Copy_0-based_2nd][T    S S N
_Multiply_top_two][S N
T   _Swap_top_two][T    S S T   _Subtract_top_two][S N
T   _Swap_top_two][T    S S T   _Subtract_top_two][T    N
S T _Print_as_integer_to_STDOUT]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer a = STDIN as integer
Integer b = STDIN as integer
Integer c = a * b
c = c - a - b
Print c as integer to STDOUT

Not much golfing involved, except for using the first input as heap-address for the second input, since it's guaranteed to be positive and we push it to stack right away.

Kevin Cruijssen

Posted 2020-01-11T00:46:56.077

Reputation: 67 575

1

Shaggy

Posted 2020-01-11T00:46:56.077

Reputation: 24 623

1

Keg, 5 bytes

*¿¿+-

Simply a port of other answers. Uses latest github interpreter.

Lyxal

Posted 2020-01-11T00:46:56.077

Reputation: 5 253

1

Excel, 12 bytes

=A1*B1-A1-B1

Same approach as other answers.

Wernisch

Posted 2020-01-11T00:46:56.077

Reputation: 2 534

1

JavaScript (V8), 13 bytes

a=>b=>a*b-a-b

Try it online!

Same solution as other answers, I almost didn't post it but for once I found a question without a JS answer, so may as well. In fact this is the exact same as Kevin Cruijssen's answer, replacing Java's lambda -> with Javascript's =>. I've included a very basic testing framework in my TIO link so it does all the test cases. Most invalid inputs still execute.

Matsyir

Posted 2020-01-11T00:46:56.077

Reputation: 81

1

Brainf*ck, 36 bytes

Cell layout: cells 1 and 2 are input, cell 3 is where the final answer is built, cell 4 is auxiliary

,->,-<[->[->+>+<<]>>[-<<+>>]<<<]>>-.

Or, with words:

,-               read a and decrement
>                move to cell 2
,-               read b and decrement
<                move back to a
 [-              while a isn't 0, decrement once and
  >              move to b (to add b to cells 3 and 4)
  [-             decrement b
   >+>+<<        add 1 to cells 3 and 4, go back to b
  ]
  >>             move to cell 4
  [-<<+>>]       copy cell 4 to cell 2 (i.e. put b again in cell 2
 <<<             move back to a
 ]
>>-.             go to cell 3, decrement and output

Try it online - this is not a link to tio.run. In this site I linked I was able to give input as \02\05 so that I could try smaller test cases, and I also get a "memory dump" to check the weird characters that were printed actually correspond to the answer.

Here, have a tio.run link as well.

RGS

Posted 2020-01-11T00:46:56.077

Reputation: 5 047

1

AWK, 14 bytes

$0=$1*$2-$1-$2

Try it online!

Assumes input in the form of x y.

rootbeersoup

Posted 2020-01-11T00:46:56.077

Reputation: 111

0

R, 11 7 bytes

a*b-a-b

Where a and b are the 2 numbers.

Thanks to Jo King for pointing out my error.

Sam

Posted 2020-01-11T00:46:56.077

Reputation: 109

2Is this actually taking input, or is a a predefined variable (which is not allowed)? – Jo King – 2020-01-12T23:06:29.313

Ah good point @JoKing. I sometimes get confused with how to input the values on CG. Changed! – Sam – 2020-01-19T20:05:36.870

...I don't think this is any better is it? Now you're using two predefined variables? It should be prefixed with function(a,b) or something like that – Jo King – 2020-01-19T20:47:58.807

Asked: 2020-01-11T00:46:56.077

Viewed: 4 944 times

Active: 2020-01-29T03:14:37.690