2
$\begingroup$

There is a card game here in China, use a standard 52 card deck of cards. Draw four cards and use any elementary operators $(+,-,\times, \div)$, and only use each card value once to get a result of 24.

The cards start with Ace = 1 to King = 13.

example: The four cards are 5,5,5,1. $\left(5-\left(1\div 5\right)\right)\times 5=24$

Is there some method other than brute force to find a solution for solvable solutions? I am asking because I don't think anyone has the time to do every combination.

$\endgroup$
  • $\begingroup$ How would you get 24 from four aces? Or four kings or four jacks? $\endgroup$ – Olivier Bégassat Mar 1 '14 at 15:37
  • $\begingroup$ @OlivierBégassat , I was so caught up on solving the example I gave, that I didn't take time to think of a counter example. Great job. I should have asked how to find all the solvable ones. $\endgroup$ – yiyi Mar 1 '14 at 15:39
  • $\begingroup$ You can modify your question. $\endgroup$ – Olivier Bégassat Mar 1 '14 at 15:40
  • 1
    $\begingroup$ I used a computer running a brute-force algorithm to enumerate 53,005 solutions, which I believe is a complete list. You can see the output here. $\endgroup$ – MJD Mar 1 '14 at 18:20
  • $\begingroup$ The current version eliminates some solutions that can be trivially obtained from others by commuting $a+b$ to $b+a$ and the like; this reduces the listing to 17,373 solutions. $\endgroup$ – MJD Mar 1 '14 at 19:44
2
$\begingroup$

I don't know of any method to solve this other than brute force, but the computer is really good at solving things by brute force, so I got the computer to do it.

The program's main data structure is a series of hash tables stored in $seen[1], $seen[2], $seen[3], $seen[4]. Each table maps numeric values to lists of expressions that represent that value. $seen[i] contains expressions with i leaves. $seen[1] is manually initialized. Then the function scan_seen is run to scan over every pair of expressions in $seen[1]. Each pair is assembled into a larger expression and inserted under the correct key in $seen[2]. Then more scans are done, until `$seen[4] is completely populated. At this point it contains every possible expression with four leaves, grouped by expression value.

The definitions of the operators are in the %op table. An operator is allowed to return an undefined value to indicate that no expression should be retained in @seen. For example, the division operator does this when the divisor is zero. But also multiplication and addition do this when the second argument exceeds the first; this prevents the program from indexing both $a+b$ and $b+a$.

Because every operator is considered to require exactly two arguments, the program distinguishes the expressions $a + (b +c)$ from $(a+b)+c$. Also the hack for eliminating commutators doesn't help the program realize that $a + (b+c)$ is the same as $b + (a + c)$. A lot of improvements could be put into the code to eliminate solutions that are too similar to other solutions.

Once every possible expression with four leaves is indexed, we just emit all the expressions in $seen[4]{24}, which is the ones whose value is 24. The complete output is here. I sorted the output expressions, which the program itself doesn't do.

It would be more effective to have the program emit all the solutions for all values, with solutions for each value into a different file, since at this point it has them all prepared; changing the program to do that is easy.

Complete code is here. Perl is good for this kind of programming because it runs reasonably quickly, and you don't waste a lot of time on implementing the data structures or doing memory management.

[ Addendum 2017-09-18: I wrote a series of articles about various aspects of this puzzle: (1) (2) (3) ]

$\endgroup$
1
$\begingroup$

You can write a computer program. Probably the easiest is to think of an RPN calculator For each set of four card values loop over the three operation signs and evaluate. Report success or failure for that combination of card values. I don't think there is a good hand approach.

$\endgroup$
  • $\begingroup$ It's not enough to loop over the operation signs; you have to also loop over the possible expression forms, because for example $1 2 3 4 + - ×$ is different from $1 2 + 3 - 4 ×$ and $1 2 + 3 4 - ×$. $\endgroup$ – MJD Mar 1 '14 at 18:31
1
$\begingroup$

Here is a Maple program to solve this by way of Rosetta-stone like enrichment. This code is compact and reasonably efficient.

Use it like this:

