# Write a word equation solver

## Introduction

Consider the following example:

  CODE
+ GOLF
——————
GREAT


This is an equation where each letter represents a decimal digit and the words represent natural numbers (similar letters represent similar digits and different letters represent different digits). The task is to match each letter with its digit value so that the equation is correct. One solution for the equation above is:

  9265
+ 1278
——————
10543


Your task is to write a program or a function which can solve such equations as seen above.

Input

The input is a string in the following format:

[A-Z]+\+[A-Z]+=[A-Z]+


Example:

1. CODE+GOLF=GREAT
2. AA+BB=CC

Spaces are omitted and only letters between capital A and Z will be used (no special or small letters).

This string can be read from the standard input, from a file, or as a function parameter.

Output

You have the following two options for the output format:

1. the original equation with the digits substituted
2. list of the letters and their values

If there are multiple solutions, any (but only one) of them should be returned. If there are no solutions, the program should return an empty string or null. The output can be returned as a string, can be written to the standard output or a file.

Example:

1. 9265+1278=10543
2. A=1 B=2 C=3 (you can use any delimiter)

## Rules

1. To make things easier, numbers are accepted to start with 0, but you can handle numbers with leading 0 as invalid solutions, it's up to you
2. Similar letters represent similar digits and different letters represent different digits
3. You can use any language and the standard library of the chosen language (no external libs)
4. You cannot connect to any resources on the internet (why would you anyways?)
5. This is a code golf task, shortest code wins. Consecutive whitespace characters count as a single character. (So any program written in whitespace automatically wins)

I have a somewhat hackish solution using 179 chars. If something is not clear, please ask me in the comments.

• I think the optimal answer is "everything is 0". You might want to specifically prohibit that. – undergroundmonorail Jun 25 '14 at 1:11
• What do you mean by everything is 0? Different letters have to denote different numbers. – David Frank Jun 25 '14 at 1:13
• Missed that, nevermind :) – undergroundmonorail Jun 25 '14 at 2:23
• If there are no solutions, the program should return an empty string or null. Infinite loops still output nothing ... may I? – Titus Oct 15 '18 at 15:14
• To avoid abusing rule #5; you should rule out whitespace in strings. – Titus Oct 15 '18 at 15:36

# Python - 48 characters

exec("".join(map(chr,map(len,'                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             '.split("    ")))))


Abusing the whitespace rule.

First I converted every character in CesiumLifeJacket's answer to its ASCII value (I could have written my own but I am lazy, and it wouldn't have affected the final score anyway). The long string in my solution is one space for each one of those ASCII values, and tabs separating them. Split at tabs, find the lengths, convert back to characters and execute.

SE converts tabs to 4 spaces each, so copypasting won't work. You'll just have to believe me :)

## Ruby 2.0, 122 characters

Brute force shuffling+eval! This doesn't yet meet the criteria of returning null/empty string when there is no solution; it just loops infinitely. If it can't find a result after ~300 million iterations, it will return nil. Close enough?

f=->s{d=*0..9
d.shuffle!&&$.+=1until$.>9**9||z=eval((r=$_.tr(s.scan(/\w/).uniq*'',d*'')).gsub(/\b0/,'').sub ?=,'==') z&&r}  It finds all the unique letters in the input, then repeatedly shuffles the digits 0-9 and attempts to match them up with the letters until it finds a configuration that works. The code is presented as a function called f which returns a string with the numbers substituted, as in Output Option 1 above. Example usage: puts f["AA+BB=CC"] #=> 22+44=66 puts f["CODE+GOLF=GREAT"] #=> 8673+0642=09315  Running time for the CODE+GOLF=GREAT example on my machine varies from instantaneous to about 6 seconds - depends on how lucky you are with the shuffles! I'm particularly unhappy with the gsub(/\b0/,'') bit to remove leading zeroes but it was the only thing I could think to prevent eval from interpreting the numbers as octal ints. (BONUS: Because it uses eval, it works for arbitrary Ruby expressions and not just addition!) • I had the same idea when I read this, but I got ~170 chars of code, so well done. 0..9 are ten digits, so shouldn't the limit be 10**10? You could use Array#permutation to loop over all possible mappings, but that might make the code longer. – blutorange Jun 25 '14 at 11:27 • @blutorange I just chose 9**9 because it was a big number you could write with few characters. It should be more than enough for any reasonable test cases I think! I haven't tried a version based on permutation, but as you say, I was primarily concerned with code length. – Paul Prestidge Jun 25 '14 at 22:59 ## LiveScript (179 chars) It has deterministic and relatively quick running time and works with other operators (+, -, *) as well. f=(s)-> # define function that takes parameter s c=s.replace /[^A-Z]/g '' # remove all the non-letters if c # if any letters remain for i from 0 to 9 # loop from 0 to 9 if s.indexOf(i)<0&&a=f s.split(c.0).join i # if i is not present in the number, replace the first letter with i and call the function recursively return a # if there is a solution, return it else # if there are no letters left if eval s.replace(/(^|\D)0+(\d)/g,'$1$2').replace \= \== # if the expression is correct (we need to remove leading 0, because javascript interprets numbers with leading 0 as octal) return s # return solution f("CODE+GOLF=GREAT")  # Python, 256 213 chars Horrific running time, will try to improve further: q='=' e=input() v=set(e)-set([q,'+']) for x in __import__('itertools').permutations(range(10),len(v)): t=e for l,n in zip(v,x):t=t.replace(l,str(n)) try: if eval(t.replace(q,q*2)):print(t);break except:pass  # JavaScript 138 for(s=prompt(p='1');eval(p.replace('=','!='));)for(p=s,i=64;i++<90;)p=p.replace(new RegExp(String.fromCharCode(i),'g'),10*Math.random()|0)  Random bruteforce. Can take a while (my best shot for CODE+GOLF=GREAT is 3 seconds, my worst 3 minutes). Try it with a simple expression like A+B=C # Haskell, 222 import Data.List z=(\(b,(_:c))->b:z c).span Data.Char.isUpper j(Just g)=g main=interact$(\d@[a,b,c]->show$take 1[e|e<-map(zip$nub$d>>=id)$permutations['0'..'9'],(\f->f a+f b==(f c::Int))(read.map(j.(lookupe)))]).take 3.z


