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
This kata fictionalizes the experience of working with someone else's code. You'll probably groan when you first see the code provided to you. The amount of code isn't overwhelming, its the prefect balance to evoke the feeling, "I can't wait to re-write this cruft." It's suggested that you use Test Driven Development with this kata. Once done, read the **spoiler** section below to see if you had a similar experience or not.
Original posting: http://iamnotmyself.com/2011/02/13/refactor-this-the-gilded-rose-kata/ http://www.iamnotmyself.com/2011/02/13/RefactorThisTheGildedRoseKata.aspx
Ruby : https://github.com/professor/GildedRose
C#: https://github.com/NotMyself/GildedRose
Java : https://github.com/wouterla/GildedRose
AS3: https://github.com/dshefman/GildedRoseAS3I believe that the Gilded Rose Kata was developed by Terry Hughes and Bobby Johnson and presented to the SC community on 2/13/2011.
Kata Text
Hi and welcome to team Gilded Rose. As you know, we are a small inn with a prime location in a prominent city ran by a friendly innkeeper named Allison. We also buy and sell only the finest goods. Unfortunately, our goods are constantly degrading in quality as they approach their sell by date. We have a system in place that updates our inventory for us. It was developed by a no-nonsense type named Leeroy, who has moved on to new adventures. Your task is to add the new feature to our system so that we can begin selling a new category of items. First an introduction to our system:
- All items have a SellIn value which denotes the number of days we have to sell the item
- All items have a Quality value which denotes how valuable the item is
- At the end of each day our system lowers both values for every item
Pretty simple, right? Well this is where it gets interesting:
- Once the sell by date has passed, Quality degrades twice as fast
- The Quality of an item is never negative
- “Aged Brie” actually increases in Quality the older it gets
- The Quality of an item is never more than 50
- “Sulfuras”, being a legendary item, never has to be sold or decreases in Quality
- “Backstage passes”, like aged brie, increases in Quality as it’s SellIn value approaches; Quality increases by 2 when there are 10 days or less and by 3 when there are 5 days or less but Quality drops to 0 after the concert
We have recently signed a supplier of conjured items. This requires an update to our system:
- “Conjured” items degrade in Quality twice as fast as normal items
Feel free to make any changes to the UpdateQuality method and add any new code as long as everything still works correctly. However, do not alter the Item class or Items property as those belong to the goblin in the corner who will insta-rage and one-shot you as he doesn’t believe in shared code ownership (you can make the UpdateQuality method and Items property static if you like, we’ll cover for you).
Carnegie Mellon University - Silicon Valley campus reflections
**Spoilers** Note: you probably want to read this section after doing the kata.
1. Most of the students thought this was a great kata for practicing TDD.
We had a great conversation about what is the best way to test this? A few started with a given initial state and looped through update quality man times. They found that their test cases were as complicated as the code they were testing. Often this code was hard to follow or read. Many tested the individual requirements to verify that when we go from state N to state N+1, a certain invariant still holds true.
2. What is the purpose of the Goblin rule?
(I need to find my notes on the class response to this one.) Most agreed that it was ok to subclass item provided that you didn't touch the code in the item class. Just to be sure, I asked Terry this question and here is his answer: "basically if the goblin sees anything different inside the Item class, everyone dies"
3. Of the 11 students who did it, only one refactored the code by creating subclasses of Item. (One student broke the Goblin rule and thus everyone died.) I believe the rest did inline modifications of the original code. (Which in my opinion wasn't that hard to do, once you had the test cases written.)
4. We make assumptions when we write software. Some of us thought that the original code worked fine and our job was to replicate the behavior. If there was a difference between the requirement and what the code did, we assumed the code was correct. Others of us thought the opposite.
We had a great conversation about when is it appropriate for the programmer to override input given by the user? For example, Sulfuras, Hand of Ragnaros has an initial quality of 80 which violates that "The Quality of an item is never more than 50" -- some people decided to enforce this rule and drop the quality from 80 to 50 (which is ironic given that “Sulfuras never decreases in Quality" while others decided to keep the behavior of the original code. We discussed what would a considerate system do and what are circumstances where you tell the user that they are wrong.
5. What did you like about this kata?
-the kata was realistic and mimic a real-life scenario
-I was confident about TDD this time
-I broke the rules and modified the Item Class
-it's a good exercise for design patterns
-need to go through all the test cases
-the kata was a great way to get familiar with the syntax of a programming language
-it was also a great avenue for applying TDD and writing strong tests
-it had the perfect level of hardness to practice TDD
-code required more thought than Prime Factors. Also made me want to refactor and think in that way before starting the code.
-I liked how it demonstrated how poor readability code and make it hard to make changes
-the kata was fun because of the little story behind it. Made it more interesting than just another problem.
-I liked how the code/spec was co convoluted that it took me a while to feel confident that I had ported the code to my language correctly. It was like a brain teaser
-handling the numerous conditions and putting them efficiently in code
If you want to try this Kata for yourself or at your dojo meeting, read the problem description and see if the Kata appeals to you. The rest is commentary and helpful clues for if you get stuck solving it. I would recommend trying the Kata for yourself before reading too much of it.
Problem Description
Once upon a time there was a series of 5 books about a very English hero called Harry. (At least when this Kata was invented, there were only 5. Since then they have multiplied) Children all over the world thought he was fantastic, and, of course, so did the publisher. So in a gesture of immense generosity to mankind, (and to increase sales) they set up the following pricing model to take advantage of Harry's magical powers.
One copy of any of the five books costs 8 EUR. If, however, you buy two different books from the series, you get a 5% discount on those two books. If you buy 3 different books, you get a 10% discount. With 4 different books, you get a 20% discount. If you go the whole hog, and buy all 5, you get a huge 25% discount.
Note that if you buy, say, four books, of which 3 are different titles, you get a 10% discount on the 3 that form part of a set, but the fourth book still costs 8 EUR.
Potter mania is sweeping the country and parents of teenagers everywhere are queueing up with shopping baskets overflowing with Potter books. Your mission is to write a piece of code to calculate the price of any conceivable shopping basket, giving as big a discount as possible.
For example, how much does this basket of books cost?
2 copies of the first book
2 copies of the second book
2 copies of the third book
1 copy of the fourth book
1 copy of the fifth book
(answer: 51.20 EUR)
Clues
You’ll find that this Kata is easy at the start. You can get going with tests for baskets of 0 books, 1 book, 2 identical books, 2 different books… and it is not too difficult to work in small steps and gradually introduce complexity.
However, the twist becomes apparent when you sit down and work out how much you think the sample basket above should cost. It isn’t 5*8*0.75+3*8*0.90. It is in fact 4*8*0.8+4*8*0.8. So the trick with this Kata is not that the acceptance test you’ve been given is wrong. The trick is that you have to write some code that is intelligent enough to notice that two sets of four books is cheaper than a set of five and a set of three.
You will have to introduce a certain amount of clever optimization algorithm. But not too much! This problem does not require a fully fledged general purpose optimizer. Try to solve just this problem well in order to share it for everyone or even in the ??? . Trust that you can generalize and improve your solution if and when new requirements come along.
- This application has nice application for
Suggested Test Cases
(Originally posted at xp-france.net/cgi-bin/wiki.pl?KataPotter)
def testBasics
assert_equal(0, price([]))
assert_equal(8, price([0]))
assert_equal(8, price([1]))
assert_equal(8, price([2]))
assert_equal(8, price([3]))
assert_equal(8, price([4]))
assert_equal(8 * 2, price([0, 0]))
assert_equal(8 * 3, price([1, 1, 1]))
end
def testSimpleDiscounts
assert_equal(8 * 2 * 0.95, price([0, 1]))
assert_equal(8 * 3 * 0.9, price([0, 2, 4]))
assert_equal(8 * 4 * 0.8, price([0, 1, 2, 4]))
assert_equal(8 * 5 * 0.75, price([0, 1, 2, 3, 4]))
end
def testSeveralDiscounts
assert_equal(8 + (8 * 2 * 0.95), price([0, 0, 1]))
assert_equal(2 * (8 * 2 * 0.95), price([0, 0, 1, 1]))
assert_equal((8 * 4 * 0.8) + (8 * 2 * 0.95), price([0, 0, 1, 2, 2, 3]))
assert_equal(8 + (8 * 5 * 0.75), price([0, 1, 1, 2, 3, 4]))
end
def testEdgeCases
assert_equal(2 * (8 * 4 * 0.8), price([0, 0, 1, 1, 2, 2, 3, 4]))
assert_equal(3 * (8 * 5 * 0.75) + 2 * (8 * 4 * 0.8),
price([0, 0, 0, 0, 0,
1, 1, 1, 1, 1,
2, 2, 2, 2,
3, 3, 3, 3, 3,
4, 4, 4, 4]))
end
Source: http://codingdojo.org/cgi-bin/wiki.pl?KataPotter
Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.
Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.
Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with A ≤ n < m ≤ B.
Limits
1 ≤ T ≤ 50.
A and B have the same number of digits.
Small dataset
1 ≤ A ≤ B ≤ 1000.
Large dataset
1 ≤ A ≤ B ≤ 2000000.
Sample
|
|
4
1 9
10 40
100 500
1111 2222
| Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287
|
Yes, we're sure about the output to Case #4.
This Kata is about implementing a simple tennis game. It is based on Wii tennis, where they have simplified tennis, so each set is one game.
The scoring system is rather simple:
1. Each player can have either of these points in one game 0 15 30 40
2. If you have 40 and you win the ball you win the game, however there are special rules.
3. If both have 40 the players are deuce. a. If the game is in deuce, the winner of a ball will have advantage and game ball. b. If the player with advantage wins the ball he wins the game c. If the player without advantage wins they are back at deuce.
===== Alternate description of the rules per Wikipedia http://en.wikipedia.org/wiki/Tennis#Scoring):
1. A game is won by the first player to have won at least four points in total and at least two points more than the opponent.
2. The running score of each game is described in a manner peculiar to tennis: scores from zero to three points are described as "love", "fifteen", "thirty", and "forty" respectively.
3. If at least three points have been scored by each player, and the scores are equal, the score is "deuce".
4. If at least three points have been scored by each side and a player has one more point than his opponent, the score of the game is "advantage" for the player in the lead.
Write a program that plays tic-tac-toe and never loses.
Details about tic-tac-toe:
http://en.wikipedia.org/wiki/Tic-tac-toe
A farmer has a forty pound stone that he uses to weigh food for his animals on a scale. One day, he loans the stone to his neighbor. A few days later, the neighbor returns the stone and apologizes to the farmer because his stone is now broken in four pieces. The farmer responds “Please don’t apologize, you have actually made my life easier because with these four pieces, I can now measure any weight between one and forty pounds.
The question is: how much do these four individual pieces weigh?
I’m adding a few clarifications, which are not necessarily what the Car Talk guys meant (I don’t have the solution and I haven’t looked at any discussion on the subject):
- The four weights are integers.
- The weights we can measure between one and forty pounds are in one pound increment.
- They are measured in one session (otherwise, you could measure forty pounds with a one pound stone by performing forty measurements).
If there is no solution (the farmer might be bad at math), show the four weights that allow to measure the most weights between one and forty pounds.
Source:
http://beust.com/weblog/2011/10/30/a-new-coding-challenge/
