Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple cryptarithmetic puzzle solver in Java, C, and Python
public class SimpleSolver {
static int eval(String q) {
int val = 0;
java.util.StringTokenizer st = new java.util.StringTokenizer(q, "*/+-", true);
while (st.hasMoreTokens()) {
String next = st.nextToken().trim();
if (next.equals("+")) {
val += Integer.parseInt(st.nextToken().trim());
} else if (next.equals("-")) {
val -= Integer.parseInt(st.nextToken().trim());
} else if (next.equals("*")) {
val *= Integer.parseInt(st.nextToken().trim());
} else if (next.equals("/")) {
val /= Integer.parseInt(st.nextToken().trim());
} else {
val = Integer.parseInt(next);
}
}
return val;
}
static String solve(String q) {
char c = 0;
for (int i = 0; i < q.length(); ++i) {
if (Character.isAlphabetic(q.charAt(i))) {
c = q.charAt(i);
break;
}
}
if (c == 0) {
String[] ops = q.split("==");
int o1 = eval(ops[0]), o2 = eval(ops[1]);
if (o1 == o2) return q;
else return "";
} else {
char[] dset = new char[10];
for (int i = 0; i < q.length(); ++i)
if (Character.isDigit(q.charAt(i)))
dset[q.charAt(i)-'0'] = 1;
for (int i = 0; i < 10; ++i) {
if (dset[i] == 0) {
String r = solve(q.replaceAll(String.valueOf(c),
String.valueOf(i)));
if (!r.isEmpty()) return r;
}
}
}
return "";
}
public static void main(String[] args) {
String query = "ABCDE * A == EEEEEE";
System.out.println(solve(query));
}
}
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
// get the value of the next integer out of the string s
// quick and dirty
int next_int(char ** s) {
char * q = *s;
char * end = q+strlen(q);
while(!isdigit(q[0]) && q < end)
q++; // advance q to first digit
char * p = q;
while(isdigit(p[0]))
p++; // advance q to character after last digit
char tmp[p-q+1];
strncpy(tmp, q, p-q);
tmp[p-q] = '\0';
*s = p; // advance s to where p is
return atoi(tmp);
}
// evaluate the simple expression q
// doesn't handle fancy stuff like precedence
int eval(char * q) {
int val=0, len=strlen(q);
char * t = q;
while(1) {
if(isdigit(t[0])) {
val = next_int(&t);
} else if (t[0]=='+') {
val += next_int(&t);
} else if (t[0]=='-') {
val -= next_int(&t);
} else if (t[0]=='*') {
val *= next_int(&t);
} else if (t[0]=='/') {
val /= next_int(&t);
} else if (t[0]=='\0') {
break;
} else {
++t;
}
}
return val;
}
// solve the cryptarithmetic puzzle q
char * solve(char * q) {
// find c, the first unbound letter of q
char c = 0;
int i = 0, j = 0, len = strlen(q);
for (i=0; i<len; ++i) {
if (isalpha(q[i])) {
c = q[i];
break;
}
}
if (c == 0) { // if there are no unbound letters
// extract op1 and op2 operands
char * end = q+len;
char * eq = strstr(q, "==");
char op1[eq-q+1], op2[end-eq-1];
strncpy(op1, q, eq-q);
strncpy(op2, eq+2, end-eq-2);
op1[eq-q] = '\0';
op2[end-eq-2] = '\0';
// evaluate op1 and op2
int eval1 = eval(op1), eval2 = eval(op2);
if(eval1 == eval2) { // solved!
char * r = (char*)malloc(len*sizeof(char));
strcpy(r, q);
return r;
} else {
return 0;
}
} else { // if c is the next unbound letter
// find unused digits
char dset[10] = {0,0,0,0,0,0,0,0,0,0};
for (i=0; i<len; ++i)
if (isdigit(q[i]))
dset[q[i]-'0'] = 1;
for (i=0; i<10; ++i) {
if (dset[i] == 0) { // if this digit i is unused
// make a new string n with c replaced with i
char * n = (char*)malloc(len*sizeof(char));
for (j=0; j<len; ++j)
n[j] = (q[j] == c) ? i + '0' : q[j];
char * r = solve(n);
free(n);
if (r) return r;
}
}
}
return 0;
}
int main() {
char * query = "ABCDE * A == EEEEEE";
char * result = solve(query);
if(result) puts(result);
else puts("No solution found.");
return 0;
}
from re import sub
def solve(q):
try:
n = (i for i in q if i.isalpha()).next()
except StopIteration:
return q if eval(sub(r'(^|[^0-9])0+([1-9]+)', r'\1\2', q)) else False
else:
for i in (str(i) for i in range(10) if str(i) not in q):
r = solve(q.replace(n,str(i)))
if r:
return r
return False
if __name__ == "__main__":
query = "ABCDE * A == EEEEEE"
r = solve(query)
print r if r else "No solution found."
# Other puzzles to try:
# query = "REASON == IT * IS + THERE"
# query = "MAD * MAN == ASYLUM"
# query = "THREE + THREE + ONE == SEVEN"
# query = "SEND + MORE == MONEY"
# query = "I + BB == ILL"
# query = "WHOSE + TEETH + ARE + AS == SWORDS"
# query = "BILL + WILLIAM + MONICA == CLINTON"
# query = "GREEN + ORANGE == COLORS"
# query = "PACIFIC + PACIFIC + PACIFIC == ATLANTIC"
# query = "CASSATT + RENOIR == PICASSO"
# query = "MANET + MATISSE + MIRO + MONET + RENOIR == ARTISTS"
# query = "COMPLEX + LAPLACE == CALCULUS"
@sameerthigale

