Four color theorem

I'm trying to solve the four color theorem in Ruby.

A map is like this:

ccaaaa
baaadc
babcdc
bbbcdc
abcccc

I have this, but it's slow. How can I make it better?

```
#!/usr/bin/env ruby

class String
def visit
@visited = true
end

def visited?
@visited == true
end

def color
@color || "_"
end

def color=(newcolor)
@color = (newcolor)
end

def colored?
@color != nil
end
end

class ColoredMap
COLORS = %w(R G B Y)

def initialize(map)
@map = map
end

def color_map
# go through each square and color the region if not already colored
@map.each_with_index do |line, row|
line.each_with_index do |cell, col|
color_region(row, col, @map[row][col], {}) unless cell.colored?
end
end
end

def color_region(x, y, name, colors_seen)
# mark as visited
@map[x][y].visit
# pick a color that hasn't been seen
chosen_color = nil

# iterate over each neighboring cell - Recurse or note color
each_direction(x, y) do |xp, yp|
if (@map[xp][yp] == name) && !@map[xp][yp].visited? # same region
chosen_color = color_region(xp, yp, name, colors_seen) # recursive call
elsif @map[xp][yp].colored? # neighboring cell already colored
colors_seen[@map[xp][yp].color] = true
end
end

# set to the color already chosen or to a color not yet seen
@map[x][y].color = chosen_color || COLORS.select{|color| !colors_seen[color]}[0]
end

# Enumerator returning each available direction
def each_direction(x, y)
yield x-1, y if x > 0 #up
yield x, y-1 if y > 0 #left
yield x, y+1 if y < @map[x].length-1 #right
yield x+1, y if x < @map.length-1 #down
end

def to_s
@map.map do |line|
line.join + "\n"
end.join

I/O bottleneck

Your first bottleneck is not the algorithm. As you see from your time output (0.29s user 0.11s system 10% cpu 3.723 total), your program only spent 10% of his time in the CPU. This means that even if your program took 0ms, you would only gain 10%!

You need to understand what takes that much time. Is it because the disk was busy? Or is it full? How long does it take when you run the program a second time? Is it faster? Is it still only spending 10% of its time in the CPU? Measure the time taken in the three main parts (read file, color map, display map) and see where it is slow (using Time.now which takes into account I/O latencies that the Ruby profiler does not).

Other bottlenecks

Once the I/O bottleneck is solved, you can turn to other optimizations. They are called micro-optimizations since the algorithm doesn't change: you're trying to use a few tricks to make it faster. Since the your code was very fast with the provided map, I created a bigger one with a few copy/pastes and ran the standard Ruby profiler to see where it was spending time.

$ time ruby -rprofile colors.rb biggermap
(colored map)
%   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
40.57    0.71      0.71     2082     0.34    10.12  ColoredMap#each_direction
15.43    0.98      0.27    55881     0.00     0.00  Array#[]
6.86     1.10      0.12     1141     0.11     0.14  Array#select
6.86     1.22      0.12     2082     0.06    10.28  ColoredMap#color_region
5.14     1.31      0.09     8219     0.01     0.03  String#colored?
.....
0.00     1.89      0.00        1     0.00     0.00  Kernel.puts
0.00     1.89      0.00        1     0.00  1890.00  #toplevel

ruby -rprofile colors.rb biggermap  1,90s user 0,13s system 99% cpu 2,034 total

I don't know how the profiler works, so we need to be careful with the results. I think it works like gprof: it adds instrumenting code to every method call, and then reconstructs a table sorted by cumulative seconds which means that it's not too precise. Here, according to the profiler, 10ms/call is spent in each direction. I think it's mostly due to the yields.

• The first candidates for slowness are all those yields. They are elegant, but you can try to unroll the loop manually to see how it improves.

• The second candidate is the recursion. You can loop from (0,0) to (n,n) and look if there are existing neighbors with a color. If not, then assign a new color. This is essentially the same algorithm but this avoids having a huge call stack and only visits each node once.

• Now that your code is iterative, you can try to minimize the number of checks like x > 0 and `y

The point is to run the profiler after each optimization and try to see if there is a new bottleneck arising.

StackExchange Code Review Q#22887, answer score: 4