SEND + MORE = MONEY: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Remove double header)
m (→‎Fast: Add optimizations and timing)
Line 118: Line 118:


=== Fast ===
=== Fast ===
Alternately, a version written in 2015 by [http://strangelyconsistent.org/blog/send-more-money-in-perl6 Carl Mäsak]. Not very concise but quite fast.
Alternately, a version written in 2015 by [http://strangelyconsistent.org/blog/send-more-money-in-perl6 Carl Mäsak]. Not very concise but quite speedy. Applying the observation that M must be 1 and S must be either 8 or 9 gets the runtime under a tenth of a second.
<syntaxhighlight lang="raku" line>my int $s = -1;
<syntaxhighlight lang="raku" line>my int $s = 7;
while ++$s <= 9 {
while ++$s <= 9 {
next if $s == 0;
next if $s == 0;
Line 140: Line 140:
my int $send = $s*1000 + $e*100 + $n*10 + $d;
my int $send = $s*1000 + $e*100 + $n*10 + $d;


my int $m = -1;
my int $m = 1;
while ++$m <= 9 {
next if $m == 0;
next if $m == $s;
next if $m == $e;
next if $m == $n;
next if $m == $d;


my int $o = -1;
my int $o = -1;
while ++$o <= 9 {
while ++$o <= 9 {
next if $o == $s;
next if $o == $s;
next if $o == $e;
next if $o == $e;
next if $o == $n;
next if $o == $n;
next if $o == $d;
next if $o == $d;
next if $o == $m;
next if $o == $m;


my int $r = -1;
my int $r = -1;
while ++$r <= 9 {
while ++$r <= 9 {
next if $r == $s;
next if $r == $s;
next if $r == $e;
next if $r == $e;
next if $r == $n;
next if $r == $n;
next if $r == $d;
next if $r == $d;
next if $r == $m;
next if $r == $m;
next if $r == $o;
next if $r == $o;


my int $more = $m*1000 + $o*100 + $r*10 + $e;
my int $more = $m*1000 + $o*100 + $r*10 + $e;


my int $y = -1;
my int $y = -1;
while ++$y <= 9 {
while ++$y <= 9 {
next if $y == $s;
next if $y == $s;
next if $y == $e;
next if $y == $e;
next if $y == $n;
next if $y == $n;
next if $y == $d;
next if $y == $d;
next if $y == $m;
next if $y == $m;
next if $y == $o;
next if $y == $o;
next if $y == $r;
next if $y == $r;


my int $money =
my int $money =
$m*10000 + $o*1000 + $n*100 + $e*10 + $y;
$m*10000 + $o*1000 + $n*100 + $e*10 + $y;
next unless $send + $more == $money;
next unless $send + $more == $money;
say 'SEND + MORE == MONEY';
say 'SEND + MORE == MONEY';
say "$send + $more == $money";
say "$send + $more == $money";
}
}
}
}
}
Line 189: Line 182:
}
}
}
}
}
}</syntaxhighlight>
printf "%.3f elapsed seconds", now - INIT now;</syntaxhighlight>
{{out}}
{{out}}
<pre>SEND + MORE == MONEY
<pre>SEND + MORE == MONEY
9567 + 1085 == 10652</pre>
9567 + 1085 == 10652
0.080 elapsed seconds</pre>


=={{header|Ring}}==
=={{header|Ring}}==

Revision as of 22:38, 10 February 2023

SEND + MORE = MONEY is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Write a program in your language to solve SEND + MORE = MONEY: A Great Puzzle.

ALGOL 68

Translation of: Julia

This task can be solved without using seven nested loops but then again, it can be solved with them - so why not?.
Uses the observations of the Julia sample (unsuprisingly as this is a translation of the Julia sample). 

