Advertisement
aaaaaa123456789

JV programming challenges, week 3, challenge 2

Dec 3rd, 2013
97
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. char * get_line(void);
  6. unsigned get_number(void);
  7. char ** get_lines(unsigned);
  8. char * check_line(char *, unsigned, unsigned);
  9. void free_lines_array(char **, unsigned);
  10. void initialize_grid(int *, unsigned, char **);
  11. int update_grid(int *, unsigned);
  12. int lowest_neighbour(int *, unsigned, unsigned, unsigned);
  13. int minimum(int, int);
  14.  
  15. inline int * cell (int * grid, unsigned row, unsigned col, unsigned size) {
  16.   return grid + (row * size + col);
  17. }
  18.  
  19. int main (void) {
  20.   unsigned size = get_number();
  21.   if (!size) {
  22.     fprintf(stderr, "Invalid size\n");
  23.     return 1;
  24.   }
  25.   char ** lines = get_lines(size);
  26.   unsigned line;
  27.   for (line = 0; line < size; line ++) lines[line] = check_line(lines[line], size, line + 1);
  28.   int * grid = malloc(sizeof(int) * size * size);
  29.   initialize_grid(grid, size, lines);
  30.   free_lines_array(lines, size);
  31.   int result;
  32.   do
  33.     result = update_grid(grid, size);
  34.   while (result == -1);
  35.   free(grid);
  36.   if (result > 0)
  37.     printf("true, %d\n", result);
  38.   else
  39.     printf("false\n");
  40.   return 0;
  41. }
  42.  
  43. char * get_line (void) {
  44.   char * line = NULL;
  45.   unsigned length = 0;
  46.   char newchar;
  47.   for (newchar = getchar(); (newchar != EOF) && (newchar != '\n'); newchar = getchar()) {
  48.     line = realloc(line, ++ length);
  49.     line[length - 1] = newchar;
  50.   }
  51.   line = realloc(line, length + 1);
  52.   line[length] = 0;
  53.   return line;
  54. }
  55.  
  56. unsigned get_number (void) {
  57.   char * line = get_line();
  58.   if (!*line) {
  59.     free(line);
  60.     return 0;
  61.   }
  62.   char * end;
  63.   unsigned number = strtoul(line, &end, 10);
  64.   if (*end) number = 0;
  65.   free(line);
  66.   return number;
  67. }
  68.  
  69. char ** get_lines (unsigned lines) {
  70.   char ** result = malloc(sizeof(char *) * lines);
  71.   unsigned line;
  72.   for (line = 0; line < lines; line ++) result[line] = get_line();
  73.   return result;
  74. }
  75.  
  76. char * check_line (char * line, unsigned size, unsigned line_number) {
  77.   unsigned length = strlen(line);
  78.   unsigned pos;
  79.   if (length > size) {
  80.     fprintf(stderr, "Line %u is %u characters long (expected: %u), truncating\n", line_number, length, size);
  81.     line = realloc(line, size + 1);
  82.     line[size] = 0;
  83.   } else if (length < size) {
  84.     fprintf(stderr, "Line %u is %u characters long (expected: %u), padding with dots\n", line_number, length, size);
  85.     line = realloc(line, size + 1);
  86.     memset(line + length, '.', size - length);
  87.     line[size] = 0;
  88.   }
  89.   for (pos = 0; pos < size; pos ++) {
  90.     if ((line[pos] == '.') || (line[pos] == 'W') || (line[pos] == 'E') || (line[pos] == 'S')) continue;
  91.     fprintf(stderr, "Line %u: spurious character 0x%02x at column %u, inserting dot\n", line_number, (int) (line[pos]), pos + 1);
  92.     line[pos] = '.';
  93.   }
  94.   return line;
  95. }
  96.  
  97. void free_lines_array (char ** lines, unsigned size) {
  98.   unsigned line;
  99.   for (line = 0; line < size; line ++) free(lines[line]);
  100.   free(lines);
  101. }
  102.  
  103. void initialize_grid (int * grid, unsigned size, char ** lines) {
  104.   unsigned row, col;
  105.   for (row = 0; row < size; row ++)
  106.     for (col = 0; col < size; col ++)
  107.       switch(lines[row][col]) {
  108.         case 'E': *cell(grid, row, col, size) = -3; break;
  109.         case 'S': *cell(grid, row, col, size) = 0; break;
  110.         case 'W': *cell(grid, row, col, size) = -2; break;
  111.         default: *cell(grid, row, col, size) = -1;
  112.       }
  113. }
  114.  
  115. int update_grid (int * grid, unsigned size) {
  116.   int * oldgrid = malloc(sizeof(int) * size * size);
  117.   memcpy(oldgrid, grid, sizeof(int) * size * size);
  118.   unsigned row, col;
  119.   int update, updated = -2;
  120.   for (row = 0; row < size; row ++)
  121.     for (col = 0; col < size; col ++)
  122.       switch (*cell(grid, row, col, size)) {
  123.         case -1:
  124.           update = lowest_neighbour(oldgrid, row, col, size);
  125.           if (update >= 0) {
  126.             *cell(grid, row, col, size) = update + 1;
  127.             updated = -1;
  128.           }
  129.           break;
  130.         case -3:
  131.           update = lowest_neighbour(oldgrid, row, col, size);
  132.           if (update >= 0) {
  133.             free(oldgrid);
  134.             return update + 1;
  135.           }
  136.       }
  137.   free(oldgrid);
  138.   return updated;
  139. }
  140.  
  141. int lowest_neighbour (int * grid, unsigned row, unsigned col, unsigned size) {
  142.   int result = -1;
  143.   if (row) result = minimum(result, *cell(grid, row - 1, col, size));
  144.   if (col) result = minimum(result, *cell(grid, row, col - 1, size));
  145.   if ((row + 1) < size) result = minimum(result, *cell(grid, row + 1, col, size));
  146.   if ((col + 1) < size) result = minimum(result, *cell(grid, row, col + 1, size));
  147.   return result;
  148. }
  149.  
  150. int minimum (int n1, int n2) {
  151.   if ((n1 < 0) && (n2 < 0)) return -1;
  152.   if (n1 < 0) return n2;
  153.   if ((n2 < 0) || (n1 < n2)) return n1;
  154.   return n2;
  155. }
Advertisement
RAW Paste Data Copied
Advertisement