スレッド: [cppll_novice:0605] <exam> 覆面算

επιστημηです。

閑古鳥が鳴いてるので ^^;

SEND + MORE = MONEY
を解きなさい。

- 各文字には 0..9 が入ります。
- S と M は 0 ではありません。

# ざくざくっと無骨に書いて試したらば、
# どうやら答は一通りのようです。

-----:-----:-----:-----:-----:-----:-----:-----:-----:-----
FUKUDA (episteme) Fumiki -- magical, but never a magic...

FUKUDA Fumikiさんの<200411050603.iA563W502200@mailsv5.nec.co.jp>から
>SEND + MORE = MONEY
>を解きなさい。

　yes, sir!
　せんせー期限ないんで、投稿しちゃいます！

　最上位の桁を見て、S+M >= 9、また、Mは計算結果の最上位の桁だか
ら、M=1、よって S >= 8, つまり、8 or 9
　S=8 のとき 8END+1ORE=1ONEY となるが、8+1+1(桁上がり)となるの
で、O=0、このときE+0=Nとなるので、E+1=N
　S=9 のとき 9END=1ORE=1ONEY となる。このとき O は 1 か 0 だが、1
はすでに使われているので O=0,E+1=N

　ここまでで M=1,S=8or9,O=0,E+1=N
　また、桁上がりをしないといけないので N+R >= 9

　これらを考慮して…

#include <stdio.h>

#define BITSET(n,v) (n |= (1 <<(v)))
#define BITOFF(n,v) (n &= ~(1 << (v)))
#define BITCHK(n,v) ((n) & (1 << (v)))

int main(void)
{
 int s,e,n,d;
 int m,o,r;
 int y;
 int bits;

 bits = 0;
 m=1;
 o=0;
 BITSET(bits, m);
 BITSET(bits, o);
 for ( s = 8; s <= 9; s++ ) {
   BITSET(bits, s);
   for ( e = 2; e <= 9; e++ ) {
     if (BITCHK(bits, e))
       continue;
     BITSET(bits, e);
     for ( n = e + 1; n <= 9; n++ ) {
       if (BITCHK(bits, n))
         continue;
       BITSET(bits, n);
       for ( d = 2; d <= 9; d++ ) {
         if (BITCHK(bits, d))
           continue;
         BITSET(bits, d);
         for ( r = 2; r <= 9; r++ ) {
           if (BITCHK(bits, r))
             continue;
           if ( n + r < 9 )
             continue;
           BITSET(bits, r);
           for ( y = 2; y <= 9; y++ ) {
             if (BITCHK(bits, y))
               continue;
             int send, more, money;
             send = s*1000+e*100+n*10+d;
             more = m*1000+o*100+r*10+e;
             money = m*10000+o*1000+n*100+e*10+y;
             if ( send+more==money ) {
               printf( "found %d%d%d%d+%d%d%d%d=%d%d%d%d%d\n",
                 s, e, n, d,
                 m, o, r, e,
                 m, o, n, e, y );
               return 0;
             }
           }
           BITOFF(bits, r);
         }
         BITOFF(bits, d);
       }
       BITOFF(bits, n);
     }
     BITOFF(bits, e);
   }
   BITOFF(bits, s);
 }
 return 1;
}

~/tmp$ ./a.out
found 9567+1085=10652

#…微妙に努力方向が違っている？(笑)

--
電柱一家
mailto:cppll@...
http://denchu.jp/

επιστημηです。

--- "[cppll_novice:0607] Re: <exam> 覆面算" / DENCHU ---

>>SEND + MORE = MONEY
>>を解きなさい。
>
>　yes, sir!
>　せんせー期限ないんで、投稿しちゃいます！

