0

Cross + roads = danger ==> the answer is ==> 96233 + 62513=158746

I'm looking for a instruction to find the answer easier for another example. one of my teacher said that we can using tree to find it. but sometimes using tree to find the answer is impossible.

How do you usually find you're cryptarithmetic solution?

false
  • 10,264
  • 13
  • 101
  • 209
Azad Com
  • 45
  • 1
  • 6
  • Are you looking for a description of how to solve these, or a program to solve them? http://s4.zetaboards.com/science/topic/7693756/1/ – user15741 Dec 21 '12 at 14:30
  • Yes, i am looking for both a description of how to solve these and also any source code to solve the cryptarithmetic problem. and also i read this link before==>http://s4.zetaboards.com/science/topic/7693756/1/ – Azad Com Dec 21 '12 at 14:36
  • Your question might be better suited for our sister site, http://mathematica.stackexchange.com/. – Ilmari Karonen Jan 11 '13 at 15:42

3 Answers3

2

One simple way :

Define the variables (just for convenience) : 

vars = Symbol[#] & /@ ("abc" <> ToString[#] & /@ Range[26]) ;

Associate a variable to each letter of the alphabet :

alphabet = Transpose[{CharacterRange["a", "z"], vars}];

Write a helper function to translate a string into an expression :

formDigits[astring_] := FromDigits[alphabet[[alphabet[[#, 2]] & /@ 
   Position[alphabet[[All, 1]], #][[1, 1]] & /@ Characters[astring], 2]]]

Example :

formDigits["cross"]
(* abc19 + 10 (abc19 + 10 (abc15 + 10 (abc18 + 10 abc3))) *)

Write the system of equations corresponding to "Cross + roads = danger" :

equation = formDigits["cross"] + formDigits["roads"] == formDigits["danger"]

Finally solve the system with the obvious additional constraints :

sol = First@FindInstance[{equation, Sequence @@ Thread[Thread[0 <= vars <= 9]], 
    Not[Apply[And, Thread[vars == 0]]]}, alphabet[[All, 2]], Integers] ;

Check :

formDigits["cross"] /. sol
formDigits["roads"] /. sol
formDigits["danger"] /. sol
(* 78644
   86614
  165258 *)
b.gatessucks
  • 1,242
  • 1
  • 15
  • 19
  • Yep, +1. But probably the _Mathematica_ tag was used by mistake – Dr. belisarius Dec 23 '12 at 01:34
  • So, if it's for fun: You aren't requiring that each letter represents a different number. Is that on purpose? :) – Dr. belisarius Dec 23 '12 at 12:43
  • BTW a brute force approach asking for different values for each letter doesn't finish in a reasonable time for this problem. Code here `NotebookPut@ImportString[Uncompress@FromCharacterCode@Flatten@ImageData[Import@ "http://i.stack.imgur.com/sOrph.png","Byte"],"NB"]` – Dr. belisarius Dec 23 '12 at 14:17
0

This is naturally solved, in Prolog. See also Faster implementation of verbal arithmetic in Prolog :

%% unique selection from narrowing domain
selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

%% a puzzle
cryp([[C,R,O,S,S]+[R,O,A,D,S]=[D,A,N,G,E,R]]):- 
   Dom=[0,1,2,3,4,5,6,7,8,9],
   selectM([S],Dom,D0), 
   N1 is S+S,          R is N1 mod 10, R=\=0, 
   selectM([R,D],D0,D1),               D=\=0,
   N2 is (N1//10)+S+D, E is N2 mod 10,
   selectM([E,O,A,G],D1,D2),
   N3 is (N2//10)+O+A, G is N3 mod 10,
   N4 is (N3//10)+R+O, N is N4 mod 10,
   selectM([N,C],D2,_), C=\=0, 
   N5 is (N4//10)+C+R, A is N5 mod 10,
   D  is  N5//10.

The key to efficiency is to choose the instantiations of digits progressively, one by one, testing right away to scrap the invalid choices as soon as possible. I'm sure this can be translated to Mathematica.

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
0

The other problem like this sum is

 CROSS + ROADS = DENGER

The solution for this problem is

 68244 + 82714 = 150958
Harsh Vyas
  • 1
  • 1