[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