早ぇよきみィ (^^

>...
>~/tmp$ ./a.out
>found 9567+1085=10652

ぴんぽん。せーかい。

>#…微妙に努力方向が違っている？(笑)

微妙に激しく違う鴨 ^^;

-----:-----:-----:-----:-----:-----:-----:-----:-----:-----
FUKUDA (episteme) Fumiki -- magical, but never a magic...

こんばんは、takeと申します。

> 　S=8 のとき 8END+1ORE=1ONEY となるが、8+1+1(桁上がり)となるの
> で、O=0、このときE+0=Nとなるので、E+1=N

S=8だとE=9になり、適当なNが無さそうです。つまりS=9かと。
で、頭から


SEND
MORE
MONEY

繰り上がりからM=1 (決定:1)
SEND
1ORE
1ONEY

S=8or9,O=0or1で1は既出のためO=0 (決定:0,1)

S=8とおいた場合
8END
10RE
10NEY

8+1+1で繰り上がるため，E+0+(N+Rの繰り上がり)>=10からE=9
しかし9+0+1ではN=0で× よってS=9 (決定:0,1,9)

以下上二桁は不要なので問題を改めて．
9END
10RE
10NEY
↓
END
RE
NEY

E+0=N,E!=NよりN=E+1 (決定:0,1,9)
E    (E+1) D
     R     E
(E+1) E     Y

D+E<10の場合
E+1+R=10+E → R=9 ×
よってD+E>=10となり
E+1+R=10+E-1 → R=8 (決定:0,1,8,9)

E    (E+1) D
     8     E
(E+1) E     Y

0,1が使えないためにD+E>=12
8,9が使えないためにD+E<=13
D/Eの組み合わせは5/7か6/7のみ
E=6の場合，N=E+1=7となりD!=7となるので×
E=7の場合，N=E+1=8となり×
よってE=5,D=7,Y=D+E-10=2


結局

9567
1085
10652

となる。

あ、プログラミングしてない……

take-w1@...さんの<892394.1099667181879@www2.local.freeml.net>から
>S=8だとE=9になり、適当なNが無さそうです。つまりS=9かと。

>あ、プログラミングしてない……

　しまった。先にやられた…(笑)

--
電柱一家
mailto:cppll@...
http://denchu.jp/

久方ぶりの投稿です。たいちうです。
あまり投稿が少ないので、こんなのも。

初めてプログラムでパズルを解こうと思ったのは覆面算だったな。
当時N88-BASICで作ったときは、枝刈りを相当真剣にやらないと
プログラムが終わらなかったのにな。

//   send     gbda
//  +more    +hfeb
//  ----- -> -----
//  money    hfdbc

#include <iostream>
using namespace std;

int main()
{
 int a, b, c, d, e, f, g, h;
 int x0, x1, x2, x3;

 // １の位
 for (a = 0; a < 10; a++) {
   for (b = 0; b < 10; b++) {
     if (a==b) continue;
     x0 = a + b;
     c = x0 % 10;
     if (a==c || b==c) continue;
     x0 /= 10;

     // １０の位
     for (d = 0; d < 10; d++) {
       if (a==d || b==d || c==d) continue;
       for (e = 0; e < 10; e++) {
         if (a==e || b==e || c==e || d==e) continue;
         x1 = d + e + x0;
         if (x1 % 10 != b) continue;
         x1 /= 10;
         
         // １００の位
         for (f = 0; f < 10; f++) {
           if (a==f || b==f || c==f || d==f) continue;
           if (e==f) continue;
           x2 = b + f + x1;
           if (x2 % 10 != d) continue;
           x2 /= 10;

           // １０００の位、１００００の位
           for (g = 1; g < 10; g++) {
             if (a==g || b==g || c==g || d==g) continue;
             if (e==g || f==g) continue;
             for (h = 1; h < 10; h++) {
               if (a==h || b==h || c==h || d==h) continue;
               if (e==h || f==h || g==h) continue;
               x3 = g + h + x2;
               if (x3 != 10 * h + f) continue;

               cout << " " << g << b << d << a << endl
                    << "+" << h << f << e << b << endl
                    << "-----" << endl
                    << h << f << d << b << c << endl;
             }
           }
         }
       }
     }
   }
 }
 return 0;
}

国本です。

思ったより回答が少ないようなので投稿します。
ユニークな数列を作るとこで工夫しようとしましたが挫折、力任せの回答になり
ました。

SEND+MORE+MONEY以外でも流せますが、汎用的ってわけでもないですね、これ。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>

// SEND + MORE = MONEY

class WildNumbers {
       std::vector<char> key_;
       int nums_[256];
public:
       WildNumbers(const char *key) {
               std::set<char> temp;
               while (*key) temp.insert(*key++);
               assert(temp.size() <= 10);                        // intで扱える限界桁数
               key_.assign(temp.begin(), temp.end());
       }
       int operator [] (const char *chrs) const {
               int val = 0;
               while (*chrs)
               {
                       val *= 10;
                       val += nums_[*chrs++];
               }
               return val;
       }
       WildNumbers &operator = (int num) {
               for (size_t i = 0, sz = key_.size(); i < sz; ++i) {
                       nums_[key_[i]] = num % 10;
                       num /= 10;
               }
               return *this;
       }
       size_t rows() const { return key_.size(); }
};

int isUniques(int num, size_t rows)
{
       char tbl[10] = { 0, };
       for (size_t i = 0; i < rows; ++i) {
               if (++tbl[num % 10] >= 2)
                       return false;
               num /= 10;
       }
       return true;
}

int iexp(int base, size_t n)
{
       int val = base;
       while (n-- > 0)
               val *= base;
       return val;
}

int main(int argc, char *argv[])
{
       WildNumbers wilds("SENDMOREMONEY");
       size_t rows = wilds.rows();

       for (int num = 0, max = iexp(10, rows); num < max; ++num) {
               if (isUniques(num, rows)) {        // 8桁のユニークな数字のみを持つ整数
                       wilds = num;
                       if (wilds["SEND"] + wilds["MORE"] == wilds["MONEY"]) {
                               if (wilds["S"] != 0 && wilds["M"] != 0) {
                                       std::cout << "SEND=" << wilds["SEND"] << std::endl;
                                       std::cout << "MORE=" << wilds["MORE"] << std::endl;
                                       std::cout << "MONEY=" << wilds["MONEY"] << std::endl;
                               }
                       }
               }
       }
       return 0;
}

国本

επιστημηです。

ほったらかしにしてました。ごめんなさい。

># ざくざくっと無骨に書いて試したらば、
># どうやら答は一通りのようです。

ざくざくっと無骨に書いた僕のコード。
総当りで各文字に数字を充てております。
なのでむっちゃ遅いっす。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <cassert>

class permutation {
private:
 std::string permutation_;
 std::string unique_;
public:
 typedef std::pair<int,std::string> pair_type;
 explicit permutation(const std::string& keywords) {
   std::set<char> unique(keywords.begin(), keywords.end());
   assert( unique.size() <= 10 );
   permutation_.assign(unique.begin(),unique.end());
   unique_ = permutation_;
   while ( permutation_.size() != 10 ) {
     permutation_.insert(permutation_.begin(), ' ');
   }
 }
 pair_type pair(const std::string& key) const {
   pair_type result(0,"");
   for ( int i = 0; i < key.size(); ++i ) {
     int n = permutation_.find(key[i]);
     result.first = result.first * 10 + n;
     result.second += (n + '0');
   }
   return result;
 }
 std::string hash() const {
   return pair(unique_).second;
 }
 bool next() {
   return std::next_permutation(permutation_.begin(), permutation_.end());
 }
};

int main() {
 const std::string A = "SEND";
 const std::string B = "MORE";
 const std::string C = "MONEY";

 permutation perm(A+B+C);
 std::set<std::string> answers;
 do {
   permutation::pair_type na = perm.pair(A);
   if ( na.second[0] == '0' ) continue;
   permutation::pair_type nb = perm.pair(B);
   if ( nb.second[0] == '0' ) continue;
   permutation::pair_type nc = perm.pair(C);
   if ( nc.second[0] == '0' ) continue;
   if ( na.first + nb.first == nc.first ) {
     if ( answers.insert(perm.hash()).second ) {
       std::cout << na.second << " + "
                 << nb.second << " = "
                 << nc.second << std::endl;
     }
   }
 } while ( perm.next() );
 return 0;
}


-----:-----:-----:-----:-----:-----:-----:-----:-----:-----
FUKUDA (episteme) Fumiki -- magical, but never a magic...