// 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;

    }

}