examples/sendmoremoney.pl

   1 use v6;
   2
   3 my $timer;
   4 sub start_timer() {
   5     $timer = time();
   6 }
   7 my $piggy_bank;
   8
   9 sub show_rate($num) {
  10     my $elapsed = time() - $timer;
  11     if $elapsed {
  12         say "Found all solutions in "~$elapsed~"s ("~($num/$elapsed)~" comb/s)";
  13     } else {
  14         say "Damn, that was fast.  Didn't even see the clock tick,";
  15         say "for searching a solution space of $num!";
  16     }
  17     if defined($piggy_bank) {
  18         say "There are $piggy_bank coins left in the bank.";
  19     }
  20 }
  21
  22 # basic test case, A + B = AC
  23 my $a = any(1..9);
  24 my $b = any(1..9);
  25 my $c = any(0..9);
  26
  27 sub do_it($a,$b,$c) {
  28     if any($a, $b, $c) == one($a, $b, $c) {
  29         my $ac = $a * 10 + $c;
  30         if $a + $b == $ac {
  31             say "  A =  $a";
  32             say "+ B =  $b";
  33             say "--------";
  34             say " AC = $ac";
  35         }
  36     }
  37 }
  38
  39 say "Finding solutions for A + B = AC";
  40 start_timer();
  41 do_it($a,$b,$c);
  42 show_rate(810);
  43
  44 # a more complicated and "classical" case :)
  45 sub show_me_the_money($s,$e,$n,$d,$m,$o,$r,$y) {
  46
  47     if all($s,$e,$n,$d,$m,$o,$r,$y) == one($s,$e,$n,$d,$m,$o,$r,$y) {
  48
  49         $piggy_bank--;
  50
  51         my $send = ((($s)*10+$e)*10+$n)*10+$d;
  52         my $more = ((($m)*10+$o)*10+$r)*10+$e;
  53         my $money = (((($m)*10+$o)*10+$n)*10+$e)*10+$y;
  54
  55         if $send + $more == $money {
  56             say " send =  $send";
  57             say "+more =  $more";
  58             say "-------------";
  59             say "money = $money";
  60         }
  61     }
  62 }
  63
  64 my $s = any(1..9);
  65 my $e = any(0..9);
  66 my $n = any(0..9);
  67 my $d = any(0..9);
  68 my $m = any(1..9);
  69 my $o = any(0..9);
  70 my $r = any(0..9);
  71 my $y = any(0..9);
  72
  73 my $c0 = any(0..1);
  74 my $c1 = any(0..1);
  75 my $c2 = any(0..1);
  76 my $c3 = any(0..1);
  77
  78 sub collapse($one, $sub) { $sub.($one) };
  79 sub collapse($one, $two, $sub) { $sub.($one, $two) };
  80 sub collapse($one, $two, $three, $sub) { $sub.($one, $two, $three) };
  81
  82 say "Finding solutions for SEND + MORE = MONEY (pseudo-optimized)";
  83 $piggy_bank = 1e8;
  84 start_timer();
  85
  86 # this is still really ugly, but fast-ish :)
  87 collapse($c3, $m, -> $c3, $m {
  88
  89     $piggy_bank--;
  90
  91     # FIFTH (most significant) column of addition
  92     if ($c3 == $m) {
  93         say "found c3 = $c3, m = $m";
  94     collapse($s, $o, $c2, -> $s, $o, $c2 {
  95
  96         # FOURTH column of addition
  97         $piggy_bank--;
  98         if ($s != $m && $s != $o && $m != $o &&
  99             (( $s+$m+$c2 ) % 10 == $o ) && ( int( ( $s+$m+$c2 ) / 10 ) == $c3 ) ) {
 100         say " found s = $s, o = $o, c2 = $c2";
 101         collapse($e, $c1, -> $e, $c1 {
 102
 103             $piggy_bank--;
 104             if ( $e != $s && $e != $o && $e != $m &&
 105                   ( int( ( $e+$o+$c1 ) / 10 ) == $c2 ) ) {
 106             say "  found e = $e, c1 = $c1";
 107             collapse($d, $y, $c0, -> $d, $y, $c0 {
 108
 109                 $piggy_bank--;
 110                 if ($d != $s && $d != $m && $d != $s && $d != $e && $d != $o &&
 111                     $y != $s && $y != $m && $y != $s && $y != $e && $y != $o &&
 112                     $d != $y &&
 113                     (( $d+$e     ) % 10 == $y ) &&
 114                     ( int( ( $d+$e     ) / 10 ) == $c0 )) {
 115                 say "   found d = $d, y = $y, c0 = $c0";
 116
 117                 collapse($n, $r, -> $n, $r {
 118
 119                     $piggy_bank--;
 120                     if ($n != $s && $n != $m && $n != $s && $n != $o &&
 121                         $n != $e && $n != $d && $n != $y &&
 122                         $r != $s && $r != $m && $r != $s && $r != $o &&
 123                         $r != $e && $r != $d && $r != $y && $r != $n &&
 124                         (( $e+$o+$c1 ) % 10 == $n ) &&
 125                         ( ( $n+$r+$c0 ) % 10 == $e ) &&
 126                         ( int( ( $n+$r+$c0 ) / 10 ) == $c1 )) {
 127
 128                         say "    found n = $n, r = $r (that should be it)";
 129
 130                         show_me_the_money($s,$e,$n,$d,$m,$o,$r,$y);
 131
 132                     }
 133                 });
 134                 }
 135             });
 136             }
 137         });
 138         }
 139     });
 140     }
 141 });
 142
 143 show_rate(16e8);
 144
 145 say "Finding solutions for SEND + MORE = MONEY (exhaustive)";
 146
 147 # in fact, cheat again :-)
 148 # note: this would take BLEEDING AGES (days or weeks) without this
 149 # cheating.
 150 my $s = any(8..9);
 151 my $e = any(5..6);
 152 my $n = any(4..7);
 153 my $d = any(6..8);
 154 my $m = any(1..2);
 155 my $o = any(0,1,9);
 156 my $r = any(7..9);
 157 my $y = any(1..3);
 158
 159 start_timer();
 160 show_me_the_money($s,$e,$n,$d,$m,$o,$r,$y);
 161 show_rate(2*2*4*3*2*3*3*3);
 162
 163 =begin kwid
 164
 165 -- Heres the equivalent SQL, as junctions have direct representation
 166 -- in Set Theory (see http://xrl.us/feh8)), then the below should be a
 167 -- very relevant way to express the problem, especially given
 168 -- MySQL/InnoDB (for one) already has the relevant logic to solve this
 169 -- problem in ~130ms on a 300MHz PII.  Although of course that is
 170 -- still over 39,000,000 cycles!  :-)  Oracle took longer - ~6s, but
 171 -- admittedly it was only running on a dual processor 1.6GHz Opteron.
 172 -- Pg took a similar amount of time on a 1.7GHz AthlonXP (5s), SQLite
 173 -- took over 30s!
 174
 175 -- The `exhaustive' solution cranks through possibilities at about
 176
 177 -- MySQL table setup (adjust for your DBMS as necessary)
 178
 179 CREATE TABLE Dx ( X INTEGER(1) );
 180 INSERT INTO Dx (X) VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
 181 CREATE TABLE Cx ( X INTEGER(1) );
 182 INSERT INTO Cx (X) VALUES (0),(1);
 183
 184 -- actual query:
 185
 186 SELECT
 187     (S.X * 1000 + E.X * 100 + N.X * 10 + D.X) as SEND,
 188     (M.X * 1000 + Oh.X * 100 + R.X * 10 + E.X) as MORE,
 189     (M.X * 10000 + Oh.X * 1000 + N.X * 100 + E.X * 10 + Y.X) as MONEY
 190 from
 191     Dx M
 192     LEFT JOIN Dx S ON (M.X != S.X)
 193     LEFT JOIN Dx E ON ( (M.X != E.X) AND (S.X != E.X) )
 194     LEFT JOIN Dx Oh ON ( (M.X !=Oh.X) AND (S.X !=Oh.X) AND (E.X !=Oh.X) )
 195     LEFT JOIN Dx N ON ( (M.X != N.X) AND (S.X != N.X) AND (E.X != N.X)
 196             AND (Oh.X != N.X) )
 197     LEFT JOIN Dx R ON ( (M.X != R.X) AND (S.X != R.X) AND (E.X != R.X)
 198             AND (Oh.X != R.X) AND (N.X != R.X) )
 199     LEFT JOIN Dx D ON ( (M.X != D.X) AND (S.X != D.X) AND (E.X != D.X)
 200             AND (Oh.X != D.X) AND (N.X != D.X) AND (R.X != D.X) )
 201     LEFT JOIN Dx Y ON ( (M.X != Y.X) AND (S.X != Y.X) AND (E.X != Y.X)
 202             AND (Oh.X != Y.X) AND (N.X != Y.X) AND (R.X != Y.X)
 203             AND (D.X != Y.X) )
 204     LEFT JOIN Cx C0 ON ( C0.X = floor( (D.X + E.X) / 10 ) )
 205     LEFT JOIN Cx C1 ON ( C1.X = floor( (N.X + R.X + C0.X) / 10 ) )
 206     LEFT JOIN Cx C2 ON ( C2.X = floor( (E.X + Oh.X + C1.X) / 10 ) )
 207     LEFT JOIN Cx C3 ON ( C3.X = floor( (S.X + M.X + C2.X) / 10 ) )
 208 WHERE
 209     ( M.X != 0 ) AND
 210     ( S.X != 0 ) AND
 211     (                C3.X    ) = M.X  AND
 212     MOD( S.X + M.X + C2.X, 10) = Oh.X  AND
 213     MOD( E.X +Oh.X + C1.X, 10) = N.X  AND
 214     MOD( N.X + R.X + C0.X, 10) = E.X   AND
 215     MOD( D.X + E.X       , 10) = Y.X
 216 ;
 217
 218 =end kwid