BEGIN # solve the SEND+MORE=MONEY puzzle - translation of the Julia sample #
  INT m = 1;
  OP C = ( INT n )CHAR: REPR ( ABS "0" + n ); # convert integer to a digit #
  FOR s FROM 8 TO 9 DO
    FOR e FROM 0 TO 9 DO
      IF e /= m AND e/= s THEN
        FOR n FROM 0 TO 9 DO
          IF n /= m AND n /= s AND n /= e THEN
            FOR d FROM 0 TO 9 DO
              IF d /= m AND d /= s AND d /= e AND d /= n THEN
                FOR o FROM 0 TO 9 DO
                  IF o /= m AND o /= s AND o /= e AND o /= n AND o /= d THEN
                    FOR r FROM 0 TO 9 DO
                      IF r /= m AND r /= s AND r /= e AND r /= n AND r /= d AND r /= o THEN
                        FOR y FROM 0 TO 9 DO
                          IF y /= m AND y /= s AND y /= e AND y /= n AND y /= d AND y /= o AND y /= r THEN
                            IF ( 1000 * ( s + m ) ) + ( 100 * ( e + o ) ) + ( 10 * ( n + r ) ) + ( d + e )
                             = ( 10 000 * m ) + ( 1000 * o ) + ( 100 * n ) + ( 10 * e ) + y
                            THEN
                              print( ( C s, C e, C n, C d, " + ", C m, C o, C r, C e, " = ", C m, C o, C n, C e, C y
                                     )
                                   )
                            FI
                          FI
                        OD
                      FI
                    OD
                  FI
                OD
              FI
            OD
          FI
        OD
      FI
    OD
  OD
END
Output:
9567 + 1085 = 10652

Julia

A hoary old task, solved with pencil before electricity was a thing.

Since the M in Money is the result of carry in base 10 of two single digits it is a 1 (we exclude 0 here though that would work, but then MONEY would be spelled ONEY).

In addition, the S plus 1 then needs to result in a carry, so S is 8 or 9, depending on whether there is a carry into that column. Pencil and paper can continue, but from here the computer is likely quicker. 

let
    m = 1
    for s in 8:9
        for e in 0:9
            e in [m, s] && continue
            for n in 0:9
                n in [m, s, e] && continue
                for d in 0:9
                    d in [m, s, e, n] && continue
                    for o in 0:9
                        o in [m, s, e, n, d] && continue
                        for r in 0:9
                            r in [m, s, e, n, d, o] && continue
                            for y in 0:9
                                y in [m, s, e, n, d, o] && continue
                                if 1000s + 100e + 10n + d + 1000m + 100o + 10r + e ==
                                   10000m + 1000o + 100n + 10e + y
                                    println("$s$e$n$d + $m$o$r$e == $m$o$n$e$y")
                                end
                            end
                        end
                    end
                end
            end
        end
    end
end
Output:

9567 + 1085 == 10652

Raku

Idiomatic

enum <D E M N O R S Y>;

sub find_solution ( ) {
    for ('0'..'9').combinations(8) -> @c {
        .return with @c.permutations.first: -> @p {
            @p[M] !== 0 and

            @p[  S,E,N,D].join
          + @p[  M,O,R,E].join
         == @p[M,O,N,E,Y].join
        }
    }
}

my @s = find_solution();
say "    {@s[  S,E,N,D].join}";
say " +  {@s[  M,O,R,E].join}";
say "== { @s[M,O,N,E,Y].join}";
Output:
    9567
 +  1085
== 10652

Fast

Alternately, a version written in 2015 by Carl Mäsak. Not very concise but quite speedy. Applying the observation that M must be 1 and S must be either 8 or 9 gets the runtime under a tenth of a second. 

my int $s = 7;
while ++$s <= 9 {
    next if $s == 0;

    my int $e = -1;
    while ++$e <= 9 {
        next if $e == $s;

        my int $n = -1;
        while ++$n <= 9 {
            next if $n == $s;
            next if $n == $e;

            my int $d = -1;
            while ++$d <= 9 {
                next if $d == $s;
                next if $d == $e;
                next if $d == $n;

                my int $send = $s*1000 + $e*100 + $n*10 + $d;

                my int $m = 1;

                my int $o = -1;
                while ++$o <= 9 {
                    next if $o == $s;
                    next if $o == $e;
                    next if $o == $n;
                    next if $o == $d;
                    next if $o == $m;

                    my int $r = -1;
                    while ++$r <= 9 {
                        next if $r == $s;
                        next if $r == $e;
                        next if $r == $n;
                        next if $r == $d;
                        next if $r == $m;
                        next if $r == $o;

                        my int $more = $m*1000 + $o*100 + $r*10 + $e;

                        my int $y = -1;
                        while ++$y <= 9 {
                            next if $y == $s;
                            next if $y == $e;
                            next if $y == $n;
                            next if $y == $d;
                            next if $y == $m;
                            next if $y == $o;
                            next if $y == $r;

                            my int $money =
                                $m*10000 + $o*1000 + $n*100 + $e*10 + $y;
                            next unless $send + $more == $money;
                            say 'SEND + MORE == MONEY';
                            say "$send + $more == $money";
                        }
                    }
                }
            }
        }
    }
}
printf "%.3f elapsed seconds", now - INIT now;
Output:
SEND + MORE == MONEY
9567 + 1085 == 10652
0.080 elapsed seconds

