http://blog.livedoor.jp/itsoku/archives/47064212.html
441:デフォルトの名無しさん 2015/07/23(木) 23:21:58.40 ID:tM+kqpz/.net
覆面算です。各英字は異なる数字です。
デュードニーの覆面算
SEND 9567
＋ MORE 1085
-------
MONEY 10652
「Googleの入社試験」より。ただし、EとMは交換可能です
WWWDOT - GOOGLE = DOTCOM
補足:上の SEND＋MORE=MONEYのように各英字に置き換えられた数字を解く問題。
スポンサードリンク
444:デフォルトの名無しさん 2015/07/24(金) 02:33:15.17 ID:i7tlJ0x5.net
数字のマップ方法が思い浮かばないなー。
445:440 2015/07/24(金) 02:44:51.78 ID:orlgr+Lf.net
さあ？ 総当たりはどうかね？
446:デフォルトの名無しさん 2015/07/24(金) 03:00:39.65 ID:i7tlJ0x5.net
辞書ないとだめじゃね？
447:440 2015/07/24(金) 03:45:43.16 ID:orlgr+Lf.net
数独(ナンプレ)よりは、簡単そうだけど
449:デフォルトの名無しさん 2015/07/24(金) 07:30:49.96 ID:i7tlJ0x5.net
>>441
C++。一応解いたが誤答も入ってる気がする。大いにする。
VCのリリースで10秒ほどかかる。＠N3700
これでググる入社だ！
辞書云々は勘違いしてた。
#include <iostream>
#include <algorithm>
#include <stdint.h>
#include <string>
#include <tuple>
#include <map>
#include <vector>
#include <functional>
//var 0.03a
enum class Op {
None,
Add,
Sub,
};
typedef std::map<char, std::uint32_t> Dic;
typedef std::tuple<std::string, std::string, std::string, Op> Data;
typedef std::vector<std::uint32_t> iVec;
typedef std::vector<std::tuple<std::uint32_t, std::uint32_t, std::uint32_t,Op,Dic>> RType;
std::int32_t MakeNumber(std::string S, Dic& D) {
std::int32_t R = 0;
for (auto& o : S) {
R *= 10;
R += D[o];
}
return R;
}
std::uint32_t CountDigit(std::uint32_t N) {
std::uint32_t c = 0;
while (N != 0) {
N /= 10;
c++;
}
return c;
}
RType MakeHoge(const Data& D){
std::string A;
std::string B;
std::string C;
Op op = Op::None;
Dic Di;
iVec v{ 0,1,2,3,4,5,6,7,8,9 };
std::size_t i = 0;
bool F=false;
RType R;
std::int32_t a = 0;
std::int32_t b = 0;
std::int32_t c = 0;
std::tie(A, B, C, op) = D;
for (auto& o : A) {
Di[o] = 0;
}
for (auto& o : B) {
Di[o] = 0;
}
for (auto& o : C) {
Di[o] = 0;
}
do {
for (auto& o : Di) {
o.second = v[i];
i++;
}
i = 0;
a = MakeNumber(A, Di);
b = MakeNumber(B, Di);
c = MakeNumber(C, Di);
switch (op)
{
case Op::Add:
F = (a + b == c);
break;
case Op::Sub:
F = (a - b == c);
break;
default:
std::cout << "unknown op prametor" << std::endl;
return{};
break;
}
if (F == true) {
R.push_back(std::make_tuple(a, b, c, op,Di));
}
} while (std::next_permutation(v.begin(), v.end()));
return R;
}
bool Show(std::string A, std::string B, std::string C, RType& R) {
std::int32_t a;
std::int32_t b;
std::int32_t c;
Op op = Op::None;
Dic D;
R.erase(std::unique(R.begin(), R.end()),R.end());
for (auto& o : R) {
std::tie(a, b, c, op,D) = o;
if (A.size() != CountDigit(a)) continue;
if (B.size() != CountDigit(b)) continue;
if (C.size() != CountDigit(c)) continue;
std::cout << A;
switch (op)
{
case Op::Add:
std::cout << " + ";
break;
case Op::Sub:
std::cout << " - ";
break;
default:
std::cout << " ? ";
break;
}
std::cout << B;
std::cout <<" = "<< C << std::endl;
std::cout << a;
switch (op)
{
case Op::Add:
std::cout << " + ";
break;
case Op::Sub:
std::cout << " - ";
break;
default:
std::cout << " ? ";
break;
}
std::cout << b;
std::cout <<" = "<< c << std::endl;
for (auto&o : D) {
std::cout << o.first << '[' << static_cast<int>(o.second) << ']';
}
std::cout << std::endl<< std::endl;
}
return true;
}
int main() {
std::string A;
std::string B;
std::string C;
Op op = Op::None;
RType R;
A = "SEND";
B = "MORE";
C = "MONEY";
R = MakeHoge(std::make_tuple(A, B, C, Op::Add));
Show(A, B, C, R);
A = "WWWDOT";
B = "GOOGLE";
C = "DOTCOM";
R = MakeHoge(std::make_tuple(A, B, C, Op::Sub));
Show(A, B, C, R);
return 0;
}
452:デフォルトの名無しさん 2015/07/24(金) 14:42:27.19 ID:EjPkrmXr.net
>>441
Java
酷いコードが出来たぜ
import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Alphametic
{
public static void main(String[] args)
{
try (Scanner in = new Scanner(System.in))
{
while (in.hasNextLine())
{
new Alphametic(in.nextLine()).print();
}
}
}
private static Pattern pat = Pattern.compile("([0-9A-Z]+)([+-\\\\*])([0-9A-Z]+)=([0-9A-Z]+)");
private final String sa;
private final String sb;
private final String sc;
private final String op;
private final String[] st;
private final Op operator;
private final int e;
private final int[] map = new int[256];
private final boolean[] used = new boolean[10];
private String[] result = new String[0];
private Alphametic(String exp)
{
Matcher mat = pat.matcher(exp);
if (!mat.matches()) throw new IllegalArgumentException();
this.sa = mat.group(1);
this.op = mat.group(2);
this.sb = mat.group(3);
this.sc = mat.group(4);
this.st = new String[] { sa, sb, sc };
switch(op)
{
case "+": operator = (a, b) -> a + b; break;
case "-": operator = (a, b) -> a - b; break;
case "*": operator = (a, b) -> a * b; break;
default: throw new IllegalArgumentException();
}
for (int i = 0; i <= 9; i++) map['0' + i] = i;
for (int i = 'A'; i <= 'Z'; i++) map[i] = i;
e = Math.max(Math.max(sa.length(), sb.length()), sc.length()) * 3;
solve(0, new long[3], 1);
}
private void solve(int p, long[] ls, long d)
{
if (p == e)
{
if (!operator.test(ls[0], ls[1], ls[2], Long.MAX_VALUE)) return;
for (String s : st) if (map[s.charAt(0)] <= 0) return;
result = Arrays.copyOf(result, result.length + 1);
result[result.length - 1] = String.format("%d%s%d=%d", ls[0], op, ls[1], ls[2]);
return;
}
int i = p / 3;
int j = p % 3;
if (p > 0 && j == 0)
{
d *= 10;
if (!operator.test(ls[0], ls[1], ls[2], d)) return;
}
int n = ch(st[j], i);
long l = ls[j];
if (n >= 'A' && n <= 'Z')
{
for (int k = 0; k < 10; k++)
{
if (used[k]) continue;
used[k] = true;
map[n] = k;
ls[j] = l + k * d;
solve(p + 1, ls, d);
used[k] = false;
}
map[n] = n;
}
else
{
ls[j] += n * d;
solve(p + 1, ls, d);
}
ls[j] = l;
}
private int ch(String s, int i)
{
return s.length() <= i ? 0 : map[s.charAt(s.length() - i - 1)];
}
void print()
{
System.out.printf("%s%s%s=%s%n", sa, op, sb, sc);
for (String s : result) System.out.println(s);
System.out.println();
}
private interface Op
{
long op(long a, long b);
default boolean test(long a, long b, long c, long d)
{
return Math.abs(op(a, b) - c) % d == 0;
}
}
}
453:デフォルトの名無しさん 2015/07/24(金) 16:21:16.16 ID:E+gh8pZi.net
>>452
すげー速いな
こういうのC++で書けないかな
456:デフォルトの名無しさん 2015/07/24(金) 19:23:23.71 ID:i7tlJ0x5.net
>>453
ポートする意外だとアイディアないな。
俺のはnext_parmitation使ってるからめちゃくちゃ遅い。o(N!)だし。
ぜひ改善してくれ。
455:デフォルトの名無しさん 2015/07/24(金) 18:23:05.71 ID:cSQMFcxl.net
>>441
Javaに勝てる気がしないけどProlog で
% fadder(A,B,C,D,E) :- A + B + C = 10E + D
:-dynamic(fadder/5).
fadder0(A,B,C,D,E) :- between(0,9,A),between(0,9,B),between(0,1,C),
D is (A + B + C) mod 10, E is floor((A +B + C)/ 10), asserta(fadder(A,B,C,D,E)).
:- setof(fadder(A,B,C,D,E),fadder0(A,B,C,D,E),L), member(X,L),asserta(X),fail;true.
:- compile_predicates([fadder/5]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
fukumen(A,B,C) :-
setof(V,varof([A,B,C],V),Vars),
setof([A,B,C],(fukumen0(A,B,C,0),alldifferent(Vars)),L),member([A,B,C],L).
fukumen0([A|X],[B|Y],[D|Z],E) :- fadder(A,B,C,D,E), D \= 0, fukumen1(X,Y,Z,C).
fukumen1([],[],[],0) :- !.
fukumen1([A|X],[B|Y],[D|Z],E) :- fadder(A,B,C,D,E), fukumen1(X,Y,Z,C).
varof(T,T) :- var(T),!.
varof(T,_) :- ground(T),!,fail.
varof(T,V) :- arg(_,T,A),varof(A,V).
alldifferent(X) :- nth0(I,X,A),nth0(J,X,B),A==B, I \= J,!,fail.
alldifferent(_).
%% ----------------------------------------------
:- write('SEND + MORE = MONEY'), nl,fukumen([0,S,E,N,D],[0,M,O,R,E],[M,O,N,E,Y]) ,
write([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]),nl,fail;nl.
:- write('WWWDOT - GOOGLE = DOTCOM'),nl,fukumen([D,O,T,C,O,M],[G,O,O,G,L,E],[W,W,W,D,O,T]),
write([W,W,W,D,O,T]-[G,O,O,G,L,E]=[D,O,T,C,O,M]),nl,fail;true.
457:デフォルトの名無しさん 2015/07/24(金) 23:56:32.13 ID:VNZ6dmGo.net
>>441
C
遅い
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int used = 0;
char str[32];
void eval()
{
char *p, *q;
int a,b,c;
a = strtol(str, 0, 10);
q = strchr(str, '='); c = strtol(q + 1, 0, 10);
p = strchr(str, '+');
if(p) {
b = strtol(p + 1, 0, 10);
if(p[1] == '0' || q[1] == '0') return;
if((a + b) == c){
printf(" %s\n", str);
}
}
p = strchr(str, '-');
if(p) {
b = strtol(p + 1, 0, 10);
if(p[1] == '0' || q[1] == '0') return;
if((a - b) == c){
printf(" %s\n", str);
}
}
}
void recur(int offs)
{
int c,n,i,old_used=used;
char old_str[32];
if((c = str[offs]) == 0) {
eval();
return;
}
if(! isalpha(c)) {
recur(offs + 1);
return;
}
strcpy(old_str, str);
for(n=((offs == 0)?1:0); n<10; n++) {
if(!(used & (1 << n))) {
used |= (1 << n);
for(i=0; str[i]; i++) {
if(str[i] == c) str[i] = '0' + n;
}
recur(offs + 1);
used = old_used;
strcpy(str, old_str);
}
}
}
main()
{
strcpy(str, "SEND+MORE=MONEY");
printf("\n%s\n", str);
recur(0);
strcpy(str, "WWWDOT-GOOGLE=DOTCOM");
printf("\n%s\n", str);
recur(0);
return 0;
}
459:デフォルトの名無しさん 2015/07/25(土) 02:34:01.78 ID:tp+9eo6i.net
>>441
Python
足し算と引き算のみ
いろいろと改良の余地が非常に多そうなので、また修正すると思う
from __future__ import unicode_literals, division, print_function
import re
def do_it(expr):
elems = parse_input(expr)
if elems is None: raise Exception()
val1, op_chr, val2, val3 = elems
op_fn, test_fn = get_operator_fn(op_chr)
precheck_fn = get_precheck_fn(val1, test_fn, val2, val3)
valid_fn = get_valid_fn(val1, op_fn, val2, val3)
def assignNum(chars, nums=range(10), a_dic={}):
if len(chars) <= 0:
if valid_fn(a_dic):
print(format_result(val1, op_chr, val2, val3, a_dic))
return True
return False
for i in range(len(nums)):
a_dic[chars[0]] = nums[i]
if not precheck_fn(a_dic):
continue
if assignNum(chars[1:], nums[0:i] + nums[i + 1:]):
return True
del a_dic[chars[0]]
return False
print(expr)
assignNum(list(set([ch for ch in val1 + val2 + val3])))
def to_num(val, a_dic):
l_val = [ch for ch in val]
l_pow = [pow(10, i) for i in reversed(range(len(l_val)))]
return sum([a_dic[ch] * i for ch, i in zip(l_val, l_pow)])
def get_precheck_fn(val1, test_fn, val2, val3):
def precheck_fn(a_dic):
try:
if any([a_dic[val[0]] == 0 for val in [val1, val2, val3]]):
return False
except KeyError:
pass
for i in range(min(len(val1), len(val2), len(val3))):
try:
if not test_fn(a_dic[val1[-i - 1]], a_dic[val2[-i - 1]], a_dic[val3[-i - 1]]):
return False
except KeyError:
pass
return True
return precheck_fn
def get_valid_fn(val1, op_fn, val2, val3):
def valid_fn(a_dic):
return op_fn(to_num(val1, a_dic), to_num(val2, a_dic)) == to_num(val3, a_dic)
return valid_fn
def get_operator_fn(op_chr):
if op_chr == '+': return lambda x, y: x + y, lambda x, y, z: z in ((x + y) % 10, (x + y + 1) % 10)
if op_chr == '-': return lambda x, y: x - y, lambda x, y, z: z in ((10 + x - y) % 10, (9 + x - y) % 10)
def parse_input(expr):
m = re.match(r'^([A-Z]+)\s*([\+\-\*/])\s*([A-Z]+)\s*=\s*([A-Z]+)', expr)
if m is not None:
return m.group(1), m.group(2), m.group(3), m.group(4)
return None
def format_result(val1, op, val2, val3, a_dic):
vals = [''.join([str(a_dic[ch]) for ch in val]) for val in [val1, val2, val3]]
return '{} {} {} = {}'.format(vals[0], op, vals[1], vals[2])
do_it('SEND + MORE = MONEY')
print()
do_it('WWWDOT - GOOGLE = DOTCOM')
460:デフォルトの名無しさん 2015/07/25(土) 04:16:19.74 ID:BtkcRlE5.net
>>441
遅ればせながらC++
#include <iostream>
#include <string>
#include <map>
#include <sstream>
#include <algorithm>
#include <functional>
#include <chrono>
template <typename unit, typename Clock = std::chrono::high_resolution_clock>
struct StopWatch {
typename Clock::time_point start;
StopWatch() : start(Clock::now()) {}
unsigned getDifference(){
return std::chrono::duration_cast<unit>(Clock::now() - start).count();
}
};
template <typename Integer>
struct Resolver {
using Calculator = std::function<Integer(Integer,Integer)>;
std::string line;
std::string word1;
std::string word2;
std::string ope;
std::string word3;
std::map<char,Integer> charCombinationMap;
Calculator calcurator;
static Calculator getBinaryCalculator(std::string& operatorString){
if( operatorString.size() == 1 ) switch(operatorString[0]){
case '+': return std::plus<Integer>();
case '-': return std::minus<Integer>();
case '*': return std::multiplies<Integer>();
case '/': return std::divides<Integer>();
}
return std::plus<Integer>();
}
Resolver(std::string& aLine) : line(aLine) {
std::string eq;
std::stringstream(line) >> word1 >> ope >> word2 >> eq >> word3;
calcurator = getBinaryCalculator(ope);
}
std::string getResultString(){
std::string result;
std::string integerMap = "0123456789";
for( auto ch :line )
result.push_back( (charCombinationMap.count(ch) > 0) ?
integerMap[ charCombinationMap[ch] ] : ch );
return result;
}
bool validate(){
for( auto word: std::vector<std::string>{word1,word2,word3} )
if( charCombinationMap[ word[0] ] == 0 )
return false;
return calcurator( toInteger(word1), toInteger(word2) ) == toInteger(word3);
}
Integer toInteger(std::string& word){
return std::accumulate( word.begin(), word.end(),0, [&](Integer prev, char ch){
return (prev * 10) + charCombinationMap[ch];
});
}
std::string getCharList(){
std::string charList;
{
std::map<char,bool> exists;
for( auto word: std::vector<std::string>{word1,word2,word3} )
for( auto ch: word )
exists[ch] = true;
for( auto entry: exists )
charList.push_back(entry.first);
}
return charList;
}
std::string resolve(){
std::string charList = getCharList();
std::vector<bool> taken(10);
std::fill(taken.end() - charList.size(), taken.end() , true);
do {
std::vector<Integer> combination;
for (int i = 0; i < 10; ++i){
if ( taken[i] )
combination.push_back(i);
}
do {
auto it = charList.begin();
for( auto value :combination ){
charCombinationMap[*it] = value;
++it;
}
if( validate() )
return getResultString();
}
while (std::next_permutation(combination.begin(), combination.end()));
}
while (std::next_permutation(taken.begin(), taken.end()));
return "not found";
}
};
int main() {
for( std::string line; std::getline(std::cin,line); ){
StopWatch<std::chrono::milliseconds> stopWatch;
std::string result = Resolver<int>(line).resolve();
std::cout << result
<< " (in " << stopWatch.getDifference() << "ms)"
<< std::endl;
}
return 0;
}
463:デフォルトの名無しさん 2015/07/25(土) 06:53:11.73 ID:BtkcRlE5.net
>>460
チューンでまあまあ速くなった
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
#include <functional>
#include <chrono>
// ä¿®æ£
template <typename unit, typename Clock = std::chrono::high_resolution_clock>
struct StopWatch {
typename Clock::time_point start;
StopWatch() : start(Clock::now()) {}
unsigned getDifference(){
return std::chrono::duration_cast<unit>(Clock::now() - start).count();
}
};
template <typename Integer>
struct Resolver {
using WordType = std::vector<Integer>;
std::string line;
std::array<WordType,3> words;
std::string operatorSymbol;
std::vector<Integer> combinationMap;
std::map<char,Integer> charMap;
Resolver(std::string& aLine) : line(aLine) {
std::array<std::string, 3> rawWords;
std::string eq;
std::stringstream(line) >> rawWords[0] >> operatorSymbol >> rawWords[1] >> eq >> rawWords[2];
{
int i = 0;
for( auto rawWord: rawWords )
for( auto ch: rawWord )
if(charMap.count(ch) <= 0)
charMap[ch] = i++;
}
for( int i = 0; i < rawWords.size(); i++ ){
std::vector<Integer> word;
for( auto ch: rawWords[i] )
word.push_back( charMap[ch] );
words[i] = word;
}
}
std::string getResultString(){
std::string buffer;
std::stringstream stream(buffer);
stream << toInteger(words[0]) << " " << operatorSymbol << " " << toInteger(words[1])
<< " = " << toInteger(words[2]);
return stream.str();
}
bool validate(){
bool found;
Integer n1 = toInteger(words[0]);
Integer n2 = toInteger(words[1]);
Integer n3 = toInteger(words[2]);
switch(operatorSymbol[0]){
default:
case '+': found = (n1 + n2) == n3; break;
case '-': found = (n1 - n2) == n3; break;
case '*': found = (n1 * n2) == n3; break;
case '/': found = (n1 / n2) == n3; break;
}
if( !found )
return false;
for( auto word: words )
if( combinationMap[ word[0] ] == 0 )
return false;
return true;
}
Integer toInteger(std::vector<Integer>& word){
return std::accumulate( word.begin(), word.end(), 0, [&](Integer prev, Integer ch){
return (prev * 10) + combinationMap[ch];
});
}
StopWatch<std::chrono::milliseconds> stopWatch;
void print(){
std::cout << line << " -> " << getResultString()
<< " (in " << stopWatch.getDifference() << "ms)"
<< std::endl;
}
void resolve(){
std::vector<bool> taken(10);
std::fill(taken.end() - charMap.size(), taken.end() , true);
combinationMap = std::vector<Integer>( charMap.size() );
do {
int n = 0;
for (int i = 0; i < 10; ++i)
if ( taken[i] )
combinationMap[n++] = i;
do if( validate() )
print();
while (std::next_permutation(combinationMap.begin(),combinationMap.end()));
}
while (std::next_permutation(taken.begin(), taken.end()));
}
};
int main() {
for( std::string line; std::getline(std::cin,line); )
Resolver<int>(line).resolve();
return 0;
}
答え：
WWWDOT 777589 - GOOGLE 18810(3)= DOTCOM 58948(6)
WWWDOT 777589 - GOOGLE 18810(6)= DOTCOM 58948(3)
