Looking over the solutions - there seem to be two fundamental
approaches.  Using RPN or using templates - although I suspect I do
not understand Rob Willams rather fast pseudorandom solution well
enough to classify it.  I converted my QM::Superpositions solution to
a more vanilla version rather straightforwardly

#!/usr/bin/perl -l

use strict;

my @tree = my @num = qw!1 5 6 7!;
my @op = qw!+ - / *!;

for ( 1..3 ) {
  my @newtree;
  for my $tree ( @tree ) {
    for my $num ( @num ) {
      for my $op ( @op ) {
        push @newtree, "($num $op $tree)","(($tree $op $num))";
      }
    }
  }
  @tree = @newtree;
}
print join "\n", grep { 21 == eval and not /(\d).*\1/ } @tree;

This can be optimized a little because I am using such a minimal
template, there are often more than one way to parse the final
expression.  If we use a hash instead of a list to store pending
expressions then duplicates get filtered out and only about half as
many expressions get evaluated.  Even with this optimization, however,
mine is the slowest of the versions so far.

Jonathan Paton's claim that:

> Easy, the fastest method is to use stack based notation (RPN).  This

turns out to be true at least on my machine (2.4G Pentium).  Other
speed benchmarks:

[EMAIL PROTECTED] perl$ for i in 1567-* ; do echo $i && time perl $i ; done
1567-jas.pl
(6 / (1 - (5 / 7)))

real    0m3.132s
user    0m3.000s
sys     0m0.130s
1567-jed.pl
6 / (1 - (5 / 7))

real    0m0.398s
user    0m0.390s
sys     0m0.010s
1567-paton.pl
Solution: 6 1 5 7 / - /

real    0m0.189s
user    0m0.180s
sys     0m0.000s
1567-rick.pl
6/(1-(5/7))

real    0m0.776s
user    0m0.580s
sys     0m0.190s
1567-rob.pl
6/(1-5/7)

real    0m0.566s
user    0m0.560s
sys     0m0.010s
1567-todd.pl
6 / (1 - (5 / 7))

real    0m0.403s
user    0m0.390s
sys     0m0.010s
1567-yitz.pl
6 / (1 - (5 / 7)) eq 21

real    0m0.333s
user    0m0.340s
sys     0m0.000s



-- 
Jasvir Nagra
http://www.cs.auckland.ac.nz/~jas

Reply via email to