-
-
Save vo/2481737 to your computer and use it in GitHub Desktop.
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" |
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.
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
Can you please provide some explanation(algorithm) of the C code