Harry Potter and the Magic of Common Good

The Harry Potter kata (https://codingdojo.org/kata/Potter/) is a simple optimization problem: there is a series of 5 books, and you can buy any number of copies of each volume (I’ll use roman numerals to refer to a volume in the series). Depending on your purchase – more specifically on the variety of volumes you choose – you get a discount: one book sells for $8; if you buy two different volumes, you get a 5% discount on those two books; 3 different volumes will get you a 10% discount (on those 3); 4 different volumes, 20% discount; 5 different volumes will get you a 25% discount. Of course, the discount depends on how you arrange the books. Say that you buy (I, I, II, II, III, III, IV, V); you can arrange them as (I, II, III, IV, V) + (I, II, III) or as (I, II, III, IV) + (I, II, III, V). Do the math, and you’ll see that the 4+4 arrangement is cheaper than the 5+3 arrangement. Your goal, given a list of books, is to find the most favorable arrangement, that is, the one that will get you the largest discount (or, in other words, the smallest price).

If you look around for common solutions, you’ll find that:

-????????? Some people just didn’t get the requirements and used a greedy algorithm (trying to pack all the 5 volumes first, then 4, etc.) and even “fixed” the test so that the 5+3 arrangement above was considered the optimal case ??.

-????????? Some added an exception just for the 5+3 -> 4+4 case. That’s ok to pass the test, although one should at least prove (formally) that it’s the only real exception (what about 12 books?). It’s also very fragile: a tiny change in the discount rates and the code doesn’t work anymore.

-????????? Some just tried all the possible combinations, which is fine if you buy e.g. 10 books but not if you buy 200 or 600.

If you’re familiar with Operations Research, you may easily recognize this as a simple case of integer programming, relatively easy to solve using e.g. a branch and bound method, as you can estimate the boundaries of a choice and use them to prune the search. However, the original text of the kata discouraged building a “fully fledged” solver, so I spent a little time thinking about different strategies.

More specifically, I wanted to see if a reasonable solution could be found through the cooperation of relatively simple actors. In nature, for instance, slime mold can find the shortest path between nodes in a graph without any “central intelligence” kind of algorithm. There are other examples of emergent behavior where actors obtain some form of balance through their interactions, like price being regulated by supply / demand in markets. In fact, my initial thought was to give each volume to an independent merchant, and then let them sell and buy books; however, we must be careful about giving merchants the right goal: minimize the total cost of owned volumes.

If a merchant operates solely with the goal of optimizing its own stock (say, trying to acquire all the 5 volumes) then what we get is no better than the greedy algorithm. It might still work if we build the stock from the ground up (and by chance we get to 4+4 instead to 5+3) but if we start with a 5+3, the merchant with 5 books would have no incentive to sell. In fact, I wanted the option to set up merchants in an unoptimized way (say 5+3) and have the code find the optimum (say at 4+4) anyway, no matter the starting point.

To achieve that, merchants should work for the common good, and to do that, we should know the impact of a transaction on the common good. Merchants should advertise something like: [I own 5 books], I can sell volume IV, and if I do, the cost of my stock will decrease by 4.4$; another could say: [I own 3 books], I can buy volume IV, and if I do, the cost of my stock will increase by 4$; the part between […] doesn’t need to be revealed, but it’s how the merchant knows the change in its own stock’s value. Then we close a deal only if it benefits the common good (like: 4.4 > 4, so the total cost will decrease, therefore it’s a good transaction). That’s lesson number one here: the common good requires full transparency about costs and benefits in a transaction.

There is a small but inherent inefficiency in this process: within a single “trading session” a merchant can be involved in only one transaction, as the calculation above depends on the current stock of each merchant. We can, however, close any number of deals in a single trading session between independent parties. Then we do another session, and so on until we can no longer improve on the common good.

Unfortunately, buying and selling only one book at a time does not work. If we start with 4 merchants, and give 4 volumes each (so: 4+4+4+4), we can’t get to 5+5+5+1 (note: those cannot be random volumes, you need to choose them so that they can be grouped as 5+5+5+1) by selling one book at a time, as the intermediate state 5+4+4+3 is worse than 4+4+4+4.

You can overcome that in different ways: for instance, if you are into randomized algorithms, you might try e.g. simulated annealing to get over the local minima, but I didn’t like the idea much. A simple deterministic approach is to allow multi-volume, multi-party transactions instead: a merchant might sell up to 3 books in a single transaction, allowing 3 independent buyers to buy one volume each. I postulate (meaning: I didn’t prove it formally) that if you need to collect N books (5 in this case), you don’t have to sell more than ceiling(N/2) books per transaction (3 in this case), and that multi-volume sales are enough, that is, there is no need for multi-volume purchases. Lesson number 2 here: the common good requires multi-party transactions, or as an alternative (that I didn’t pursue) the introduction of intermediaries with inventory (or stochastic risk-taking).

With all this in mind, and having done the calculations above on paper ??, being in the middle of a moderate heat wave I didn’t want to spend much time in front of my computer, so I designed the entire thing and wrote most of the code in my mind as I was walking among the trees. I also wrote most of this text the same way. I realize it’s far from the dopamine cycle of writing a test and getting it to green, but it’s greener in its own way ??.

In the end, my design ended up like this (yes, it’s a dreaded UML thing; I’m also using colors that I introduced ages ago by extending the work of Peter Coad, but let’s not get into that):

Sure, there are a lot of small classes and collaborations (you might be calling those "dependencies"); however, the only public classes are the Basket and the BookSet; everything inside the dashed red rectangle is an implementation detail (of course it could actually be turned into a specific optimization strategy, using the strategy pattern; I just didn’t care: it’s a wabi-sabi thing).

The code is in C# and is OK-ish, meaning that there are a few places where I would quibble with it if it were your code, but I’m OK with it because it’s my code; for instance, the offset in the price table is there to avoid some conditionals when creating multi-volume sale offers, but it’s not really obvious by reading the code. There are a few tests in place, that I used mostly to check for correctness while sampling the effectiveness of a few optimizations; I’m sure many of you would write more, but I used tests to manage risk and check overall correctness, not to drive coding (sorry, I know it hurts; but the code was already in my mind anyway).

The overall strategy is simple:

-????????? The Basket will distribute volumes to merchants; you can also add merchants directly if you want to test the evolution from a sub-optimal state.

-????????? Merchants will create offers to buy missing volumes and to sell owned volumes.

-????????? The Market will cycle through the sales, and ask the Deal if there is a match with the purchases. Here we have to exclude multiple transactions involving the same party.

-????????? The Deal will try to match one of the volumes for sale with a purchase, and if necessary (multi-volume deals), will try to create a sub-deal for the remaining volumes; this is done through recursion, which gives “expert beginners” the shivers, but the depth is limited by the number of volumes in a sale, so you won’t get more than 3 calls deep.

-????????? The Basket will keep asking Merchants to trade until we can no longer improve on the total cost. At that point the remaining Merchants (those with an empty stock are removed along the way) form the optimal partition.

A few notes:

-????????? In essence, the code is still greedy: the Market class will privilege the sale with the largest decrease in value; a Deal will privilege the purchase with the smallest increase. However, I postulate that in this case being greedy is only about converging faster: if you remove that part of the code and just close any deal which benefits the common good, eventually you’ll still end up with an optimal solution.

-????????? To be fair, the effectiveness of being greedy is relatively small: to privilege the largest / smallest value you have to sort a collection, which costs you some time. In fact, the single most important optimization I had to put in (I needed to be in front of my PC and look at the code as it was executing on a few hundred books to get this idea) was to “cut off” and stop looking for solutions when what we lose by selling a book cannot be compensated by any theoretical purchase (this can be calculated from the discount table).

-????????? The idea above is still sort of reminiscent of a branch and bound, and in fact the code was fun to write, but it’s still too complicated; I can write a centralized branch & bound thing in fewer lines. Oh, well.

-????????? It still takes about 5 seconds on my crappy PC to solve a case with 600 books, 100 of which cannot be paired (so you end up with 100*5 sets + 100*1 sets). Still, good luck solving that by brute force. The slow tests are disabled in the code you find on github.

-????????? One could approach the Market in a different way, not by being greedy, but by looking for the “best” set of non-overlapping transactions given the offers. Fun thing: this would be way more complicated than solving the original optimization problem ?? as now you also have to deal with the non-overlapping part. On the other hand, you could see it from the opposite side: if your problem is that of optimizing a set of non-overlapping transactions, maybe you can restate it in a way that (like the original problem) doesn’t require that part. That would be a cool result.

-????????? I keep hearing that posts with links outside the platform are somewhat “punished” by the sharing algorithm, and that I should put links in comments; but I already put a link to the kata above, so here is the github repo: https://github.com/carlopescio/PotterKata. I suppose you can compensate for that by sharing this post ??.

-????????? As I said before: the solution space is larger than most people dare to explore. Be brave. Go outside the common boundaries. The cave you fear to enter holds the treasure you seek. And some other guru-like stuff.

-????????? Have fun!

?