Yitzchak Scott-Thoennes wrote:
>
> 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;
> }
> }
or, using a golf glob trick (with a fix for *):
#!/usr/bin/perl -l
use strict;
my $n = '{1,5,6,7}';
my $op = '{+,-,%,/}';
tr/%/*/, /1/ && /5/ && /6/ && /7/ && eval == 21 && print for
<($n$op$n)$op($n$op$n)>,
<(($n$op$n)$op$n)$op$n>,
<($n$op($n$op$n))$op$n>,
<$n$op(($n$op$n)$op$n)>,
<$n$op($n$op($n$op$n))>,
--
Rick Klement
