Hacker News Reader

Comment by Rangi42 | Hacker News Reader

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))
    ))()))))))))

View on HN

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).

Reply on news.ycombinator.com