// from https://rosettacode.org/wiki/Zhang-Suen_thinning_algorithm#Java

// image is _ for bg, anything else for fg
srecord noeq ZhangSuenDemo(S image) {
  static char empty = '_';
  
  static final int[][] nbrs = {{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1},
        {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}};
 
  static final int[][][] nbrGroups = {{{0, 2, 4}, {2, 4, 6}}, {{0, 2, 6},
        {0, 4, 6}}};
 
    List<Point> toWhite = new ArrayList<>();
    char[][] grid;
 
    S get() {
      var image = toStringArray(lines(this.image));
      grid = new char[image.length][];
      for (int r = 0; r < image.length; r++)
          grid[r] = image[r].toCharArray();

      thinImage();
      
      ret charGridToString(grid);
    }
 
    void thinImage() {
        boolean firstStep = false;
        boolean hasChanged;
 
        do {
            hasChanged = false;
            firstStep = !firstStep;
 
            for (int r = 1; r < grid.length - 1; r++) {
                for (int c = 1; c < grid[0].length - 1; c++) {
 
                    if (grid[r][c] == empty)
                        continue;
 
                    int nn = numNeighbors(r, c);
                    if (nn < 2 || nn > 6)
                        continue;
 
                    if (numTransitions(r, c) != 1)
                        continue;
 
                    if (!atLeastOneIsWhite(r, c, firstStep ? 0 : 1))
                        continue;
 
                    toWhite.add(new Point(c, r));
                    print("Clearing " + c + "/" + r);
                    hasChanged = true;
                }
            }
 
            for (Point p : toWhite)
                grid[p.y][p.x] = empty;
            toWhite.clear();
 
        } while (firstStep || hasChanged);
        
    }
 
    int numNeighbors(int r, int c) {
        int count = 0;
        for (int i = 0; i < nbrs.length - 1; i++)
            if (grid[r + nbrs[i][1]][c + nbrs[i][0]] != empty)
                count++;
        return count;
    }
 
    int numTransitions(int r, int c) {
        int count = 0;
        for (int i = 0; i < nbrs.length - 1; i++)
            if (grid[r + nbrs[i][1]][c + nbrs[i][0]] == empty) {
                if (grid[r + nbrs[i + 1][1]][c + nbrs[i + 1][0]] != empty)
                    count++;
            }
        return count;
    }
 
    boolean atLeastOneIsWhite(int r, int c, int step) {
        int count = 0;
        int[][] group = nbrGroups[step];
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < group[i].length; j++) {
                int[] nbr = nbrs[group[i][j]];
                if (grid[r + nbr[1]][c + nbr[0]] == empty) {
                    count++;
                    break;
                }
            }
        return count > 1;
    }
}