Skip to main content
4 of 6
Remove misleading use of "remove"

Switch colour of largest non-unique connected shape

Given a rectangular grid of square cells, find the non-unique connected shapes with the largest area, and switch their colour

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

Output

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

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
  • switching 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

.  .

..  ..

.#  #.

.#  .#
..  ..

.#  #.
#.  .#

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

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

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

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

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

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

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

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

The same test cases 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