# Four color theorem

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

A map is like this:

ccaaaa
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
end

def to_color
@map.map do |line|
line.map { |cell| cell.color }.join << "\n"
end.join
end

def to_debug
@map.map do |line|
line.map do |cell|
puts cell + cell.color + (cell.visited? ? "v" : ".") + " "
end
end.join
end
end

if __FILE__ == $PROGRAM_NAME abort "NO ARGUMENTS GIVEN - map file must be provided" unless ARGV[0] begin mapfile = File.new(ARGV[0]) rescue abort "Unable to open file '#{ARGV[0]}'" end # read in map file regions = [] mapfile.each_with_index do |line, line_num| regions[line_num] = line.chomp.split(//) end # color map mymap = ColoredMap.new(regions) mymap.color_map # display colored map puts mymap.to_color end  - How are you defining slow? The algorithm itself is optimal, and the code is fast! You could go for micro-optimizations, but how fast do you want the code to be? And for what map sizes? Have you consider writing this in a language like C? – Quentin Pradet Feb 19 '13 at 12:23 Here, it is 0,01s user 0,01s system 91% cpu 0,018 total on an old Core 2 CPU. Profiling using ruby -rprofile shows that most of the time is spent in each_direction. But is it because of the tests? The Ruby VM? Something else? Hard to say! I can provide a few alternative ways to program color_region if you wish. – Quentin Pradet Feb 19 '13 at 13:06 Don't remove the question! It's not stupid, it can happen to anyone. You can simply say that it was indeed an I/O issue. No worries, everybody is here to learn and every programmer can be bitten by such issues. – Quentin Pradet Feb 19 '13 at 14:32 @Cygal Yeah Sorry, I was really thinking it was a stupid question after all but it might help others actually. – bl0b Feb 19 '13 at 14:48 ## 1 Answer # 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 < .... If you find a simple way to predict that you are in the middle of the loop, then no checks are needed.

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

-