[Wellington-pm] SEND + MORE = MONEY

[Sam Vilain]

Grant McLean wrote:
> Can anyone come up with creative solutions for this?
> 
> Given the equation:
> 
>   SEND
>  +MORE
>  =====
>  MONEY
> 
> Where each letter represents a digit (0-9) and neither S nor M can be
> zero.  Find the values for the letters which satisfy the equation.
> There is only one solution.
> 
> I came up with a brute force approach (below) which takes nearly two
> minutes (1:50) on my workstation to check all possible answers and prove
> the assertion that there is only one answer.

OK, so I started a solution based on Quantum::Superpositions.  The idea
is to build up an expression that forms the thing you want to test, then
let the system collapse to the superposition of the possible states.

However, it seems that the objects returned by any() and all() in that
distribution aren't `entangled' when used twice in an expression; that
is,

    use Quantum::Superpositions;
    $\="\n";

    my $a = any(1,0);
    print ($a + $a == 1);  # prints 1, actually impossible
    print (2 * $a == 1);   # prints any() (ie, none)

This is something of a shame, otherwise, the below script might have
stood some chance of working, though no doubt it would take the longest
of all :-)  Until we figure out how to link the quantum computers that
control our wetware to Quantum::Superpositions, that is.  Then it will
take constant time, of course.

#!/usr/bin/env perl -w

use strict;
use utf8;
use Scriptalicious;

# logical && can't be overloaded in Perl :-(
sub And {
     $_[0] && $_[1];
}

use Quantum::Superpositions BINARY_LOGICAL => [ "main::And" ];

my $no_dups;
getopt("nodups|n" => \$no_dups);
my $message = @ARGV ? (join " ", @ARGV) : 'SEND + MORE = MONEY';

# first, convert the input to a closure
my %q;
my $expr = "sub { ";
while ( $message =~ m{\G(?: ([A-Z]+)
		      |     ([\(\)\+\-=/×])
		      |     \s+
		      |     (.)
		     )}gx ) {
     my ($word, $oper) = ($1, $2);

     barf "bad character $3 in input" if $3;

     if ( $word ) {
	$expr .= "(";
	my $digit = 1;
	my $length = length $word;
	for my $letter ( split //, $word ) {
	    $expr .= "+" if $digit > 1;
	    $expr .= (" \$q{$letter}"
		      .($length-$digit
			? (" * ".(10**($length-$digit))." ")
			: " "));
	    # RULE: leading digits cannot be 0
	    $q{$letter} ||= ($digit == 1 ? any(1..9) : any(0..9));
	    $digit++;
	}
	$expr .= ")";
     }
     elsif ( $oper ) {
	$expr .= "\n\t";
	if ($oper eq "=") {
	    $expr .= " == ";
	} elsif ($oper eq "×") {
	    $expr .= " * ";
	} else {
	    $expr .= " $oper "
	}
	$expr .= "\n\t";
     }
}
$expr .= " }";

say "Sub is: $expr";

my $coderef = eval $expr;

$@ and barf "sub built badly; GIGO?  \$\@: $@";

start_timer;
my $superpos = $coderef->();

say "Constructed superposition in ".show_delta;

if ( $no_dups ) {
     say "now adding letters != each other restrictions";
     my %seen;
     my @list = sort keys %q;
     while ( my $key = shift @list ) {
	mutter("$key != $_"),
	    ($superpos = And($superpos, ( $q{$key} != $q{$_} )))
		foreach @list;
     }
}

say "now computing eigenstates";

my @states = eigenstates( $superpos );

say "Completed in ".show_delta.", eigenstates are:";

print "$_\n" foreach @states;



-- 
Sam Vilain, sam /\T vilain |><>T net, PGP key ID: 0x05B52F13
(include my PGP key ID in personal replies to avoid spam filtering)