Playing with Dijkstra

# I have written this program to learn ruby... and after reading
# docs & books and hours of listining to great music like Ghosts
# from Nine Inch Nails, and some crazy stuff (do you know the band
# Cynic - they do a addictive jazz/deathmetal/disharmonic/bla mix °_°)
# ... I got the basics ;)
#
# Also... thanks to the orgas of this challenge ;)
#
# OK... lets start ;)

# important program constants
Version = 1.0

# include source files
require 'lpers.rb'
require 'nfig.rb'
require 'nu.rb'
require 'v.rb'
require 'go.rb'

# 'global' function that lets start the solution algo ;)
def start(lab)
  unless lab.instance_of? Env
    raise ArgumentError, 'ease set a labyrinth file!'
  else
    # put out the lab filename again
    puts 'byrinth file:  ' << Config[:file].to_s unless Config[:output]==:clean
    # start timer
    timer = Time.now
    # calculate and display!
    lab.output_path Config[:algo]||:dijkstra, Config[:output]||:console
    # output timer
    puts "me needed for calculation and output: #{ime.now - timer)}econds" unless Config[:output]==:clean
  end
end


# now do what the command line options tell us to do
if Config[:info]
  Menu.info # display info and exit
elsif !Config[:file]
  Menu.idle # go to menu..
elsif Config[:force_menu]
  Menu.idle Env.new Config[:file] # [forced menu! - but file is already set]
else
  start Env.new Config[:file] # ..or start the code if file was set by command line options
end

# this methods add some functionality to some existing classes - in ruby, every class can be 'reopened'!

# helper: trims the first char of both args and merges them into the object hash
class Hash
  def merge_without_first!(arg,arg_val)
    if arg
      arg = arg[1,arg.length].to_sym
      arg_val = arg_val.empty? ? true : arg_val[1,arg_val.length].to_sym
      self[arg] = arg_val
    end
  end
end

# helper: output currently configured file path
def File.full_path(prm_path,expanded=false)
  if prm_path[0] == '/' or prm_path[0] == '~' or prm_path[1] == ':' # too easy way to detect absolute pahts
    prm_path.to_s
  elsif expanded
    File.expand_path(Config::BasePathLabs + prm_path.to_s)
  else
    Config::BasePathLabs + prm_path.to_s
  end
end

require 'yaml' # yet another markup language # comment out this line for JRuby 1.2.0 support (see readme!)

 # Config: global class/module which holds all configuration
 # access current program configuration by 'Config[:foo]' # => 'bar'
 # access general configuration (loaded by config file) as constants: 'Config::Foo' # => 'bar'
module Config
  @settings = {};
  def self.[](key); @settings[key]; end # config getter
  def self.[]=(key,val); # config setter
    raise ArgumentError, 'Sorry, the given algorithm is not suppported (see info!)'     if key == :algo   && ![:dijkstra,:astar,:astar_b,:backtracking].member?(val)
    raise ArgumentError, 'Sorry, the given output format is not suppported (see info!)' if key == :output && ![:console,:html,:both,:clean].member?(val)
    @settings[key] = val;
  end

  # This hash will hold program arguments..
  args = {}
  # ..get those now
  while arg = ARGV.shift
    unless arg[0]=='-' # param is no option
      arg = ARGV.shift # go to next argument
    else
      arg_val = '' # start with empty values..
      temp_val = ARGV.shift # (next param)
      while temp_val && temp_val[0]!='-'
        arg_val += ' ' + temp_val #..and add them to current the current arg-value
        temp_val = ARGV.shift # (next param)
      end
      args.merge_without_first!(arg,arg_val) # put options answers in hash
      ARGV.unshift(temp_val) # temp_val is next arg
    end
  end
  args.merge_without_first!(arg,arg_val) # put options answers in hash - also if end was already reached in loop

  # save allowed configuration
  args.each { |arg,arg_val| @settings[arg] = arg_val if [:file,:algo,:output,:force_menu,:info].member? arg}

  # load settings from config file
  config_path = (args[:config] || 'config/default.yaml').to_s
  base = YAML::load(File.read(config_path)) if File.file? config_path # comment out this line for JRuby 1.2.0 support (see readme!)
  # base = nil # remove comment from this line for JRuby 1.2.0 support (see readme!)

  if base and base['base_paths']
    BasePathLabs = base['base_paths']['labs']
    BasePathHtml = base['base_paths']['html']
  else
    BasePathLabs = 'labs/' # std
    BasePathHtml = 'html/' #   paths
  end
end

