Return to Answer

Converted the digit grouping.

Source Link

edited Apr 28, 2014 at 19:33

Joe Z.

35.5k
14
66
166

C - 2 480 714,480,714 steps

Still not optimal, but it is now faster and scores better.

deleted 1 character in body

Source Link

edited Apr 28, 2014 at 13:28

SteelTermite

C - 2 481 229480 714 steps

#include <stdio.h> #include <string.h> #include <stdbool.h> char map[19][19], reach[19][19]; int reachsum[6], totalsum[6]; bool loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0; while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break; memcpy(map[row++], buf, 19); } return row == 19; } void calcreach(bool first, size_t row, size_t col); void check(char c, bool first, size_t row, size_t col) { if (map[row][col] == c) calcreach(first, row, col); else if (first) calcreach(false, row, col); } void calcreach(bool first, size_t row, size_t col) { char c = map[row][col]; reach[row][col] = c; reachsum[c - '1']++; if (row < 18 && !reach[row + 1][col]) check(c, first, row + 1, col); if (col < 18 && !reach[row][col + 1]) check(c, first, row, col + 1); if (row > 0 && !reach[row - 1][col]) check(c, first, row - 1, col); if (col > 0 && !reach[row][col - 1]) check(c, first, row, col - 1); } void calctotal() { size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) totalsum[map[row][col] - '1']++; } void apply(char c) { char d = map[9][9]; size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) if (reach[row][col] == d) map[row][col] = c; } int main() { char c, best; size_t steps = 0; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp)) { do { memset(reach, 0, sizeof reach); memset(reachsum, 0, sizeof reachsum); calcreach(true, 9, 9); if (reachsum[map[9][9] - '1'] == 361) break; memset(totalsum, 0, sizeof totalsum); calctotal(); reachsum[map[9][9] - '1'] = 0; for (best = 0, c = 0; c < 6; c++) { if (!reachsum[c]) continue; if (reachsum[c] == totalsum[c]) { best = c; break; } else if (reachsum[c] >=> reachsum[best]) { best = c; } } apply(best + '1'); } while (++steps); } fclose(fp); printf("steps: %zu\n", steps); return 0; }

C - 2 481 229 steps

#include <stdio.h> #include <string.h> #include <stdbool.h> char map[19][19], reach[19][19]; int reachsum[6], totalsum[6]; bool loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0; while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break; memcpy(map[row++], buf, 19); } return row == 19; } void calcreach(bool first, size_t row, size_t col); void check(char c, bool first, size_t row, size_t col) { if (map[row][col] == c) calcreach(first, row, col); else if (first) calcreach(false, row, col); } void calcreach(bool first, size_t row, size_t col) { char c = map[row][col]; reach[row][col] = c; reachsum[c - '1']++; if (row < 18 && !reach[row + 1][col]) check(c, first, row + 1, col); if (col < 18 && !reach[row][col + 1]) check(c, first, row, col + 1); if (row > 0 && !reach[row - 1][col]) check(c, first, row - 1, col); if (col > 0 && !reach[row][col - 1]) check(c, first, row, col - 1); } void calctotal() { size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) totalsum[map[row][col] - '1']++; } void apply(char c) { char d = map[9][9]; size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) if (reach[row][col] == d) map[row][col] = c; } int main() { char c, best; size_t steps = 0; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp)) { do { memset(reach, 0, sizeof reach); memset(reachsum, 0, sizeof reachsum); calcreach(true, 9, 9); if (reachsum[map[9][9] - '1'] == 361) break; memset(totalsum, 0, sizeof totalsum); calctotal(); reachsum[map[9][9] - '1'] = 0; for (best = 0, c = 0; c < 6; c++) { if (!reachsum[c]) continue; if (reachsum[c] == totalsum[c]) { best = c; break; } else if (reachsum[c] >= reachsum[best]) { best = c; } } apply(best + '1'); } while (++steps); } fclose(fp); printf("steps: %zu\n", steps); return 0; }

C - 2 480 714 steps

