money.c
2.27 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "fdc_int.h"
#define LETTERS 26
#define MAX_SIZE (10 * LETTERS) // whatever
int main(int argc, char *argv[])
{
char *equation = "send+more=money";
fd_int letters[LETTERS], used[LETTERS];
fd_int eqvars[MAX_SIZE];
int eqcoefs[MAX_SIZE];
fd_int zero;
int n; // different letters used
int l; // number of letters in the equation
int p;
char c, *s;
int solutions = 0, one_solution = 1;
int i, j;
fd_init(&argc, &argv);
for (i = 1; i < argc; ++i)
if (!strcmp(argv[i], "--all"))
one_solution = 0;
else
{
equation = argv[i];
break;
}
zero = fd_new(0, 0);
memset(letters, 0, sizeof(letters));
n = 0; l = 0;
// first summand
for (i = 0; (c = equation[i]) != '+'; ++i)
{
if (letters[c - 'a'] == 0)
used[n++] = letters[c - 'a'] = fd_new(0, 9);
eqvars[l++] = letters[c - 'a'];
if (i == 0)
fd_gt(letters[c - 'a'], zero);
}
for (j = l - 1, p = 1; j >= 0; --j, p *= 10)
eqcoefs[j] = p;
// second summand
s = equation + i + 1;
for (i = 0; (c = s[i]) != '='; ++i)
{
if (letters[c - 'a'] == 0)
used[n++] = letters[c - 'a'] = fd_new(0, 9);
eqvars[l++] = letters[c - 'a'];
if (i == 0)
fd_gt(letters[c - 'a'], zero);
}
s += i + 1;
for (j = 0, p = 1; j < i; ++j, p *= 10)
eqcoefs[l - 1 - j] = p;
// sum
for (i = 0; (c = s[i]) != '\0'; ++i)
{
if (letters[c - 'a'] == 0)
used[n++] = letters[c - 'a'] = fd_new(0, 9);
eqvars[l++] = letters[c - 'a'];
if (i == 0)
fd_gt(letters[c - 'a'], zero);
}
for (j = 0, p = -1; j < i; ++j, p *= 10)
eqcoefs[l - 1 - j] = p;
// constraints
fd_all_different(used, n);
fd_poly_eq(eqcoefs, eqvars, l, zero);
while (fd_solve() == FD_OK)
{
printf("solution %d:\n", ++solutions);
printf("\t%s\n", equation);
putchar('\t');
for (s = equation; *s; ++s)
if (islower(*s))
printf("%d", fd_var_value(letters[*s - 'a']));
else
putchar(*s);
putchar('\n');
#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
if (one_solution)
#endif
break;
}
if (solutions)
printf("%d solutions found\n", solutions);
else
printf("inconsistent CSP\n");
fd_end();
return !solutions;
}