Change for a dollar? I’ve got three ways to help you with that (i.e., the Coin Changer Kata)

I worked on another fun kata this week – the Coin Changer kata.

How it Works: Given a certain amount of cents, the algorithm should return the most efficient change equivalent to that amount. For example, if you need to get back $0.89, you should receive 3 quarters, 1 dime, and 4 pennies.

Solution #1: Hello TDD

I started out simple–my favorite advantage of TDD so far–by solving for an empty array [ ], an array with just one penny [1], and an array with multiple pennies [1,1,1]. I quickly realized there was a pattern developing (which was very similar to the Roman Numeral Kata). With the help of TDD, I was able to come up with the following algorithm quickly. It loops through each coin and adds the appropriate number of coin to the coins_returned array:

def get_change(remaining_cents)
	coins_returned = []
	[25, 10, 5, 1].each do |coin|
		while remaining_cents >= coin
			coins_returned << coin
			remaining_cents -= coin

Solution #2: Let’s use math

My mentor Ryan challenged me to think about other ways to complete the kata. He wanted me to try and solve it without using loops. But before I arrived at the loop-free solution, I came up with the following…

How do I actually make the correct change in my head? I quickly solve for the number of necessary coins with division and subtraction, right? For $0.89, I quickly think.. “okay .89/.25 = 3. Then I’m left with .14 and .14/.10 = 1. Then I’m left with .04 and .04/.01 = 4. So that ends up being 3 quarters, 1 dime, and 4 pennies.” I tried to replicate this thought process to see what the code would look like. This is what I came up with:

def change_amount(remaining_cents)
	coins_returned = []
	[25, 10, 5, 1].each do |coin|
		(remaining_cents/coin).times { coins_returned << coin }
		remaining_cents -= (coin * (remaining_cents/coin))

Solution #3: Can't use a loop? Try recursion.
So like I said, my mentor wanted me to do the Coin Changer kata sans looping. Say whaaat? Yeah, how Iam I going to do that?

After a few people told me I should think about using recursion and googling it for a while, I finally began to understand what they were talking about.

Here is a user-friendly definition in the words of a StackOverflow genius: A recursive method calls itself. For a recursive algorithm to terminate you need a base case (e.g. a condition where the function does not call itself recursively) and you also need to make sure that you get closer to that base case in each recursive call.

After much trial and error with TDD, I arrived at the solution below. You'll see that my base case is when remaining_cents is equal to zero. In order to get closer to the base case, I add coins to the coin_array once I check to see if each coin in the demoninations array is needed, I eliminate that coin in the denominations array once I'm done with it, and then I subtract from remaining_cents.

def change_amount(cents)
	get_change(cents, [], [25,10,5,1])

def get_change(remaining_cents, coin_array, denominations)
	return coin_array if remaining_cents == 0

	current_coin = denominations[0]
 	remaining_denominations = denominations.drop(1)

 	if remaining_cents >= current_coin
 		number_of_coins = remaining_cents/current_coin
 		remaining_cents -= (number_of_coins * current_coin)
 		get_change(remaining_cents, add_items_to_array(coin_array, number_of_coins, current_coin), remaining_denominations)
 		get_change(remaining_cents, coin_array, remaining_denominations)

def add_items_to_array(current_array, number_of_items_to_add, item)
	number_of_items_to_add.times {current_array << item}
	return current_array

While the last solution was the most challenging and the most rewarding, and although it actually reads pretty nicely, I'm not sure it makes the most sense for this kata. The first two are much more efficient. However, I'm sure this new recursion knowledge will come in handy many times on my coding journey...

Leave a Reply

Your email address will not be published.