Send more money (in Perl 6) | Hacker News Reader

Send more money (in Perl 6)

strangelyconsistent.org

59 pointskamaal8 comments

When solving a combinatorial (optimization) problem, using a suitable modelling language is always nice. I'm partial to MiniZinc (http://www.minizinc.org/) myself, where Send more money would look like this

  include "globals.mzn";

  var 1..9: S;
  var 0..9: E;
  var 0..9: N;
  var 0..9: D;
  var 1..9: M;
  var 0..9: O;
  var 0..9: R;
  var 0..9: Y;

  constraint      1000 * S + 100 * E + 10 * N + D
                + 1000 * M + 100 * O + 10 * R + E
    = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

  constraint alldifferent([S,E,N,D,M,O,R,Y]);

  solve satisfy;

  output [ " ",show(S),show(E),show(N),show(D),"\n",
          "+ ",show(M),show(O),show(R),show(E),"\n",
  "= ",show(M),show(O),show(N),show(E),show(Y),"\n"];

A couple of nice things to note are the initial domains (defining the non-zero aspect of S and M), the use of alldifferent to make sure all variables have unique values, and letting the solving-strategy be determined by the back-end solver used.

A straightforward translation of the first program to Python 3 runs in 11 seconds:

    digits = set(range(10))
    
    def choose(choices, fn):
        for value in choices:
            fn(value)
    
    def guard(condition, fn):
        if condition:
            fn()
    
    def ten(*digits):
        return int(''.join(map(str, digits)))
    
    choose(digits - {0}, lambda s:
    choose(digits - {s}, lambda e:
    choose(digits - {s, e}, lambda n:
    choose(digits - {s, e, n}, lambda d:
    choose(digits - {0, s, e, n, d}, lambda m:
    choose(digits - {s, e, n, d, m}, lambda o:
    choose(digits - {s, e, n, d, m, o}, lambda r:
    choose(digits - {s, e, n, d, m, o, r}, lambda y:
    (lambda
    send = ten(s, e, n, d),
    more = ten(m, o, r, e),
    money = ten(m, o, n, e, y):
    guard(send + more == money, lambda:
    print("{} + {} = {}".format(send, more, money))
    ))()))))))))

This was quite fun to write in racket:

    #lang racket
    
    (define (ten digits)
      (apply (compose string->number string-append)
             (map number->string digits)))
    
    (define (solve)
      (for* ([s                               (range 1 10)]
             [e (remove s                     (range 0 10))]
             [n (remove* (list s e)           (range 0 10))]
             [d (remove* (list s e n)         (range 0 10))]
             [m (remove* (list 0 s e n d)     (range 0 10))]
             [o (remove* (list s e n d m)     (range 0 10))]
             [r (remove* (list s e n d m o)   (range 0 10))]
             [y (remove* (list s e n d m o r) (range 0 10))]
             #:when (=   (+ (ten (list s e n d))
                            (ten (list m o r e)))
                          (ten (list m o n e y))))
        (displayln
         (format
          "     S E N D        ~a ~a ~a ~a~n +   M O R E    +   ~a ~a ~a ~a~n------------   ------------~n   M O N E Y      ~a ~a ~a ~a ~a"
          s e n d m o r e m o n e y))))

Excuse the ugly format line :)

    sendmore.rkt> (time (solve))
         S E N D        9 5 6 7
     +   M O R E    +   1 0 8 5
    ------------   ------------
       M O N E Y      1 0 6 5 2
    cpu time: 7124 real time: 7120 gc time: 80

Ah, too late to edit, but using for*/first to terminate the first time it finds a match is faster still.

I suspect he used something slow to emulate sets in Perl 5. I get:

    $ time python3 send.py 
    9567 + 1085 = 10652

    real	0m16.388s
    user	0m16.299s
    sys	0m0.049s

    $ time perl send.pl 
    9567 + 1085 = 10652

    real	0m16.838s
    user	0m16.732s
    sys	0m0.063s

