Subversion Repositories wimsdev

Rev

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

  1. /*  Le compte est bon - recherche de la plus grande somme
  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.                         res = p->val + q->val;
  81.                         break;
  82.                 case MULT:
  83.                         res = p->val * q->val;
  84.                         break;
  85.                 case SUB:
  86.                         res = p->val - q->val;
  87.                         break;
  88.                 case DIV:
  89.                         if (!q->val) return NULL;
  90.                         if (!(p->val%q->val))
  91.                                 res = p->val / q->val;
  92.                         else
  93.                                 return NULL;
  94.                         break;
  95.                 case EMPTY:
  96.                         return NULL; /* prevents a compiler warning */
  97.         }
  98.         r = resinit();
  99.         r->op = ops[op];
  100.         r->l = p;
  101.         r->r = q;
  102.         r->val = res;
  103.         return r;
  104. }
  105.  
  106. struct result * best = NULL;
  107. int min = 10000;
  108. int goal;
  109.  
  110. /* add all possible results using the p & q operands to the s list */
  111. void addresults(struct result ***s, struct result *p, struct result *q)
  112. {
  113.         unsigned short used;
  114.         int i;
  115.         struct result * r;
  116.         /* switch if needed */
  117.         if (p->val < q->val)
  118.         {
  119.                 struct result *tmp;
  120.                 tmp = p;
  121.                 p = q;
  122.                 q = tmp;
  123.         }
  124.         if (compatible(p,q,&used))
  125.                 for (i=0; i<4; i++) /* for each operator */
  126.                         if ((r = add(p,q,i)))
  127.                         {
  128.                                 r->used = used;
  129.                                 **s = r;
  130.                                 *s = &(r->next);
  131.                         }
  132. }
  133.  
  134. unsigned int calc_sum(struct result * r)
  135. {
  136.         if (r)
  137.                 return calc_sum(r->l) + r->val + calc_sum(r->r);
  138.         else
  139.                 return 0;
  140. }
  141.  
  142. /* main routine */
  143. int main(int argc, char * argv[])
  144. {
  145.         struct result * results[6];
  146.         struct result *p, **s, *q = NULL;
  147.         int i;
  148.         int argp = 1;
  149.         unsigned int biggestsum = 0;
  150.         if (argc!=8)
  151.         {
  152.                 printf("There should be 7 arguments. goal, following by the 6 numbers"
  153.                                 "to use\n");
  154.                 exit(-1);
  155.         }
  156.         /* we read the goal */
  157.         goal = atoi(argv[argp++]);
  158.         /* we read the 6 base numbers */
  159.         results[0] = resinit();
  160.         p = results[0];
  161.         q = results[0];
  162.         p->val = atoi(argv[argp++]);
  163.         p->used = 1;
  164.         for (i = 1; i < 6; i++)
  165.         {
  166.                 p = resinit();
  167.                 p->val = atoi(argv[argp++]);
  168.                 p->used = 1 << i;
  169.                 q->next = p;
  170.                 q = p;
  171.         }
  172.  
  173.         printf("Processing ");
  174.         for (p = results[0]; p; p=p->next)
  175.                 printf("%d ", p->val);
  176.         printf(". Goal : %d\n", goal);
  177.  
  178.         /* 1) results composed by 2 base numbers
  179.          * = res[0] X res[0] */
  180.         s = &(results[1]);
  181.         for (p = results[0]; p->next; p=p->next)
  182.                 for (q = p->next; q; q=q->next)
  183.                         addresults(&s, p, q);
  184.  
  185.         /* 2) results composed by 3 base numbers
  186.          * = res[1] X res[0] */
  187.         s = &(results[2]);
  188.         for (p = results[1]; p; p=p->next)
  189.                 for (q = results[0]; q; q=q->next)
  190.                         addresults(&s, p, q);
  191.  
  192.         /* 3) results composed by 4 base numbers
  193.          * = res[1] X res[1] + res[2] X res[0] */
  194.         s = &(results[3]);
  195.         for (p = results[1]; p->next; p=p->next)
  196.                 for (q = p->next; q; q=q->next)
  197.                         addresults(&s, p, q);
  198.  
  199.         for (p = results[2]; p; p=p->next)
  200.                 for (q = results[0]; q; q=q->next)
  201.                         addresults(&s, p, q);
  202.  
  203.         /* 4) results composed by 5 base numbers
  204.          * = res[2] X res[1] + res[3] X res[0] */
  205.         s = &(results[4]);
  206.         for (p = results[3]; p; p=p->next)
  207.                 for (q = results[0]; q; q=q->next)
  208.                         addresults(&s, p, q);
  209.  
  210.         for (p = results[2]; p; p=p->next)
  211.                 for (q = results[1]; q; q=q->next)
  212.                         addresults(&s, p, q);
  213.  
  214.         /* 5) results composed by 6 base numbers
  215.          * = res[2] X res[2] + res[3] X res[1] + res[4] X res[0] */
  216.         s = &(results[5]);
  217.         for (p = results[2]; p->next; p=p->next)
  218.                 for (q = p->next; q; q=q->next)
  219.                         addresults(&s, p, q);
  220.  
  221.         for (p = results[3]; p; p=p->next)
  222.                 for (q = results[1]; q; q=q->next)
  223.                         addresults(&s, p, q);
  224.  
  225.         for (p = results[4]; p; p=p->next)
  226.                 for (q = results[0]; q; q=q->next)
  227.                         addresults(&s, p, q);
  228.  
  229.         /* results analysis */
  230.         /* here, find best result */
  231.         for (i=0; i<6; i++)
  232.         {
  233.                 p = results[i];
  234.                 while (p)
  235.                 {
  236.                         if (abs((int)p->val-goal)<min)
  237.                         {
  238.                                 best = p;
  239.                                 min = p->val-goal;
  240.                         }
  241.                         if (abs((int)p->val)==goal)
  242.                         {
  243.                                 unsigned int tmp = calc_sum(p);
  244.                                 if (tmp > biggestsum)
  245.                                 {
  246.                                         biggestsum = tmp;
  247.                                         best = p;
  248.                                 }
  249.                         }
  250.                         p = p->next;
  251.                 }
  252.         }
  253.         if (min)
  254.                 printf("NOTFOUND %d %d\n", best->val, min);
  255.         else
  256.                 printf("FOUND\n");
  257.         dispres(best);
  258.         exit(0);
  259. }
  260.