Advertisement
Guest User

Cryptic Clue Maze Finder

a guest
Jul 25th, 2016
154
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <ctype.h>
  6.  
  7. #define die(...) exit((printf(__VA_ARGS__), puts(""), 1))
  8.  
  9. #define H 48
  10. #define W 40
  11. #define N 18
  12.  
  13. char maze[H][W] = {
  14.     "#################",
  15.     "##########   ####",
  16.     "##########   ####",
  17.     "##########   ########",
  18.     "##########   ########",
  19.     "##########   ########",
  20.     "##########   ############",
  21.     "##########   ###  #######",
  22.     "##########   ###  #######",
  23.     "#####  ###   ###  ###########",
  24.     "#####  ###   ###  ###########",
  25.     "#####  ###   ###  ###########",
  26.     "#####             ###########",
  27.     "#####             ###########",
  28.     "  E                ##########",
  29.     "                    #########",
  30.     "                     ################",
  31.     "                            #########",
  32.     "                            #########",
  33.     "                            #########",
  34.     "                            #########",
  35.     "                          ###########",
  36.     "                          ###########",
  37.     "                          ###########",
  38.     "                          #####",
  39.     "                              #",
  40.     "                              #",
  41.     "                              #",
  42.     "                              #",
  43.     "                              #",
  44.     "                              #",
  45.     "                              #",
  46.     "                     ##########",
  47.     "                     ##########",
  48.     "                     ##########",
  49.     "                     ##########",
  50.     "                     ##########",
  51.     "                     ##########",
  52.     "                     ##########",
  53.     "                     ############",
  54.     "                     ############",
  55.     "                     ############",
  56.     "                     ############",
  57.     "                     ############S",
  58. };
  59.  
  60. const char *words[N] = {
  61.     "AMENDMENT",
  62.     "BACON",
  63.     "BASKETBALL",
  64.     "BRANDNEW",
  65.     "CARBONARA",
  66.     "DRACONIAN",
  67.     "ENTOURAGE",
  68.     "FORENSICS",
  69.     "GRAY",
  70.     "HARPO",
  71.     "INSTANCE",
  72.     "LACED",
  73.     "LAXSECURITY",
  74.     "LOGAN",
  75.     "RENOVATED",
  76.     "SCARS",
  77.     "SONOROUS",
  78.     "WORKAHOLIC",
  79. };
  80.  
  81. enum {
  82.     Down, Across
  83. };
  84.  
  85. enum {
  86.     Plain, Postscript
  87. };
  88.  
  89. void print(int mode)
  90. {
  91.     if (mode == Plain) {
  92.         for (int j = 0; j < H; j++) {
  93.             for (int i = 0; i < W; i++) {
  94.                 if (isalpha((unsigned char) maze[j][i])) {
  95.                     putchar(maze[j][i]);
  96.                 } else {
  97.                     putchar(maze[j][i] == '#' ? '.' : ' ');
  98.                 }
  99.             }
  100.             putchar('\n');
  101.         }
  102.     } else if (mode == Postscript) {
  103.         puts("%!PS-Adobe 3.0");
  104.         puts("/W 12 def");
  105.         puts("/M { W mul } bind def");
  106.         puts("/S { newpath moveto W 0 rlineto");
  107.         puts("    0 W rlineto W neg 0 rlineto closepath stroke");
  108.         puts("} bind def");
  109.         puts("/L { moveto");
  110.         puts("    dup stringwidth pop -0.5 mul 0 rmoveto show");
  111.         puts("} bind def");
  112.         puts("/Helvetica findfont W 0.9 mul scalefont setfont");
  113.         puts("0.5 setlinewidth");
  114.        
  115.         for (int j = 0; j < H; j++) {
  116.             for (int i = 0; i < W; i++) {
  117.                 int al = isalpha((unsigned char) maze[j][i]);
  118.                
  119.                 if (al || maze[j][i] == '#') {
  120.                     int x = i + 2;
  121.                     int y = H + 2 - j;
  122.                    
  123.                     printf("%d M %d M S\n", x, y);
  124.                     if (al) printf("(%c) %d.5 M %d.15 M L\n", maze[j][i], x, y);
  125.                 }
  126.             }
  127.         }
  128.        
  129.         puts("showpage");
  130.     }
  131. }
  132.  
  133. void put(const char *str, char *p, int y, int x, int dir)
  134. {
  135.     while (*str) {
  136.         if (p) *p++ = maze[y][x];
  137.         maze[y][x] = *str++;
  138.         if (dir == Across) x++; else y++;
  139.     }
  140.    
  141.     if (p) *p = '\0';
  142. }
  143.  
  144. int test(const char *str, int y, int x, int dir)
  145. {
  146.     if (x < 0 || y < 0) return 0;
  147.    
  148.     while (*str) {
  149.         if (y >= H) return 0;
  150.         if (x >= W) return 0;
  151.         if (maze[y][x] != '#' && maze[y][x] != *str) return 0;
  152.         str++;
  153.         if (dir == Across) x++; else y++;
  154.     }
  155.    
  156.     return 1;
  157. }
  158.  
  159. int final(const char *w, int y, int x, int dir)
  160. {    
  161.     int len = strlen(w);
  162.    
  163.     if (dir == Down) y += len; else x += len;
  164.    
  165.     if (y == 15 && x == 2) return 1;
  166.     if (y == 43 && x == 34) return 1;
  167.     return 0;
  168. }
  169.  
  170. void try(int y, int x, int n, int k, int curr, int dir)
  171. {
  172.     const char *ww = words[k];
  173.  
  174.     if (test(ww, y, x, dir)) {
  175.         char save[20];
  176.  
  177.         words[k] = words[--n];
  178.         put(ww, save, y, x, dir);
  179.        
  180.         if (n == 0) {
  181.             if (final(ww, y, x, dir)) {
  182.                 print(Plain);
  183.             }
  184.         } else {
  185.             for (int l = 0; ww[l]; l++) {           // letter in this word
  186.                 if (abs(l - curr) < 2) continue;
  187.  
  188.                 for (int i = 0; i < n; i++) {       // possible next word
  189.                     const char *s = words[i];
  190.  
  191.                     for (int j = 0; s[j]; j++) {    // letter in next word
  192.                         if (ww[l] == s[j]) {                        
  193.                             if (dir == Across) {
  194.                                 try(y - j, x + l, n, i, j, Down);
  195.                             } else {
  196.                                 try(y + l, x - j, n, i, j, Across);
  197.                             }
  198.                         }
  199.                     }
  200.                 }
  201.             }
  202.         }
  203.  
  204.         put(save, NULL, y, x, dir);
  205.         words[k] = ww;
  206.         n++;
  207.    }
  208.  
  209. }
  210.  
  211. void tryword(const char *w, int y, int x, int dir)
  212. {
  213.     for (int i = 0; i < N; i++) {
  214.         if (strcmp(w, words[i]) == 0) {
  215.             int len = strlen(w);
  216.            
  217.             if (dir == Down) {
  218.                 try(y - len, x, N, i, len, dir);
  219.             } else {
  220.                 try(y, x - len, N, i, len, dir);
  221.             }
  222.            
  223.             return;
  224.         }
  225.     }
  226.    
  227.     printf("%s not found", w);
  228. }
  229.  
  230. int main()
  231. {
  232. #if 0
  233.     tryword("INSTANCE", 15, 2, Down);
  234.     tryword("ENTOURAGE", 15, 2, Down);
  235. #else
  236.     tryword("SCARS", 43, 34, Across);
  237.     tryword("SONOROUS", 43, 34, Across);
  238.     tryword("FORENSICS", 43, 34, Across);
  239. #endif
  240.    
  241.     return 0;
  242. }
Advertisement
RAW Paste Data Copied
Advertisement