With:

    use strict;
    use warnings;
    
    my %digits = map { $_ => 1 } ( 0 .. 9 );
    
    sub choose ($&) {
        my ( $set, $sub ) = @_;
        map { $sub->($_) } grep { $set->{$_} } keys %$set;
    }
    
    sub guard { $_[1]->() if $_[0] }
    
    choose { %digits, map { $_ => 0 } ( 0 ) }, sub { my $s = $_[0];
    choose { %digits, map { $_ => 0 } ( $s ) }, sub { my $e = $_[0];
    choose { %digits, map { $_ => 0 } ( $s, $e ) }, sub { my $n = $_[0];
    choose { %digits, map { $_ => 0 } ( $s, $e, $n ) }, sub { my $d = $_[0];
    choose { %digits, map { $_ => 0 } ( 0, $s, $e, $n, $d ) }, sub { my $m = $_[0];
    choose { %digits, map { $_ => 0 } ( $s, $e, $n, $d, $m ) }, sub { my $o = $_[0];
    choose { %digits, map { $_ => 0 } ( $s, $e, $n, $d, $m, $o ) }, sub { my $r = $_[0];
    choose { %digits, map { $_ => 0 } ( $s, $e, $n, $d, $m, $o, $r ) }, sub { my $y = $_[0];
        my $send = $s . $e . $n . $d;
        my $more = $m . $o . $r . $e;
        my $money = $m . $o . $n . $e . $y;
        guard( ($send + $more == $money), sub {
            printf("%d + %d = %d\n", $send, $more, $money);
        });
    }}}}}}}};

That makes more sense; I didn't think Perl was as slow as he claimed.

You can even get a similarly-structured program in C with macro abuse and C99's compound literals:

    #include <stdio.h>
    
    #define NUMARGS(...) (sizeof((int[]){__VA_ARGS__}) / sizeof(int))
    #define FOR_EACH_DIGIT(v) for (int v = 0; v < 10; v++)
    #define EXCEPT(v, ...) if (in(v, (int[]){__VA_ARGS__}, NUMARGS(__VA_ARGS__))) continue
    #define FOR_EACH_DIGIT_EXCEPT(v, ...) FOR_EACH_DIGIT(v) { EXCEPT(v, __VA_ARGS__);
    #define TEN(...) ten((int[]){__VA_ARGS__}, NUMARGS(__VA_ARGS__))
    
    int in(int v, int a[], int n) {
        for (int i = 0; i < n; i++) if (a[i] == v) return 1;
        return 0;
    }
    
    int ten(int a[], int n) {
        int v = 0;
        for (int i = 0; i < n; i++) v = v * 10 + a[i];
        return v;
    }
    
    int main() {
        FOR_EACH_DIGIT_EXCEPT(s, 0)
        FOR_EACH_DIGIT_EXCEPT(e, s)
        FOR_EACH_DIGIT_EXCEPT(n, s, e)
        FOR_EACH_DIGIT_EXCEPT(d, s, e, n)
        FOR_EACH_DIGIT_EXCEPT(m, 0, s, e, n, d)
        FOR_EACH_DIGIT_EXCEPT(o, s, e, n, d, m)
        FOR_EACH_DIGIT_EXCEPT(r, s, e, n, d, m, o)
        FOR_EACH_DIGIT_EXCEPT(y, s, e, n, d, m, o, r)
        int send = TEN(s, e, n, d), more = TEN(m, o, r, e), money = TEN(m, o, n, e, y);
        if (send + more == money) printf("%d + %d = %d\n", send, more, money);
        }}}}}}}}
        return 0;
    }

Definitely not idiomatic C, but at least it's fast (0.07 seconds).

A solution using the Yices SMT solver which can be found at http://yices.csl.sri.com/yices2-documentation.html:

    (define d::int)
    (define e::int)
    (define m::int)
    (define n::int)
    (define o::int)
    (define r::int)
    (define s::int)
    (define y::int)

    (assert
       (and
          (and (>= d 0) (<= d 9))
          (and (>= e 0) (<= e 9))
          (and (>= m 0) (<= m 9))
          (and (>= n 0) (<= n 9))
          (and (>= o 0) (<= o 9))
          (and (>= r 0) (<= r 9))
          (and (>= s 0) (<= s 9))
          (and (>= y 0) (<= y 9))
          (and (/= d e) (/= d m) (/= d n) (/= d o) (/= d r) (/= d s) (/= d y))
          (and (/= e m) (/= e n) (/= e o) (/= e r) (/= e s) (/= e y))
          (and (/= m n) (/= m o) (/= m r) (/= m s) (/= m y))
          (and (/= n o) (/= n r) (/= n s) (/= n y))
          (and (/= o r) (/= o s) (/= o y))
          (and (/= r s) (/= r y))
          (/= s y)
          (=
             (+
                (+ (* s 1000) (* e 100) (* n 10) d)
                (+ (* m 1000) (* o 100) (* r 10) e)
             )
             (+ (* m 10000) (* o 1000) (* n 100) (* e 10) y)
          )
       )
    )

    (check)
    (show-model)

which gives

    sat
    (= m 1)
    (= r 8)
    (= y 2)
    (= o 0)
    (= s 9)
    (= n 6)
    (= d 7)
    (= e 5)
    ./bin/yices money.ys  0.01s user 0.00s system 76% cpu 0.012 total

Very nice! Not sure if it will get Perl 6 any better adoption, but still very nice.

Reply on news.ycombinator.com