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 3-mug and the 5-mug.

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 2012-03-06 13:54:14