Here's an even better response from a friend of mine:
definitely liked this problem (enough that I hacked on it some last
night and then got up early to finish it today).
[ spoiler. don't read if you want to work on this problem or apply at
ITA. ]
The problem is equivalent to finding a 9-leafed (at most binary) parse
tree corresponding to an expression (leaf nodes are "9", internal nodes
are operators in [*/+-]) which, when postorder traversed and evaluated
as an expression, produces the desired result. So going to postfix
actually doesn't change the problem any (as the parse tree is identical,
it's just the method of traversal which changes).
The brute force solution is exponential since it's basically "the same"
[0]
as optimal matrix multiplication which has the complexity of the Catalan
numbers. I admit I had to look up the actual recurrence for the Catalan
numbers (it's not one of those things I keep fresh in my head), which
is:
C(n) = 1/(n+1) * [ 2n choose n ]
which works out to a lower bound of
Omega( 4^n / n^(3/2) )
which is not good asymptotically [1].
Realistically, however, C(9) by that relation is only on the order of
10000. With 65536 sentences to parenthesize we should be able to
determine the exact value of every "9 9s" expression in ~ 650M tests
(multiply that by 2^9 when we allow unary minus, however). That's big
but potentially tractable, especially if you like to take a long time
getting your coffee. It shouldn't make us feel too good though,
especially considering that we may be able to find an O(n^3) dynamic
programming solution (as that's the usual method of solving optimal
matrix multiplication). For n=9 that's some constant overhead times 729
tests. This may be mere parenthesization, requiring all 65536 sentences
to be parenthesized to find the smallest non-expressible integer, but
we've still saved more than a factor of 10 even if we have to punt
there.
The parse tree representation suggests itself since it is inherently
recursive, which makes for easy building of larger solutions from
already computed smaller solutions (a hallmark of dynamic programming).
Note that building possible parse trees recursively (i.e., "top down")
is equivalent to brute-force enumeration.
The expression containing one 9 is represented by the simple parse tree:
9
The parse tree for this expression consists of 1 node with the value 9.
If we consider the possible parse trees with one more leaf node (a "9",
of course) we have ("9." represents the original single node tree, where
it is relevant) the following 6 trees:
- - + * / /
9. 9 9 9. 9 9 9 9 9. 9 9 9.
with expression values:
0 0 18 81 1 1
Let V(T) represent the value of the expression encoded by the tree T.
The final piece of the puzzle is to realize that a value V_n is
representible by an n-leaf tree T_n if there are two trees T_i and T_j
such that:
i,j integer
1 <= i,j < n,
i + j = n
V(T_i) + V(T_j) = n
or
V(T_i) - V(T_j) = n
or
V(T_i) / V(T_j) = n
or
V(T_i) * V(T_j) = n
or
V(T_j) - V(T_i) = n
or
V(T_j) / V(T_i) = n
This implies that higher-order solutions are a combination of lower
order solutions.
The perl script below uses dynamic programming to solve the problem
relatively efficiently (it takes a couple of minutes to run on my
PII-400 -- while ripping mp3's; of course it only takes 33 seconds to
run on scooby) and even leaves some flexibility for experimentation:
[0] There are 8 operator positions, each with 4 possible values. This
is equivalent to 65536 different expression sentences -- each of which
has a Catalan number [ C(9) ] of parenthesizations. This must be
multiplied by an additional factor of 2^9 to account for the possibility
of using the unary '-' at any location (this is equivalent to allowing
'-9' to appear as a leaf node in addition to '9'). The optimal matrix
multiplication problem is a problem in which the placement of
parentheses is the only real variable. Thus optimal matrix
multiplication solves the "9 9s" problem, modulo a factor of 65536
(modulo unary '-') so by this analysis the brute-force enumeration is
for most purposes equivalent, though this problem is asymptotically
worse in the general case (well Omega(C(n) * 4^(n-1)*2^n) =>
Omega(4^(3n-1)/n^(3/2))). It should be clear that the "enumerate
expressions and solve parenthesization" problem is identical with the
"find a binary parse tree" problem since there is a 1:1 correspondences
between sentences+parenthesization and parse trees.
[1] optimal matrix multiplication in relation to the Catalan numbers is
discussed on pp. 302-4 of Cormen, Leisersen, Rivest, _Introduction to
Algorithms_. Note that dynamic programming reduces optimal matrix
multiplication to an O(n^3) problem which requires O(n^2) space.
----------------------------------------------------------------------
#!/usr/bin/perl -w
#
# "9 9s" solution by Rick Bradley ([EMAIL PROTECTED], [EMAIL PROTECTED])
# c.f. http://www.itasoftware.com/careers/programmers.php for problem
# description
#
use strict;
use vars qw($epsilon $max_level $values $level $i $j $later %seen $test $solutions
@temp $temp_val $val1 $val2 @new $newer $current $element);
$|++;
# set tolerance for comparison of /-produced values
$epsilon = 0.00000000001;
# set maximum number of levels in tree
$max_level = $ARGV[0] || 9;
#initialize solutions for trees with n nodes
$values = [];
# set possible leaf nodes
$values->[1] = defined ($ARGV[1]) ? [ split(',', $ARGV[1]) ] : [ 9, -9 ];
# find tree values for k-node trees, 2 <= k <= max_level
for ($level = 2; $level <= $max_level ; $level++) {
print "Evaluating trees for level $level...\n";
@new = ();
$newer = [];
%seen = ();
# solutions for n are found by combining solutions for k and n - k
print "[";
$later = 0;
for ($i = 1; $i < $level; $i++) {
print ''.($later++ ? ' ' : '')."$i";
$j = $level - $i;
foreach $val1 (@{$values->[$i]}) {
foreach $val2 (@{$values->[$j]}) {
@temp = ();
# consider trees formed by each operand
push @temp, $val1 + $val2;
push @temp, $val1 - $val2;
push @temp, $val1 * $val2;
push @temp, $val1 / $val2 if (abs($val2) > $epsilon);
push @temp, $val2 - $val1;
push @temp, $val2 / $val1 if (abs($val1) > $epsilon);
foreach $temp_val (@temp) {
if (!exists $seen{$temp_val}) {
$seen{$temp_val} = 1;
push @new, $temp_val;
}
}
}
}
}
print "]\n";
# clean list for new level
print "Sorting ".scalar(@new)." elements\n";
@new = sort { $a <=> $b} @new;
print "Cleaning...\n";
undef $current;
foreach $element (@new) {
if (not defined $current or abs($current - $element) > $epsilon) {
# eliminate duplicates
push (@{$newer}, $element);
$current = $element;
}
}
# save
$values->[$level] = $newer;
print "Found ".scalar(@{$newer})." solutions for level $level\n";
}
# extract solution from max_level solutions
$test = $i = 0;
$solutions = $values->[$max_level];
while ($i < scalar($solutions)) {
$test++, $i++, next if (abs($test-$solutions->[$i]) < $epsilon);
$i++, next if ($solutions->[$i] < $test);
print "Solution: $test\n";
last;
}
----------------------------------------------------------------------
Btw, the solution for the problem stated is: 195
The closest representable values to 195 are 194.4 and 196.
Rick
_
Philippine Linux Users Group. Web site and archives at http://plug.linux.org.ph
To leave: send "unsubscribe" in the body to [EMAIL PROTECTED]
To subscribe to the Linux Newbies' List: send "subscribe" in the body to
[EMAIL PROTECTED]
