Created
April 24, 2012 17:28
-
-
Save vo/2481737 to your computer and use it in GitHub Desktop.
Simple cryptarithmetic puzzle solver in Java, C, and Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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