• Articles
    • Popular
  • Katas
    • Get Started
  • Subscribe
  • Github Sign in with Github

Craftsmanship

Reviewed katas for software excellence
Shore_198

←Older posts
Newer posts→
New Kata

Coin Change Kata

Updated on May 05, 2013 by Todd Sedano 459
Rating:   

Challenge Level: Low
Category: Others
Suggested Categories: Test Driven Development Algorithmic Complexity Dynamic Programming

Source: Todd Sedano

 

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
 
 

 

32 Reviews

32 Reviews

Upvote 3 Downvote

Either extremely easy or impossible to solve

Rating:    Challenge Level: Low Programming Language: Ruby

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 kaushikgopal192

Upvote 3 Downvote

An inspiring starter for DP

Rating:    Challenge Level: Low Programming Language: C++

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 lakeskysea247

Upvote 1 Downvote

no title

Rating:    Programming Language: Javascript

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

Upvote 1 Downvote

Tricky and interesting kata

Rating:    Challenge Level: High Programming Language: Java
Suggested Categories: Dynamic Programming    

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 oscaralvaro162

Upvote 1 Downvote

Easy but can get complex

Rating:    Challenge Level: High Programming Language: C++

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 Madhok30

Upvote 1 Downvote

There are two sides to this Kata

Rating:    Challenge Level: Medium Programming Language: Java
Suggested Categories: Test Driven Development    

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 fortner25

Upvote 1 Downvote

no title

Rating:    Programming Language: Javascript

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

Upvote 1 Downvote

Easy to test

Rating:    Challenge Level: Medium Programming Language: Python

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 Niyungeko88

Upvote 1 Downvote
Rating:    Challenge Level: High Programming Language: python

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 lydian79

Upvote 1 Downvote

Easy but worth it!

Rating:    Challenge Level: Low Programming Language: Dart

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 Hennessy200

Upvote 0 Downvote

Not as Easy as It Seems to Be

Rating:    Challenge Level: Low Programming Language: Java

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 Xin111

Upvote 0 Downvote

Nice twist

Rating:    Programming Language: Javascript

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

Upvote 0 Downvote

no title

Rating:    Programming Language: Javascript

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

Upvote 0 Downvote

Easy and fun!

Rating:    Challenge Level: Low Programming Language: C++

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 VidyaPissaye63

Upvote 0 Downvote

Practicing the red/green/refactor mantra

Rating:    Challenge Level: Low Programming Language: C++
Suggested Categories: Test Driven Development    

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 Owen104

Upvote 0 Downvote

Easy but needs caution.

Rating:    Challenge Level: Low Programming Language: Java
Suggested Categories: Test Driven Development    

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 seanxiaoxiao99

Upvote 0 Downvote

no title

Rating:    Programming Language: Javascript

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

Good practice for TDD

Rating:    Programming Language: Ruby

 

Updated on Feb 26, 2013 by nehasinha

Upvote 0 Downvote

Easy but good for TDD

Rating:    Challenge Level: Low Programming Language: Ruby

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 Kumar227

Upvote 0 Downvote

Good Kata!

Rating:    Challenge Level: Medium Programming Language: C#
Suggested Categories: Test Driven Development    

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 ZhipengLi32

Great exercise for TDD

Rating:    Programming Language: Javascript

 

Updated on Feb 26, 2013 by Himani

Classical algorithm problem suitable for practicing DP.

Rating:    Programming Language: Javascript

 

Updated on Feb 26, 2013 by evivrus

Upvote 0 Downvote

Simple but worth it!

Rating:    Challenge Level: Low Programming Language: Java

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 singhprabhjot54

Upvote 0 Downvote

Simple, but a good starting point for TDD

Rating:    Challenge Level: Low Programming Language: Objective-C
Suggested Categories: Test Driven Development    

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 kateliu70

Upvote 0 Downvote

Easy but difficult!

Rating:    Challenge Level: Medium Programming Language: Java

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 shamahoque109

Upvote 0 Downvote

Hidden complexity

Rating:    Challenge Level: Medium Programming Language: C++
Suggested Categories: Test Driven Development    

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 RashmiDR30

Upvote 0 Downvote

Coin Changer

Rating:    Challenge Level: Medium Programming Language: Java

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 davliu70

Upvote 0 Downvote

Another good kata for one to consider test case coverage and complexity

Rating:    Challenge Level: Medium Programming Language: JavaScript

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 Li89

Upvote 0 Downvote

no title

Rating:    Programming Language: C++

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

Upvote 0 Downvote

Good for TDD in simple case but can get crazy for edge cases

Rating:    Challenge Level: Medium Programming Language: Ruby
Suggested Categories: Algorithmic Complexity     Test Driven Development    

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 pfeffed35

Upvote 0 Downvote

Realized that kata wasn't so simple

Rating:    Programming Language: Clojure5

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

It was a very simple exercise and could be used as a primer for TDD.

Rating:    Programming Language: Python

 

Updated on Feb 26, 2013 by Nishith Nand

Please sign in to review.

Sign in with Github
Carnegie Mellon University - Silicon Valley
Rss-news
Powered by Hibiscus.