I'm trying to solve the four color theorem in ruby. A map is like this:
ccaaaa
baaadc
babcdc
bbbcdc
abcccc
And so far i have this following code but it's slow, how could 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
0,01s user 0,01s system 91% cpu 0,018 totalon an old Core 2 CPU. Profiling using ruby -rprofile shows that most of the time is spent ineach_direction. But is it because of the tests? The Ruby VM? Something else? Hard to say! I can provide a few alternative ways to programcolor_regionif you wish. – Quentin Pradet Feb 19 at 13:06