Subversion Repositories wimsdev

Rev

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
}