
my $max_expr_size = 9;
my @exprs;

my @ops = qw(+ - * /);

$exprs[1]{"9/1"} = '9';

################################################################
# Rational arithmetic

sub gcd { 
  my ($a, $b) = @_;
  $b ? gcd($b, $a%$b) : $a;
}

sub rat {
  my ($n, $d) = @_;
  my $gcd = gcd(@_);
  join '/', $n/$gcd, $d/$gcd;
}

sub splitrats {
  (split(m{/}, $_[0]), split(m{/}, $_[1]));
}

sub mul_r { my ($an,$ad,$bn,$bd) = @_;
            rat($an*$bn, $ad*$bd);      }

sub div_r { my ($an,$ad,$bn,$bd) = @_;
            rat($an*$bd, $ad*$bn);      }

sub add_r { my ($an,$ad,$bn,$bd) = @_;
            rat($an*$bd+$bn*$ad, $ad*$bd);       }

sub sub_r { my ($an,$ad,$bn,$bd) = @_;
            rat($an*$bd-$bn*$ad, $ad*$bd);      }

################################################################

for $size (2 .. $max_expr_size) {
  for $a (1 .. $size-1) {
    my $b = $size - $a;
    print STDERR "$a + $b = $size\n";
    my %a_exprs = %{$exprs[$a]};
    my %b_exprs = %{$exprs[$b]};
    $exprs[$size] = {} unless defined $exprs[$size];
    my $x = $exprs[$size];
    while (my ($av, $ae) = each %a_exprs) {
      while (my ($bv, $be) = each %b_exprs) {
        my @parts = splitrats($av, $bv);
        my @new;
        push @new, add_r(@parts) => '+' if $a <= $b;
        push @new, sub_r(@parts) => '-';
        push @new, mul_r(@parts) => '*' if $a <= $b;
        push @new, div_r(@parts) => '/' if $parts[2] != 0;

        while (@new) {
          my ($val, $op) = splice @new, 0, 2;
          $x->{$val} = "($ae$op$be)" unless defined $x->{$val};
        }
      }
    }
    for my $val (keys %$x) {
      my $neg = "-$val";
      $neg =~ s/^--//;
      $x->{$neg} = "-($x->{$val})" unless defined $x->{$neg};
      $x->{$val} =~ s/--/+/g;
    }
  }
}

for my $s (2 .. $max_expr_size) {
  my $v;
  printf "\n\n With $s nines:\n";
  for ($v = 1; defined($exprs[$s]{"$v/1"}); $v++) {
    printf "%4d: %s\n", $v, $exprs[$s]{"$v/1"};
  }
  print "Smallest number that can't be made from $s nines: $v\n";
}

exit;
use Data::Dumper;
print Data::Dumper::Dumper(\@exprs);
