caterpillar.rb

#
# This class represents a path in the tree. It stores the positions along the x axis
# as a function of the depth and the sum of the leaves along the path
#
class Path
  attr_accessor :path
  attr_accessor :sum
  
  def initialize(parent, xpos, value)
    if parent
      @path = parent.path.dup
      @path << xpos
      @sum = parent.sum + value
    else
      @path = [xpos]
      @sum = value
    end
  end
  
  def depth
    @path.size-1
  end
  
  #
  # Returns the next positions where the caterpillar could go
  #
  def possible_next_positions
    [@path.last, @path.last+1]
  end
  
  def to_s
    "#{@path.inspect}, sum #{@sum}"
  end
  
end


#
# This is a brute force caterpillar advisor. It traverse the entire tree in order to find the
# optimal path for the poor hungry caterpillar
#
class CaterpillarAdvisor
  
  def guide_caterpillar(branches)
    @branches = branches
    @possible_paths = []
    @possible_paths << Path.new(nil, 0, branches[0][0])
      
    1.upto(branches.size-1) do |depth|
      analyze_branches_of_depth(depth)
    end
    
    best_path = @possible_paths.max{ |p1, p2| p1.sum <=> p2.sum }
    
    puts "Best path #{best_path}"
    
    [best_path.sum, best_path.path]
  end
  
  def analyze_branches_of_depth(depth)
    puts "Analyzing branches of depth #{depth}"
    @possible_paths = @possible_paths.collect{ |path| possible_next_paths_from(path)}.flatten
    puts "#{@possible_paths.size} possible paths so far"
  end
  
  def possible_next_paths_from(path)
    next_pos = path.possible_next_positions
    [path_for_possition(path, next_pos[0]), path_for_possition(path, next_pos[1])]
  end
  
  def path_for_possition(parent, xpos)
    next_depth = parent.depth+1
    value = @branches[next_depth][xpos]
    Path.new(parent, xpos, value)
  end

end


#
# This euristic caterpillar advisor eliminates the less promising paths after each iteration.
#
class HeuristicCaterpillarAdvisor < CaterpillarAdvisor
  
  #
  # Initialize with the maximum number of paths to consider in each iteration.
  #
  def initialize(max_possible_paths)
    @max_possible_paths = max_possible_paths
  end
  
  def analyze_branches_of_depth(depth)
    puts "Analyzing branches of depth #{depth}"
    @possible_paths = @possible_paths.collect{ |path| possible_next_paths_from(path)}.flatten
    @possible_paths = @possible_paths.sort_by{|path| path.sum}.last(@max_possible_paths)
    puts "#{@possible_paths.size} possible paths so far"
  end
  
end

caterpillar_test.rb

require "test/unit"
require "rubygems"
require 'json'
require 'contest'

$LOAD_PATH.unshift("#{File.dirname(__FILE__)}")

require "caterpillar"

class CaterpillarTest < Test::Unit::TestCase
  
  test "can read json" do
    @branches = JSON.parse(File.read('branches1.json'))
    assert @branches[3][1] == 5
  end
  
  test "find path in small tree" do
    @branches = JSON.parse(File.read('branches1.json'))
    advisor = CaterpillarAdvisor.new
    sum, path = advisor.guide_caterpillar(@branches)
    
    print_path(path)
    
    assert(sum == 23, "The sum must be 23") 
    assert(path == [0,0,1,2], "The path must be 0,0,1,2")
  end
  
  test "find path in medium tree" do
    @branches = JSON.parse(File.read('branches2.json'))
    advisor = CaterpillarAdvisor.new
    sum, path = advisor.guide_caterpillar(@branches)
    
    print_path(path)
  end
  
  test "find path in huge tree" do
        @branches = JSON.parse(File.read('branches3.json'))
        sums = []
        [100, 1000, 10000, 50000, 100000].each do |max|
          advisor = HeuristicCaterpillarAdvisor.new(max)
          sum, path = advisor.guide_caterpillar(@branches)
          sums << sum
          puts "For a maxium of #{max} paths considered, the sum of leafs is #{sum}"
          print_path(path)
        end
        assert sums[0] < sums[1]
        assert sums[1] < sums[2]
        assert sums[2] < sums[3]
        assert sums[4] == sums[3] # Reached a local maximum 
      end
    
  test "heuristic advisor is good with the medium tree" do
    @branches = JSON.parse(File.read('branches2.json'))
    brute = CaterpillarAdvisor.new
    heuristic = HeuristicCaterpillarAdvisor.new(3) # It finds the optimal path considering only 3 path each iteration!!!!
    assert brute.guide_caterpillar(@branches)[0] ==  heuristic.guide_caterpillar(@branches)[0]
  end
  
  test "heuristic wont find the best path unlees it considered a large of path" do
    @branches = JSON.parse(File.read('branches2.json'))
    brute = CaterpillarAdvisor.new
    heuristic = HeuristicCaterpillarAdvisor.new(2)
    assert brute.guide_caterpillar(@branches)[0] >  heuristic.guide_caterpillar(@branches)[0]
  end
  
  def print_path(path)
    final_path = []
    0.upto(@branches.size-1) do |depth|
      final_path << @branches[depth][path[depth]]
    end
    puts "Final path #{final_path}"
  end
end