I was asked about a week or so ago if I knew what a Kata was, I said that I didn't. If I had taken my time to think about it I may have remembered those practice karate moves my brother showed me a few years ago. If I had taken that time, then my answer wouldn't have been a million miles away. I won't try and explain, take a quick look
here. Shortly after being asked I was set a little challenge. What follows is my attempt at the
Harry Potter Kata, in Java (of course), hopefully I'll be able to give it a go in Ruby some day.
Step 1, I'm going to write a test for the first acceptance of the criteria. No order, no charge.
public class BookstoreTest extends TestCase {
private Bookstore bookstore;
protected void setUp() throws Exception {
super.setUp();
bookstore = new Bookstore();
}
public void testNoBooksOrdered() {
assertEquals(0.0, bookstore.totalPrice(new int[]{}));
}
}
A red light as expected. Next step, a simple implementation that returns 0.
public class Bookstore {
/**
* Calculates the total price of the order placed.
*
* @param orders - an array of ints representing orders
* @return total cost
*/
public double totalPrice(int[] orders) {
return 0;
}
}
Ok, that was simple but I like this approach. I find it helps set a tempo, only do enough to pass the test (and keep all the others passing of course). Next up isn't going to be anymore difficult but again it doesn't have to be in order to pass the test.
Here are the new tests. They assert that one order placed is charged at the price of one volume.
public void testOneBookInRangeOrdered() {
assertEquals(8.0, bookstore.totalPrice(new int[]{0}));
assertEquals(8.0, bookstore.totalPrice(new int[]{1}));
assertEquals(8.0, bookstore.totalPrice(new int[]{2}));
assertEquals(8.0, bookstore.totalPrice(new int[]{3}));
assertEquals(8.0, bookstore.totalPrice(new int[]{4}));
}
They all fail, a simple change and all tests should pass.
public double totalPrice(int[] orders) {
return 8 * orders.length;
}
As expected all tests now pass. Time for another test, this time test that 2 copies of same volume are not discounted.
public void testTwoBooksOfSameVolumeOrderedProvidesNoDiscount() {
assertEquals((double) 8 * 2, bookstore.totalPrice(new int[]{1, 1}));
}
This time no need to change any implementation code, all tests pass. The next test will assert that 3 copies of the same volume are not discounted.
public void testTwoBooksOfSameVolumeOrderedProvidesNoDiscount() {
assertEquals((double) 8 * 2, bookstore.totalPrice(new int[]{1, 1}));
}
Again all tests pass. Ok that's all the basic cases catered for, now to have a go at the simple discounts. First up two different volumes.
public void testDiscountAppliedToTwoUniqueVolumes() {
assertEquals((double) 8 * 2 * 0.95, bookstore.totalPrice(new int[]{1, 2}));
}
Red light as expected, my implementation is returning 16 but 15.2 is required. So I need to now start taking into account the order type. If I create a Map that holds each order type requested as a key and the count of each type then I should then be able to calculate the cost. Ok that should be simple enough to test and I think the implementation should merit it's own method.
public void testTwoMapEntriesCreatedEachWithACountOfOne() {
Map<Integer, Integer> orderCounts = new HashMap<Integer, Integer>();
orderCounts.put(1, 1);
orderCounts.put(2, 1);
assertEquals(orderCounts, bookstore.createVolumeCountMap(new int[]{1, 2}));
}
I'm perfectly happy to implement the createVolumeCountMap as a package scope method in order to test it. I don't see any harm in it, we are solving a domain problem not creating an API.
Map createVolumeCountMap(int[] orders) {
Map<Integer, Integer> orderCounts = new HashMap<Integer, Integer>();
for (int i = 0; i < orders.length; i++) {
if(orderCounts.containsKey(orders[i])){
Integer count = orderCounts.get(orders[i]);
count++;
orderCounts.put(orders[i], count);
}
else{
orderCounts.put(orders[i], 1);
}
}
return orderCounts;
}
Now that the orders are in a more manageable form we need to identify how many occurrences of each discount type there are.
public void testSmallestCountForDiscountType1() {
Map<Integer, Integer> orderCounts = new HashMap<Integer, Integer>();
orderCounts.put(1, 3);
orderCounts.put(2, 3);
assertEquals(3, bookstore.identifySmallestCountForDiscountType(orderCounts, 1));
}
public void testSmallestCountForDiscountType2() {
Map<Integer, Integer> orderCounts = new HashMap<Integer, Integer>();
orderCounts.put(1, 3);
orderCounts.put(2, 3);
assertEquals(3, bookstore.identifySmallestCountForDiscountType(orderCounts, 2));
}
After a couple of attempts this is what I came up with.
int identifySmallestCountForDiscountType(Map<Integer, Integer> orderCounts, int discountType) {
if (orderCounts.size() == discountType) {
Integer smallestCountOfVolumes = null;
Collection<Integer> values = orderCounts.values();
for (Iterator<Integer> iterator = values.iterator(); iterator.hasNext();) {
Integer volumeCount = iterator.next();
if (smallestCountOfVolumes == null) {
smallestCountOfVolumes = volumeCount;
} else if (volumeCount < smallestCountOfVolumes) {
smallestCountOfVolumes = volumeCount;
}
}
return smallestCountOfVolumes;
}
return 0;
}
Ok now I need to go back to the totalPrice method and start integrating some of this code. First thing is to convert the orders into the Map using the createVolumeCountMap method. Next thing that I see is the Bookstore needs some sort of repository for the discount type per unique number of volumes. Should be straightforward enough, just add a Map containing the number of unique volumes and the discount that can be applied. Now I can iterate over the discount types and identify how many of each are in the orderCounts map. With that I should then be able to start a running total. I'll also need to make sure I'm managing the orderCounts map, reducing the number of orders accordingly.
So the TODO list at the moment is:
- Use the createVolumeCountMap to convert the int[] into a Map
- Create a repository for the discount type per unique number of volumes
- Iterate over the discount types
- Calculate the running total
- Reduce the orderCounts map
I'll tackle reducing the orderCounts map first.
public void testReduceMapEntriesByCount() {
Map<Integer, Integer> orderCounts = new HashMap<Integer, Integer>();
orderCounts.put(1, 3);
orderCounts.put(2, 3);
bookstore.reduceAllEntriesByCount(orderCounts, 3);
assertEquals(0, (int) orderCounts.get(1));
assertEquals(0, (int) orderCounts.get(2));
}
Straightforward enough, introduced the reduceToNoLessThanZero to make sure that it can be tested more easily.
void reduceAllEntriesByCount(Map<Integer, Integer> orderCounts, Integer reduction) {
Set<Integer> keys = orderCounts.keySet();
Integer count;
Integer key;
for (Iterator<Integer> iterator = keys.iterator(); iterator.hasNext();) {
key = iterator.next();
count = orderCounts.get(key);
orderCounts.put(key, reduceToNoLessThanZero(count, reduction));
}
}
public void testReductionToNoLessThanZero() {
assertEquals(0, bookstore.reduceToNoLessThanZero(3, 4));
assertEquals(1, bookstore.reduceToNoLessThanZero(4, 3));
}
int reduceToNoLessThanZero(Integer count, Integer reduction) {
Integer newValue = count - reduction;
return newValue >= 0 ? newValue : 0;
}
Now I have the implementation to reduce the map entries I can now check off the rest of the TODO list.
So totalPrice now looks like this.
public double totalPrice(int[] orders) {
Double total = 0.0;
Map<Integer, Integer> orderCounts = createVolumeCountMap(orders);
Set<Integer> discountTypes = uniqueVolumesPercentageCharge.keySet();
for (Iterator<Integer> iterator = discountTypes.iterator(); iterator.hasNext();) {
Integer discountType = iterator.next();
Integer smallestNumberPerType = identifySmallestCountForDiscountType(orderCounts, discountType);
total = addToTotal(total, smallestNumberPerType, discountType);
reduceAllEntriesByCount(orderCounts, smallestNumberPerType);
}
return total;
}
The addToTotal method is there, again, to make the code more readable and to ensure that it's properly tested.
public void testAddToTotal(){
assertEquals(8.0, bookstore.addToTotal(0.0, 1, 1));
assertEquals(16.0, bookstore.addToTotal(0.0, 2, 1));
assertEquals(15.2, bookstore.addToTotal(0.0, 1, 2));
assertEquals(23.2, bookstore.addToTotal(8.0, 1, 2));
}
Double addToTotal(Double total, Integer smallestNumberPerType, Integer discountType) {
return total + (smallestNumberPerType * costPerVolume * discountType)
* uniqueVolumesPercentageCharge.get(discountType);
}
Ok now all lights are green!! Time to return to the acceptance criteria. Added all the simple discount tests and everything passes!! Added the 1st of the several discounts combined and it fails. Ok closer inspections shows that I’m not calculating the discount in the correct order, so I'll need to put them in reverse chronological order.
public void testReverseOrder() {
Set<Integer>originalOrder = new TreeSet<Integer>();
originalOrder.add(1);
originalOrder.add(2);
originalOrder.add(3);
originalOrder.add(4);
originalOrder.add(5);
Integer[] reverseOrder = bookstore.putInReverseOrder(originalOrder);
assertEquals(new Integer(5), reverseOrder[0]);
assertEquals(new Integer(1), reverseOrder[4]);
}
Integer[] putInReverseOrder(Set<Integer> discountTypes) {
Set<Integer> orderKeySet = new TreeSet<Integer>(discountTypes);
Integer[] orderedKeys = orderKeySet.toArray(new Integer[discountTypes.size()]);
Arrays.sort(orderedKeys, Collections.reverseOrder());
return orderedKeys;
}
Green light for all of the several discount combined acceptance tests. Now for the vicious tests. As expected they fail, I knew it wasn't going to just fall into place! Ok so I'm calculating the cost for 1*5 and 1*3 different volumes and the test is asserting 2*4 in the 1st test. In the second test 4*5 and 1*3 different volumes as opposed to 3*5 & 2*4.
|
Before I go any further and start throwing code at it I'll take step back and have a look at what I've got. At the moment I'm creating a Map that has the count for each volume. So for vicious case one it looks like this...
|
|
|
| Volume | Number Ordered |
| 0 |
2 |
| 1 |
2 |
| 2 |
2 |
| 3 |
1 |
| 4 |
1 |
I need it to look like this...
| Volume | Number Ordered |
| 0 |
2 |
| 1 |
2 |
| 2 |
2 |
| 3 |
2 |
How am I going to do that?
I'm not; the data is being stored in the wrong format. I need to create bundles not counts per volume, something like this...
| Volume 1 | Volume 2 | Volume 3 | Volume 4 | Volume 5 |
| X |
X |
X |
X |
|
| X |
X |
X |
|
X |
So I’m going to have to do some refactoring. Best thing to do first is get the createVolumeCount method refactored to return a List and I'll go from there.
public void testCreateVolumeBundlesForViciousForCaseOne() {
List<Set> orderBundles = new ArrayList<Set>();
Set<Integer> bundle1 = new HashSet<Integer>();
bundle1.add(0);
bundle1.add(1);
bundle1.add(2);
bundle1.add(3);
orderBundles.add(bundle1);
Set<Integer> bundle2 = new HashSet<Integer>();
bundle2.add(0);
bundle2.add(1);
bundle2.add(2);
bundle2.add(4);
orderBundles.add(bundle2);
assertEquals(orderBundles, bookstore.createVolumeBundles(new int[]{0, 0, 1, 1, 2, 2, 3, 4}));
}
Cracked it!
List<Set> createVolumeBundles(int[] orders) {
List<Set> bundles = new ArrayList<Set>();
for (int order : orders) {
Set<Integer> bundle = findSmallestAvailableBundle(bundles, order);
bundle.add(order);
}
return bundles;
}
private Set<Integer> findSmallestAvailableBundle(List<Set> bundles, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order) && !containsSmallerAvailableBundle(bundles, bundle, order)) {
return bundle;
}
}
return createNewBundle(bundles);
}
private boolean containsSmallerAvailableBundle(List<Set> bundles,
Set<Integer> bundleBeingConsidered, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order) && bundle.size() < bundleBeingConsidered.size()) {
return true;
}
}
return false;
}
Ok so now almost all of my other tests fail. Instead of weeding out the redundant tests and code, I’ll re-implement the totalPrice method and then remove the redundant code.
totalPrice now looks like...
public double totalPrice(int[] orders) {
Double total = 0.0;
List<Set> orderBundles = createVolumeBundles(orders);
for (Set<Integer> bundle: orderBundles){
total = addToTotal(total, bundle.size());
}
return total;
}
Typical, now 2 of the several discounts at once tests fail.
What I think I need to do now is create another list of bundles only this time instead of having them contain the smallest possible bundles have them contain the natural/largest bundles. Then compare the cost of each bundle and return the lowest cost.
public void testCreateVolumeBundlesForSeveralDiscountsTest3() {
List<Set> orderBundles = new ArrayList<Set>();
Set<Integer> bundle1 = new TreeSet<Integer>();
bundle1.add(0);
bundle1.add(1);
bundle1.add(2);
bundle1.add(3);
orderBundles.add(bundle1);
Set<Integer> bundle2 = new TreeSet<Integer>();
bundle2.add(0);
bundle2.add(2);
orderBundles.add(bundle2);
assertEquals(orderBundles, bookstore.createLargestVolumeBundles(new int[]{0, 0, 1, 2, 2, 3}));
}
List<Set> createLargestVolumeBundles(int[] orders) {
List<Set> bundles = new ArrayList<Set>();
for (int order : orders) {
Set<Integer> bundle = findAvailableBundle(bundles, order);
bundle.add(order);
}
return bundles;
}
private Set<Integer> findAvailableBundle(List<Set> bundles, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order)) {
return bundle;
}
}
return createNewBundle(bundles);
}
A slight modification to totalPrice and all lights are green!!
After all that it boils down to 91 lines of code...
import java.util.*;
public class Bookstore {
private Map<Integer, Double> uniqueVolumesPercentageCharge = new HashMap<Integer, Double>();
private int costPerVolume;
public Bookstore(Map<Integer, Double> uniqueVolumesPercentageCharge, int costPerVolume) {
this.uniqueVolumesPercentageCharge = uniqueVolumesPercentageCharge;
this.costPerVolume = costPerVolume;
}
/**
* Calculates the smallest total price of the order placed.
*
* @param orders - an array of ints representing orders
* @return total cost
*/
public double totalPrice(int[] orders) {
Double smallBundlesTotal = calculateCostOfOrders(createSmallestVolumeBundles(orders));
Double largeBundlesTotal = calculateCostOfOrders(createLargestVolumeBundles(orders));
return smallBundlesTotal < largeBundlesTotal? smallBundlesTotal:largeBundlesTotal;
}
private Double calculateCostOfOrders(List<Set> orderBundles) {
Double total = 0.0;
for (Set<Integer> bundle: orderBundles){
total = addToTotal(total, bundle.size());
}
return total;
}
Double addToTotal(Double currentTotal, int bundleSize) {
return currentTotal + (costPerVolume * bundleSize
* uniqueVolumesPercentageCharge.get(bundleSize));
}
List<Set> createSmallestVolumeBundles(int[] orders) {
List<Set> bundles = new ArrayList<Set>();
for (int order : orders) {
Set<Integer> bundle = findSmallestAvailableBundle(bundles, order);
bundle.add(order);
}
return bundles;
}
private Set<Integer> findSmallestAvailableBundle(List<Set> bundles, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order)
&& !containsSmallerAvailableBundle(bundles, bundle, order)) {
return bundle;
}
}
return createNewBundle(bundles);
}
private boolean containsSmallerAvailableBundle(List<Set> bundles,
Set<Integer> bundleBeingConsidered, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order) && bundle.size() < bundleBeingConsidered.size()) {
return true;
}
}
return false;
}
List<Set> createLargestVolumeBundles(int[] orders) {
List<Set> bundles = new ArrayList<Set>();
for (int order : orders) {
Set<Integer> bundle = findAvailableBundle(bundles, order);
bundle.add(order);
}
return bundles;
}
private Set<Integer> findAvailableBundle(List<Set> bundles, int order) {
for (Set<Integer> bundle : bundles) {
if (!bundle.contains(order)) {
return bundle;
}
}
return createNewBundle(bundles);
}
private Set<Integer> createNewBundle(List<Set> bundles) {
Set<Integer> bundle = new TreeSet<Integer>();
bundles.add(bundle);
return bundle;
}
}
