16
\$\begingroup\$

Relatable scenario: I'm going to the store to buy a single item, but only have a $100k bill. As a result, I need exactly $99,979 in change, and in the fewest coins/bills possible because I'm quite obviously a very practical person.

The denominations of these coins/bills follow the hyperinflation sequence: \$1, 2, 5, 10, 20, 50, 100, 200\$, and so on.

(I'd proposed an OEIS sequence for this, but the first 100k terms are identical to another one so it got rejected)

Task:

Given an amount of money as a nonnegative integer, such as \$73\$, return the minimum number of coins/bills needed to total to that amount. In this example, it would be \$4\$. The coins required would be \$50 + 20 + 2 + 1\$.

As per the standard rules for , you can also choose to return all terms up to an inputted index, or return a (potentially infinite) lazy list or generator that represents the whole sequence.

Test cases:

0       0
1       1
2       1
3       2
4       2
5       1
6       2
7       2
8       3
9       3
10      1
11      2
20      1
30      2
37      4
90      3
111     3
147     5
1000    1
1002    2
1010    2
12478   9

Other:

This is , so shortest answer in bytes per language wins!

\$\endgroup\$
7
  • \$\begingroup\$ @RobinRyder Yes, sorry about that \$\endgroup\$ Apr 12 at 14:28
  • \$\begingroup\$ Very closely related, if not practically a duplicate: Minimally Making Change \$\endgroup\$
    – Etheryte
    Apr 12 at 14:31
  • 2
    \$\begingroup\$ @Etheryte The premise is similar, but the challenge is very different. I doubt the solutions to the two will be anywhere near similar. \$\endgroup\$ Apr 12 at 14:33
  • \$\begingroup\$ Can I take input as a list of digits? \$\endgroup\$ Apr 12 at 15:05
  • 1
    \$\begingroup\$ The store manager is going to get suspicious... \$\endgroup\$
    – emanresu A
    Apr 13 at 10:15

16 Answers 16

14
\$\begingroup\$

Husk, 11 9 8 bytes

Edit: -1 byte thanks to caird coinheringaahing

ṁo⌈½ṁB5d

Try it online!

       d   # get the digits
    ṁB5    # convert them all to base-5
           # (this gives a 1 for each 5-denomination coin needed,
           # as well as the leftover for each digit.
           # We'll need 2 more coins for those with leftover 3 or 4, 
           # and only one more coin if the leftover is 1 or 2.)
ṁo         # So: map across all the base-5 digits
   ½       # dividing each of them by 2
  ⌈        # and then getting the ceiling;
           # and finally output the sum
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 8 bytes, using ceiling and halve rather than increment and integer divide \$\endgroup\$ Apr 12 at 17:59
  • \$\begingroup\$ @cairdcoinheringaahing - Nice! Thankyou very much! \$\endgroup\$ Apr 13 at 9:17
14
\$\begingroup\$

JavaScript (ES7),  36  35 bytes

Similar to other answers. Using a Black Magic formula instead of a lookup table.

f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

Try it online!

Here is a script that looks for \$(p,m)\$ pairs such that \$(n^p\bmod m)\bmod 4=a_n\$ for all \$n\in[0..9]\$.

It's worth noting that this code takes IEEE-754 precision errors into account. So the results are correct but the math is wrong.

With exact values, we could do instead:

$$\big((n \bmod 10)^{18}\bmod 4011\big)\bmod 4$$

Or better yet, as suggested by @dingledooper:

$$\big((n \bmod 10)^{55}\bmod 767\big)\bmod 4$$

For instance, in Python:

Python 2, 40 bytes

f=lambda n:n and(n%10)**55%767%4+f(n/10)

Try it online!


JavaScript (ES7), 71 bytes

Expects the amount as a string.

A naive recursive approach that subtracts one coin/bill at a time.

n=>(k=10**n.length,g=t=>+n?k>n?g(t,k/=~++i%3?2:2.5):g(t+1,n-=k):t)(i=0)

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ In Python, I think (n%10)**55%767%4 is 1 byte shorter. \$\endgroup\$ Apr 12 at 18:13
  • \$\begingroup\$ @dingledooper Weird. This was within my search bounds but I guess I simply didn't notice it. Thank you! \$\endgroup\$
    – Arnauld
    Apr 12 at 18:29
  • 1
    \$\begingroup\$ "How can you find the black magic (n%10)**55%767%4 that is equivalent to the [0123456789] -> [0112212233] lookup table?" - asked by jolreal, who doesn't have enough reputation to comment \$\endgroup\$ Apr 13 at 12:11
  • \$\begingroup\$ I used n/5%2-n%5/-2 in my Python answer, can that be profitably adapted to JS? \$\endgroup\$
    – xnor
    Apr 13 at 21:05
  • \$\begingroup\$ @xnor Unfortunately, I don't think it's as interesting in JS that it is in Python. By using BigInts to force integer division, the best I can think of so far is 35 bytes as well. \$\endgroup\$
    – Arnauld
    Apr 13 at 21:49
10
\$\begingroup\$

Haskell, 5541 40 bytes

  • -1 byte thanks to xnor, for using a string instead of the hard-coded list.
a=0:tail[i+read[j]|i<-a,j<-"0112212233"]

Try it online!

a is the infinite sequence.

How?

It's not hard to find the recursive formula $$ a(n)=a\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+a(n \operatorname{mod} 10) $$ with the base cases for \$n\in\{0,\ldots,9\}\$ given by $$ [0,1,1,2,2,1,2,2,3,3]. $$

This means that the infinite list a satisfies the equality

a==[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

Now, Haskell is magical, but not magical enough to compute a from the definition

a=[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

However, giving the first term explicitly is enough:

a=0:tail[i+j|i<-a,j<-[0,1,1,2,2,1,2,2,3,3]]

The 40-bytes code above is equivalent to this, but shorter.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Nice recursive list! Looks like compressing the hardcoded list to a string breaks ahead: TIO \$\endgroup\$
    – xnor
    Apr 12 at 19:28
8
\$\begingroup\$

R, 54 51 47 45 bytes

Edit: converted to console input instead of a full function to try not to fall behind Robin Ryder's answer

d=utf8ToInt(scan(,''))-48;sum(d>0,d>5,d%%5>2)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Well done! I'm not giving up yet… \$\endgroup\$ Apr 12 at 17:28
  • \$\begingroup\$ It's a tie! \$\endgroup\$ Apr 13 at 18:44
7
\$\begingroup\$

Jelly, 7 bytes

Db5FHĊS

Try it online!

Steals Ports Dominic Van Essen's Husk answer, be sure to upvote that!

How it works

Db5FHĊS - Main link. Takes an integer n on the left
D       - Convert to digits
 b5     - Convert each digit to base 5
   F    - Flatten
    H   - Halve each
     Ċ  - Ceiling of each
      S - SUm

Jelly, 11 bytes

Dị“FȮŀO’D¤S

Try it online!

How it works

Dị“FȮŀO’D¤S - Main link. Takes n on the left
D           - Convert n to digits
         ¤  - Create a nilad:
  “FȮŀO’    -   Compressed integer: 1122122330
        D   -   To digits
 ị          - Index into the digits of this integer
          S - Sum
\$\endgroup\$
7
\$\begingroup\$

R, 64 52 50 45 bytes

sum(c(1,2,1:3)[.6*utf8ToInt(scan(,""))-28.4])

Try it online!

Same strategy as Delfad0r's Haskell answer, which is nicely explained.

First, scan(,"") reads in input as a string. Then, utf8ToInt(...)-48 takes a string of digits and converts it to a vector of integer digits. This works out shorter than taking input as an integer and splitting it into digits.

The digits from 0 to 9 then have to be mapped to the vector c(0,1,1,2,2,1,2,2,3,3). To do this, consider the vector a=c(1,2,1,2,3). For digit d, a[.4+d*.6] is the value we want. This uses the fact that when calling a non-integer index in a vector (say a[2.8]), R rounds down the index (here a[2]), and also the fact that a[0] returns NULL which will be ignored in the sum.

Putting this operation with the operation to convert the string to digits simplifies to .6*utf8ToInt(...)-28.4.

Note that Dominic van Essen has a solution of (currently) the same length with a different strategy.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ <s>Bah!</s> Nice work! \$\endgroup\$ Apr 12 at 15:41
  • \$\begingroup\$ Your solutions are getting more and more esoteric! \$\endgroup\$
    – Xi'an
    Apr 14 at 6:40
  • \$\begingroup\$ This is a very, very clever solution! Well done! Much better than mine (even if the bytes are the same). I'm very jealous... and (despite trying for too long last night) I don't think I'll be able to bet mine any shorter... \$\endgroup\$ Apr 14 at 10:48
6
\$\begingroup\$

05AB1E, 11 bytes

S<•δ¬Èº•sèO

Try it online!

Same approach as my Jelly answer.

How it works

S<•δ¬Èº•sèO - Program. Input: n
S           - Cast n to digits
 <          - Decrement
  •δ¬Èº•    - Compressed integer: 1122122330
        sè  - Using n's digits, index into the digits of 1122122330
          O - Sum

Kudos to Kevin Cruijssen's excellent integer compressor!

\$\endgroup\$
3
  • \$\begingroup\$ A port of the Husk answer is also shorter in 05AB1E: S5δв˜;îO. And can be another byte shorter in the legacy version of 05AB1E by removing the leading S. \$\endgroup\$ May 4 at 13:09
  • \$\begingroup\$ @KevinCruijssen You're welcome to post that if you'd like, I'm going to keep this as the digit lookup approach \$\endgroup\$ May 4 at 13:11
  • \$\begingroup\$ It's basically the same as your top Jelly answer, but sure, I'll post it as a separated answer. \$\endgroup\$ May 4 at 13:12
4
\$\begingroup\$

Husk, 23 bytes

L◄Lfo=⁰Σ↑o≤⁰LṖƒ(+İ€m*10

Try it online!

Extremely slow past 11.

Explanation

L◄Lfo=⁰Σ↑o≤⁰LṖƒ(+İ€m*10
              ƒ(        create an infinite list using:
                 ݀     currency denomination builtin: [1,1/2,1/5,...200]
                +       plus
                   m*10 the input mapped to *10
                        this gives [1,1/2,...100] + 10*([1,1/2,...100] + (10*[1,1/2,...100]...))
             Ṗ          powerset(unordered)
        ↑o≤⁰L           take all sequences which have length ≤ input
                        this makes sure everything till [1]*n is in the list
   fo=⁰Σ                filter out the ones which do not sum to the input
 ◄L                     maximum element by length
L                       take the length
\$\endgroup\$
4
  • 3
    \$\begingroup\$ "currency denomination builtin"? Seriously? :P \$\endgroup\$
    – Delfad0r
    Apr 12 at 15:11
  • \$\begingroup\$ yep, "Euro coin and bill values" :P \$\endgroup\$
    – Razetime
    Apr 12 at 15:16
  • \$\begingroup\$ This would seem to be the perfect challenge for the 'currency denomination builtin', and yet... \$\endgroup\$ Apr 12 at 15:26
  • \$\begingroup\$ @DominicvanEssen I figured there was a much better method, looking at all the non golflang answers. (I just couldn't pass up using fix) \$\endgroup\$
    – Razetime
    Apr 12 at 15:28
4
\$\begingroup\$

Wolfram Language (Mathematica), 39 bytes

⌈.4#⌉-⌊#/5⌋&@*IntegerDigits/*Tr

Try it online!

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

Python 2, 37 bytes

f=lambda n:n and n/5%2-n%5/-2+f(n/10)

Try it online!

Uses a formula rather than a lookup table for each digit. n/5%2 counts the five-cent coin, and subtracting -n%5/-2 is equivalent to adding (n%5+1)/2 for the one- and two-cent coins.

n%10      0 1 2 3 4 5 6 7 8 9
-----------------------------
n/5%2     0 0 0 0 0 1 1 1 1 1
0-n%5/-2  0 1 1 2 2 0 1 1 2 2
Total     0 1 1 2 2 1 2 2 3 3
\$\endgroup\$
3
\$\begingroup\$

C (gcc), 39 bytes

f(n){n=n?f(n/10)+""[n%10]:0;}

Try it online!

JavaScript (Node.js), 37 bytes

f=n=>n&&+"0112212233"[n%10]+f(n/10|0)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Golfed your JS one: f=n=>n&&+"311221223"[n%9]+f(n/10|0) \$\endgroup\$ Apr 12 at 15:02
  • \$\begingroup\$ @RedwolfPrograms How does that work? \$\endgroup\$
    – l4m2
    Apr 12 at 15:04
  • \$\begingroup\$ Oh wait, it doesn't. Sorry about that (forgot n%10 can be 0 with n being nonzero) \$\endgroup\$ Apr 12 at 15:04
3
\$\begingroup\$

Python 2, 48 bytes

f=lambda x:x and int("0112212233"[x%10])+f(x/10)

Try it online!

49 bytes in Python 3 because you'd need // for floor division.

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

Charcoal, 13 bytes

IΣ⭆S⭆↨Iι⁵L↨λ³

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

   S            Convert input to a string
  ⭆             Map over characters and join
       ι        Current character
      I         Cast to integer
     ↨  ⁵       Convert to base 5
    ⭆           Map over base 5 digits and join
           λ    Current digit
          ↨ ³   Convert to base 3
         L      Take the length
 Σ              Take the (digital) sum
I               Cast to string
                Implicitly print

Table of base 5 digit to base 3 length:

Decimal Base 3 Length
0       []     0
1       [1]    1
2       [2]    1
3       [1, 0] 2
4       [1, 1] 2
\$\endgroup\$
3
\$\begingroup\$

Vyxal, d, 5 bytes

5vτ½⌈

Try it Online!

A port of the Jelly answer which is a port of short husk answer.

Explained

5vτ½⌈
5vτ   # convert each digit of the input to base 5
   ½  # halve each item in that list (halving vectorises all the way down)
    ⌈ # ceiling each item in that list
      # -d deep sums the list and implicitly outputs
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 20 15 bytes

.
$*1,
1{5}|11?

Try it online! Link includes test cases. Explanation:

.
$*1,

Convert each digit to unary separately.

1{5}|11?

Count the number of 5s, 2s and 1s needed to make each digit.

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

05AB1E (legacy), 7 bytes

5δв˜;îO

Port of @Dominic van Essen's Husk answer, so make sure to upvote him as well!

Uses the legacy version of 05AB1E to get rid of a leading S that would be required in the new version of 05AB1E in this case, due to the way the δ acts on strings/integers.

Try it online or verify all test cases.

Explanation:

 δ       # Map each digit in the (implicit) input-integer to:
5 в      #  A base-5 list
   ˜     # Flatten this list of lists
    ;    # Halve each integer
     î   # Ceil each float
      O  # Sum the integers in the list together
         # (after which the result is output implicitly)
\$\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.