Solving twenty-four puzzles | Hacker News Reader

Solving twenty-four puzzles

blog.plover.com

46 pointsColinWright10 comments

This was the problem for round 2 of the C International Conciseness Contest in early 1993. Submitted programs were to take on stdin a file consisting of one or more problem instances, where each instance consisted of three lines, and solve those there were solvable, and report as unsolvable those that were not.

The first line of each instance gave the number of numbers you had to work with, the second line gave those numbers separated by space, and the third line gave the target number.

Conciseness was measured by the number of tokens in the source code. Here is a copy of the problem specification: http://computer-programming-forum.com/47-c-language/3e0a04a3...

Here was the token counter used for that round: https://pastebin.com/bdaEedD7

Here is the first runner up and the winner: https://pastebin.com/JcamKieX

The runner up is 336 tokens. The winner is 335 tokens.

The best I was able to do was 460 tokens. (Well, the best without exploiting limitations of the token counter, but I was on dial up and so did not have the time to upload a 4 GB source file...)

I never bothered creating a program to solve this as I prefer to do the exercise mentally. I've been playing with 1440 puzzles: one for each display of a 24 hour clock. The puzzle is simple: take a displayed time and using the 4 displayed numbers and the 4 basic operations (+ - x /), make it solve to zero. To make it more complex, it is forbidden to multiply by zero. Eg. 12:34 >> (1+4)-(2+3)=0. The puzzle does not solve for all hours, but it does for 12:3x and many other times

That's a neat puzzle! Here is the Prolog code I posted earlier, extended and adapted to solve such tasks:

First, let us again start with a suitable operator definition, so that we can use × as an infix operator in expressions:

    :- op(400, yfx, ×).

Next, let us declaratively describe what we mean by a "clock", using integer constraints:

    clock(Vs) :-
            Vs = [H0,H1,M1,M2],
            Vs ins 0..9,
            H0*10 + H1 #< 24,
            M1*10 + M2 #< 60,
            label(Vs).

For example:

    ?- clock(Vs).
    Vs = [0, 0, 0, 0] ;
    Vs = [0, 0, 0, 1] ;
    Vs = [0, 0, 0, 2] ;
    Vs = [0, 0, 0, 3] .

We can collect all solutions as a quick verification:

    ?- findall(., clock(Vs), Ls), length(Ls, L).
    Ls = ['.', '.', '.', '.', '.', '.', '.', '.', '.'|...],
    L = 1440.

This confirms that there are 1440 puzzles of this kind, one for each possible clock time.

The puzzle now asks for expressions that evaluate to 0. We can relate any given clock display to an expression like this:

    clock_solution(Vs, Expr) :-
            clock(Vs),
            numbers_tree(Vs, T),
            tree_op_expr_value(T, _, Expr, 0).

This reuses predicates I posted earlier, which I only need to slightly modify to prohibit multiplication by zero, and which I repeat here for completeness:

    numbers_tree([N], leaf(N)).
    numbers_tree(Vs0, binary(Left, Right)) :-
            permutation(Vs0, Vs),
            append([L|Ls], [R|Rs], Vs),
            numbers_tree([L|Ls], Left),
            numbers_tree([R|Rs], Right).

    tree_op_expr_value(leaf(N), _, N, N).
    tree_op_expr_value(binary(Left0, Right0), Op, Expr, Value) :-
            tree_op_expr_value(Left0, _, Left, VL),
            tree_op_expr_value(Right0, _, Right, VR),
            op_values_value(Op, VL, VR, Value),
            Expr =.. [Op,Left,Right].

    op_values_value(+, A, B, V) :- V is A + B.
    op_values_value(-, A, B, V) :- V is A - B.
    op_values_value(×, A, B, V) :- A =\= 0, B =\= 0, V is A * B.
    op_values_value(/, A, B, V) :- B =\= 0, V is A rdiv B.

We can use this to enumerate all times that have a solution:

    ?- clock(C),
       once(clock_solution(C, S)).
    C = [0, 0, 0, 0],
    S = 0+(0+(0+0)) ;
    C = [0, 0, 0, 1],
    S = 0/(0+(0+1)) ;
    C = [0, 0, 0, 2],
    S = 0/(0+(0+2)) ;
    C = [0, 0, 0, 3],
    S = 0/(0+(0+3)) .

