You can skip the - very easily
There is a complete and utter symmetry of positive and negative at the numbers you can reach in all of the calculations. Noticing and using this means that if you only consider calculations with non-negative pairs of numbers that will result in non-negative numbers, you get a factor of 4 reduction in combinations of pairs of numbers, and have shorter sets of expressions to include.
This ties directly into the fact that there is no need to consider every possible expression. You merely need to be sure that you visit every possible value. (Or actually every non-negative value.)
For the Perl solution you also have to assume that floating point round-off is not going to rear its ugly head. This is true, but proving it is non-trivial.
The following solution is not my fastest in Perl, but it is not too far off and has the benefit that with a -v argument you get told the expressions leading to smaller numbers. Note that Perl is an extremely poor solution for this problem because it spends a lot of time doing number-string conversions. (As is seen by the fact that building up the actual string expressions is relatively little extra work.)
(BTW Scott, I loathe my workaround for the extra returns...)
#! /usr/bin/perl
use strict;
use Getopt::Std;
getopts('v');
use vars qw($opt_v @find_in);
# Set up my array of hashes of how to find various numbers with
# n 9's.
@find_in =(
{}, # None of size 0!
{ 9 => '9' }, # 2 with 1 9
map {}, 2..9
);
foreach my $i (1..9) {
print "Searching depth $i\\n" if $opt_v;
my $find_in_a = $find_in[$i];
foreach my $j (1..$i) {
next if 9 < $i + $j;
print " Searching combinations of $i, $j\\n" if $opt_v;
my $find_in_b = $find_in[$j];
my $find_in_sum = $find_in[ $i+$j ];
foreach my $val_a (keys %$find_in_a) {
my $expr_a = $find_in_a->{$val_a};
foreach my $val_b (keys %$find_in_b) {
my $expr_b = $find_in_b->{$val_b};
$find_in_sum->{$val_a + $val_b} ||= "($expr_a + $expr_b)";
$find_in_sum->{$val_a * $val_b} ||= "($expr_a * $expr_b)";
\tif ($val_a < $val_b) {
$find_in_sum->{$val_b - $val_a} ||= "($expr_b - $expr_a)";
\t}
\telse {
$find_in_sum->{$val_a - $val_b} ||= "($expr_a - $expr_b)";
\t}
if (0 != $val_b) {
$find_in_sum->{$val_a / $val_b} ||= "($expr_a / $expr_b)";
}
if (0 != $val_a) {
$find_in_sum->{$val_b / $val_a} ||= "($expr_b / $expr_a)";
}
}
}
}
}
my $ans = 1;
while (exists $find_in[9]{$ans}) {
print "$ans\\t$find_in[9]{$ans}\\n" if $opt_v;
$ans++;
}
print "ANSWER: $ans\\n";
Cheers,
Ben
