Reviewed katas for software excellence

You've just created a virtual vending machine that will dispense widgets of programming goodness when a user puts money into the machine. The machine should dispense the proper change. You now need the programming logic to determine which coins to dispense.

Write a program that will correctly determine the least number of coins to be given to the user such that the sum of the coins' value would equal the correct amount of change.

Input: change amount

Input: coin denomination array (ie [1, 5, 10, 25, 100] )

Output: number of coins array (ie [1, 0, 1, 0, 0] would represent $0.11

For example

An input of 15 with [1, 5, 10, 25, 100] should return fifteen cents or [0, 1, 1, 0, 0]

An input of 40 with [1, 5, 10, 25, 100] should return two dimes or [0, 1, 1, 1, 0]

Part of the challenge with this exercise is to think through your testing strategy. Do you test every possible input for the change amount, or do you test specific boundary cases?

Use Test Driven Development (TDD) to solve this problem. Start writing tests, write enough code to get the tests to pass, and then refactor your code. Allow your design to emerge from writing tests; don't try to solve the problem first.

If you prefer to return a hash instead of am array, that's ok too. {1 => 1, 5 => 0, 10 => 1, 25 => 0, 100 => 0} equals $0.11

I've got really mixed feelings about this one. The question though is not "if I should do this kata", the question is "when should i do this kata?". If denomination array is fixed, my review is as follows: + Kata is pretty darn simple + Great for a beginner trying to get acquainted with a language. + I see great value in this Kata for refactoring (got my code to almost 1/3rd the original number of lines) - I don't particularly see the value of TDD here, as the tests were pretty basic. Oddly, I landed up feeling a little depressed after doing this Kata primarily because the problem was relatively simple and I didn't come up with more elegant code in the first shot ( I mean the Kata is pretty straightforward). The only reason I chose to refactor, was because I thought there was a catch somewhere. In a real work life environment, if i had passing green tests I would have just went on with my first version of the code. I really had to force myself to rethink and refactor the code. If denomination array is not fixed, my review is as follows: This is a miserably hard problem. I would just do the potter kata twice (from scratch) than attempt this one. Insanely difficult and not even sure if all the combinations can be solved.

Updated on May 06, 2013
by
kaushikgopal**202**

A very interesting and classic DP problem. (I started this kata in a DP category so that's the way I followed). A normal DP problem usually suggests recursion. But recursion encountered difficulties here because there are just too many possibilities from S(n-1) to S(n), and a plenty of them are repeated. Going from the other direction makes the algorithm much cleaner. And that's what makes this kata interesting.

Updated on May 05, 2013
by
lakeskysea**247**

It can be interesting if you notice the complexity, like the Potter kata. It has a similar solution though so I would chose one or the other, not necessarily both. I had done the Potter kata before and I took pretty much the same approach Some test cases take too long to finish because I didn't implement memoization for the DP approach. I did in the interest of time and focusing on my learning objective (TDD)

Updated on Feb 26, 2013 by Kristoffer Pantic

At the beginning, this kata looked very simple to solve with a greedy method. However, while I was solving it, I got a hunch that maybe there was some cases where the solution fails to provide the optimum set of coins. But I didn't pay too much attention and solve with the greedy method. This kata taught me that I have to be more careful when solving and algorithm and to pay attention to the edge cases.

Updated on May 05, 2013
by
oscaralvaro**162**

The problem seemed to be easy at the beginning. However, it became complicated when denominations changed to different values. For example, if the denominations changed to [1,10,15,25,100] and the input change amount is $1.21, the output should be [1,2,0,0,1] rather than [6,0,1,0,1]. This is because the vending machine should provide minimum number of coins. Using TDD to solve the problem was fun,but I could not find solution for all inputs of coin denomination.

Updated on May 05, 2013
by
Madhok**30**

There are two sides to this Kata; simple and complex. You can solve this using the simple "greedy" solution by using normal coin sets. This is still moderately difficult and you need to think about different test coverage to make sure your algorithm works. The complex side of this Kata is allowing any kind of coin set and designing an algorithm that will work on something like [1, 5, 15, 20, 25], which would fail using the "greedy" method. For a greater challenge, solve this set and build test cases for it.

Updated on May 05, 2013
by
dan fortner**25**

It can be interesting if you notice the complexity, like the Potter kata. It has a similar solution though so I would chose one or the other, not necessarily both.

Updated on Feb 26, 2013 by Kristoffer Pantic

This Kata is a typical candidate to solve using a greedy algorithm. The test for that, as the problem statement warns, is tricky. I chose a test based on a mathematical proof. Check it out at: https://github.com/Aristide1o/python_kata/blob/master/coin_changer.py ... after you finish doing the Kata on your own of course :)

Updated on Feb 25, 2013
by
Aristide Niyungeko**88**

I think the difficult part of this algorithm is not to implement it, but to think of the edge test cases. Therefor I search online and find a special cases. The kata itself is a very famous algorithm questions, and having different variations. For people who tried this kata, I would recommend also try the variation, too.

Updated on May 05, 2013
by
lydian**79**

The kata was pretty easy, but it gave me plenty to think about in terms of code readability. I refactored my dispense method into several smaller methods in order to create even levels of abstraction. The kata was fun and helped me learn about my language's collection API.

Updated on May 05, 2013
by
Mark Hennessy**200**

If we haste to solve it with DP and greedy algorithm, it is very possible that we will get the incomplete solution. A few tricky cases should be noticed. For example, how about the case that the dominations are {2, 4} but the change is 5? There is no solution for this case. It should be handled properly. We need to spend more time on thinking test cases before we start solve the problem.

Posted on Feb 25, 2013
by
Minjie Xin**111**

It has a neat twist when you figure out greedy approach doesn't work. I had an ah-hah moment was realizing the greedy approach didn't work.

Updated on Feb 26, 2013 by trevor-umeda

Its a good activity and very similar to Potter Kata. However, in the beginning I misunderstood the problem and followed greedy approach.

Updated on Feb 26, 2013 by charuaggarwal

The kata was easy and fun to solve. A good candidate for TDD especially for beginners in TDD because the kata can be solved one test case at a time to arrive at the final solution.

Posted on Feb 21, 2013
by
VidyaPissaye**63**

This kata is excellent for practicing the red/green/refactor mantra because its setting allows us to start from the most basic test cases and build our solution up from there. At certain point, we'll figure out that the if statements here and there are not necessary and put on the refactoring hat. PS. I wonder if the generalized version of this problem (i.e. arbitrary coin denomination array such as [2, 3, 7, 9, 13]) is still a good candidiate for practicing TDD?

Posted on Feb 24, 2013
by
Owen**104**

This is a very easy kata. However, it may have some traps when considering some edge cases. Such as if the coins value are not in order, or two coins have the same value in the input. Anyway, it is a good kata to practice TDD. I really enjoy doing it.

Posted on Feb 25, 2013
by
seanxiaoxiao**99**

It was a simple TDD kata, easier than Potter. It helped me take baby steps. I Learned a lot about the different data structures i had to use.

Updated on Feb 26, 2013 by swapnavarghese

It is a relatively easy problem, but if you do it in TDD, it has numerous opportunity to improve the design of the code.

Posted on Feb 26, 2013
by
Sumeet Kumar**227**

If we only consider the given set of coins, then this Kata is rather easy and almost everyone can give a quick solution. However, if we change the set of coins to some special cases, and then choose a special total, then this problem becomes as interesting as the Potter Kata. Overall, this is a good Kata for Test Driven Development practice.

Posted on Feb 26, 2013
by
ZhipengLi**32**

Updated on Feb 26, 2013 by evivrus

The kata is not hard but worth doing it. It is fun solving this kata as writing test cases comes out be tricky.

Posted on Feb 26, 2013
by
singhprabhjot**54**

This kata is simple, but worth doing it. It is a good starting point for TDD because its solution is easy and you know exactly what you are testing for. Also, you can further practice refactoring your code after your first draft is done. Your test cases will provide you a degree of confidence to do so.

Posted on Feb 26, 2013
by
kateliu**70**

This problem seemed straight forward when I started solving it with the given set of examples, and it didn't take too long to get the tests to pass. But after I took into consideration that denominations can be anything, writing tests to ensure my algorithm was finding the minimum number of coins for all possible combinations became very difficult.

Posted on Feb 26, 2013
by
shamahoque**109**

It is easy if the denominations are fixed and gets incredibly tough if the denominations vary. This kata gives a good start for learning TDD. I recommend this kata as a first step towards learning TDD.

Posted on Feb 26, 2013
by
RashmiDR**30**

At first, it seemed like a very straightforward problem, but then it felt TOO straightforward. That was when the comprehensive test cases came into play. This kata DOES help in writing better test cases. HINT: Try different coin sets!!!

Posted on Feb 28, 2013
by
davliu**70**

Like the Potter kata, this kata seems to be straightforward at first, but turns out to be one with some complexity if your test cases have a good coverage on all possible scenarios. Nevertheless, there are still several ways to solve this kata, just make sure that you have done something to prevent your algorithm from doing pure brute-force.

Posted on Mar 02, 2013
by
Clyde Li**89**

This is a good example for dynamic programming. I created an two dimensional array to save the results. At first, I misunderstood the requirement for this kata. I simply solved this kata by greedy approach. And recursive solution is too time consuming.

Updated on Feb 26, 2013 by CarinaZheng

This exercise is what you make of it. My goal for it was to practice TDD. I designed a greed solution that works for every real world coin system I tried (US, Euro, and a few others); however, it is limited in that each coin must be at least twice as large as the next smallest coin. For example, this condition holds for the US coins 1, 5, 10, 25, 50, 100 and euro coins 1, 2, 5, 10, 20, 50, 100, 200. My solution does not work when this condition is violated - for example, 1,3,4 making 6 cents. Because my algorithm is greedy, it would choose 4, 1, 1, which is 3 coins rather than the correct solution of two 3 cent coins. Because my focus was to practice TDD rather than writing an elegant algorithm to solve the problem, I let it as is. I think the flexibility of this kata to let the coder take it as far as he wants to makes it a great option for people at all skill levels. I highly recommend it. Also, you'll never look at a vending machine the same ever again!

Posted on Apr 23, 2013
by
pfeffed**35**

When I first did this kata, I didn't consider strange sets of coins. Initially, I thought this was too simple, as I only did the greedy strategy. Now I think this will be worth doing after all.

Updated on Feb 26, 2013 by Isak Sky

Updated on Feb 26, 2013 by Nishith Nand