As part of the Christmas presents, Santa has to provide a whole lot of wooden toys to the young of the world’s children. According to this site there are 1.9 billion children so a rough ball park figure is that 500 million are of the age to get these wooden toys.
Santa’s Elves have a budget of several millions tons of wood, sheds full of nails, a few million bath tubs of 3 colours of paints. They need to build the following toys using just those materials and a bunch of Elves: wooden tractor, rocking chair horse, wooden steam train, dolls house, toy castle, set of 12 wooden toys, Noah’s Ark. Each toy takes a certain amount of wood, nails, various paints (Red, Green and Blue) and a number of Elf hours to make.
Toy,Wood,Nails,Red Paint,Green Paint, Blue Paint,Elves
Rocking Chair Horse,15,20,0,0,1,6
Wooden Steam Train,7,24,1,0,1,4
12 Wooden Puzzles,6,24,2,0,0,4
Wood is in weight by Kgs, Paint by Litres. There are seven toys to make out of the 5 different commodities. The amounts shown are enough to make 1 toy in one hour. Could we make the toys faster? As it takes nine months for one woman to have a baby, could nine women produce one baby in a month? No.
The amount of commodities available are for each batch of production is Wood 5,600 KG, 8,000 Nails, Paint (Red, Green and Blue), 600, 500, 500 and 80 Elves. Note these represent quantities one million times bigger (including Elves), I’m just simplifying the figures.
What is the optimal amount of each toy to make given the resources and the constraint that the number of each toy must be 8% or higher of the total made? I.e. the numbers of each must not be less than 8% of the total toys made?
A simple first calculation dividing each commodity by the total; needed, for example 1 of each toy needs 157 nails. So we could make 51 (= 8,000 / 157). Doing this for all the commodities reveals that based on each commodity the most we can make of 1 of each is 84, 51, 67, 71, 50. Realistically we only have enough to produce 50 of each toy as that uses up all the blue paint.
So the problem is to determine the mix of toys so that as little as possible is wasted and as many toys as possible are made. Based on the Blue Paint if we made 50 (ie 50 million if you multiply by 1,000,000) of each of the seven toys that’s 350 million catered for, not bad for our initial guess of 500 million children but still short. Maybe a better mix would get us to the correct number of toys?
Looking at the costs, a tractor only uses 3KG of wood, 12 nails and 4 Litres of paint. Noah’s Ark takes 18 KG of wood, 25 nails and 15 litres of paint, so we could probably produce 3 – 4 times as many tractors as Noah’s Arks for roughly the same amount of commodities.
In this case, it’s probably a simple enough problem that we can brute force it. We have seven toys to make so we can try varying the proportions of numbers of each toy made to minimise the commodities wasted. We need to pass an array of 7 quantities of each toy with the minimum value of each being no less than 8% of the total made. That way the GetScore() method returns a single value. If any of the commodities remaining goes negative because we’ve specified too many toys to be built then the function returns a very high value.
The brute force algorithm starts with one of each toy and increments the left most element representing the number of Wooden Tractors. First time through it passes in 1,1,1,1,1,1,1 then next time 2,1,1,1,1,1,1 and so on.
Now it’s just a matter of trying each set of values from 1,1,1,1,1,1,1 to the maximum values which I set at 500. Unfortunately it’s 500<sup>7</sup> which is a big number about seven million million million. It’s rather a lot and much of it wasted. But the evaluation function is simple and fast. Originally I was going to do this in Python, but for speed, I chose C#.
This is on Github. It’s been thrown together and there has been little or no optimisation. It will take a very long time to run and should be optimised to run code on other tasks to take advantage of multi core processors.
The structure is a seven nested loop with each being an index into the seven element array holding the number of each toy. Using for loops is highly inefficient, as there’s no way to know which toy number hit the limit. The Evaluate routine determines how many commodities are required for the numbers of each toy and subtracts that from the amount allowed. If any commodity goes negative, the evaluation awards a Fail Score of a million. The lower score the better.
There is a much better way than brute force. It’s called the Simplex algorithm and it creates a multi-dimensional space for each of the components so in this case there would be five. This is nothing to do with time travel or multiple dimensions, just imagine a five dimensional space as an array with five dimensions var a = new Space5d[int,int,int,int,int];
What the Simplex algorithm does is it tries to minimise the distance between your current location and the target location. It’s rated as one of the top ten algorithms of the twentieth century. Merry Christmas!