Verbal arithmetic (복면산) C++ 코드

 

 

복면산(覆面算)은 수학 퍼즐의 한 종류로, 문자를 이용하여 표현된 수식에서 각 문자가 나타내는 숫자를 알아내는 문제이다. 숫자를 문자로 숨겨서 나타내므로 숫자가 “복면”을 쓰고 있는 연산이라는 뜻에서 복면산이라 이름 지어졌다. [1]

verbal arithmetic, alphametics, cryptarithmetic, crypt-arithmetic, cryptarithm or word addition in english.

 

풀이.

// 글자 하나와 그 값을 저장함 struct Character { Character(char c) : _char(c), _value(-1), _noneZero(false) {} char _char; // A ~ Z int _value; // 0 ~ 9 bool _noneZero; // (true == not-zero) };

// 단어. 내부에 글자의 리스트를 가지고 있음 class Word { public: Word() {} ~Word() {} public: void push(char c) { Character character(c); if (_word.empty()) { character._noneZero = true; // the first letter can be ZERO } _word.push_back(character); } bool empty() const { return _word.empty(); } void clear() { _word.clear(); } int32 getValue() const { int32 value = 0; const size_t size = _word.size(); for (size_t i = 0; i < size; i++) value = value * 10 + _word[i]._value; return value; } void getCharacters(set<char> &characters) { const size_t size = _word.size(); for (size_t i = 0; i < size; i++) { characters.insert(_word[i]._char); } } void setValues(const vector<int> &map) { const size_t size = _word.size(); for (size_t i = 0; i < size; i++) { _word[i]._value = map[_word[i]._char - 'A']; } } void printCharacter() const { const size_t size = _word.size(); for (size_t i = 0; i < size; i++) cout << _word[i]._char; cout << endl; } void printValue() const { const size_t size = _word.size(); for (size_t i = 0; i < size; i++) cout << _word[i]._value; cout << endl; } bool isValid() { return (_word[0]._value != 0); // the for letter of word can be ZERO } private: vector<Character> _word; };

// 전체 식을 저장하고 있음. class Formula { public: Formula() {} ~Formula() {} public: void pushLeftSide(const Word &w) { _leftSides.push_back(w); } void setRightSide(const Word &w) { _rightSide = w; } bool isValid() { int32 left(0), right(0); size_t size = _leftSides.size(); if (!_rightSide.isValid()) return false; for (size_t i = 0; i < size; i++) { if (!_leftSides[i].isValid()) return false; left += _leftSides[i].getValue(); } right = _rightSide.getValue(); return (left == right); } vector<char> getCharacters() { set<char> characters; size_t size = _leftSides.size(); for (size_t i = 0; i < size; i++) _leftSides[i].getCharacters(characters); _rightSide.getCharacters(characters); vector<char> result; set<char>::const_iterator it = characters.begin(); for (; it != characters.end(); it++) { result.push_back(*it); } return result; } void setValues(const vector<int> &map) { size_t size = _leftSides.size(); for (size_t i = 0; i < size; i++) _leftSides[i].setValues(map); _rightSide.setValues(map); } void printCharacter() const { size_t size = _leftSides.size(); for (size_t i = 0; i < size; i++) _leftSides[i].printCharacter(); _rightSide.printCharacter(); } void printValues() const { size_t size = _leftSides.size(); for (size_t i = 0; i < size; i++) _leftSides[i].printValue(); _rightSide.printValue(); } private: vector<Word> _leftSides; Word _rightSide; };

// main : 파일로부터 값을 읽고, 문제를 풀어 결과를 출력함. ////////////////////////////////////////////////////////////// // function prototypes void printUsage(); void getInput(const char* inFile); bool getLeftSides(ifstream &in); void getRightSide(ifstream &in); void solve(); bool permutation(vector<int> &list, int n, int length, int level, int flag); template<typename T> void printSet(const vector<T> &characters); bool solved(const vector<int> &solution); Formula g_formula; vector<char> g_charList; int32 main(int32 argc, char *argv[]) { if (argc != 2) { printUsage(); return -1; } getInput(argv[1]); // no error check //g_formula.printCharacter(); // for debugging solve(); return 0; } void printUsage() { cout << "executable input_file_path" << endl; } void getInput(const char* inFile) { ifstream in(inFile); getLeftSides(in); getRightSide(in); } bool getLeftSides(ifstream &in) { Word word; while (!in.eof()) { char c = in.get(); if (c >= 'A' && c <= 'Z') { word.push(c); } else if (c == '+') { g_formula.pushLeftSide(word); word.clear(); } else if (c == '=') { if (!word.empty()) { g_formula.pushLeftSide(word); } break; } } return true; } void getRightSide(ifstream &in) { Word word; while (!in.eof()) { char c = in.get(); if (c >= 'A' && c <= 'Z') { word.push(c); } } g_formula.setRightSide(word); } void solve() { g_charList = g_formula.getCharacters(); printSet<char>(g_charList); vector<int> solution; permutation(solution, 10, static_cast<int>(g_charList.size()), 0, 0); printSet<int>(solution); //g_formula.printValues(); } /** * * return true if solution found or finished */ bool permutation(vector<int> &list, int n, int length, int level, int flag) { if (level == length) { return (solved(list)); } for (int i = 0; i < n; i++) { if (flag & (0x1 << i)) { // used continue; } list.push_back(i); if (permutation(list, n, length, level + 1, flag | 0x1 << i)) { return true; } list.pop_back(); } return false; } template<typename T> void printSet(const vector<T> &characters) { typedef typename std::vector<T>::const_iterator ConstIterator; ConstIterator it = characters.begin(); for (; it != characters.end(); it++) { cout << *it << " "; } cout << endl; } bool solved(const vector<int> &solution) { vector<int> map; map.resize(26); size_t size = solution.size(); for (size_t i = 0; i < size; i++) { map[g_charList[i] - 'A'] = solution[i]; } g_formula.setValues(map); return g_formula.isValid(); }

입력이 다음과 같을 때,

SEND + MORE = MONEY

출력 : 

D E M N O R S Y

7 5 1 6 0 8 9 2

references

[1] http://ko.wikipedia.org/wiki/%EB%B3%B5%EB%A9%B4%EC%82%B0

[2] http://en.wikipedia.org/wiki/Verbal_arithmetic