Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 21. August 2011 16:15

Let’s take a last stab at our beer-delivery problem. We tried out a Sieve, we used the Microsoft Solver – time for some recursion.

How can we organize our recursion?

If we had only 1 type of beer pack, say, 7-packs, the best way to supply n bottles of beer is to supply the closest integer greater than n/7, that is, $$\lceil {n \over 7} \rceil$$

If we had 7-packs and 13-packs, we need to consider multiple possibilities. We can select from 0 to the ceiling of n/7 7-packs, and, now that we have only one type of case pack left, apply the same calculation as previously to the remaining bottles we need to supply – and select the best of the combinations, that is, the combination of beer packs closest to the target.

If we had even more types of beer packs available, we would proceed the same way, by trying out the possible quantities for the first pack, and given the first, for the second, and so on until we reach the last type of pack – which is pretty much the outline of a recursive algorithm.

More...

by Mathias 14. August 2011 13:41

In our last post, we looked at a Sieve-like algorithm to help a Brewery find how closely they can match the number of beer bottles their thirsty customers desire, using only 7-packs and 13-packs of delicious beer; in less appetizing but more precise terms, we are trying to solve the following problem:

Suppose that you are given a list of integers, and a target integer. Your goal is to find the closest value that is greater or equal to the target, by combining integers (“packs”) from the list (only positive combinations are allowed). For instance, given 3 and 5, the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the closest to 17 would be 3 x 6 = 18.

The Sieve solution is pretty effective, but has some limitations. Today, we’ll take another approach: leveraging the Microsoft Solver Foundation.

The beauty of the Solver is that it allows you to focus on what you want to achieve, rather than on how to achieve it. As long as you can define clearly what your goal, your decision variables and your constraints are, you can leave it to the Solver engine to figure out what the best way to achieve that goal is, by searching the best values for the Decision variables you defined.

So what are we trying to achieve here? Our goal, in Solver terms, is to minimize the extra number of bottles shipped, under the constraint that the number of bottles shipped is greater than the requested target number. Our Decision variables are the number of units of each Beer Pack we will ship, with a constraint that Decisions must be integer (we cannot ship half-packs), and positive.

Let’s add a reference to the Solver in our project (details here), and see how this looks like in code:

More...

by Mathias 6. August 2011 18:26

In my last post, I presented a small problem which I found interesting: how to help a Brewery of the glorious land of Bizzarostan in finding the perfect combination of 7-packs and 13-packs of beer. Or, in more serious terms,

Suppose that you are given a list of integers, and a target integer. Your goal is to find the closest value that is greater or equal to the target, by combining integers (“packs”) from the list (only positive combinations are allowed). For instance, given 3 and 5, the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the closest to 17 would be 3 x 6 = 18.

My first take on the problem was inspired by the Sieve of Eratosthenes. The idea is to accumulate in a list all possible combinations of packs, and take the smallest combination greater than the target. The main difference with the Sieve of Erathostene is that for prime numbers, we only care about listing numbers that are multiples of primes, whereas here we need to enumerate linear combinations of packs, and not simply all the multiples of single packs.

For instance, in the example where we search for a target of 16 using a combination of 3- and 5-packs, the procedure looks like:

* Add 0 to the combinations, i.e. {0}

* Add the multiples of 3, until 17 is reached, i.e. {0, 0 + 3 x 1, 0 + 3 x 2 = 6, 9, 12, 15, 18}

* For each element of the list, create multiples of 5, and progressively add them to the list, i.e.

{0, 3, 6, 9, 12, 15, 18, 0 + 5, 0 + 2 x 5, 0 + 3 x 5, 0 + 4 x 5, 3 + 5 x 1, 3 + 5 x 2, 3 + 5 x 3, 6 + 5 x 1, … }

Note that we need to accumulate all the intermediate combinations, and cannot simply store the first number greater than the limit for each pack, because we need to consider solutions which combine multiple packs – like 16 = 3 x 2 + 5 x 2

More...

by Mathias 4. August 2011 15:53

A fun problem came my way today. Imagine that you are the owner of a renowned brewery in Bizzarostan, a country where beer is sold only in 7-packs and 13-packs, sometimes described as the ++ packs. Beer is a serious matter in Bizzarostan, and buying single bottles is not tolerated by the law.

You take great pride in doing what’s best for your customers, so when a customers asks you for, say, 20 beers, you always try your best to find the combination of 7-packs and 13-packs that will meet your customer’s thirst, for the least amount of hard-earned money – in that case, a 7-pack and a 13-pack.

To be extra clear, the goal is to find a combination of 7- and 13-packs containing at least as many bottles as requested, with a total number of bottles as close as possible to the amount requested.

But the unquenchable thirst of the population of Bizzarostan has been increasing lately, which is making your job harder. How would you know on top of your head what’s the best combination for a hundred bottles of Beer? Having great faith in the wonders of modern technology, you decide it’s time to write an application to find that ideal combination of beer packs.

I got a rather brute-force working solution already, which I will share in the next few days. This may be massive overkill, but that’s also a problem the Microsoft Solver Foundation can handle fairly easily, so we’ll look into that as well. I have this nagging feeling that there is an elegant recursive solution to the problem, but couldn’t write anything clever so far; if you have thoughts, please share them in the comments!

PS: no, I haven’t started working for a company that manufacture 7-packs of beers, it’s a transposition of a real-world, analogous problem.

PPS: I think this is also the closest I ever got to seeing a real application of the FizzBuzz problem in the real world.

by Mathias 2. August 2011 16:06

When working with Excel, it is common to use small optimization tricks, like setting Excel.ScreenUpdating to false to avoid un-necessary screen refreshes, during lengthy operations – something along these lines:

public void DoJob(Worksheet  worksheet)
{
   var excel = worksheet.Application;

   var initialScreenUpdating = excel.ScreenUpdating;
   var initialCursor = excel.Cursor;

   excel.ScreenUpdating = false;
   excel.Cursor = XlMousePointer.xlWait;

   // do stuff

   excel.ScreenUpdating = initialScreenUpdating;
   excel.Cursor = initialCursor;
}

This is a good outline of what we would like to happen, but as is, this code has limitations. We would like to be certain that whenever we capture the state, the final two lines, which reset the state to what it was originally, are executed.

More...

Comments

Comment RSS