#! /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)";
	if ($val_a < $val_b) {
          $find_in_sum->{$val_b - $val_a} = "($expr_b - $expr_a)";
	}
	else {
          $find_in_sum->{$val_a - $val_b} = "($expr_a - $expr_b)";
	}
        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 = 0;
while (exists $find_in[9]{$ans}) {
  print "$ans\t$find_in[9]{$ans}\n" if $opt_v;
  $ans++;
}
print "ANSWER: $ans\n";