begin
  require 'lib/charlie'
rescue LoadError
  require 'rubygems'
  require 'charlie'
end

class Symbol
  # This one works with ALL the RVMs. Charlie's default or the Rubinius' one doesn't work with Rubinius!
  def to_proc
    Proc.new { |*args| 
      obj = args.shift
      args.empty? ? obj.__send__(self) : obj.__send__(self, *args)
    }
  end if RUBY_VERSION < '1.9'
end

def TSPGenotype(costs)
  n = costs.size
  elements = (0...n).to_a

  Class.new(Genotype) {
    define_method(:size){ n }
    define_method(:elements){ elements }

    define_method(:fitness){
      d=0
      (genes + [genes[0]]).each_cons(2) do |a,b|
        d += costs[a][b]
      end
      -d
    }

    def initialize
      @genes = elements.dup.shuffle
    end

    def to_s
      @genes.inspect
    end

    use TournamentSelection, 
        PCrossN(EdgeRecombinationCrossover=>0.02, PermutationCrossover=>0.75), 
        PMutateN(InversionMutator=>0.4,InsertionMutator=>0.4)

    cache_fitness
  }
end

class TSPSolver

  def initialize(costs = {})
    @costs = costs
    @genotype = TSPGenotype(costs)
  end

  def solve!
    population = Population.new(@genotype,100).evolve_silent(1000)
    fittest = population[0]
    solution = @costs.sort_by{ |point| fittest.genes.index(point[0]) }
    # p solution
    puts fittest.fitness
    puts fittest
  end

  # The coords hash must be in the following form:
  # {
  #   0 => [x1, y1],
  #   1 => [x2, y2],
  #   etc...
  # }
  # where x1,y1 are Integers and represent the cartesian coordinates of the "city" of the associated key (number).
  def self.from_cartesian_coords(coords = {}, real_distance = false)    
    costs = {}
    coords.each do |point, v|
      costs[point] = {}
    end

    if real_distance
      raise "Real distance not implemented"
    else
      coords.each do |a_key, a_values|
        coords.each do |b_key, b_values|
          if a_key != b_key and costs[a_key][b_key] == nil
            d = Math.sqrt( (a_values[0]-b_values[0])**2 + (a_values[1]-b_values[1])**2 )
            costs[a_key][b_key],costs[b_key][a_key] = d,d
          end
        end
      end
    end

    solver = self.new(costs)
  end

  def self.example(n = 100)
    grid = (0...n).map{|i| (0...n).map{|j| [i,j] } }.inject{|a,b|a+b}
    tmp_grid = Array.new(grid)
    coords = {}
    n.times do |city_num|
      coords[city_num] = tmp_grid.delete_at((rand(10000) - coords.size).to_i)
    end
    example = self.from_cartesian_coords(coords)
  end
end

TSPSolver.example.solve!