#include <stdio.h> #include <string.h> #include <stdbool.h> char map[19][19], reach[19][19]; int reachsum[6], totalsum[6]; bool loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0; while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break; memcpy(map[row++], buf, 19); } return row == 19; } void calcreach(bool first, size_t row, size_t col); void check(char c, bool first, size_t row, size_t col) { if (map[row][col] == c) calcreach(first, row, col); else if (first) calcreach(false, row, col); } void calcreach(bool first, size_t row, size_t col) { char c = map[row][col]; reach[row][col] = c; reachsum[c - '1']++; if (row < 18 && !reach[row + 1][col]) check(c, first, row + 1, col); if (col < 18 && !reach[row][col + 1]) check(c, first, row, col + 1); if (row > 0 && !reach[row - 1][col]) check(c, first, row - 1, col); if (col > 0 && !reach[row][col - 1]) check(c, first, row, col - 1); } void calctotal() { size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) totalsum[map[row][col] - '1']++; } void apply(char c) { char d = map[9][9]; size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) if (reach[row][col] == d) map[row][col] = c; } int main() { char c, best; size_t steps = 0; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp)) { do { memset(reach, 0, sizeof reach); memset(reachsum, 0, sizeof reachsum); calcreach(true, 9, 9); if (reachsum[map[9][9] - '1'] == 361) break; memset(totalsum, 0, sizeof totalsum); calctotal(); reachsum[map[9][9] - '1'] = 0; for (best = 0, c = 0; c < 6; c++) { if (!reachsum[c]) continue; if (reachsum[c] == totalsum[c]) { best = c; break; } else if (reachsum[c] > reachsum[best]) { best = c; } } apply(best + '1'); } while (++steps); } fclose(fp); printf("steps: %zu\n", steps); return 0; }

Improved algorithm

Source Link

edited Apr 28, 2014 at 12:52

SteelTermite

C - 2 601 982481 229 steps

Probably a poor implementation of a suboptimal algorithmStill not optimal

is now faster and

marginally

than BurntPizza's(_biatch_)

#include <stdio.h> #include <string.h>   unsigned#include <stdbool.h> char map[19][19]; map[19][19], reach[19][19]; int reachsum[6], totalsum[6]; bool loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0, col;0;  /* assume exactly one trailing newline */  while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break;   for memcpy(colmap[row++], =buf, 0;19);  col < }  return row == 19; } void col++calcreach(bool first, size_t row, size_t col); void check(char c, bool first, size_t row, size_t col) {  if (map[row][col] === buf[col]c)  - '1';  calcreach(first, row, row++;col); } else if (first)  return row == 19 ? 0 :calcreach(false, -1;row, col); } intvoid calcreach(unsigned charbool reach[19][19]first, size_t row, size_t col) { intchar retc = 0;map[row][col];     size_t creach[row][col] = map[row][col]; c; reach[row][col]reachsum[c =- 1;'1']++; if (row < 18 && map[row + 1][col] == c && !reach[row + 1][col])   ret += calcreachcheck(reachc, first, row + 1, col) + 1;; if (col < 18 && map[row][col + 1] == c && !reach[row][col + 1]) ret += calcreachcheck(reachc, first, row, col + 1) + 1;; if (row > 0 && map[row - 1][col] == c && !reach[row - 1][col])   ret += calcreachcheck(reachc, first, row - 1, col) + 1;; if (col > 0 && map[row][col!reach[row][col - 1])  ==  check(c, &&first, !reach[row][colrow, col - 1]1); } void calctotal() { size_t row, col;  ret +=for calcreach(reach,row = 0; row, col< -19; 1row++)   + 1; for (col = 0; col < 19; col++) return ret; totalsum[map[row][col] - '1']++; } void apply(unsignedchar c) { char reach[19][19],d = map[9][9];  size_t c)row, col; { for (size_t row = 0; row < 19; row++) for (size_t col = 0; col < 19; col++) if (reach[row][col] == d) map[row][col] = c; }  int main() { unsigned char curreach[19][19]c, newreach[19][19];best; intsize_t steps = 0, reachsum[6], *best = reachsum;0; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp) != -1) { do { memset(curreachreach, 0, sizeof curreachreach);  memset(reachsum, 0, sizeof reachsum); calcreach(curreachtrue, 9, 9); if (reachsum[map[9][9] - '1'] == 361) break; memset(totalsum, 0, sizeof totalsum);  calctotal(); reachsum[map[9][9] - '1'] = 0; for (size_tbest = 0, c = 0; c < 6; c++) { apply(curreach,if c(!reachsum[c]); memset(newreach, 0, sizeof newreach); continue;   if (reachsum[c] == totalsum[c]) {  best = 1c;  + calcreach(newreach, 9, 9); break; } else if (reachsum[c] >= *bestreachsum[best]) { best = &reachsum[c];c; }  }  apply(curreach, best - reachsum); } steps++;apply(best + '1'); } while (*best < 19 * 19++steps); } fclose(fp); printf("steps: %i\n"%zu\n", steps); return 0; }

