10
\$\begingroup\$

Note: In this post, the terms 'character' and 'color' mean essentially the same thing

This image:

example map

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:

example five color map

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.

Sandbox link

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I see, at least in your example, that the "maps" aren't actually planar graphs, given that non-contiguous regions seem to have to be the same color. This means that you could easily create a graph that needed 6 or more colors to color. Should we treat the map 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\$ Oct 31, 2017 at 5:44
  • 2
    \$\begingroup\$ There isn't an error in the example, it's just that the example could work either way - its not wrong, just ambiguous. It would help to specify whether different regions labeled with the same character are the same or multiple regions in the rules. \$\endgroup\$ Oct 31, 2017 at 5:49
  • 1
    \$\begingroup\$ Funnily enough, I'm writing an essay on the proof of the four color theorem right now. I have to say, the proof for the five color theorem is a lot less complicated \$\endgroup\$ Oct 31, 2017 at 5:50

1 Answer 1

6
\$\begingroup\$

Python 2, 375 361 359 357 355 353 350 347 bytes

e=enumerate
C=set('12345')
def f(s):
 s=[map(ord,l)for l in s]
 for i,v in e(s):
	for j,w in e(v):
	 if{w}-C:
		F,N=g([],s,i,j,w)
		for y,x in F:s[y][x]=min(C-N)
 return s
def g(m,s,i,j,c):
 n={s[i][j]}
 if(n^{c}or(i,j)in m)<1:
	m+=(i,j),
	for x,y in(0,1),(0,-1),(1,0),(-1,0):
	 if len(s)>i+x>-1<j+y<len(s[0]):m,N=g(m,s,i+x,j+y,c);n|=N
 return m,n

Try it online!

Takes input as a list of strings, and returns a list of lists

f takes the map input and colors it, g returns all connected characters and the set of their neighbors, to the area can be colored with a distinct color.

\$\endgroup\$
6
  • \$\begingroup\$ 361 bytes \$\endgroup\$
    – ovs
    Oct 31, 2017 at 9:27
  • \$\begingroup\$ 359 bytes \$\endgroup\$ Oct 31, 2017 at 9:56
  • \$\begingroup\$ if~-(n!={c}or(i,j)in m): for -2 bytes \$\endgroup\$ Oct 31, 2017 at 10:31
  • \$\begingroup\$ s=map(list,s) for -11 bytes \$\endgroup\$ Oct 31, 2017 at 10:38
  • \$\begingroup\$ you can receive the input as a list of list of characters, it would save, that would save 24 bytes from your current solution \$\endgroup\$ Oct 31, 2017 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.