Re: Perl 'Medium' Quiz-of-the-Whatever for 2009-08-11 : Plusified Equations

Hello Shlomi,

I have heard that 'a thousand monkeys at a thousand
typewriters will eventually type out the entire works
of Shakespeare'. So, I put my best team of monkeys
on this problem and it resulted in the program below.  :-)

This was a good exercise. My solution saw that
the '+' signs distributed between the numbers
as a power set.

For example, for the number 7637, I first
modified it to be '7 6 3 7', (with 3 spaces as placeholders).
The power set distributing '+'s for this number would be:
000
001
010
011
100
101
110
111

There are 8, (2**3), ways the plus sign could be
distributed. To generate the 8 expressions, I
tested the binary representation (above). If the bit was 1,
I replaced the space with a '+' and if not, removed
the space (placeholder). The results are:
7637
763+7
76+37
76+3+7
7+637
7+63+7
7+6+37
7+6+3+7

Then, I used string 'eval' to get the sum and placed
it and the expression in the %sums hash.

 $sums{$number}{$sum}{$expr} = ();

After calculating all the sums, I found a match If
a sum from the 'left' side == a sum from the 'right'.


*** requirement 2:
2. They will be sorted so consecutive digits will
   take precedence over "+"'s.

To achieve this requirement, I sorted the results
using nsort() from the module 'Sort::Naturally'.



Two errors I encountered were:

1. The worst error, (because it silently gave incorrect sums),
was when an expression had an octal number. I stumbled
across this by chance and if not discovered, would have
made my program incorrect. I don't know how a person
could have caught this using tests unless he was aware
that octal addition was an (incorrect) possibility.

An example of an octal number (derived from one of
the numbers you provided) would be the expression:

1+010

(one of the arrangements when given the number 1010
to distribute the plus signs through).

It gives the sum '9' when what you really wanted was '11'.
I guess I never would have caught it except by the chance
that you just happened to use this number in one
of your examples for the problem.


2. (I think) you were not aware when setting up the
problem that more than 1 arrangement on ONE side could
have the same sum. From my %sums hash:

'11' => {
        '1+0+10' => undef,
        '1+010' => undef,
        '10+1+0' => undef
      },

For the sample numbers you had as input, none of the
solutions had more than one value per side. But my
code addresses this by doing a 'cross product'
(in the output section) to allow for this possibility .

Cheers,

Chris

NOTE: 1. Program dies if you supply one or more 0's as
      one of the numbers.

      2. Can't use a number longer than 31 digits.



*** Program

#!/usr/bin/perl
use strict;
use warnings;
use Sort::Naturally;

@ARGV == 2  or die "Must supply two numbers: $!";
my %sums;

for my $number (@ARGV) { # Left then Right
 
 # plus signs distribute between digits as a power set
 # i.e., if a number is 4 digits long, find pwr set (2**3)
 my $nbits = length($number)-1;
 my $nsubsets = 2**$nbits;
 
 for my $subset (0 .. $nsubsets-1) {
  
  # if $number is '7637', then $expr is '7 6 3 7'
  (my $expr = $number) =~ s/\B/ /g;
  
  for my $shift (reverse 0 .. $nbits-1) {
   $expr =~ s/ /$subset & (1 << $shift) ? '+' : ''/e;
  }
  
  # remove 'leading' 0's (to prevent octal addition)
  (my $eval_str = $expr) =~ s/\+0+\B/+/g;
  
  my $sum = eval "$eval_str" or die $!;
  $sums{$number}{$sum}{$expr} = ();
 }
}

my @data;
my ($L, $R) = @ARGV;
for my $sum (keys %{ $sums{$L} }) {
 next unless exists $sums{$R}{$sum};
 # Cross Product
 for my $L_expr ( keys %{ $sums{$L}{$sum} } ) {
  for my $R_expr ( keys %{ $sums{$R}{$sum} } ) {
   push @data, "$L_expr=$R_expr";
  }
 }
}

print join("\n", reverse nsort @data), "\n";