SHARE
TWEET

Stage 1 solver

ossifrage Apr 25th, 2015 255 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. /* http://puzzling.stackexchange.com/q/12624/40 */
  4.  
  5. #define BEG 0
  6. #define ADD 1
  7. #define SUB 2
  8. #define MUL 3
  9. #define END 4
  10.  
  11. int ops[16] = { BEG, MUL, SUB, SUB,
  12.                 SUB, ADD, MUL, MUL,
  13.                 SUB, ADD, ADD, SUB,
  14.                 ADD, MUL, ADD, END };
  15. int val[16] = {  5,   3,   4,   3,
  16.                  8,   4,   7,   6,
  17.                  3,   9,   8,   1,
  18.                  5,   2,   1,   0  };
  19. int nhb[16][8] = { { 1, 4, 5,-1,-1,-1,-1,-1 },   /* A */
  20.                    { 0, 2, 4, 5, 6,-1,-1,-1 },   /* B */
  21.                    { 1, 3, 5, 6, 7,-1,-1,-1 },   /* C */
  22.                    { 2, 6, 7,-1,-1,-1,-1,-1 },   /* D */
  23.                    { 0, 1, 5, 8, 9,-1,-1,-1 },   /* E */
  24.                    { 0, 1, 2, 4, 6, 8, 9,10 },   /* F */
  25.                    { 1, 2, 3, 5, 7, 9,10,11 },   /* G */
  26.                    { 2, 3, 6,10,11,-1,-1,-1 },   /* H */
  27.                    { 4, 5, 9,12,13,-1,-1,-1 },   /* I */
  28.                    { 4, 5, 6, 8,10,12,13,14 },   /* J */
  29.                    { 5, 6, 7, 9,11,13,14,15 },   /* K */
  30.                    { 6, 7,10,14,15,-1,-1,-1 },   /* L */
  31.                    { 8, 9,13,-1,-1,-1,-1,-1 },   /* M */
  32.                    { 8, 9,10,12,14,-1,-1,-1 },   /* N */
  33.                    { 9,10,11,13,15,-1,-1,-1 },   /* O */
  34.                    {10,11,14,-1,-1,-1,-1,-1 } }; /* P */
  35. int viz[16] = { 0 };
  36.  
  37. int findpath(int cur_cell, int step_num, int score, int target_score) {
  38.   int i, c;
  39.   viz[cur_cell] = step_num++;
  40.   for (i=0; i<8 && (c=nhb[cur_cell][i])>=0; i++) {
  41.     if (!viz[c]) {
  42.       switch(ops[c]) {
  43.         case END:
  44.           if (score==target_score) {
  45.             viz[c] = step_num;
  46.             return 1;
  47.           }
  48.           else return 0;
  49.         case MUL:
  50.           viz[c] = step_num;
  51.           if (findpath(c,step_num,score * val[c],target_score)) return 1;
  52.           break;
  53.         case SUB:
  54.           viz[c] = step_num;
  55.           if (findpath(c,step_num,score - val[c],target_score)) return 1;
  56.           break;
  57.         case ADD:
  58.           viz[c] = step_num;
  59.           if (findpath(c,step_num,score + val[c],target_score)) return 1;
  60.           break;
  61.         default:
  62.           puts("WTFIGOH?");
  63.       }
  64.       viz[c] = 0;
  65.     }
  66.   }
  67.   return 0;
  68. }
  69.      
  70.  
  71.  
  72. int main() {
  73.   int targets[8] = { 1600, 1800, 1900, 2300, 2400, 3600, 4500, 5000 };
  74.   int t, i;
  75.   for (t=0; t<8; t++) {
  76.     for (i=0; i<16; i++) viz[i] = 0;
  77.     if (findpath(0, 1, 5, targets[t])) {
  78.       printf("%d: L=%d\n",targets[t],viz[15]);
  79.       for (i=0; i<16; i++) {
  80.         printf("%2d ",viz[i]);
  81.         if ((i&3)==3) putchar('\n');
  82.       }
  83.       putchar('\n');
  84.     }
  85.     else printf("%d: No solution",targets[t]);
  86.   }
  87.   return 0;
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top