24 game automated solver
The goal is to write a program, whose byte size is minimized, that inputs four integers, not necessarily distinct, chosen from $1, 2, 3, ..., 9$ and then determines if it is possible to combine the inputted numbers using only the operations of addition, subtraction, multiplication and division to form a mathematical expression whose value is $24$. Parentheses are allowed.
If it is possible, the program displays an expression whose value is $24$.
Otherwise, the program displays the word "Impossible", false, 0 or something similar; the choice is yours as long as you are consistent.
By "display", I mean any output (such as displaying on the screen or the return value of a function).
Clarifications:
You may choose any input format you like as long as you use the same format for all test cases.
You may choose any output format you like for expressions such as normal mathematical notation OR Reverse Polish Notation OR …
The expression you form must contain each inputted number exactly once.
You may only use the four arithmetic operations mentioned above, so no square roots, no factorials, …
Although subtraction is allowed, the use of a negative sign is not allowed. Similarly, negation of a number or expression is not allowed.
Decimal points are not allowed.
Assume everything is done in base $10$.
Concatenation in any form is not allowed.
Test cases:
There may be multiple ways for the inputted numbers to form $24$. Your program only needs to display one such expression, not necessarily the ones listed below.
3357 -> 3(3x5-7)
1346 -> 6/(1-3/4)
3377 -> 7(3+3/7)
3388 -> 8/(3-8/3)
1116 -> Impossible
1179 -> Impossible
1557 -> Impossible
1577 -> Impossible
1277 -> (7x7-1)/2
1668 -> 6/(1-6/8)
5599 -> 5x5-9/9
2244 -> 2(2x4+4)
2222 -> Impossible
3358 -> Impossible
3467 -> Impossible
7899 -> Impossible
3333 -> 3x3x3-3
If you wish you can try my 24 Game solver available here:
https://openprocessing.org/sketch/2927650
You interact with my program with finger taps or mouse clicks.
2 answers
Perl 5, 228 bytes
Brute-force check.
Reads line of space-separated digits from stdin. Prints answer to stdout.
If empty output is permitted as "impossible", omit final say to save 10 bytes.
perl -aE'map{@o=/./g;for$f("15(26(374))","15((263)74)","(15(263))74","(152)6(374)","((152)63)74"){map{$_=sprintf$f=~s/\d/%$&\$s/gr,@F[@o],/./g;24-eval||exit!say}glob"{+,-,\\*,/}"x 3}}grep!/(.).*\1/,glob"{0,1,2,3}"x 4;say"false"'
echo 1 2 3 4 | perl -aE '
# 0. the four numbers are loaded into @F by -a option
# 2. loop over each permutation of offsets
map {
@o = /./g; # temp var as $_ is overwritten in inner map
# 3. loop over the five ways to group operations
# $f is a compressed format string for sprintf
for $f (
"15(26(374))",
"15((263)74)",
"(15(263))74",
"(152)6(374)",
"((152)63)74"
){
# 5. loop over each operator combination
map {
# 6. expand the format string
# substitute in the numbers and operators
# save resulting expression as $_ (for eval/say)
$_ =
sprintf
$f =~ s/\d/%$&\$s/gr,
@F[@o], /./g
;
# 7. execute the expression
# if result is 24, print expression and exit
24-eval || exit !say
# 4. generate all combinations of three operators
} glob "{+,-,\\*,/}" x 3
}
# 1. generate all permutations of the offsets into @F
} grep !/(.).*\1/, glob "{0,1,2,3}" x 4;
# 8. if we get here, no solution was found
say "false"
'
Perl 5, 178 bytes
Another brute-force approach.
Reads line of space-separated digits from stdin.
If possible, prints answer to stdout and exits 1. Otherwise prints nothing and exits 0.
perl -aE'sub R{for my$i(0..$#_-1){for my$j($i+1..$#_){my@r=@_;$a=splice@r,$j,1;$b=splice@r,$i,1;map{@r?R(@r,"($_)"):24eq eval&&exit say}map{("$a$_$b","$b$_$a")}qw|+ - * /|}}}R@F'
echo 2 7 8 9 | perl -aE'
# recursive checker
sub R {
# get all choices of two arguments
for my $i (0..$#_-1) {
for my $j ($i+1..$#_) {
# extract them and save the remainder
my @r = @_;
$a = splice @r,$j,1;
$b = splice @r,$i,1;
# build list of expressions that apply
# an operation to the choice
# for each expression:
# if there is a remainder, recurse with them
# else expression is complete
# so if it equals 24, print it and exit(1)
map {
@r ? R(@r,"($_)")
: 24 eq eval && exit say
} map {
("$a$_$b","$b$_$a")
} qw|+ - * /|
}
}
}
# digits are loaded into @F by -a option
# invoke the checker on them
R @F
# if we get here, exit(0)
'
0 comment threads
2 comment threads