Mazes for Programmers/

...

/

Implementing Eller's Algorithm

Implementing Eller's Algorithm

Learn how to implement Eller's algorithm using Ruby.

We'll cover the following...

The Ellers class

Eller’s algorithm works strictly one row at a time, so our implementation will take advantage of that by leaning on a row-centric state object. Once we have that state object, the rest of the algorithm comes together quickly. We’ll start with the RowState class, which we’ll place under the namespace of the Ellers class. So, let’s first create the RowState class.

The RowState class

Press + to interact
  class RowState
    def initialize(starting_set=0)
      @cells_in_set = {}
      @set_for_cell = []
      @next_set = starting_set
    end
    def record(set, cell)
      @set_for_cell[cell.column] = set
      @cells_in_set[set] = [] if !@cells_in_set[set]
      @cells_in_set[set].push cell
    end
    def set_for(cell)
      if !@set_for_cell[cell.column]
        record(@next_set, cell)
        @next_set += 1
      end
      @set_for_cell[cell.column]
    end
    def merge(winner, loser)
      @cells_in_set[loser].each do |cell|
        @set_for_cell[cell.column] = winner
        @cells_in_set[winner].push cell
      end
      @cells_in_set.delete(loser)
    end
    def next
      RowState.new(@next_set)
    end
    def each_set
      @cells_in_set.each { |set, cells| yield set, cells }
      self
    end
  end

Code explanation

Lines 2–6: The initialize method has a starting_set parameter (defaulting to 0), which is used to determine what value is used for new sets. It then sets up a few instance variables that are used for keeping track of sets within the current row.

The next three methods allow us to query and manipulate those sets. We add these just after that initialize ...