Skip to main content
3 of 6
deleted 1 character in body

Remove largest non-unique connected shapes

Given a rectangular grid of square cells, find the non-unique connected shapes with the largest area, and remove all copies

Input

  • A rectangular grid of cells, each of which has 1 of 2 distinct values
  • You can choose to accept any of
  • an image with only 2 distinct pixel colours
  • text with only 2 distinct characters (also allowing newlines for forming a rectangle)
  • a 2d array, with each element having 1 of 2 distinct values
  • a 1d array, plus a width and/or height

The 2 distinct values will be referred to as "colours", but the rules apply similarly for all of the permitted formats

Let me know if there is an alternative format you would like to be considered

Output

  • A rectangular grid of cells in the same format as the input, using the same 2 distinct values
  • For each shape required to be changed, all of its cells have been switched to the other of the 2 distinct values

Rules

  • Each cell is part of a connected shape, which contains all cells of the same colour that can be reached by a path made up only of vertical or horizontal steps to adjacent cells of the same colour (no diagonal steps)
  • The grid does not wrap: a shape cannot be connected across the outer boundary
  • A shape is identical to another if it can be made to coincide exactly with it by any combination of
  • translation
  • rotation by an integer multiple of 90 degrees
  • reflection in any vertical or horizontal line
  • reversing its colour
  • A shape is unique if no other shape is identical to it
  • The area of a shape is the number of cells it contains
  • The shapes to be changed are those with the largest area, of those that are non-unique
  • If 2 or more distinct shapes are non-unique and have the largest area, all copies of each distinct shape must be changed
  • If there are no non-unique shapes, the output is the same as the input
  • A grid (input or output) may sometimes contain only 1 of the 2 colours

Test cases

Each test case is an input followed by its unique correct output

.  .

..  ..

.#  #.

.#  .#
..  ..

.#  #.
#.  .#

..#  ...
...  ...
.#.  ...

.......  .......
##.....  .......
#.....#  .......
.....##  .......

....##.  ....##.
##..##.  ....##.
#.....#  .......
.....##  .......

#.....###.  ..........
#.......#.  ..........
##...##...  ..........
.....##...  ..........
##........  ..........
##..####..  ....####..

.......###  .......###
..##..####  ......####
..#..###.#  .....#####
....###..#  ....######
...#######  ...#######

.......###  #######...
.##...####  ######....
.#...###.#  #####.....
....###..#  ####......
...#######  ###.......

........####  ########....
.###...#...#  #######.....
.#..#.#.##.#  ##..##..##..
.###.###...#  #####.......
....########  ####........

........####  ########....
.###...#...#  #######.....
.#..#.#....#  ##..##......
.###.###...#  #####.......
....########  ####........

With colour coding for human reading (click image for larger version):

test cases with colour coding

Scoring

  • This is
  • Your score is the number of bytes in your source code
  • For each language, the code with the lowest score wins

Sandbox thoughts

  • Any important/useful test cases welcome
  • Is there a more useful format for 2d test cases?
  • Are there 2 distinct characters that would make human reading easier?
  • Is this a duplicate?
  • Can anything be made clearer or more succinct?
  • I'm also trying to think of a better name