Long time no see. About two months without anything interesting (related to dev topics at least) happening.
Recently I had a look at some of the katas at Coding Dojo. Quite interesting stuff. Today I want to present my shot at the Harry Potter book discount kata.
First things first: I used xUnit and especially xUnit’s data theories for TDD’ing my solution. I took a leave out of the kata’s book and used simple integer arrays to represent the shopping basket. I started with the simplest possible implementation. One class (DiscountCalculator) with a single method (Calculate(int[])). But well … that didn’t get me too far. Basically it solved the problem up to “we have two different books, how much is that?” before I decided that I hate the resulting code.
So I leaned back and thought about the problem a bit more. What I needed was a way to find subsets of the books inside the shopping basket that would maximize the discount. Some kind of partitioning algorithm. After a little back and forth I chose to implement that algorithm as a combination of three simple steps:
- If the basket is empty, you are done and no more partitioning is needed.
- If you have 8 books left in the basket and you can form two partitions with 4 distinct books each, you should prefer that to a 5/3 partition.
- Take as many distinct books as possible from the basket.
This is the code for those three steps:
public class EmptyBasket : IBasketPartitioner
{
public void Partition(PartitioningContext context)
{
if (context.Basket.Length == 0)
{
context.Finished = true;
}
}
}
public class Prefer44To53 : IBasketPartitioner
{
public void Partition(PartitioningContext context)
{
if (context.Basket.Length == 8)
{
List<int> basketCopy = new List<int>(context.Basket);
int[] part1 = context.Basket.Distinct().Take(4).ToArray();
if (part1.Length == 4)
{
foreach (int book in part1)
{
basketCopy.Remove(book);
}
int[] part2 = basketCopy.Distinct().ToArray();
if (part2.Length == 4)
{
context.MakePartition(part1);
context.MakePartition(part2);
}
}
}
}
}
public class GreedyGrabDistinctBooks : IBasketPartitioner
{
public void Partition(PartitioningContext context)
{
int[] differentBooks = context.Basket.Distinct().ToArray();
if (differentBooks.Length > 0)
{
context.MakePartition(differentBooks);
}
}
}
Admittedly the implementation of the 4/4 rule could use some polishing. But it works for now.
To host those steps I used a variation of the chain-of-responsibility pattern. This chain would loop through the different steps. Each step would take some of the books from the basket and put them in a list of partitions until there are no books left. The order of the steps is important! To achieve the desired outcome of the “prefer 4/4 partition to 5/3 partition” rule you need to take those books from the basket before the greedy “take as many distinct books as possible” rule applies. I chose to remove both 4/4 chunks from the basket in step 2 to reduce the overhead of the calls to Distinct().
public class PartitionerChain
{
private readonly List<IBasketPartitioner> partitioners;
public PartitionerChain(params IBasketPartitioner[] partitioners)
{
this.partitioners = new List<IBasketPartitioner>(partitioners);
}
public IEnumerable<int[]> GetPartitions(int[] originalBasket)
{
var context = new PartitioningContext(originalBasket);
int index = 0;
do
{
this.partitioners[index].Partition(context);
index = (index + 1) % this.partitioners.Count;
}
while (!context.Finished && context.Basket.Length > 0);
return context.Partitions;
}
}
The chain hands a context from step to step which contains the current content of the shopping basket, a list of partitions and a flag that indicates when the partitioning process is finished.
public class PartitioningContext
{
private readonly List<int[]> basketPartitions;
public PartitioningContext(int[] originalBasket)
{
this.Basket = originalBasket;
this.basketPartitions = new List<int[]>();
}
public int[] Basket { get; private set; }
public bool Finished { get; set; }
public IEnumerable<int[]> Partitions { get { return this.basketPartitions; } }
public void MakePartition(int[] partition)
{
this.basketPartitions.Add(partition);
List<int> newBasket = new List<int>(this.Basket);
foreach (int book in partition)
{
newBasket.Remove(book);
}
this.Basket = newBasket.ToArray();
}
}
To calculate the actual price of the books I switched from the switch-case solution to (yet again) a chain-of-responsibility based one.
public abstract class DiscountStrategy
{
public DiscountStrategy Next { get; protected set; }
public abstract double GetPrice(int[] basket);
}
public class NoDiscount : DiscountStrategy
{
public override double GetPrice(int[] basket)
{
return basket.Sum(book => 8.0);
}
}
public class TwoBooks : DiscountStrategy
{
public TwoBooks(DiscountStrategy next)
{
this.Next = next;
}
public override double GetPrice(int[] basket)
{
if (basket.Length == 2)
{
return 2 * 8 * 0.95;
}
return this.Next.GetPrice(basket);
}
}
public class ThreeBooks : DiscountStrategy
{
public ThreeBooks(DiscountStrategy next)
{
this.Next = next;
}
public override double GetPrice(int[] basket)
{
if (basket.Length == 3)
{
return 3 * 8 * 0.9;
}
return this.Next.GetPrice(basket);
}
}
public class FourBooks : DiscountStrategy
{
public FourBooks(DiscountStrategy next)
{
this.Next = next;
}
public override double GetPrice(int[] basket)
{
if (basket.Length == 4)
{
return 4 * 8 * 0.8;
}
return this.Next.GetPrice(basket);
}
}
public class FiveBooks : DiscountStrategy
{
public FiveBooks(DiscountStrategy next)
{
this.Next = next;
}
public override double GetPrice(int[] basket)
{
if (basket.Length == 5)
{
return 5 * 8 * 0.75;
}
return this.Next.GetPrice(basket);
}
}
[OT] Did I mention that I LOVE the chain-of-responsibility pattern? It is super flexible. It allows for clear separation of concerns. Favors small, easy to understand (and test) classes. Changing the behavior of your solution becomes a simple matter of reordering steps that you have already implemented. [/OT]
By this you can easily swap out different discount rules.
After that the calculator was a rather dumb shell. It assembles the two chains in its constructor. This can be seen as a violation of the D(ependency Inversion) of SOLID software development. I chose to encapsulate the knowledge of how to order the different pieces in the chains there nonetheless. If I ever need to make that step configurable, it would be a no-brainer as the assignment already happens in the calculator’s constructor.
All the calculator has to do now is to let the partioners divide the shopping basket into handy pieces and then let the discount strategies calculate the price for the individual chunks. Sweet!
public class DiscountCalculator
{
private readonly PartitionerChain partitioners;
private readonly DiscountStrategy discounts;
public DiscountCalculator()
{
this.partitioners = new PartitionerChain(new EmptyBasket(), new Prefer44To53(), new GreedyGrabDistinctBooks());
this.discounts = new FiveBooks(new FourBooks(new ThreeBooks(new TwoBooks(new NoDiscount()))));
}
public double Calculate(int[] basket)
{
var partitions = this.partitioners.GetPartitions(basket);
double total = partitions.Sum(partition => this.discounts.GetPrice(partition));
return total;
}
}
One more word to the testing aspect. I mentioned that I used xUnit data theories. With these it was almost effortless to use the test cases described at the bottom of the kata.
[Theory]
[InlineData(0d, new int[0])]
[InlineData(8d, new[] { 0 })]
// ...
[InlineData(2 * 8 * 4 * 0.8, new[] { 0, 0, 1, 1, 2, 2, 3, 4 })]
[InlineData(3 * 8 * 5 * 0.75 + 2 * 8 * 4 * 0.8, new[]
{
0, 0, 0, 0, 0,
1, 1, 1, 1,1,
2, 2, 2, 2,
3, 3, 3, 3, 3,
4, 4, 4, 4
})]
public void CalculatesCorrectPrice(double expected, int[] basket)
{
DiscountCalculator sut = new DiscountCalculator();
Assert.Equal(expected, sut.Calculate(basket));
}
It was never ever that easy to setup tests that use different data but are equivalent otherwise. If you are interested in data theories and how they can make your life as a tester so much easier I strongly recommend that you have a look at Mark Seemann’s awesome series of posts about his implementation of the String Calculator kata. Mind blowing!
So that’s it for now. I think I will have a look at the other katas. Hope they are as much fun 🙂
Outlawtrail - .NET Development 