And here is the list of all times that don't have a solution:

    ?- clock(C),
       \+ clock_solution(C, S).
    C = [1, 6, 4, 8] ;
    C = [1, 7, 4, 9] ;
    C = [1, 7, 5, 9] ;
    C = [1, 8, 4, 6] ;
    C = [1, 9, 4, 7] ;
    C = [1, 9, 5, 7] ;
    false.

Hmm, I think there also needs to be a rule that you can't have a numerator of 0, otherwise any case where you have an expression a * b = 0 with a = 0 then either b=0 or a / b = 0. So the restriction that you can't multiply by 0 becomes somewhat meaningless.

The constraints I impose are sufficient to exclude such cases in multiplications: a/b is first evaluated, and if the result is 0, it is precluded from multiplications. To avoid also divisions resulting in 0, you are right: We can easily constrain the nominator to express this, completely analogously to multiplication. This goes beyond the initial requirements though.

Nice, thank you for sharing! For comparison, here is a Prolog solution for one of the mentioned puzzles, namely "an unusually difficult puzzle of this type, which is to make 2,5,6,6 total to 17".

Let us start by defining suitable operators so that we can conveniently use the domain-specific language to reason about such tasks, using infix notation:

    :- op(400, yfx, ×).
    :- op(400, yfx, ÷).

Next, I describe the relation between a list of numbers and possible shapes of binary trees we can build from these numbers. We distinguish between leaves and inner nodes of the tree, and consequently use two functors that let us symbolically distinguish the different cases:

    numbers_tree([N], leaf(N)).
    numbers_tree(Vs0, binary(Left, Right)) :-
            permutation(Vs0, Vs),
            append([L|Ls], [R|Rs], Vs),
            numbers_tree([L|Ls], Left),
            numbers_tree([R|Rs], Right).

For example:

    ?- numbers_tree([1,2], T).
    T = binary(leaf(1), leaf(2)) ;
    T = binary(leaf(2), leaf(1)) ;
    false.

This does not yet say anything about the arithmetic operators that we can use. Note that this definition may yield redundant solutions, as in:

    ?- numbers_tree([1,1], T).
    T = binary(leaf(1), leaf(1)) ;
    T = binary(leaf(1), leaf(1)) ;
    false.

That's completely OK though, and we can think about making it more efficient if necessary.

Now we are almost done. It only remains to describe how different arithmetic operations affect the result of the evaluation. This can be expressed with the following relations:

    tree_op_expr_value(leaf(N), _, N, N).
    tree_op_expr_value(binary(Left0, Right0), Op, Expr, Value) :-
            tree_op_expr_value(Left0, _, Left, VL),
            tree_op_expr_value(Right0, _, Right, VR),
            op_values_value(Op, VL, VR, Value),
            Expr =.. [Op,Left,Right].

    op_values_value(+, A, B, V) :- V is A + B.
    op_values_value(-, A, B, V) :- V is A - B.
    op_values_value(×, A, B, V) :- V is A * B.
    op_values_value(÷, A, B, V) :- B =\= 0, V is A rdiv B.

Time to try it out, using for example the following query:

    ?- time((numbers_tree([2,5,6,6], T),
             tree_op_expr_value(T, _, Expr, 17))).

This yields:

    % 6,060 inferences, 0.004 CPU in 0.004 seconds (92% CPU, 1551459 Lips)
    T = binary(binary(leaf(2), binary(leaf(5), leaf(6))), leaf(6)),
    Expr =  (2+5÷6)×6 .

It seems to work nicely. On backtracking, all solutions are generated. Note that this solution uses built-in rational numbers that are available in several Prolog systems.

Thank you for this! As soon as I saw the problem, I thought "use prolog".

You are welcome! Prolog is a great investment: Once you have put in enough effort to solve practical tasks with it, it pays off big time, much like compound interest of capital.

I used to ask this as an interview question at Parse. I don't think it's that good of an interview question any more though. But it is definitely interesting to see how people try to solve it!

i wonder what the complexity of the generalized version of the problem is. it is a bit similar to subset sum, which is np complete.

in this problem we have 4 operators (+, -, /, *) to consider instead of just 1 (+), so it is more complex than subset sum in this regard. also as a result of having different operators, the ordering of the numbers matter in this case, which doesn't matter in subset sum. however the fact that we have to use each number exactly once significantly reduces the search space

Reply on news.ycombinator.com