Brute force. Tries every possible matching until it finds one, or after it has finished trying them all. I stretched the output rules: prints something like [[('C','3'),('O','8'),('D','6'),('E','7'),('G','0'),('L','5'),('F','2'),('R','4'),('A','1'),('T','9')]] for the solution, and if none exists, prints []. Let me know if I need to change this.

• I think, this output is acceptable. – David Frank Jun 25 '14 at 10:12

# CJam - 17

"

""
"f#3b127b:c~


Total 975 characters, but 960 of them are whitespace in 2 sequences, so those count as 2 characters, and together with the other 15, we get 17.
975 may seem like a lot, but note that undergroundmonorail's python solution has 18862 characters, they're just on a single line :)

You can run it at http://cjam.aditsu.net/ for short words, but you should probably use the java interpreter for longer ones. With java on my laptop, SEND+MORE=MONEY runs in 30-40 sec and CODE+GOLF=GREAT in almost 3 min. It doesn't accept numbers starting with 0 (because that's not cool).

Here's a program that generates the program above (also helps if StackExchange doesn't show the whitespace correctly):

"{L__&=}:U;
{L!!{L))_9>{;:L;I}{+:L;}?}*}:I;
{{U!_{I}*}g}:M;
{L,N<L,g&}:K;
{I{K{L0+:L;}*MK}g}:G;
{{C#L=}%si}:R;
{XRYR+ZR=PRAb0#0<&}:F;
l'+/~'=/~:Z;:Y;:X;
[X0=Y0=Z0=]:P;
XYZ++_&:C,:NB<{0a:L;{F0{GL}?}g}*
L{XR'+YR'=ZR}{L}?"
127b3b[32 9 A]:cf='"\'"_32c9cAc"\"f#3b127b:c~"


The first 11 lines contain the original program (not really golfed) in a string, and the last line does the conversion and adds the decoding part.

# Powershell, 137 bytes

port of LiveScript

$f={param($s)if($c=$s-replace'[^A-Z]'){0..9|?{$s-notmatch$_}|%{&$f ($s-replace$c[0],$_)}|Select -f 1}elseif($s-replace'=','-eq'|iex){$s}}


Ungolfed test script:

$f={ param($s)                           # parameter string
$c=$s-replace'[^A-Z]'               # remove all the non-letters
if($c){ # if any letters remain 0..9|?{ # loop from 0 to 9$s-notmatch$_ # if$s is not contains current number
}|%{
&$f ($s-replace$c[0],$_)    # replace the first letter with current number and call the function recursively
}|Select -f 1                   # seelct first non-null value (break if found)
}
elseif($s-replace'=','-eq'|iex){ # else if evaluated value if the expression is$true
$s # return$s as solution
}

}

&$f "AA+BB=CC" &$f "A+AB=A"            # empty because it has no solution
&$f "CODE+GOLF=GREAT"  Output: 11+22=33 2846+0851=03697  # PHP, 118 113 bytes for(;;)eval(strtr($argn,"=".$w=substr(count_chars($argn,3),2),"-".$n=str_shuffle(1234567890))."||die('$w
$n');");  prints digits below letters and exits program; loops infinitely if unsolvable. Run as pipe with -nr. breakdown for(;;) eval( # 6. evaluate strtr($argn,                    # 4. translate letters to digits, "=" to "-"
"=".$w=substr( # 2. remove non-letters count_chars($argn,3)    # 1. get characters used in the argument
,2),
"-".$n=str_shuffle(1234567890) # 3. shuffle digits )."||die('$w\n$n');" # 5. if falsy (A+B-C==0), print translation and exit ) ;  # PHP, 145 bytes function f($s){for(;$i<10*preg_match("/[A-Z]/",$s,$m);)strpos(_.$s,++$i+47)||f(strtr($s,$m[0],$i-1));$i||eval(strtr($s,"=","-")."||die('$s');");}  recursive function, prints solved equation and exits program; returns NULL when unsolvable. Try it online breakdown function f($s)
{
for(;
$i<10 # loop$i from 0 to 9
*preg_match("/[A-Z]/",$s,$m)    # find a letter; if not found: $i<10*0 == falsy ; ) strpos(_.$s,++$i+47) # find$i in string
||f(strtr($s,$m[0],$i-1)); # if not found, replace letter with$i, recurse
$i|| # no letter found ($i is unset):
eval(                   # evaluate:
strtr($s,"=","-") # replace "=" with "-" ."||die('$s');"         # if falsy (A+B-C==0), print equation, exit program
);
# else implicitly return NULL
}