On Thu, Aug 14, 2003 at 11:02:19AM +0100, Jonathan E. Paton wrote:
> Easy, the fastest method is to use stack based notation (RPN). This
> completely avoids the need for those pesky brackets. The stack is
> arranged into each of the permutations, and then the operators applied
> in each permutation. There is only 24 permutations of the numbers, and
> 64 permutations of the operators, combined there is 1536 different
> expressions. We need to select only those evaluating to 21.
Each of those 1536 expressions has 5 variants corresponding to
the five different ways of parenthesizing the non-RPN version.
You only seem to check 1 of the 5.
Where n is one of the numbers and op is one of the ops, you
need to try:
RPN non-RPN
n n n n op op op n op (n op (n op n))
n n n op n op op n op ((n op n) op n)
n n n op op n op (n op (n op n)) op n
n n op n n op op (n op n) op (n op n)
n n op n op n op ((n op n) op n) op n
Here's my try. Note that special handling may be needed to avoid an
answer for which the computer gets 20.9999999999999 or similar, when
the true answer would be 21. This could involve using something like
Math::BigRat instead of floating point math, or checking for an answer
within some small margin of 21 (which can be done somewhat
automatically by setting the deprecated $# var to the appropriate
precision and stringifying the number). On my system, fudging this
way isn't needed for this problem, but not all the world is 64-bit
IEEE.
#!perl -l
use strict;
# $# = "%.6g"; # uncomment this if needed for your system's floating point math
use warnings;
# build series of ops to use (4*4*4)
my @ops = [];
@ops = map {["+",@$_],["-",@$_],["/",@$_],["*",@$_]} @ops for 1..3;
# apply each possible precedence (4*4*4*5)
my @templates = map {
sprintf("%%d %s (%%d %s (%%d %s %%d)) eq 21", @$_),
sprintf("%%d %s ((%%d %s %%d) %s %%d) eq 21", @$_),
sprintf("(%%d %s (%%d %s %%d)) %s %%d eq 21", @$_),
sprintf("(%%d %s %%d) %s (%%d %s %%d) eq 21", @$_),
sprintf("((%%d %s %%d) %s %%d) %s %%d eq 21", @$_)} @ops;
# and try each permutation of numbers (4*4*4*5*24)
for my $nums (permute(1,5,6,7)) {
eval(sprintf $_, @$nums) and printf("$_\n", @$nums) for @templates;
}
sub permute {
@_ <= 1 ? (wantarray ? [EMAIL PROTECTED] : 1) : do {
my @ret;
for my $i (0..$#_) {
push @ret, grep push(@$_, $_[$i]), permute(@_[0..$i-1,$i+1..$#_])
}
@ret;
}
}
