ruby euler 15

ruby_euler_15.rb

class NxNGrid
  
  class Node
    attr_accessor :paths
    
    def initialize(pos)
      @pos = pos
    end

    def to_i
      @pos.to_i
    end
  end
  
  
  attr_reader :nodes
  
  def initialize(num_of_cols)
    raise "Grid dimension must be >= 1"
    @num_of_cols = num_of_cols+1
    n = @num_of_cols**2    
    @nodes = (0...n).map { |i| Node.new(i) }
    @adj_matrix = Array.new(n) { Array.new(n) { 0 }}
    connect_edges()
  end
  
  def start_node()
    @nodes.first()
  end

  def end_node()
    @nodes.last()
  end

  def adj_nodes(node)
    nodes = []
    (0...@nodes.length).each do |i|
      nodes << @nodes[i] if @adj_matrix[i][node.to_i] == 1
    end
    nodes
  end
  
  def num_of_paths()
    num_of_paths_helper(start_node())
  end


  private
  
  def num_of_paths_helper(node)
    if node == end_node()
      return 1
    elsif node.paths()
      return node.paths()
    else
      paths = 0
      adj_nodes(node).each do |n|
        if n.paths
          paths += n.paths
        else
          p = num_of_paths_helper(n)
          n.paths = p
          paths += p
        end
      end
      return paths
    end
  end
  
  def connect_edges()
    (0...@nodes.length).each do |i|
      if top_row?(i) && far_col?(i)
        next
      elsif top_row?(i)
        connect_right_edge(i)
      elsif far_col?(i)
        connect_top_edge(i)
      else
        connect_right_edge(i)
        connect_top_edge(i)
      end
    end
  end
  
  def connect_right_edge(i)
    @adj_matrix[i+1][i] = 1
  end

  def connect_top_edge(i)
    @adj_matrix[i+@num_of_cols][i] = 1    
  end
  
  def top_row?(pos)
    (@nodes.length)-(@num_of_cols) <= pos
  end

  def far_col?(pos)
    n = @nodes.length-1
    positions = []
    while n > 0
      positions << n
      n -= @num_of_cols
    end
    positions.include?(pos)
  end
end


if $0 == __FILE__
  graph = NxNGrid.new(ARGV[0].to_i)
  puts graph.num_of_paths()
end