This is in continuation of
A Cup Of Coffee.
You have a five cup mug, a three cup mug, a water supply, a sink with a drain, and a packet of instant coffee which when dissolved in one cup of water produces coffee of strength 100%.
The packet may be used at any time, but the entire contents of the packet must be dissolved into a single mug when it is used.
What integer values of c (from 1 to 25 inclusively) is possible if the task is to fix 4 cups of coffee at exactly c% strength? Prove that these are indeed the only possible values of c.
The last item in each group below is the percent, so those values are: 0, 25, 20, 5, 4, 16 and 2. A digit followed by "Fill" means to fill that sized mug. A digit followed by "T" means to transfer from that mug to the other mug as much as possible. A digit followed by "Dump" means just to dump the contents in the drain. "Pckt" means to mix the packet into that mug. The two numbers before the final percent represent the number of cups left in the 3mug and the 5mug.
3Fill 3T 3Fill 3T 3Dump 3Fill 3Dump 3Fill 3Dump 5T 3Dump 5T 5Fill 5T 3Dump 0 4 0
3Fill 3T 3Fill 3T 3Dump 3Fill 3Dump 5T 3Dump 5T 5Fill 5T 3Dump 5Pckt 5T 3 1 25
3Fill 3T 3Fill 3T 3Dump 3Fill 3Dump 5T 3Dump 5T 5Fill 5Pckt 5T 3Dump 5T 3 1 20
3Fill 3T 3Fill 3T 3Pckt 5T 3T 5T 3T 5Dump 3T 3Fill 3T 5T 3 1 5
3Fill 3T 3Fill 3T 5Pckt 5T 3T 5T 3T 5Dump 3T 3Fill 3T 5T 3 1 4
3Fill 3T 5Fill 5T 3Dump 5T 5Fill 5Pckt 5T 3Dump 3Fill 3T 5T 3Dump 5T 3 1 16
5Fill 5Pckt 5T 5Dump 3T 3Fill 3T 5T 3T 5Dump 3T 3Fill 3T 5T 3 1 2
The program explored only to what's possible with up to 15 steps, and it's not necessarily the shortest that is reported.
To take the 16% as an example:
3mug 5mug
3Fill 3 0
3T 0 3
5Fill 0 5 (such a waste here,
5T 3 2 but this one came first in the logic)
3Dump 0 2
5T 2 0
5Fill 2 5
5Pckt 2 5 (20%)
5T 3(x%) 4 (20%)
3Dump 0 4 (20%)
3Fill 3 4 (20%)
3T 2 5 (16%)
5T 3(x%) 4 (16%)
3Dump 0 4 (16%) (why didn't it stop here?; bug?)
5T 3(16%) 1 (16%)
I see my bug: the percent was different in the two mugs, though there was nothing in one.
CLEAR , , 25000
DIM SHARED cup5, cup3, pct5, pct3, hist(15) AS STRING, pkt, used(25)
pkt = 1
OPEN "coffee 2.txt" FOR OUTPUT AS #2
chooseOpt 1
CLOSE 2
SUB chooseOpt (moveNo)
FOR cup = 3 TO 5 STEP 2
IF pkt THEN max = 4: ELSE max = 3
FOR action = 1 TO max
cup5h = cup5: cup3h = cup3: pct5h = pct5: pct3h = pct3: pkth = pkt
SELECT CASE action
CASE 1
hist(moveNo) = LTRIM$(STR$(cup)) + "T"
IF cup = 3 THEN holds = 5  cup5: ELSE holds = 3  cup3
IF cup = 3 THEN has = cup3: ELSE has = cup5
IF has < holds THEN trans = has: ELSE trans = holds
IF trans > 0 THEN
IF cup = 3 THEN
pct5 = (pct5 * cup5 + pct3 * trans) / (cup5 + trans)
cup5 = cup5 + trans: cup3 = cup3  trans
ELSE
pct3 = (pct3 * cup3 + pct5 * trans) / (cup3 + trans)
cup3 = cup3 + trans: cup5 = cup5  trans
END IF
END IF
CASE 2
hist(moveNo) = LTRIM$(STR$(cup)) + "Dump"
IF cup = 3 THEN cup3 = 0: ELSE cup5 = 0
CASE 3
hist(moveNo) = LTRIM$(STR$(cup)) + "Fill"
IF cup = 3 THEN
pct3 = pct3 * cup3 / 3
cup3 = 3
ELSE
pct5 = pct5 * cup5 / 5
cup5 = 5
END IF
CASE 4
IF cup = 3 AND cup3 > 0 OR cup = 5 AND cup5 > 0 THEN
hist(moveNo) = LTRIM$(STR$(cup)) + "Pckt"
IF cup = 3 THEN pct3 = 100 / cup3: ELSE pct5 = 100 / cup5
pkt = 0
END IF
END SELECT
IF cup5 + cup3 = 4 THEN
pctr5 = INT(pct5 + .5): pctr3 = INT(pct3 + .5)
IF pctr5 = pctr3 THEN
IF ABS(pctr5  pct5) < .00001 THEN pct5 = pctr5
IF ABS(pctr3  pct3) < .00001 THEN pct3 = pctr3
IF pct3 = INT(pct3) AND pct5 = INT(pct5) THEN
IF used(pct3) = 0 THEN
FOR i = 1 TO moveNo
PRINT hist(i); " ";
PRINT #2, hist(i); " ";
NEXT
PRINT cup3; cup5; pct3
PRINT #2, cup3; cup5; pct3
used(pct3) = 1
END IF
END IF
END IF
END IF
IF (cup3 > 0 OR cup5 > 0) AND moveNo < 15 AND (cup5 <> cup5h OR cup3 <> cup3h OR pkt <> pkth) THEN chooseOpt moveNo + 1
cup5 = cup5h: cup3 = cup3h: pct5 = pct5h: pct3 = pct3h: pkt = pkth
NEXT
NEXT
END SUB

Posted by Charlie
on 20120306 13:54:14 