Ring

t1 = clock() // start
see "works..." + nl + nl
aListSend = []
aListMore = []

for s = 0 to 9
    for e1 = 0 to 9
        for n = 0 to 9
            for d = 0 to 9
                bool = s!=e1 and s!=n and s!=d and e1!=n and e1!=d and n!=d
                if bool
                   sendmore = s*1000+e1*100+n*10+d
                   add(aListSend,sendmore)
                   add(aListMore,sendmore)
                ok
            next
        next
    next
next

for ind1 = len(aListSend) to 1 step -1 
    for ind2 = 1 to len(aListMore)
        strSend = string(aListSend[ind1])
        strMore = string(aListMore[ind2])
        m = substr(strMore,1,1)
        o = substr(strMore,2,1)
        r = substr(strMore,3,1)
        e2 = substr(strMore,4,1)
        bool1 = substr(strSend,m)
        bool2 = substr(strSend,o)
        bool3 = substr(strSend,r)
        if substr(strSend,2,1) = substr(strMore,4,1)
            bool4 = 0
        else
            bool4 = 1
        ok
        boolSendMore = bool1 + bool2 + bool3 + bool4
        if boolSendMore < 1
           if substr(strSend,2,1) = substr(strMore,4,1)
              for y = 0 to 9
                  strMoney1 = substr(strMore,1,1) + substr(strMore,2,1) + substr(strSend,3,1)
                  strMoney2 = substr(strMore,4,1) + string(y)
                  strMoney = strMoney1 + strMoney2
                  numMoney = number(strMoney)
                  numSend = number(strSend)
                  numMore = number(strMore)
                  y1 = substr(strMoney,5,1)
                  ySend = substr(strSend,y1)
                  yMore = substr(strMore,y1)
                  yCheck = ySend + yMore
                  r = substr(strMore,3,1)
                  rCheck = substr(strSend,r)
                  if (numSend + numMore = numMoney) and yCheck < 1 and rCheck < 1
                      see "SEND = "+strSend+" MORE = "+strMore+" MONEY = "+strMoney+nl+nl              
                      exit 3
                  ok
             next
           ok
        ok
    next
next
see "Time: "+ clock() - t1 // end
see "done..." + nl
Output:
works...
SEND = 9567 MORE = 1085 MONEY = 10652
done...
Time: 31.9 s

Wren

Clearly M = 1 and S must be 8 or 9. Brute force can be used to solve for the other letters. 

var start = System.clock
var sends = []
var ors = []
var m = 1
var digits = (0..9).toList
digits.remove(m)
for (s in 8..9) {
    for (e in digits) {
        if (e == s) continue
        for (n in digits) {
            if (n == s || n == e) continue
            for (d in digits) {
                if (d == s || d == e || d == n) continue
                sends.add([s, e, n, d])
            }
        }
    }
}
for (o in digits) {
    for (r in digits) {
        if (r == o) continue
        ors.add([o, r])
    }
}
System.print("Solution(s):")
for (send in sends) {
    var SEND = 1000 * send[0] + 100 * send[1] + 10 * send[2] + send[3]
    for (or in ors) {
        if (send.contains(or[0]) || send.contains(or[1])) continue
        var sendmore = send + or
        var MORE = 1000 * m + 100 * or[0] + 10 * or[1] + send[1]
        for (y in digits) {
            if (sendmore.contains(y)) continue
            var MONEY = 10000 * m + 1000 * or[0] + 100 * send[2] + 10 * send[1] + y
            if (SEND + MORE == MONEY) {
                System.print("%(SEND) + %(MORE) = %(MONEY)")
            }
        }
    }
}
System.print("\nTook %(System.clock - start) seconds.")
Output:
Solution(s):
9567 + 1085 = 10652

Took 0.245002 seconds.
Retrieved from "https://rosettacode.org/wiki/SEND_%2B_MORE_%3D_MONEY?oldid=336813"