Subversion Repositories wimsdev

Rev

Rev 3812 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2143 bpr 1
/*  Le compte est bon - version récursive
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
 
24
struct result {
25
        unsigned int val; /* value */
26
        operation op; /* operator */
27
        struct result * l; /* left operand */
28
        struct result * r; /* right operand */
29
};
30
 
31
const operation ops[4] = { ADD, MULT, SUB, DIV };
32
const char dispops[4] = { '+', '*', '-', '/' };
33
 
34
/* initializes a result struct */
35
struct result * resinit()
36
{
37
        struct result * p;
38
        p = (struct result *)malloc(sizeof(struct result));
39
        p->l = NULL;
40
        p->r = NULL;
41
        p->op = EMPTY;
42
        return p;
43
}
44
 
45
/* display the result in a readable form. called recursively. */
46
void dispres(struct result * p)
47
{
48
        if (p->op!=EMPTY)
49
        {
50
                dispres(p->l);
51
                dispres(p->r);
52
                printf("%u %c %u = %u\n", p->l->val, dispops[p->op],p->r->val, p->val);
53
        }
54
}
55
 
56
/* calculate the result with those 2 operands and the operator provided */
57
/* /!\ MUST HAVE p->val >= q->val */
58
struct result * add(struct result * p, struct result * q, int op)
59
{
60
        unsigned int res = 0;
61
        struct result *r;
62
        switch(ops[op])
63
        {
64
                case ADD:
65
                        if (!(p->val&&q->val)) return NULL;
66
                        res = p->val + q->val;
67
                        break;
68
                case MULT:
69
                        if ((p->val==1)||(q->val==1)) return NULL;
70
                        res = p->val * q->val;
71
                        break;
72
                case SUB:
73
                        if (!(p->val&&q->val)) return NULL;
74
                        res = p->val - q->val;
75
                        break;
76
                case DIV:
77
                        if (!q->val) return NULL;
78
                        if (q->val==1) return NULL;
79
                        if (!(p->val%q->val))
80
                                res = p->val / q->val;
81
                        else
82
                                return NULL;
83
                        break;
84
                case EMPTY:
85
                        return NULL; /* prevents a compiler warning */
86
        }
87
        r = resinit();
88
        r->op = ops[op];
89
        r->l = p;
90
        r->r = q;
91
        r->val = res;
92
        return r;
93
}
94
 
95
struct result * best = NULL;
96
int min = 10000;
97
int goal;
98
 
99
/* tests if result is better */
100
void resultest(struct result * res)
101
{
102
        int tmp;
103
        if ((tmp = abs(res->val - goal)) < min)
104
        {
105
                min = tmp;
106
                best = res;
107
                if (!min)
108
                {
109
                        printf("FOUND\n");
110
                        dispres(best);
111
                        exit(0);
112
                }
113
        }
114
}
115
 
116
/* recursively try to find an appropriate result */
117
void compute (struct result ** base, int nb)
118
{
119
        struct result * new[6];
120
        struct result * backup1, * backup2;
121
        int i, j, k;
122
 
123
        /* generate a brand new array ! */
124
        memcpy(new, base, sizeof(struct result *) * 6);
125
        if (nb > 1)
126
        {
127
                for (i = 0; i < nb - 1; i++)
128
                {
129
                        for (j = i + 1; j < nb; j++)
130
                        {
131
                                /* now try to replace the 2 values with a combined one */
132
                                backup1 = new[i];
133
                                backup2 = new[j];
134
                                for (k = 0; k < 4; k++) /* for each operator */
135
                                {
136
                                        if ((backup1->val > backup2->val) ? (new[i] = add(backup1, backup2, k)) != NULL : (new[i] = add(backup2, backup1, k)) != NULL)
137
                                        {
138
                                                resultest(new[i]);
139
                                                new[j] = new[nb - 1];
140
                                                compute(new, nb - 1);
141
                                                new[j] = backup2;
142
                                        }
143
                                        new[i] = backup1;
144
                                }
145
                        }
146
                }
147
        }
148
}
149
 
150
/* main routine */
151
int main(int argc, char * argv[])
152
{
153
        struct result * base[6];
154
        int i;
155
 
156
        if (argc!=8)
157
        {
158
                printf("There should be 7 arguments. goal, following by the 6 numbers"
159
                                "to use\n");
160
                exit(-1);
161
        }
162
        /* we read the goal */
163
        goal = atoi(argv[1]);
164
        /* we read the 6 base numbers */
165
        for (i = 0; i < 6; i++)
166
        {
167
                base[i] = resinit();
168
                base[i]->val = atoi(argv[i+2]);
169
        }
170
 
171
        printf("Processing ");
172
        for (i = 0; i < 6; i++)
173
                printf("%d ", base[i]->val);
174
        printf(". Goal : %d\n", goal);
175
 
176
        for (i = 0; i < 6; i++)
177
                resultest(base[i]);
178
 
179
        compute(base, 6);
180
 
181
        printf("NOTFOUND %d %d\n", best->val, min);
182
        dispres(best);
183
        exit(0);
184
}