Subversion Repositories wimsdev

Rev

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