It's well known to cartographers that you can color a (planar) map using only 4 colors so that no neighbouring countries get the same color. Your job is to find such a coloring for a given 10x10 map.
on STDIN you will get a representation of a map, each country represented by a capital letter (a country will not contain any disconnected pieces). The input will match /^([A-Z]{10}\n){10}\z/, for example:
AAAAAAAAAA ABBDDAAAAA BBBDDHAAAA ACCDDHAAAA ACCDDHAAAA AAAAAHAAAA AEEFFHAAAA AEEFFHAAAA AGGFFAIAAA AAAAAAAAAASo we have countries A,B,C,D,E,F,G,H and I. A is a neigbour of every other country, I is a neighbour of only A (not of H, diagonal connections don't count). So if we give A color 0, none of the other countries can get color 0. (The topology is not a torus, so the outer edges of the input have no neigbours).
On STDOUT you should print a valid color-assignment so neighbouring countries never get the same color. You may use at most 4 colors, represented by 0,1,2 and 3. You may use more colors than strictly needed (e.g. use 4 colors where 3 are sufficient), but never more than 4. The output has each country character replaced by it's color, so something like:
1111111111 1223311111 2223301111 1003301111 1003301111 1111101111 1332201111 1332201111 1002210111 1111111111As you can see the output matches /^([0-3]{10}\n){10}\z/. Nothing should appear on STDERR. The returncode of the program does not matter.
some other inputs you can try:
AAAAAAAAAA AAAAAAAAAA AJJJKKLLLA AJEEEFFFLA AJEEBBFFLA AGGCBBDIIA AGGCCDDIIA AGGGHHIIIA AAAAAAAAAA AAAAAAAAAA
AAAAAAAAAA AAANNNNAAA AJJJKKLLLA AJEEEFFFLA AJEEBBFFLA AGGCBBDIIA AGGCCDDIIA AGGGHHIIIA AAAMMMMAAA AAAAAAAAAA
SBCDEFGHJJ SBCDEFGHJJ KKLLMMNOOJ KKLLMMNNOJ PPPQQQRRRJ PPPQQIIRRJ TTTTUUUUVJ TTTTUUUUVJ WWWWWXXXXJ WAAWWXYZZJ
There is a testprogram provided by MTV Europe.
The challenge runs under the generic perl golf rules.
Tell the length of your solutions (but not the solution itself) to ton- on ircnet #perl or mail the number to perl-golf@ton.iguana.be
The challenge finishes at 2002/07/28 22:00:00 UTC
70 tybalt89 (rejected) 75 mtve 78 tybalt89 83 ton
tybalt89 70 -0p $$3++while/(.)(\C{10})?(?!\1)(.)(??{$$1%4!=$$3%4})/;s/(.)/$$1%4/ge (rejected)
mtve 75 -p0i(.{10}|) $Q=$_;$==rand 4,/$&$^I$=|$=$^I$&/s?$_=$Q:s/$&/$=/gwhile/[A-Z]/
mtve 75 -p0aF% $==rand 4,/$&(.{10}|)$=|$=(.{10}|)$&/s?($_)=@F:s/$&/$=/gwhile/[A-Z]/
tybalt89 78 -0p $${$.^=2}^=rand 4while/(.)(\C{10})?(?!\1)(.)(??{$$1!=$$3})/;s/(.)/3-$$1/ge
mtve 80 -p0i(.{10}|) $Q=$_;$==rand 4,/$&$^I$=|$=$^I$&/s?$=||=$_=$Q:s/$&/$=/gwhile/[A-Z]/
ton 83 -n0i(.{10}|) for$n(!s/$&/$n/g..3){s#$#/\pL/?!/$&$^I$n|$n$^I$&/s&&do$0:exit print#e}
tybalt89 90 -0p s/./$&0/g;$==rand 4,s/(${1+3*$|--})./$1$=/gwhile/(.)(\d)(\C{19})?(?!\1)(.)\2/;y/A-Z//d
ton 102 -n0i(.{10}|) sub f{y/0-3/1230/;/$&$^I0|0$^I$&/s||map{s/$&/0/g*/[A-Z]/?&f+&f+&f+&f:exit print}"$_"}f/./
Post-mortem:
ton+mtve 73 -p0i(.{10}|) $Q=$_;$==rand 4,/$&$^I$=|$=$^I$&/s?$_=$Q:s/$&/$=/gwhile/\pL/