> query([5,5,5,5,5,6], 40, 45);
40: ((((6 / (5 + 5)) * 5) + 5) * 5)
41: (((((6 / 5) + 5) * 5) + 5) + 5)
42: ((6 * (((5 * 5) + 5) + 5)) / 5)
43: (((5 - (6 / 5)) * (5 + 5)) + 5)
44: (((((5 + 5) * 5) - 6) - 5) + 5)
45: (((6 - ((5 + 5) / 5)) + 5) * 5)

or like this

> query([1,2,3,4,5], 40, 45);
40: (((5 + (4 * 2)) * 3) + 1)
41: ((((5 + 3) + 2) * 4) + 1)
42: ((((5 * 4) * 2) + 3) - 1)
43: (((5 + (3 * 2)) * 4) - 1)
44: (((5 + 4) * (3 + 2)) - 1)
45: (((5 + 4) * (3 + 2)) * 1)

or like this

> query([2,2,2,2,2], 16, 32);
16: ((((2 + 2) + 2) + 2) * 2)
17: FAIL
18: ((((2 + 2) * 2) * 2) + 2)
19: FAIL
20: ((((2 + 2) * 2) + 2) * 2)
21: FAIL
22: FAIL
23: FAIL
24: ((((2 + 2) + 2) * 2) * 2)
25: FAIL
26: FAIL
27: FAIL
28: FAIL
29: FAIL
30: FAIL
31: FAIL
32: ((((2 + 2) * 2) * 2) * 2)

or finally

> query([4,4,4,6,6], 16, 32);
16: ((((6 - 6) * 4) + 4) * 4)
17: ((((6 * 6) / 4) + 4) + 4)
18: ((((6 * 4) - 6) - 4) + 4)
19: ((((6 + 4) * 6) / 4) + 4)
20: ((((6 * 6) / 4) - 4) * 4)
21: (((6 / 6) + (4 * 4)) + 4)
22: (((6 - (6 / 4)) * 4) + 4)
23: ((4 - ((4 / 6) / 4)) * 6)
24: (((6 * (4 - 4)) + 6) * 4)
25: (((6 + 4) * (6 + 4)) / 4)
26: ((((6 * 4) - 6) + 4) + 4)
27: (((6 / (4 + 4)) + 6) * 4)
28: ((((6 + 6) / 4) + 4) * 4)
29: ((((6 / 4) + 4) * 6) - 4)
30: ((((6 * 4) + 6) - 4) + 4)
31: (((6 * 6) - (4 / 4)) - 4)
32: ((((6 - 6) + 4) + 4) * 4)

This is the source code in Maple:

with(combinat);

expr :=
proc(mset)
    option remember;
    local res, len, idx, bits, b, mseta, msetb,
    ta, tb, exa, exb, vp, vals, seen;

    len := nops(mset);

    res := table();

    if len = 1 then
        res[mset[1]] := convert(mset[1], string);
        return op(res);
    fi;

    seen := table();

    for idx from 2^len+1 to 2^(len+1)-2 do
        bits := convert(idx, base, 2);
        mseta := []; msetb := [];

        for b to len do
            if bits[b] = 0 then
                mseta := [op(mseta), mset[b]];
            else
                msetb := [op(msetb), mset[b]];
            fi;
        od;

        if type(seen[mseta], boolean) then
            next;
        fi;
        seen[mseta] := true;

        ta := expr(mseta); tb := expr(msetb);

        for exa in [indices(ta, 'nolist')] do
            for exb in [indices(tb, 'nolist')] do
                vals :=
                [[exa + exb,
                  sprintf("(%s + %s)", ta[exa], tb[exb])],
                 [exa - exb,
                  sprintf("(%s - %s)", ta[exa], tb[exb])],
                 [exa * exb,
                  sprintf("(%s * %s)", ta[exa], tb[exb])]];

                if exb <> 0 then
                    vals :=
                    [op(vals),
                     [exa / exb,
                      sprintf("(%s / %s)", ta[exa], tb[exb])]];
                fi;

                for vp in vals do
                    if not(type(res[vp[1]], string)) then
                        res[vp[1]] := vp[2];
                    fi;
                od;
            od;
        od;
    od;

    op(res);
end;

query :=
proc(vals, targmin, targmax)
    local targ, res;

    res := expr(sort(vals));

    for targ from targmin to targmax do
        if type(res[targ], string) then
            printf("%d: %s\n", targ, res[targ]);
        else
            printf("%d: FAIL\n", targ);
        fi;
    od;
end;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.