Assignment 5 Witches

Programming Assignment 5

2 Witches
Three witches are brewing potions around their cauldron when they notice that
someone has mixed up all n of their carefully crafted potions. Each potion is a
carefully-measured mixture of exact ratios of m distinct individual components
(e.g. eye of newt, etc.). Mixed together, even though the components are the
same, the ratios of the potions are now all wrong and will not have the desired
effect.
Luckily, the vials in which the potions are kept are bottomless. In theory,
the witches have an unbounded amount of each of the messed-up potions.
There is one potion in particular that the witches are interested in making
so they need to combine the potions that they have into their cauldrons so as
to come up with the correct ratio for it.
Consider the following example where n = 2 and m = 3: Two potions are
available with the ratios of 1:2:3 and 3:7:1, respectively. By mixing those two
solutions together in the ratio 1:2, it is possible to obtain a solution of the m = 3
components with ratio 7:16:5, but there is no way to combine these two potions
together into a new one with ratio 3:4:5. However, if the witches find another
potion with ratio 2:1:2 (making the problem into one where n = 3), then a 3:4:5
mixture is possible with eight parts of 1:2:3, one part 3:7:1, and 5 parts of 2:1:2.
So clearly, determining which mixtures can be obtained from a given set of
potions is not trivial. It is your goal in this assignment to do so.
3 Input/Output
The top line of the input file (input.txt) will be a line with a desired ratio in
the form a1 : a2 : a3 : . . . : am. The next n lines will be the base solution ratios.
Your output file (output.txt) will consists of n lines, each containing a single
integer. These will indicate the parts necessary to get the desired ratio. If no
combination is possible, then return the value −1 on each line.
1
So, for example above, the input file (input.txt) would look as follows:
3:4:5
1:2:3
3:7:1
2:1:2
and the output file (output.txt) would look as follows:
8
1
5
2