# as you might have thought - the program menu
module Menu
  # show the menu
  def self.show(flash=nil)
    system("clear") #print "\e[2J\e[f" - low level function... will not work @ some systems :(
    puts "== AKMRubyLabyrinth #{Version} coded for AKMProgChallenge09 =="
    puts
    puts 'Current configuration'
    puts " LABYRINTH-FILE:\t#{ Config[:file]   || '---'}"
    puts " ALGORITHM:     \t#{(Config[:algo]   || 'Dijkstra [standard]').to_s.capitalize}"
    puts " OUTPUT-FORMAT: \t#{(Config[:output] || 'Console  [standard]').to_s.capitalize}"
    puts
    puts 'Please type one of the commands:'
    puts " info  \t- Give some information"
    puts " file  \t- Read-in the labyrinth-file"
    puts " algo  \t- Select algorithm to use"
    puts " output\t- Select output format to use"
    puts " start \t- Calculate the solution path! [labyrinth file must be loaded]"
    puts " quit  \t- Exit program"
    if flash
      puts
      puts 'Message:'
      puts ' ' << flash
    end
    puts
  end

  # some infos ;)
  def self.info
    system("clear")
    puts '== Info ==
 This program calculates the shortest path in a 9x9 labyrinth. The player
 starts in the top left corner and wants to reach the bottom right one.
 For more info about the task, see <https://akamentor.net/prog/>

 You can choose between following algorithms:
  - Dijkstra
  - Astar
  - Astar_b (variation)
  - Backtracking

 Additionally you can choose between the output formats:
  - Console
  - Html
  - Both
  - Clean (puts out only the solution path)

 The output is a line of commands describing where to go from the start point:
  - u: up
  - d: down
  - l: left
  - r: right

 This program is written in ruby, the shiny great programming language. If you
 do not know it - feel free to study the source of this program and learn it ;)
 If your thoughts the same as mine and you rather like writing nice code than
 super performant, but unreadable c-or-whatever code... than do it!

 Feel free to mail me about the program or ruby: <mail@janlelis.de>

 Some more information about this program can be found in the readme file.

> Press <Enter>'
  end

  # and the main method... idling in the menu till user decides to quit
  def self.idle(lab=nil)
    @lab = lab if lab
    show
    print '>> '; input = gets.strip.downcase.to_sym # get user command
    until input == :quit; begin # extra block for rescueing Err
      case input
        when :file
          temp_file = get_setting "Please enter the path to the labyrinth file\n (base path is: \"#{File.expand_path(Config::BasePathLabs)}\")"
          @lab = Env.new  temp_file # try to load specified file (throws exception if not sucessful)
          Config[:file] = temp_file
          show
        when :algo   then Config[:algo]   = get_setting 'Please enter the algorithm to use';     show
        when :output then Config[:output] = get_setting 'Please enter the output format to use'; show
        when :info   then info;       gets; show
        when :start  then start @lab; gets; show # 'global' method - start the solution!
      end
    rescue ArgumentError => e # error! inform user what he did wrong.
    #  show e.message
    puts '> ' << e.message
    else # no errors
    #  show
    ensure # do this always [errors or no errors]
      print '>> '; input = gets.strip.downcase.to_sym # - get next command
    end; end
  end

  # helper method which gets the settings that we want!
  def self.get_setting(instruction='Please enter a value for this setting') # gets the value of one setting
    print '> ' << instruction << ': '; gets.strip.downcase.to_sym
  end
end

require 'set' # std lib for sets [alternative to arrays]

