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.

  • swlabr@awful.systems
    link
    fedilink
    English
    arrow-up
    3
    ·
    11 months ago
    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:

    1. iterate through the characters to find a * symbol
    2. Search the characters around it for a digit.
    3. Get the value of the number associated with that digit by searching backwards until you find the start of a number
    4. Use union-find to track whether or not you’ve seen this number before (because you can’t assume that the same value is the same number)

    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);
    }
    
    • swlabr@awful.systems
      link
      fedilink
      English
      arrow-up
      3
      ·
      edit-2
      11 months ago
      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);
      }