Subversion Repositories wimsdev

Rev

Rev 8837 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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 char dispops[4] = { '+', '*', '-', '/' };
  37.  
  38. /* initializes a result struct */
  39. struct result * resinit()
  40. {
  41.         struct result * p;
  42.         p = (struct result *)malloc(sizeof(struct result));
  43.         p->l = NULL;
  44.         p->r = NULL;
  45.         p->next = NULL;
  46.         p->op = EMPTY;
  47.         p->used = 0;
  48.         return p;
  49. }
  50.  
  51. /* display the result in a readable form. called recursively. */
  52. void dispres(struct result * p)
  53. {
  54.         if (p->op!=EMPTY)
  55.         {
  56.                 dispres(p->l);
  57.                 dispres(p->r);
  58.                 printf("%u %c %u = %u\n", p->l->val, dispops[p->op],p->r->val, p->val);
  59.         }
  60. }
  61.  
  62. /* test if 2 operands are compatible */
  63. boolean compatible (struct result *p, struct result *q, unsigned short *used)
  64. {
  65.         if (p->used&q->used) return FALSE;
  66.         *used = p->used|q->used;
  67.         return TRUE;
  68. }
  69.  
  70. /* operators */
  71. unsigned int op_add(unsigned int a, unsigned int b)
  72. {
  73.         if (!(a&&b)) return -1;
  74.         return a + b;
  75. }
  76.  
  77. unsigned int op_mult(unsigned int a, unsigned int b)
  78. {
  79.         if ((a==1)||(b==1)) return -1;
  80.         return a * b;
  81. }
  82.  
  83. unsigned int op_sub(unsigned int a, unsigned int b)
  84. {
  85.         if (!(a&&b)) return -1;
  86.         return a - b;
  87. }
  88.  
  89. unsigned int op_div(unsigned int a, unsigned int b)
  90. {
  91.                         if ((!b)||(b==1)||(a%b)) return -1;
  92.                         return a / b;
  93. }
  94.  
  95. unsigned int (*ops_func[4]) (unsigned int, unsigned int) = { op_add, op_mult, op_sub, op_div };
  96. const operation ops[4] = { ADD, MULT, SUB, DIV };
  97.  
  98. /* calculate the result with those 2 operands and the operator provided */
  99. /* /!\ MUST HAVE p->val >= q->val */
  100. struct result * add(struct result * p, struct result * q, int op)
  101. {
  102.         unsigned int res = 0;
  103.         struct result *r;
  104.         if ((res = ops_func[op](p->val, q->val)) == -1)
  105.                 return NULL;
  106.         r = resinit();
  107.         r->op = ops[op];
  108.         r->l = p;
  109.         r->r = q;
  110.         r->val = res;
  111.         return r;
  112. }
  113.  
  114. struct result * best = NULL;
  115. int min = 10000;
  116. int goal;
  117.  
  118. /* tests if result is better */
  119. void resultest(struct result * res)
  120. {
  121.         if (res->val==goal)
  122.         {
  123.                 printf("FOUND\n");
  124.                 dispres(res);
  125.                 exit(0);
  126.         }
  127. }
  128.  
  129. /* add all possible results using the p & q operands to the s list */
  130. void addresults(struct result ***s, struct result *p, struct result *q)
  131. {
  132.         unsigned short used;
  133.         int i;
  134.         struct result * r;
  135.         /* switch if needed */
  136.         if (p->val < q->val)
  137.         {
  138.                 struct result *tmp;
  139.                 tmp = p;
  140.                 p = q;
  141.                 q = tmp;
  142.         }
  143.         if (compatible(p,q,&used))
  144.                 for (i=0; i<4; i++) /* for each operator */
  145.                         if ((r = add(p,q,i)))
  146.                         {
  147.                                 r->used = used;
  148.                                 **s = r;
  149.                                 *s = &(r->next);
  150.                                 resultest(r);
  151.                         }
  152. }
  153.  
  154. /* main routine */
  155. int main(int argc, char * argv[])
  156. {
  157.         struct result * results[6];
  158.         struct result *p, **s, *q = NULL;
  159.         int i;
  160.         int argp = 1;
  161.         if (argc!=8)
  162.         {
  163.                 printf("There should be 7 arguments. goal, following by the 6 numbers"
  164.                                 "to use\n");
  165.                 exit(-1);
  166.         }
  167.         /* we read the goal */
  168.         goal = atoi(argv[argp++]);
  169.         /* we read the 6 base numbers */
  170.         results[0] = resinit();
  171.         p = results[0];
  172.         q = results[0];
  173.         p->val = atoi(argv[argp++]);
  174.         p->used = 1;
  175.         for (i = 1; i < 6; i++)
  176.         {
  177.                 p = resinit();
  178.                 p->val = atoi(argv[argp++]);
  179.                 p->used = 1 << i;
  180.                 q->next = p;
  181.                 q = p;
  182.         }
  183.  
  184.         printf("Processing ");
  185.         for (p = results[0]; p; p=p->next)
  186.                 printf("%d ", p->val);
  187.         printf(". Goal : %d\n", goal);
  188.  
  189.         /* 0) results composed by 1 base number
  190.          * = res[0] */
  191.         for (p = results[0]; p->next; p=p->next)
  192.                 resultest(p);
  193.  
  194.         /* 1) results composed by 2 base numbers
  195.          * = res[0] X res[0] */
  196.         s = &(results[1]);
  197.         for (p = results[0]; p->next; p=p->next)
  198.                 for (q = p->next; q; q=q->next)
  199.                         addresults(&s, p, q);
  200.  
  201.         /* 2) results composed by 3 base numbers
  202.          * = res[1] X res[0] */
  203.         s = &(results[2]);
  204.         for (p = results[1]; p; p=p->next)
  205.                 for (q = results[0]; q; q=q->next)
  206.                         addresults(&s, p, q);
  207.  
  208.         /* 3) results composed by 4 base numbers
  209.          * = res[1] X res[1] + res[2] X res[0] */
  210.         s = &(results[3]);
  211.         for (p = results[1]; p->next; p=p->next)
  212.                 for (q = p->next; q; q=q->next)
  213.                         addresults(&s, p, q);
  214.  
  215.         for (p = results[2]; p; p=p->next)
  216.                 for (q = results[0]; q; q=q->next)
  217.                         addresults(&s, p, q);
  218.  
  219.         /* 4) results composed by 5 base numbers
  220.          * = res[2] X res[1] + res[3] X res[0] */
  221.         s = &(results[4]);
  222.         for (p = results[3]; p; p=p->next)
  223.                 for (q = results[0]; q; q=q->next)
  224.                         addresults(&s, p, q);
  225.  
  226.         for (p = results[2]; p; p=p->next)
  227.                 for (q = results[1]; q; q=q->next)
  228.                         addresults(&s, p, q);
  229.  
  230.         /* 5) results composed by 6 base numbers
  231.          * = res[2] X res[2] + res[3] X res[1] + res[4] X res[0] */
  232.         s = &(results[5]);
  233.         for (p = results[2]; p->next; p=p->next)
  234.                 for (q = p->next; q; q=q->next)
  235.                         addresults(&s, p, q);
  236.  
  237.         for (p = results[3]; p; p=p->next)
  238.                 for (q = results[1]; q; q=q->next)
  239.                         addresults(&s, p, q);
  240.  
  241.         for (p = results[4]; p; p=p->next)
  242.                 for (q = results[0]; q; q=q->next)
  243.                         addresults(&s, p, q);
  244.  
  245.         /* results analysis */
  246.         /* here, find best result */
  247.         for (i=0; i<6; i++)
  248.         {
  249.                 p = results[i];
  250.                 while (p)
  251.                 {
  252.                         if (abs((int)p->val-goal)<min)
  253.                         {
  254.                                 best = p;
  255.                                 min = p->val-goal;
  256.                         }
  257.                         p = p->next;
  258.                 }
  259.         }
  260.         printf("NOTFOUND %d %d\n", best->val, min);
  261.         dispres(best);
  262.         exit(0);
  263. }
  264.