#!/usr/bin/ruby

class Problem
    @matrix
    @initial
    attr_reader :colors, :width
    def initialize(width = 14, colors = 6)
        srand 42
        @colors = colors
        @width = 14
        @matrix = Array.new(@width, Array.new(@width))
        @matrix.map! {|line| line.map {rand(@colors)} }
        @initial = Marshal.load(Marshal.dump(@matrix))
    end

    def reset
        @matrix = Marshal.load(Marshal.dump(@initial))
    end

    def to_s
        str = ""
        @matrix.each do |line|
            str << line.inject("|"){|r,el| r + el.to_s + "|"} << "\n"
        end
        return str
    end

    def propagate col
        origine = @matrix[0][0]
        closed = []
        open = [[0,0]]
        while !open.empty? do
            x,y = open.pop
            closed << [x,y]
            open << [x-1,y] if x > 0 && @matrix[x-1][y] == origine && !closed.index([x-1,y])
            open << [x+1,y] if x < @width-1 && @matrix[x+1][y] == origine && !closed.index([x+1,y])
            open << [x,y-1] if y > 0 && @matrix[x][y-1] == origine && !closed.index([x,y-1])
            open << [x,y+1] if y < @width-1 && @matrix[x][y+1] == origine && !closed.index([x,y+1])
            @matrix[x][y] = col
        end
    end

    # propage toutes les couleurs et donne le score
    # nombre d'essais + points restant à la fin
    def propagate_all colors
        colors.each_with_index do |col,i|
            propagate col
            return i if score == @width * @width
        end
        return colors.size + (@width * @width - score)
    end

    def eval colors
        mark = propagate_all colors
        reset
        return mark
    end

    def score
       color = @matrix[0][0]
       return @matrix.inject(0){ |r,l|
           r + l.inject(0){|r2,e| if e == color then r2 + 1 else r2 end }
       }
    end
end

class Solver
    attr_reader :population
    def initialize problem
        @population = []
        @nb = 30
        @x_rate = 0.1
        @mutation_rate = 0.1
        @length = 40
        @problem = problem
        0.upto @nb-1 do
            @population << Array.new(@length) { rand(@problem.colors) }
        end
    end

    def cross
        father = @population[rand(@population.size)]
        mother = @population[rand(@population.size)]
        puts "mom", father.length if father.length != @length
        puts "dad", mother.length if mother.length != @length
        cut = rand(@length)
        son = father.slice(0..cut-1)
        if son == nil
            print father, "(", cut
        end
        son.concat(mother.slice(cut..-1))
        if son.size != @length
            puts "WFTF?/?", son.length
        end
        @population << son
        son = mother.slice(0..cut-1)
        if son == nil || father.slice(cut..-1) == nil
            print father, "(", cut
        end
        son.concat(father.slice(cut..-1))
    end

    def mutate
        @population[rand(@population.size)][rand(@lenght)] = rand(@problem.colors)
    end

    def filter
        @population.sort! do |a,b|
             @problem.eval(a) <=> @problem.eval(b)
        end
        @population.slice!(@nb..-1)
    end

    def run
        10.times do
            cross
            mutate if rand < @mutation_rate
        end
        filter

        @population.each{|p| puts "Score=" + (@problem.eval p).to_s }
    end

end