4 ms·

A straightforward translation of the first program to Python 3 runs in 11 seconds: digits = set(range(10)) def choose(choices, fn): for va

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