This comment has been minimized.

Copy link

sameerthigale commented Sep 22, 2014

Can you please provide some explanation(algorithm) of the C code

@RamvigneshPasupathy

This comment has been minimized.

Copy link

RamvigneshPasupathy commented Jun 20, 2015

it seems your c algorithm have some bug. plays + well == better must have provided 97426 + 8077 == 105503. instead your algo is providing 17348 + 9277 == 026625 as the output.

@sweed33

This comment has been minimized.

Copy link

sweed33 commented Mar 27, 2018

import java.util.Scanner;

public class SimpleSolver {
static int eval(String q) {
int val = 0;
java.util.StringTokenizer st = new java.util.StringTokenizer(q, "+", true);
while (st.hasMoreTokens()) {
String next = st.nextToken().trim();
if (next.equals("+")) {
val += Integer.parseInt(st.nextToken().trim());
} else if (next.equals("
")) {
val *= Integer.parseInt(st.nextToken().trim());
} else {
val = Integer.parseInt(next);
}
}
return val;
}
static String solve(String q) {
char c = 0;
for (int i = 0; i < q.length(); ++i) {
if (Character.isAlphabetic(q.charAt(i))) {
c = q.charAt(i);
break;
}
}
if (c == 0) {
String[] ops = q.split("=");
int o1 = eval(ops[0]), o2 = eval(ops[1]);
if (o1 == o2)return q;
else return "";
} else {
char[] dset = new char[10];
for (int i = 0; i < q.length(); ++i)
if (Character.isDigit(q.charAt(i)))
dset[q.charAt(i)-'0'] = 1;
for (int i = 0; i < 10; ++i) {
if (dset[i] == 0) {
String r = solve(q.replaceAll(String.valueOf(c),
String.valueOf(i)));
if (!r.isEmpty()) {
String[] p=r.split(" ");
int sw=0;
for(int j=0;j<p.length;j++){
if(p[j].charAt(0)=='0'){
sw=1;
break;
}
}
if(sw==0)return r;
}
}
}
}
return "";
}
public static void main(String[] args) {
Scanner t=new Scanner(System.in);
while(t.hasNext()){
String query =t.nextLine();
System.out.println(solve(query));
}
}
}

no 0 at left

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.