4 ms·

Send more money (in Perl 6)

59 points by kamaal 11y ago

bayonetz 11y ago
Very nice! Not sure if it will get Perl 6 any better adoption, but still very nice.
Rangi42 11y ago
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)) ))()))))))))
- minikomi 11y ago
  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
  - minikomi 11y ago
    Ah, too late to edit, but using for*/first to terminate the first time it finds a match is faster still.
- peteretep 11y ago
  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); }); }}}}}}}};
  - Rangi42 11y ago
    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).
VeXocide 11y ago
A solution using the Yices SMT solver which can be found at http://yices.csl.sri.com/yices2-documentation.html 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
mzl 11y ago
When solving a combinatorial (optimization) problem, using a suitable modelling language is always nice. I'm partial to MiniZinc (http://www.minizinc.org/ 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.

59 points by kamaal 11y ago

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

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

minikomi 11y ago
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
- minikomi 11y ago
  Ah, too late to edit, but using for*/first to terminate the first time it finds a match is faster still.
peteretep 11y ago
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); }); }}}}}}}};
- Rangi42 11y ago
  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).

VeXocide 11y ago

A solution using the Yices SMT solver which can be found at http://yices.csl.sri.com/yices2-documentation.html 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

mzl 11y ago

When solving a combinatorial (optimization) problem, using a suitable modelling language is always nice. I'm partial to MiniZinc (http://www.minizinc.org/ 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.