C - 2 601 982 steps

Probably a poor implementation of a suboptimal algorithm

marginally

than BurntPizza's(_biatch_)

#include <stdio.h> #include <string.h>   unsigned char map[19][19];  int loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0, col;  /* assume exactly one trailing newline */  while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break;   for (col = 0; col < 19; col++) map[row][col] = buf[col] - '1';  row++; }  return row == 19 ? 0 : -1; } int calcreach(unsigned char reach[19][19], size_t row, size_t col) { int ret = 0;   size_t c = map[row][col];  reach[row][col] = 1; if (row < 18 && map[row + 1][col] == c && !reach[row + 1][col])   ret += calcreach(reach, row + 1, col) + 1; if (col < 18 && map[row][col + 1] == c && !reach[row][col + 1]) ret += calcreach(reach, row, col + 1) + 1; if (row > 0 && map[row - 1][col] == c && !reach[row - 1][col])   ret += calcreach(reach, row - 1, col) + 1; if (col > 0 && map[row][col - 1] == c && !reach[row][col - 1]) ret += calcreach(reach, row, col - 1) + 1; return ret; } void apply(unsigned char reach[19][19], size_t c) { for (size_t row = 0; row < 19; row++) for (size_t col = 0; col < 19; col++) if (reach[row][col]) map[row][col] = c; }  int main() { unsigned char curreach[19][19], newreach[19][19]; int steps = 0, reachsum[6], *best = reachsum; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp) != -1) { do { memset(curreach, 0, sizeof curreach); calcreach(curreach, 9, 9); for (size_t c = 0; c < 6; c++) { apply(curreach, c); memset(newreach, 0, sizeof newreach); reachsum[c] = 1 + calcreach(newreach, 9, 9); if (reachsum[c] >= *best) best = &reachsum[c]; }  apply(curreach, best - reachsum); steps++; } while (*best < 19 * 19); } fclose(fp); printf("steps: %i\n", steps); return 0; }

C - 2 481 229 steps

Still not optimal

is now faster and

#include <stdio.h> #include <string.h> #include <stdbool.h> char map[19][19], reach[19][19]; int reachsum[6], totalsum[6]; bool loadmap(FILE *fp) { char buf[19 + 2]; size_t row = 0; while (fgets(buf, sizeof buf, fp) && row < 19) { if (strlen(buf) != 20) break; memcpy(map[row++], buf, 19);   }  return row == 19; } void calcreach(bool first, size_t row, size_t col); void check(char c, bool first, size_t row, size_t col) {  if (map[row][col] == c)  calcreach(first, row, col); else if (first)  calcreach(false, row, col); } void calcreach(bool first, size_t row, size_t col) { char c = map[row][col];    reach[row][col] = c; reachsum[c - '1']++; if (row < 18 && !reach[row + 1][col]) check(c, first, row + 1, col); if (col < 18 && !reach[row][col + 1]) check(c, first, row, col + 1); if (row > 0 && !reach[row - 1][col]) check(c, first, row - 1, col); if (col > 0 && !reach[row][col - 1])    check(c, first, row, col - 1); } void calctotal() { size_t row, col;  for (row = 0; row < 19; row++)    for (col = 0; col < 19; col++)  totalsum[map[row][col] - '1']++; } void apply(char c) { char d = map[9][9];  size_t row, col; for (row = 0; row < 19; row++) for (col = 0; col < 19; col++) if (reach[row][col] == d) map[row][col] = c; } int main() { char c, best; size_t steps = 0; FILE *fp; if (!(fp = fopen("floodtest", "r"))) return 1; while (loadmap(fp)) { do { memset(reach, 0, sizeof reach);  memset(reachsum, 0, sizeof reachsum); calcreach(true, 9, 9); if (reachsum[map[9][9] - '1'] == 361) break; memset(totalsum, 0, sizeof totalsum);  calctotal(); reachsum[map[9][9] - '1'] = 0; for (best = 0, c = 0; c < 6; c++) { if (!reachsum[c])  continue;   if (reachsum[c] == totalsum[c]) {  best = c;   break; } else if (reachsum[c] >= reachsum[best]) { best = c; }   } apply(best + '1'); } while (++steps); } fclose(fp); printf("steps: %zu\n", steps); return 0; }