Create a gist now

Instantly share code, notes, and snippets.

@newrelic /billkayser.rb Secret
Created Jan 17, 2010

# AN INFECTIOUS SOLUTION FOR SOLVING MAZES
#
# A maze consists of a network of cells which can be empty or infected
# by a virus. A virus is an organism that lives in a single cell. It
# divides and spreads to adjacent cells. A virus keeps track of what
# generation it is--the number of divisions that have occured since
# the introduction of the first virus into the maze.
#
# The younger the virus, the stronger it is. As a virus spreads, it
# divides and takes over adjacent cells that are either normal or
# already infected with an older, weaker virus. This approach ensures
# that after the infection has spread completely across the maze, only
# the youngest virus will survive at B and the generation number will
# represent the shortest possible number of steps required to reach B.
#
# This solution was an experiment in the use of a metaphor and
# syntactic features of Ruby for a literate, prosy presentation. It
# also has lots of cowbell.
#
# Maze solution by Bill Kayser, bkayser@newrelic.com
# Jan 16, 2010
#
#
#
require 'stringio'
class Maze
# A maze is solvable if an infection placed at
# point A eventually spreads point B.
def solvable?
infect the cell at a
while we have more? new_infections and not infected? at b do
spread a new_infection
end
is infected? at b
end
# We can determine the steps from A to B by infecting the maze at A,
# waiting until there are no more new infections, and then seeing
# what generation virus occupies point B.
def steps
infect the cell at a
while we have more? new_infections do
spread a new_infection
more cowbell!
end
if the maze is infected? at b then return the generation at b else return 0 end
end
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# A set of newly infected cells which are ready to spread the
# infection to nearby cells
attr_reader :new_infections
# The Map that keeps track of the content of all the cells
attr_reader :map
def initialize(maze)
@map = Map.new(maze)
@new_infections = []
end
# Take the virus from the given cell and infect each neighboring cell.
# Yes, it's repetitive, but I thought it reads nicer.
def spread(infectious_cell)
infectious_cell.virus.divide.infect cell north of infectious_cell
infectious_cell.virus.divide.infect cell south of infectious_cell
infectious_cell.virus.divide.infect cell east of infectious_cell
infectious_cell.virus.divide.infect cell west of infectious_cell
end
# DSL Methods
#
# These are just simple methods and connectors for expressing the
# algorithms in the solvable? and steps methods.
#
def cell(loc)
@map[loc]
end
def north(cell); Loc.new(cell.loc.row - 1, cell.loc.col); end
def south(cell); Loc.new(cell.loc.row + 1, cell.loc.col); end
def east(cell); Loc.new(cell.loc.row, cell.loc.col + 1); end
def west(cell); Loc.new(cell.loc.row, cell.loc.col - 1); end
def infect(cell)
Virus.new(self).infect(cell)
end
def more?(list)
list && list.size > 0
end
def infected?(loc)
(cell at loc).infected?
end
def generation(loc)
(cell at loc).virus.generation
end
# Could be either an article or a reference to position a
def a(*args)
return map.a if args.empty?
super
end
def b
map.b
end
# Get the next location off the list of new infections
def new_infection
new_infections.shift
end
# This just allows us to throw in little connector words in the
# algorithms for readability. If a method isn't found it just skips
# it by passing the arg along to the return value.
def method_missing(method, *args)
args[0]
end
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#
# Supporting Classes
#
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#
# A Virus has a location and knows what generation it is. When it
# divides it bumps the generation.
#
class Virus
attr_accessor :generation
def initialize(maze, generation = 0)
@maze = maze
@generation = generation
end
# Return self if you successfully infect the cell, otherwise nil
def infect(cell)
if cell && (cell.empty? || (cell.infected? && cell.virus.generation > self.generation))
cell.virus = self
# Add the cell to the list of newly infected cells, if it's not already
# on the list.
@maze.new_infections << cell unless @maze.new_infections.include? cell
end
end
def divide
Virus.new @maze, generation + 1
end
end
#
# A Map represents the contents of all the cells in the maze,
# addressable by Loc objects. It's initialized with the ASCII input
# data.
#
class Map
attr_reader :a, :b
def initialize(data)
@data = []
StringIO.new(data).readlines.each_with_index do |line, rownum |
@data << []
line.chomp.chars.each_with_index do | char, colnum |
loc = Loc.new(rownum, colnum)
@data.last << Cell.new(char, loc)
@a = loc if char == 'A'
@b = loc if char == 'B'
end
end
end
def [](loc)
return nil if loc.row < 0 || loc.col < 0
@data[loc.row][loc.col]
end
# I used this while developing the solution
def show
@data.each do | row |
row.each do | cell |
if cell.infected?
print "%3s" % cell.virus.generation
else
print " #{cell.content} "
end
end
puts
end
end
end
#
# A Cell represents what occupies a maze at a particular location
#
class Cell
attr_accessor :virus
attr_reader :loc, :content
def initialize char, loc
@content = char
@loc = loc
end
def empty?
[' ', 'A', 'B'].include?(@content) && virus.nil?
end
def infected?
not virus.nil?
end
end
#
# Loc represents a position in the map by row and column.
#
class Loc
attr_reader :row, :col
def initialize(row,col)
@row, @col = row, col
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment