Instantly share code, notes, and snippets.

@henix /game24.pro
Last active Dec 16, 2015

Embed
What would you like to do?
A 24-game solver in Prolog
/* RPN = Reverse Polish notation */
operator(add).
operator(sub).
operator(mul).
operator(div).
doop(add, A, B, C) :- C = A + B.
doop(sub, A, B, C) :- C = A - B.
doop(mul, A, B, C) :- C = A * B.
doop(div, A, B, C) :- B1 is B, B1 \= 0, C = A / B.
/* rpn2exp(Stack: List, Prog: List, Result: Int, Expr) */
rpn2exp([X], [], X).
rpn2exp(Stack, [Head|Tail], Res) :-
integer(Head),
rpn2exp([Head|Stack], Tail, Res).
rpn2exp([X,Y|Others], [Head|Tail], Res) :-
operator(Head),
doop(Head, Y, X, X1),
rpn2exp([X1|Others], Tail, Res).
eval_rpn(Prog, Res) :- rpn2exp([], Prog, Exp), Res is Exp.
try_prog([A, B, C, D], [A, B, X, C, Y, D, Z], N) :- eval_rpn([A, B, X, C, Y, D, Z], N).
try_prog([A, B, C, D], [A, B, X, C, D, Y, Z], N) :- eval_rpn([A, B, X, C, D, Y, Z], N).
try_prog([A, B, C, D], [A, B, C, X, D, Y, Z], N) :- eval_rpn([A, B, C, X, D, Y, Z], N).
try_prog([A, B, C, D], [A, B, C, X, Y, D, Z], N) :- eval_rpn([A, B, C, X, Y, D, Z], N).
try_prog([A, B, C, D], [A, B, C, D, X, Y, Z], N) :- eval_rpn([A, B, C, D, X, Y, Z], N).
solve24order(Numbers, Prog) :- try_prog(Numbers, Prog, 24).
solve24order(Numbers, Prog) :- try_prog(Numbers, Prog, 24.0).
solve24(Numbers, Prog) :- setof(T, lists:perm(Numbers, T), Bag), lists:member(T1, Bag), solve24order(T1, Prog), rpn2exp([], Prog, E), write(E), nl, fail.
@henix

This comment has been minimized.

Owner

henix commented Apr 21, 2013

TODO: 解决浮点精度问题,比如 3 3 8 8 就得不到答案

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment