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 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.         }
  179.  
  180.         printf("Processing ");
  181.         for (p = results[0]; p; p=p->next)
  182.                 printf("%d ", p->val);
  183.         printf(". Goal : %d\n", goal);
  184.  
  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.                 {
  248.                         if (abs((int)p->val-goal)<min)
  249.                         {
  250.                                 best = p;
  251.                                 min = p->val-goal;
  252.                         }
  253.                         p = p->next;
  254.                 }
  255.         }
  256.         printf("NOTFOUND %d %d\n", best->val, min);
  257.         dispres(best);
  258.         exit(0);
  259. }
  260.