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.

Below, with an improved, hopefully self-explanatory, notation, is the minimum number of steps needed to produce the shown percentages. In the case of zero percent, 3 cups of water are left in the 3-mug and 1 cup in the 5-mug; in all the rest, all 4 cups of the dilute coffee is left in the 5-mug.

The moves:                                                                      # steps  pct
3Fill 3-->5 3Fill 3-->5 5Dump 3-->5 3Fill                                           7      0 
5Fill 5Pckt 5-->3 5Dump 3-->5 3Fill 3-->5 5-->3 3-->5 5Dump 3-->5 3Fill 3-->5      13      2 
3Fill 3-->5 3Fill 3-->5 5Pckt 5-->3 3-->5 5-->3 3-->5 5Dump 3-->5 3Fill 3-->5      13      4 
3Fill 3-->5 3Fill 3Pckt 3-->5 5-->3 3-->5 5Dump 3-->5 3Fill 3-->5                  11      5 
5Fill 5-->3 3Dump 5-->3 5Fill 5Pckt 5-->3 3Dump 3Fill 3-->5 5-->3 3Dump            12     16 
5Fill 5-->3 3Dump 5-->3 5Fill 5Pckt 5-->3 3Dump                                     8     20 
5Fill 5-->3 3Dump 5-->3 5Fill 5-->3 3Dump 5Pckt                                     8     25 

CLEAR , , 55000
DIM SHARED cup5, cup3, pct5, pct3, hist(16) AS STRING, pkt, used(25)
DIM SHARED minNo(25), mhist(25, 16) AS STRING
FOR i = 0 TO 25: minNo(i) = 99: NEXT

pkt = 1
OPEN "coffee 2.txt" FOR OUTPUT AS #2
chooseOpt 1
PRINT "----"
PRINT #2, "----"
FOR i = 0 TO 25
    IF minNo(i) < 99 THEN
        FOR j = 1 TO minNo(i)
            PRINT mhist(i, j); " ";
            PRINT #2, mhist(i, j); " ";
        NEXT
        PRINT minNo(i); i
        PRINT #2, minNo(i); i
    END IF
NEXT

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 = 0 THEN pct5 = pct3
        IF cup3 = 0 THEN pct3 = pct5
        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 moveNo < minNo(pct3) THEN
                        minNo(pct3) = moveNo
                        FOR i = 1 TO moveNo
                            PRINT hist(i); " ";
                            PRINT #2, hist(i); " ";
                            mhist(pct3, i) = hist(i)
                        NEXT
                        PRINT cup3; cup5; pct3
                        PRINT #2, cup3; cup5; pct3
                    END IF
                END IF
            END IF
        END IF
        IF (cup3 > 0 OR cup5 > 0) AND moveNo < 16 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

Edited on March 9, 2012, 1:33 pm

Posted by Charlie on 2012-03-09 13:14:39