Rev 8837 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2143 | bpr | 1 | /* Le compte est bon - version dynamique |
2 | * Copyright (C) 2002 Lucas Nussbaum <lucas@lucas-nussbaum.net> |
||
3 | * |
||
4 | * This program is free software; you can redistribute it and/or modify |
||
5 | * it under the terms of the GNU General Public License as published by |
||
6 | * the Free Software Foundation; either version 2 of the License, or |
||
7 | * (at your option) any later version. |
||
8 | * |
||
9 | * This program is distributed in the hope that it will be useful, |
||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
12 | * GNU General Public License for more details. |
||
13 | * |
||
14 | * You should have received a copy of the GNU General Public License |
||
15 | * along with this program; if not, write to the Free Software |
||
16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
17 | */ |
||
18 | |||
19 | #include <stdlib.h> |
||
20 | #include <stdio.h> |
||
21 | |||
22 | typedef enum {ADD, MULT, SUB, DIV, EMPTY} operation; |
||
23 | typedef int boolean; |
||
24 | #define TRUE 1 |
||
25 | #define FALSE 0 |
||
26 | |||
27 | struct result { |
||
28 | unsigned int val; /* value */ |
||
29 | operation op; /* operator */ |
||
30 | struct result * l; /* left operand */ |
||
31 | struct result * r; /* right operand */ |
||
32 | unsigned short used; /* digits used */ |
||
33 | struct result * next; /* you know what a linked list is, don't you ? */ |
||
34 | }; |
||
35 | |||
36 | const operation ops[4] = { ADD, MULT, SUB, DIV }; |
||
37 | const char dispops[4] = { '+', '*', '-', '/' }; |
||
38 | |||
39 | /* initializes a result struct */ |
||
40 | struct result * resinit() |
||
41 | { |
||
42 | struct result * p; |
||
43 | p = (struct result *)malloc(sizeof(struct result)); |
||
44 | p->l = NULL; |
||
45 | p->r = NULL; |
||
46 | p->next = NULL; |
||
47 | p->op = EMPTY; |
||
48 | p->used = 0; |
||
49 | return p; |
||
50 | } |
||
51 | |||
52 | /* display the result in a readable form. called recursively. */ |
||
53 | void dispres(struct result * p) |
||
54 | { |
||
55 | if (p->op!=EMPTY) |
||
56 | { |
||
57 | dispres(p->l); |
||
58 | dispres(p->r); |
||
59 | printf("%u %c %u = %u\n", p->l->val, dispops[p->op],p->r->val, p->val); |
||
60 | } |
||
61 | } |
||
62 | |||
63 | /* test if 2 operands are compatible */ |
||
64 | boolean compatible (struct result *p, struct result *q, unsigned short *used) |
||
65 | { |
||
66 | if (p->used&q->used) return FALSE; |
||
67 | *used = p->used|q->used; |
||
68 | return TRUE; |
||
69 | } |
||
70 | |||
71 | /* calculate the result with those 2 operands and the operator provided */ |
||
72 | /* /!\ MUST HAVE p->val >= q->val */ |
||
73 | struct result * add(struct result * p, struct result * q, int op) |
||
74 | { |
||
75 | int res = 0; |
||
76 | struct result *r; |
||
77 | switch(ops[op]) |
||
78 | { |
||
79 | case ADD: |
||
80 | if (!(p->val&&q->val)) return NULL; |
||
81 | res = p->val + q->val; |
||
82 | break; |
||
83 | case MULT: |
||
84 | if ((p->val==1)||(q->val==1)) return NULL; |
||
85 | res = p->val * q->val; |
||
86 | break; |
||
87 | case SUB: |
||
88 | if (!(p->val&&q->val)) return NULL; |
||
89 | res = p->val - q->val; |
||
90 | break; |
||
91 | case DIV: |
||
92 | if (!q->val) return NULL; |
||
93 | if (q->val==1) return NULL; |
||
94 | if (!(p->val%q->val)) |
||
95 | res = p->val / q->val; |
||
96 | else |
||
97 | return NULL; |
||
98 | break; |
||
99 | case EMPTY: |
||
100 | return NULL; /* prevents a compiler warning */ |
||
101 | } |
||
102 | r = resinit(); |
||
103 | r->op = ops[op]; |
||
104 | r->l = p; |
||
105 | r->r = q; |
||
106 | r->val = res; |
||
107 | return r; |
||
108 | } |
||
109 | |||
110 | struct result * best = NULL; |
||
111 | int min = 10000; |
||
112 | int goal; |
||
113 | |||
114 | /* tests if result is better */ |
||
115 | void resultest(struct result * res) |
||
116 | { |
||
117 | if (res->val==goal) |
||
118 | { |
||
119 | printf("FOUND\n"); |
||
120 | dispres(res); |
||
121 | exit(0); |
||
122 | } |
||
123 | } |
||
124 | |||
125 | /* add all possible results using the p & q operands to the s list */ |
||
126 | void addresults(struct result ***s, struct result *p, struct result *q) |
||
127 | { |
||
128 | unsigned short used; |
||
129 | int i; |
||
130 | struct result * r; |
||
131 | /* switch if needed */ |
||
132 | if (p->val < q->val) |
||
133 | { |
||
134 | struct result *tmp; |
||
135 | tmp = p; |
||
136 | p = q; |
||
137 | q = tmp; |
||
138 | } |
||
139 | if (compatible(p,q,&used)) |
||
140 | for (i=0; i<4; i++) /* for each operator */ |
||
141 | if ((r = add(p,q,i))) |
||
142 | { |
||
143 | r->used = used; |
||
144 | **s = r; |
||
145 | *s = &(r->next); |
||
146 | resultest(r); |
||
147 | } |
||
148 | } |
||
149 | |||
150 | /* main routine */ |
||
151 | int main(int argc, char * argv[]) |
||
152 | { |
||
153 | struct result * results[6]; |
||
154 | struct result *p, **s, *q = NULL; |
||
155 | int i; |
||
156 | int argp = 1; |
||
157 | if (argc!=8) |
||
158 | { |
||
159 | printf("There should be 7 arguments. goal, following by the 6 numbers" |
||
160 | "to use\n"); |
||
161 | exit(-1); |
||
162 | } |
||
163 | /* we read the goal */ |
||
164 | goal = atoi(argv[argp++]); |
||
165 | /* we read the 6 base numbers */ |
||
166 | results[0] = resinit(); |
||
167 | p = results[0]; |
||
168 | q = results[0]; |
||
169 | p->val = atoi(argv[argp++]); |
||
170 | p->used = 1; |
||
171 | for (i = 1; i < 6; i++) |
||
172 | { |
||
173 | p = resinit(); |
||
174 | p->val = atoi(argv[argp++]); |
||
175 | p->used = 1 << i; |
||
176 | q->next = p; |
||
177 | q = p; |
||
178 | } |
||
8837 | bpr | 179 | |
2143 | bpr | 180 | printf("Processing "); |
181 | for (p = results[0]; p; p=p->next) |
||
182 | printf("%d ", p->val); |
||
183 | printf(". Goal : %d\n", goal); |
||
8837 | bpr | 184 | |
2143 | bpr | 185 | /* 0) results composed by 1 base number |
186 | * = res[0] */ |
||
187 | for (p = results[0]; p->next; p=p->next) |
||
188 | resultest(p); |
||
189 | |||
190 | /* 1) results composed by 2 base numbers |
||
191 | * = res[0] X res[0] */ |
||
192 | s = &(results[1]); |
||
193 | for (p = results[0]; p->next; p=p->next) |
||
194 | for (q = p->next; q; q=q->next) |
||
195 | addresults(&s, p, q); |
||
196 | |||
197 | /* 2) results composed by 3 base numbers |
||
198 | * = res[1] X res[0] */ |
||
199 | s = &(results[2]); |
||
200 | for (p = results[1]; p; p=p->next) |
||
201 | for (q = results[0]; q; q=q->next) |
||
202 | addresults(&s, p, q); |
||
203 | |||
204 | /* 3) results composed by 4 base numbers |
||
205 | * = res[1] X res[1] + res[2] X res[0] */ |
||
206 | s = &(results[3]); |
||
207 | for (p = results[1]; p->next; p=p->next) |
||
208 | for (q = p->next; q; q=q->next) |
||
209 | addresults(&s, p, q); |
||
210 | |||
211 | for (p = results[2]; p; p=p->next) |
||
212 | for (q = results[0]; q; q=q->next) |
||
213 | addresults(&s, p, q); |
||
214 | |||
215 | /* 4) results composed by 5 base numbers |
||
216 | * = res[2] X res[1] + res[3] X res[0] */ |
||
217 | s = &(results[4]); |
||
218 | for (p = results[3]; p; p=p->next) |
||
219 | for (q = results[0]; q; q=q->next) |
||
220 | addresults(&s, p, q); |
||
221 | |||
222 | for (p = results[2]; p; p=p->next) |
||
223 | for (q = results[1]; q; q=q->next) |
||
224 | addresults(&s, p, q); |
||
225 | |||
226 | /* 5) results composed by 6 base numbers |
||
227 | * = res[2] X res[2] + res[3] X res[1] + res[4] X res[0] */ |
||
228 | s = &(results[5]); |
||
229 | for (p = results[2]; p->next; p=p->next) |
||
230 | for (q = p->next; q; q=q->next) |
||
231 | addresults(&s, p, q); |
||
232 | |||
233 | for (p = results[3]; p; p=p->next) |
||
234 | for (q = results[1]; q; q=q->next) |
||
235 | addresults(&s, p, q); |
||
236 | |||
237 | for (p = results[4]; p; p=p->next) |
||
238 | for (q = results[0]; q; q=q->next) |
||
239 | addresults(&s, p, q); |
||
240 | |||
241 | /* results analysis */ |
||
242 | /* here, find best result */ |
||
243 | for (i=0; i<6; i++) |
||
244 | { |
||
245 | p = results[i]; |
||
246 | while (p) |
||
247 | { |
||
8860 | bpr | 248 | if (abs((int)p->val-goal)<min) |
2143 | bpr | 249 | { |
250 | best = p; |
||
8837 | bpr | 251 | min = p->val-goal; |
2143 | bpr | 252 | } |
253 | p = p->next; |
||
254 | } |
||
255 | } |
||
256 | printf("NOTFOUND %d %d\n", best->val, min); |
||
257 | dispres(best); |
||
258 | exit(0); |
||
259 | } |