Rules: no spoilers.
The other rules are made up as we go along.
Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.
Rules: no spoilers.
The other rules are made up as we go along.
Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.
3 a
I read this wrong initially and thought that you only needed to check adjacency on the same line. Whoops! Then I wrote a bad algorithm that finds numbers THEN searches for symbols. That alg isn’t inherently bad, except…
3 b
If I had chosen a symbol first approach, I would not have had as much pain as I did here. Also, I probably under and overthought this one. I went with my first idea, which was guaranteed to work.
The approach this time was:
A simpler approach would consider that you only have two numbers on the same line for the same gear if the character in the gear column is a non-digit; otherwise, if a number is adjacent to a gear, there is only one on that row. Union-find is completely overkill, but I like using it even when I don’t need to.
Anyway, upon reflecting on this, while the general approach is fine, I didn’t think too hard about the implementation and just ended up with globs of overly memoized spaghetti. I probably should check if Dart has a python-like tuple object or similar. Whatever. Behold!
void day3s() { List lines = [ for (String? line = stdin.readLineSync(); line != null; line = stdin.readLineSync()) line ]; List> digs = [for (int i = 0; i < lines.length; i++) Map()]; int? isDigitMem(int r, int c) { return digs[r].putIfAbsent(c, () => isDigit(lines[r][c])); } // first entry is parentc, second is size List>> uf = List.generate( lines.length, (i) => List.generate(lines[0].length, (j) => [j, 1, -1])); int find(int r, int c) { if (uf[r][c][0] != c) { uf[r][c][0] = find(r, uf[r][c][0]); return uf[r][c][0]; } return uf[r][c][0]; } void union(int r, int cp, int c) { cp = find(r, cp); c = find(r, c); if (c == cp) { return; } if (uf[r][cp][1] >= uf[r][c][1]) { uf[r][c][0] = cp; uf[r][cp][1] += uf[r][c][1]; } else { uf[r][cp][0] = c; uf[r][c][1] += uf[r][cp][1]; } } int stoi(int row, int col) { int acc = 0; for (int i = col; i < lines[0].length; i++) { int? d = isDigitMem(row, i); if (d != null) { acc = (acc * 10) + d; union(row, col, i); } else { break; } } return acc; } int? stoiSearch(int row, int col) { assert(row >= 0 && col >= 0 && row < lines.length && col < lines[0].length); if (isDigitMem(row, col) == null) { return null; } int i = col - 1; while (i >= 0) { if (isDigitMem(row, i) == null) { return stoi(row, i + 1); } i--; } return stoi(row, 0); } List> s2i = [for (int i = 0; i < lines.length; i++) Map()]; int? stoiSearchMem(int row, int col) { return s2i[row].putIfAbsent(col, () => stoiSearch(row, col)); } int count = 0; for (int i = 0; i < lines.length; i++) { for (int j = 0; j < lines[0].length; j++) { if (lines[i][j] != "*") { continue; } List gearVals = List.empty(growable: true); for (int x = -1; x <= 1; x++) { if (i + x < 0 || i + x > lines.length) { continue; } Set parents = {}; for (int y = -1; y <= 1; y++) { if (j + y < 0 || j + y > lines[0].length) { continue; } int? cur = stoiSearchMem(i + x, j + y); int parent = find(i + x, j + y); if (parents.contains(parent)) { continue; } parents.add(parent); if (cur != null) { gearVals.add(cur); } } } if (gearVals.length == 2) { count += gearVals[0] * gearVals[1]; } } } print(count); }
3b redux
I took out the union find, the code is simpler and more readable now. I also leaned in to using null values, which is gross but whatever, it works.
void day3s() { List lines = [ for (String? line = stdin.readLineSync(); line != null; line = stdin.readLineSync()) line ]; // lazy processing + memoization List> digs = [for (int i = 0; i < lines.length; i++) Map()]; int? isDigitMem(int r, int c) { if (r < 0 || r > lines.length || c < 0 || c > lines[0].length) return null; return digs[r].putIfAbsent(c, () => isDigit(lines[r][c])); } int stoi(int row, int col) { int acc = 0; for (int i = col; i < lines[0].length; i++) { int? d = isDigitMem(row, i); if (d != null) { acc = (acc * 10) + d; } else { break; } } return acc; } int? stoiSearch(int row, int col) { assert(row >= 0 && col >= 0 && row < lines.length && col < lines[0].length); if (isDigitMem(row, col) == null) { return null; } int i = col - 1; while (i >= 0) { if (isDigitMem(row, i) == null) { return stoi(row, i + 1); } i--; } return stoi(row, 0); } List> s2i = [for (int i = 0; i < lines.length; i++) Map()]; int? stoiSearchMem(int row, int col) { if (row < 0 || row >= lines.length) return null; if (col < 0 || col >= lines[0].length) return null; return s2i[row].putIfAbsent(col, () => stoiSearch(row, col)); } int count = 0; for (int i = 0; i < lines.length; i++) { for (int j = 0; j < lines[0].length; j++) { if (lines[i][j] != "*") { continue; } List gearVals = List.empty(growable: true); for (int x = -1; x <= 1; x++) { int? left = stoiSearchMem(i + x, j - 1); int? mid = stoiSearchMem(i + x, j); int? right = stoiSearchMem(i + x, j + 1); if (isDigitMem(i + x, j) == null) { if (left != null) { gearVals.add(left); } if (right != null) { gearVals.add(right); } } else if (left != null) { gearVals.add(left); } else if (mid != null) { gearVals.add(mid); } else if (right != null) { gearVals.add(right); } } if (gearVals.length == 2) { count += gearVals[0] * gearVals[1]; } } } print(count); }