[Wellington-pm] SEND + MORE = MONEY

[michael at diaspora.gen.nz]

Douglas Bagnall writes:
>Anyway, I the best solution will recognise the letters as representing 
>powers of ten, and use some kind of modulus and division trickery.

For the modulus trickery, one can observe that we have multiple equations
that can be used to filter a brute force search space; eg, in the example
'SEND + MORE = MONEY', the following equations must hold:

    (D + E) % 10 == Y
    (N + R) % 10 == E
    (E + O) % 10 == N
    (S + M) % 10 == O

(there are probably more based on remainders; for example, if D + E is >
10, then that implies something about N, R, and E, because of the carry.)

A quick hack on Grant's code (below) checks the first equation, and uses
that to prune the search space.  It seems to work; drops the time on my
workstation from over 60 seconds (I got bored waiting) to ~ 13 seconds.

The next step would be to change the $letters generation to carefully
preserve significance order in the sort of the letters (as I have done
for the least significant three), and then change the elsif clause in
the solve function to look for equivalances to solve, rather than just
checking for the least significant one as at present.

It'd still be a brute force, depth first search though.
    -- michael.

spoilers below
^L^L^L

#!/usr/bin/perl -w
use strict;

my $message = 'SEND + MORE = MONEY';

my $letters = join '', sort keys %{{ map { $_, 1} ($message =~ /([A-Z])/g) }};
my $required = length $letters;
my $remove = join '', $message =~ /(\w)\b/g;
$letters =~ s/[$remove]//g;
$_ = $remove;
# remove duplicated letters while preserving order
s/(.)\1\1/$1/;
s/(.)\1/$1/g;
s/(.)(.)\1/$1$2/;
$letters = $_ . $letters;

print "$message\n";
solve('', 0..9);

sub solve {
  my $digits = shift;
  $_ = $message;
  eval "tr/$letters/${digits}b/";
  return if(/\b0/);
  # hope that we can find a partial equation
  if (length $digits == $required) {
    if(/^(\d+) \+ (\d+) = (\d+)/o) {
      print "$letters $_\n" if($1 + $2 == $3);
    }
    return;
  } elsif (/^\w+(\d) \+ \w+(\d) = \w+(\d)$/o) {
    return unless ($1 + $2) % 10 == $3;
  }
  foreach (1.. at _) {
    my $next = shift;
    solve($digits . $next, @_);
    push @_, $next;
  }
}