[Wellington-pm] SEND + MORE = MONEY
Ewen McNeill
ewen at naos.co.nz
Tue Mar 1 23:54:02 PST 2005
In message <20050302054105.BBCD63C4877C at basilica.la.naos.co.nz>, Ewen McNeill wr
ites:
>In message <1109700654.4261.11.camel at localhost>, Grant McLean writes:
>>Given the equation: [SEND + MORE = MONEY]
>
>Proof that there's a CPAN module for everything. [4:39 brute force solution]
Proof that what you need is a better algorithm, not a faster computer.
It still feels more complicated than it should be, but it exhausts the
search space in 4.2 seconds on a 700MHz Pentium III (and 1.4 seconds
on a 2.1GHz AMD Athlon XP 2700+; both figures "user" time from "time"
in bash). AFAICT Douglas's sub-1-second program may or may not find
the answer, so it's not a completely fair comparision.
I'd like to make the recursion go away (recursion feels "wrong" -- I
guess that means I didn't grow up a LISP programmer), but it's already
complicated enough without doing explicit stack management.
Ewen
#! /usr/bin/perl -w
# Intelligently solve word number addition puzzles
#
# Rules: 1. Each letter always corresponds to the same digit
# 2. A digit is only used once
# 3. Most sigificant digit in values in the equation is never zero
# Written by Ewen McNeill <ewen at naos.co.nz>, 2005/03/02
use strict;
my $message = 'SEND + MORE = MONEY';
solve($message);
# (@list) = do_substs($from, $to, @list)
sub do_substs
{
my ($from, $to, @list) = @_;
for (0..$#list)
{
$list[$_] =~ s/${from}/${to}/g;
}
return @list;
}
# $bool = is_digit($val)
sub is_digit
{
return $_[0] =~ /\d/;
}
# $bool = is_available($digit, @list)
sub is_available
{
my ($digit, @list) = @_;
return ($list[$digit] eq $digit);
}
# @list = reserve($letter, $digit, @list)
sub reserve
{
my ($letter, $digit, @list) = @_;
unless ($list[$digit] eq $digit)
{
die "Attempt to re-reserve $digit for $letter in ", join(",", @list), "\n"
}
$list[$digit] = $letter;
return @list;
}
# try_substs($a, $b, $sum, $carry, @available)
# $carry is 1 iff next least signifant pair caused a carry
sub try_substs
{
my ($a,$b,$sum,$carry, at available) = @_;
my ($lena,$lenb,$lensum) = (length $a, length $b, length $sum);
die "Sum doesn't make sense\n" if ($lensum < $lena || $lensum < $lenb);
# warn "try_substs($a,$b,$sum,$carry,", join(",", at available), ")\n";
# All substituted?
if ($a !~ /\D/ && $b !~ /\D/ && $sum !~ /\D/)
{
print "Success: $message is $a + $b = $sum\n" if ($a + $b == $sum);
return; # No more substitutions possible on this search branch
}
# Sum has more digits than components? If so, MSD of sum must be 1.
if ($lensum > $lena && $lensum > $lenb && ! is_digit(substr($sum,0,1)))
{
die "Someone stole 1\n" unless is_available(1, @available);
my $letter = substr($sum,0,1);
try_substs(do_substs($letter, 1, $a,$b,$sum), $carry,
reserve($letter, 1, @available));
return; # All possibilities tried in recursive call
}
# Look for a good subsitution, working backwards from LSDs
# - if Nth last digit in $a and Nth last digit in $b are substituted
# then Nth last digit in their sum _must_ be ($a + $b + $carry) % 10
# - if Nth last digit in $a is not substituted, try all available
# values for that
# - if Nth last digit in $a is substituted, and Nth last digit in $b
# is not substituted, try all available values for that.
for my $offset (0 .. ($lensum-1))
{
my $a_char = ($offset > $lena ? '#' : substr($a,($lena-$offset-1),1));
my $b_char = ($offset > $lenb ? '#' : substr($b,($lenb-$offset-1),1));
my $sum_char = (substr($sum,($lensum-$offset-1),1));
# warn "offset = $offset; a_char = $a_char; b_char = $b_char; sum_char = $sum_char\n";
if ((($offset > $lena) || is_digit($a_char)) &&
(($offset > $lenb) || is_digit($b_char)) &&
(! is_digit($sum_char)))
{
my $wanted = ($a_char + $b_char + $carry) % 10;
if (is_available($wanted, at available))
{
$carry = (($a_char + $b_char + $carry) >= 10);
try_substs(do_substs($sum_char,$wanted,$a,$b,$sum), $carry,
reserve($sum_char,$wanted, at available));
}
return; # Either impossible, or all tried in recursive call
}
if ($offset < $lena && ! is_digit($a_char))
{
for my $possibility (0..9)
{
if (is_available($possibility, at available))
{
try_substs(do_substs($a_char,$possibility,$a,$b,$sum), $carry,
reserve($a_char,$possibility, at available));
}
}
return; # All possibilities tried in recursive call
}
elsif ($offset < $lenb && ! is_digit($b_char))
{
for my $possibility (0..9)
{
if (is_available($possibility, at available))
{
try_substs(do_substs($b_char,$possibility,$a,$b,$sum), $carry,
reserve($b_char,$possibility, at available));
}
}
return; # All possibilities tried in recursive call
}
}
die "Implementation error: fell through search for substitutions\n";
}
sub solve
{
my $addition = shift;
if ($addition =~ /^(\S+)\s*\+\s*(\S+)\s*=\s*(\S+)$/)
{
try_substs($1,$2,$3,0, 0 .. 9);
}
else
{
die "Malformed addition problem: $addition\n";
}
}
More information about the Wellington-pm
mailing list