Note: In this post, the terms 'character' and 'color' mean essentially the same thing
This image:
can be represented as
....'''333
.eeee'''3e
..dddd33ee
%%%dd####e
(mapping colors to ascii characters)
The four color theorem states that "given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions." - Wikipedia (link)
This means that it should be possible to color a map using four colors so that no two parts which share an edge share a color.
The algorithm to color a map using only four colors is complicated so in this challenge your program only needs to color the map using five or less colors.
The previous map recolored could look like this:
which could be represented as
....'''333
.eeee'''3e
..dddd33ee
333dd....e
or equivalently
@@@@$$$!!!
@^^^^$$$!^
@@<<<<!!^^
!!!<<@@@@^
Challenge:
Given a "map" made of ascii characters (where each character represents a different color), "recolor" the map (represent the map using different ascii characters) so that it only uses five or less colors.
Example:
Input:
%%%%%%%%%%%%##########$$$$$$$$%%
*****%%%####!!!!!!!%%%%%%%%%#^^^
(((((((***>>>>??????????%%%%%%%%
&&&&&&&&$$$$$$$^^^^^^^))@@@%%%%%
^^^^^^%%%%%%%%%%%%##############
Possible output:
11111111111122222222223333333311
44444111222255555551111111112444
22222224441111444444444411111111
55555555222222255555553355511111
22222211111111111122222222222222
Clarifications:
- The input map will always use six or more characters
- You may use any five different characters in the output
- You can use less than different five characters in the output
- You may take the input in any reasonable format (including an array of arrays, or an array of strings)
- This is code-golf so the shortest answer wins.
121
as 3 separate regions to avoid this problem, even though the example implies otherwise, or should we treat it as 2, and assume that no map will be given that needs more than 5 colors? \$\endgroup\$