Subversion Repositories wimsdev

Rev

Rev 3812 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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. }
  185.