solver for http://numb3rs.wolfram.com/516/puzzle.html

colored_path.rb

#!/usr/bin/env ruby
# solver for http://numb3rs.wolfram.com/516/puzzle.html

# a node in the graph
Node = Struct.new(:label, :color, :edges)
class Node
  # hash equalit for nodes is only dependent on label (which is unique)
  def hash
    label.hash
  end
  def eql?(other)
    label == other.label
  end
end
# an edge in the graph
Edge = Struct.new(:color, :endpoints)
# a class for storing a complete graph
# (useful for creating dot files for GraphViz)
class Graph
  def initialize(nodes)
    @nodes = nodes
    @edges = nodes.map { |node| node.edges.select { |edge| edge.endpoints.first == node } }.flatten
  end
  def self.node_to_dot(node)
    "#{node.label} [color=#{node.color}];"
  end
  def self.edge_to_dot(edge)
    "#{edge.endpoints.first.label} -- #{edge.endpoints.last.label} [color=#{edge.color}];"
  end
  def to_dot
    <<-DOT
graph { 
  #{@nodes.map { |node| node_to_dot(node) }.join("\n\t")}
  #{@edges.map { |edge| edge_to_dot(edge) }.join("\n\t")}
}
    DOT
  end
end
# a complete problem
module Problem
  class State
    attr_accessor :left, :right, :transitions, :visited
    def initialize(left,right)
      @left,@right = left,right
      @transitions = 
        left.edges.select { |edge| edge.color == right.color }.map { |edge| (edge.endpoints - [left]) + [right] } +
        right.edges.select { |edge| edge.color == left.color }.map { |edge| [left] + (edge.endpoints - [right]) }
      @index = -1
    end
    def next
      @index += 1
      @transitions[ @index ] 
    end
    def nodes
      [@left, @right]
    end
  end
  # use depth first search to find the paired path 
  # on the product graph
  def self.solve(start_nodes, end_nodes)
    states = Hash.new do |_states, nodes|
      if nodes
        left,right = *nodes
        _states[ [right,left] ] = _states[ [left,right] ] = State.new(left,right)
      end
    end
    start_state = states[ start_nodes ]
    end_state = states[ end_nodes ]
    path = [ start_state ]

    while path.last != end_state
      path.last.visited = true
      begin
        next_state = states[ path.last.next ]
        unless next_state
          path.pop
          return nil if path.empty?
          next
        end
      end while next_state.nil? or next_state.visited
      path << next_state
    end

    return path.map { |state| state.nodes }
  end
end

if __FILE__ == $0
  def die(code,msg)
    STDERR.puts "ERROR: #{msg}"
    exit code
  end

  LABELS = []
  COLORS = []
  NODES = Hash.new { |_nodes,label| _nodes[label] = Node.new(label, nil, []) }
  $start_nodes = nil
  $end_nodes = nil

  # read in and validate input
  DATA.each_with_index do |line, lineno|
    line.chomp!
    case line
    when /^labels:\s+(\w+(?:\s+\w+)*)\s*$/:
      LABELS.concat $1.split(/\s+/)
    when /^colors:\s+(\w+(?:\s+\w+)*)\s*$/:
      COLORS.concat $1.split(/\s+/)
    when /^start_nodes:\s+(\w+)\s+(\w+)\s*$/:
      unless LABELS.include? $1
        die(-1, "Unrecognized label #$1 in start state definition #{line.inspect} on line #{lineno}")
      end
      unless LABELS.include? $2
        die(-1, "Unrecognized label #$2 in start state definition #{line.inspect} on line #{lineno}")
      end
      $start_nodes = [ NODES[$1], NODES[$2] ]
    when /^end_nodes:\s+(\w+)\s+(\w+)\s*$/:
      unless LABELS.include? $1
        die(-1, "Unrecognized label #$1 in end state definition #{line.inspect} on line #{lineno}")
      end
      unless LABELS.include? $2
        die(-1, "Unrecognized label #$2 in end state definition #{line.inspect} on line #{lineno}")
      end
      $end_nodes = [ NODES[$1], NODES[$2] ]
    when /^(\w+)\s+(\w+)\s*$/:
      unless LABELS.include? $1
        die(-1, "Unrecognized label #$1 in node definition #{line.inspect} on line #{lineno}")
      end
      unless COLORS.include? $2
        die(-1, "Unrecognized color #$2 in node definition #{line.inspect} on line #{lineno}")
      end
      NODES[$1].color = $2
    when /^(\w+)\s+(\w+)\s+(\w+)\s*$/
      unless LABELS.include? $1
        die(-1, "Unrecognized label #$1 in edge definition #{line.inspect} on line #{lineno}")
      end
      unless LABELS.include? $2
        die(-1, "Unrecognized label #$2 in edge definition #{line.inspect} on line #{lineno}")
      end
      unless COLORS.include? $3
        die(-1, "Unrecognized color #$3 in edge definition #{line.inspect} on line #{lineno}")
      end
      endpoints = [ NODES[$1], NODES[$2] ]
      edge = Edge.new($3, endpoints)
      endpoints.each { |node| node.edges << edge }
    when /^\s+$/: 
      # skip
    else
      die(-1, "Unrecognized input #{line.inspect} in graph definition on line #{lineno}")
    end
  end
  
  # check for completeness
  die(-1, "No node definition found in input for node #{label}") unless NODES.all? { |label,node| node.color }
  die(-1, "No start nodes found in input") unless $start_nodes
  die(-1, "No end nodes found in input") unless $end_nodes

  if (path = Problem.solve($start_nodes, $end_nodes))
    path.each do |left,right|
      puts "#{left.label} #{right.label}"
    end
  else
    puts "no solution found"
  end

end


__END__
labels: A B C D E F G H I J K L M N O P Q R S T
colors: red yellow blue green
start_nodes: K K
end_nodes: I I
A red
B green
C yellow
D green
E yellow
F green
G red
H green
I red
J blue
L blue
K yellow
M blue
N green
O blue
P yellow
Q red
R yellow
S red
T blue
A B red
A F red
A K yellow
B C green
B G yellow
C D blue
C H blue
D E red
D I green
E I red
E J green
F L red
F P red
G H blue
G L blue
H I blue
I J green
I N blue
J O green
K P yellow
L M red
L Q yellow
M N green
M R green
N O yellow
N S blue
N T green
O T blue
P Q yellow
Q R yellow
R S yellow
S T red