# Env = Environment = labyrinth - loads the labyrinth file and do things with it
class Env
  attr_reader :array, :nodes, :edges, :path # getter for instance vars

  # reads file into lab-array
  def initialize(prm_path)
    @array = []

    raise ArgumentError, 'Sorry, could not load the labyrinth file "'<< File.full_path(prm_path,true) << '"' unless File.exist?(File.full_path(prm_path))

    File.open(File.full_path(prm_path)) do |b_file| # Read file..
      b_file.each {|b_line| b_line.rstrip!; @array << b_line.split(';').collect {|a_ele| a_ele.to_i} } # ..and put ele as int into an multi-dim-array [A and Z are converted to 0 by to_i]
    end

    raise ArgumentError, 'Sorry, could not load the labyrinth: the labyrinth file is empty!' if @array.empty? || @array[0].empty?
    raise ArgumentError, 'Sorry, could not load the labyrinth: wrong format!' unless @array.size == 9 # only a weak test
  end


  # get the solution :)
  def output_path(prm_algo=:dijkstra,prm_format=:console)
    # choose algo
    algo = (prm_algo==:backtracking) ? Algo.const_get(prm_algo.to_s.capitalize) : Algo::Dijkstra
    # (currently, the std algo is Dijkstra -- needs to be changed if algos get more complex or more are added!)

    # init calculation
    transform_to_graph if algo::NeedsGraph

    case prm_algo
      when :dijkstra
        algo.init(@nodes,@edges)
      when :astar
        # with a block appended describing the heuristic, the dijkstra module turns into A* :]
        algo.init(@nodes,@edges) do |idx,tupel|
          tupel.d + 16-(idx/9+idx%9) # ...
        end
      when :astar_b
        h = [16, 15, 14, 13, 12, 11, 10, 9, 8, 15, 14, 13, 12, 11, 10, 9, 8, 7, 14, 13, 12, 11, 10, 9, 8, 7, 6, 13, 12, 11, 10, 9, 8, 7, 6, 5, 12, 11, 10, 9, 8, 7, 6, 5, 4, 11, 10, 9,8, 7, 6, 5, 4, 3, 10, 9, 8, 7, 6, 5, 4, 3, 2, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0]
        algo.init(@nodes,@edges) do |idx,tupel|
          tupel.d + h[idx] # same as above, only with hardcoded values
        end
      when :backtracking
        algo.init(@array)
    end

    # calculate! :)
    @path = algo.calc

    # put out
    if prm_format == :console or prm_format == :both
      puts "Algorithm:       #{prm_algo.capitalize}"
      puts '_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _'
      if @path and @path.is_a? Array
        puts algo::info
        puts 'Path:'
      end
      puts @path
    end

    # html output in a very ugly way ;)
    if prm_format == :html or prm_format == :both
      # calculate file name
      now_name = "#{Config::BasePathHtml}#{Time.now.strftime("%y%m%d_%H%M%S_" + Config[:file].to_s + "_" + (Config[:algo]||:dijkstra).to_s)}.htm"
      # and create sub dir if not present
      Dir.mkdir 'html' unless File.directory? 'html'

      # write the file ;)
      File.open(now_name,'w') do |out|
        out.puts "<html><head><title>AKMRubyLabyrinth - File: #{Config[:file]} - Algorithm: #{(Config[:algo]||:dijkstra).to_s.capitalize}</title>"
        out.puts '<style type="text/css">
 body 	              {background:#333;font-family:Arial;color:white}
 h1,h3,.info          {background:#777;border:darkred solid 1px}
 h1,h2,h3,.info,.sub  {padding:5px;margin:5px}
 .sub                 {background:#777;border:darkred dashed 1px}
</style></head><body>'# some style blabla
        out.puts '<h1>AKMRubyLabyrinth</h1>'
        out.puts "<h3>File: #{Config[:file]}<br/>"
        out.puts "Algorithm: #{(Config[:algo]||:dijkstra).to_s.capitalize}</h3>"
        out.puts '<div class="info">'
        if path.is_a? Array
          out.puts " <div class=\"sub\">Path length: #{path.size}</div>"
          out.puts " <div class=\"info\">Solution: <strong>"
          path.each {|step| out.print " #{step}"}
        elsif
          out.puts "<div class=\"sub\"><strong>#{path}"
        end
        out.puts ' </strong></div>'
        out.puts '</div>'

        out.puts '</body></html>'
      end
      # (weak) check if it was successful
      if File.file? now_name
        puts 'Output saved in ' << now_name
      else
        puts 'Sorry, could not save the solution in a html document..'
      end
    end

    # or clean °_°
    if prm_format == :clean
      puts @path
    end
  end


  # transforms @array into @nodes and @edges
  def transform_to_graph()
    @edges = Set.new  # start
    @nodes = Set.new  #      values

    9.times do |i| # 0.upto 9
	    9.times do |j|
        if @array[i][j] == 0 # field is valid node
          ni = node_ident(i,j)
          @nodes << ni
          @edges << [node_ident(i,j-1),ni] << [ni,node_ident(i,j-1)] if j>0 and @array[i][j-1] == 0 # valid edge version 1
          @edges << [node_ident(i-1,j),ni] << [ni,node_ident(i-1,j)] if i>0 and @array[i-1][j] == 0 # valid edge version 2
        end
      end
    end
  end

  # helper: takes indexes, returns node ident-number (0-80)
  def node_ident(i,j);  9*i+j;  end
end

require 'set'

# now it gets interesting: this module holds the algorithms
module Algo
  # each Algo has its own namespace
  module Dijkstra
   NeedsGraph = true
   class << self # everything are module methods - dont write self. prefix everytime..

    def info # is displayed as console info
      'Shortest path length: ' << @path.length.to_s
    end

    # init dijkstra, if an heuristic is given, how to decide [by min] which sould be the next node, than use it!
    def init(nodes,edges,&heuristic)
      @a, @edges, @heuristic = nodes, edges, heuristic||proc{|sn| sn[1].d} # std heuristic is dijkstra [next node is the one with min. distance]
      @m = {} # marked nodes
      @s = {} # sidenodes
    end

    # calculate the solution!
    def calc()
      # get shortest distance tupel :)
      current = DTupel.new(0,0,0) # 0 is startnode
      until current.n == 80 or @a.empty?
        @a.delete current.n # delete node from @a
        @s.delete current   # .. and from @s
        @m[current.n] = current # add tupel to @m

        new_tupels = create_tupels current # get new sidenode-tupels
        new_tupels.each do |sn|
          @s[sn.n] = sn  if !@s[sn.n] or @s[sn.n].d > sn.d # add sidenode if it does not exist or choose the one with smallest distance
        end
        # check if there are sidenodes
        return '*No solution path is possible in this labyrinth!*' if @s.empty?
        # get minimum for next iteration
        next_node = @s.min_by(&@heuristic) # classical dijkstra: {|sn| sn[1].d }
        current = next_node[1]
        @s.delete next_node[0]
      end

      # get final path
      ret = []
      until current.n == 0
        ret << get_direction(current.n, current.p)
        current = @m[current.p]
      end
      @path = ret.reverse
    end

    # create new sidenode tupels
    def create_tupels(tupel)
      # get open edges
      # comment out next line for JRuby 1.2.0 support (see readme!)
      open_edges = @edges.select {|cur,other| tupel.n==cur and @a.include? other} # connection between current and a still available ones - this is the normal way, working in 1.9
      # remove comment next line for JRuby 1.2.0 support (see readme!)
      # open_edges = []; @edges.each{|cur,other| open_edges << [cur,other] if tupel.n==cur&&@a.include?(other)}
      open_edges.collect {|e| DTupel.new(e[1],tupel.d+1,tupel.n) }
    end

    # calculate direction by node identifier
    def get_direction(n1,n2)
      case
        when n2 - n1 == 1 then 'l' # left
        when n1 - n2 == 1 then 'r' # right
        when n2 - n1 == 9 then 'u' # up
        when n1 - n2 == 9 then 'd' # down
      end
    end

   end

   # One tupel takes @n,@d,@p -> current node, current (shortest) distance, prior node
   class DTupel
     attr_reader :n,:d,:p
     attr_writer    :d,:p

     def initialize(n,d=1.0/0,p=nil) # d = Infinity xD
       @n,@d,@p = n,d,p #node, distance, prior node
     end
   end

  end


 module Backtracking
    NeedsGraph = false
    class << self

      def info
        "This algorithm does not calculate the shortest path!\nIt's calculating *a* path to the finish!\nPath length: #{@path.length}"
      end

      def init(a)
        @a = a;
        @coords = [[0,0]]
        @path   = []
      end

      def calc()
        catch :found do
          search 0,0,@coords # backtrack for solutions (-->coords) and stop! if one is found
          return '*No solution path is possible in this labyrinth!*' if @coords.last != [8,8]
        end

        @coords.each_cons(2) {|old,new| @path << get_direction(old,new)}
        @path
      end

      def consistent(x,y,coords)
        (0..8).member? x and (0..8).member? y and @a[x][y] == 0 and not coords.member?([x,y])
      end

      def search(x,y,coords)
        if x==8&&y==8 # reached finish! abort..
          @coords = coords
          throw :found
        end
        (x+=1;coords << [x,y];search x,y,coords.clone) if consistent(x+1,y,coords)
        (y+=1;coords << [x,y];search x,y,coords.clone) if consistent(x,y+1,coords)
        (x-=1;coords << [x,y];search x,y,coords.clone) if consistent(x-1,y,coords)
        (y-=1;coords << [x,y];search x,y,coords.clone) if consistent(x,y-1,coords)
     end

     def get_direction(old,new) # ...between two points
       if old[0] == new[0]
         if old[1] == new[1]-1 then  'r' # right
         else                        'l' # left
         end
       elsif old[0] == new[0]-1 then 'd' # down
       else                          'u' # up
       end
     end

   end
 end
end