14
\$\begingroup\$

Introduction

You have a friend that keeps asking you for loans and you are getting tired of it. Today, he came for a loan again. Instead of turning down his offer, you get a great idea: troll your friend by giving him as many coins/bills as possible.

Challenge

You will take as input: the amount of money your friend wants a loan for and the amount of coins/bills you have. For this challenge, the possible denominations are $20.00, $10.00, $5.00, $2.00, $1.00, $0.25, $0.10, $0.05, and $0.01. An example of input is 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2] if you friend wants $5.67 and you have 5 $20 bills, 3 $10 bills, etc. Your output will be the amount of coins/bills that gives your friend as much metal/paper/plastic as possible.

If it is not possible to give your friend the exact amount of money he wants, give him the closest amount of money you can pay that is greater than what he wants. For example, if your friend wants $0.07 but you only have [0, 0, 0, 0, 0, 2, 4, 2, 0], give him 2 $0.05 coins (not 1 $0.10 because that wouldn't be giving him as many coins as possible!).

If your friend wants more money than you have, give him all your money (and pray you won't need to buy anything).

Test cases

Input:  6.54, [9, 8, 7, 6, 5, 4, 3, 2, 4]
Output: [0, 0, 0, 1, 4, 1, 2, 1, 4]

Input:  2, [0, 1, 0, 0, 0, 0, 0, 0, 0]
Output: [0, 1, 0, 0, 0, 0, 0, 0, 0]

Input:  9999, [0, 0, 0, 0, 0, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 1]

Input:  0, [99, 99, 99, 99, 99, 99, 99, 99, 99]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]

This is so shortest code wins.

\$\endgroup\$
6
  • \$\begingroup\$ You have 2.00 and 20.00 but no 0.2 or 0.02 :( \$\endgroup\$
    – Mr. Xcoder
    Dec 24, 2017 at 15:48
  • 3
    \$\begingroup\$ @Mr.Xcoder many challenges uses very arbitrarily chosen currency systems. We might want to make a meta to decide whether currency related challenges should determine their own system, have a single universal system agreed upon, allow the usage of several systems or even make all this challenges to also support the system as input, although that might result in input-validation symptoms for some langauges \$\endgroup\$
    – Uriel
    Dec 24, 2017 at 15:58
  • \$\begingroup\$ @Mr.Xcoder Perhaps you're thinking of two-dollar bills? I was thinking toonies. \$\endgroup\$
    – ericw31415
    Dec 24, 2017 at 16:28
  • \$\begingroup\$ Do our answers need to run for all inputs, just for the ones posted, or can they work for small inputs, but fail for the 4th one? \$\endgroup\$
    – jrtapsell
    Dec 27, 2017 at 13:11
  • \$\begingroup\$ @jrtapsell Input 4 shouldn't cause problems though? 99 is generally a small enough number. \$\endgroup\$
    – ericw31415
    Dec 27, 2017 at 14:19

3 Answers 3

3
\$\begingroup\$

Clean, 167 bytes

import StdEnv
@n l#m=[p\\p<-[[if(y==u)(x-1)x\\x<-l&y<-[0..]]\\u<-[0..]&v<-l|v>0]|sum[a*b\\a<-[2000,1000,500,200,100,25,10,5,1]&b<-p]>=toInt(n*100.0)]
|m>[]= @n(hd m)=l

Defines the function @, taking Real and [Int].

Try it online!

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

JavaScript, 213 Bytes

x=>y=>(F=(x,y,z,u=9)=>u--?[...Array(y[0]+1)].map((_,i)=>F(x-i*[1,5,10,25,100,200,500,1e3,2e3][u],y.slice(1),[...z,i],u))&&G:x>0||G.push([z,x-1/eval(z.join`+1+`)]),F(x*100,y,G=[]).sort((a,b)=>b[1]-a[1])[0]||[y])[0]

It's pretty slow and cost memory, so only try small cases

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

Kotlin, 298 bytes

{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)

Beautified

        { t, c ->
            with(c.fold(listOf(listOf<Int>())) { o, x ->
                o.flatMap { a -> (0..x).map { a + it } } /* Get all of the options. */
            }.groupBy { it.zip(C).map { (a, b) -> a * b }.sum() }
                .mapValues { (_,b)->b.maxBy { it.sum() }!! }
                .toSortedMap().asSequence()) {
                firstOrNull { it.key == t } ?:
                        firstOrNull { it.key > t } ?:
                        last()
            }.value
        }
val C = listOf(20.0, 10.0, 5.0, 2.0, 1.0, 0.25, .1, .05, .01)

Test

val calc: (target: Double, coins: List<Int>) -> List<Int> =
{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)

data class Test(val target: Double, val input: List<Int>, val output: List<Int>)

val tests = listOf(
        Test(2.0, listOf(0, 1, 0, 0, 0, 0, 0, 0, 0), listOf(0, 1, 0, 0, 0, 0, 0, 0, 0)),
        Test(9999.0, listOf(0, 0, 0, 0, 0, 0, 0, 0, 1), listOf(0, 0, 0, 0, 0, 0, 0, 0, 1)),
        Test(6.54, listOf(9, 8, 7, 6, 5, 4, 3, 2, 4), listOf(0, 0, 0, 1, 4, 1, 2, 1, 4)),
        Test(0.0, listOf(99, 99, 99, 99, 99, 99, 99, 99, 99), listOf(0, 0, 0, 0, 0, 0, 0, 0, 0))
)

fun main(args: Array<String>) {
    for (t in tests) {
        if (t.output != calc(t.target, t.input)) {
            throw AssertionError()
        } else {
            println("Passed")
        }
    }
}

Example 4 causes OutOfMemory, but the other 3 work well.

\$\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.