# Solution au defi Ruby #3 - Des chiffres et des lettres
# copyright 2007 - Jean-Marc Lagace (jean-marc.lagace@m2i3.com)
#
require 'timeout'
require 'thread'

module ChiffreLettre
	MATH_OPERATIONS = [:+,:-,:*,:/]
	
	class CalculInvalide < Exception; end
	
	class Solver
		attr_reader :meilleure_solution
	
		@mutex = nil
		@resultat_meilleure_solution = 0
		@meilleure_solution = []
		@thread_recherche = []
		@mutex
		
		def initialize()
			@mutex = ::Mutex.new
		end
				
		def calculate(operation)
			result=0.0
			operation.each {|operation_mathematique,nombre|
				result = result.send(operation_mathematique,nombre)
				
				raise CalculInvalide,"Le nombre doit rester entier" if result.to_i != result 
				raise CalculInvalide,"Les nombres negatifs ne sont pas permis" if result < 0
			}
			return result
		end

		def explore_espace_solution_etendu(selected, available)
			if available.size > 0 
				available.each {|n|
					MATH_OPERATIONS.each {|o|						
						explore_espace_solution_etendu(selected + [[o,n]], available - [n])
					}
				}
			else
				begin
				result = calculate(selected) 
				rescue CalculInvalide
				else				
					if result <= @resultat_attendu					
						if result > Thread.current["resultat_meilleure_solution"]
							Thread.current["meilleure_solution"] = selected
							Thread.current["resultat_meilleure_solution"] = result							
							if result == @resultat_attendu 																		
								@mutex.synchronize {
									@thread_recherche.each {|aThread| aThread.exit}
								}														
							end
						end
					
					end				
				end
			end
		end
		
		def explore_espace_solution(available, resultat_attendu)
			@resultat_attendu = resultat_attendu			
			@thread_recherche = []			
			
			available.each {|n|	
				@thread_recherche << Thread.new(available, n) {|my_available, myn|						
					Thread.current["resultat_meilleure_solution"]  = 0
					Thread.current["meilleure_solution"] = []
					explore_espace_solution_etendu([[:+,myn]], my_available - [myn])					
				}			
			}
	
			@thread_recherche.each { |aThread|  aThread.join }
			
			best_thread = @thread_recherche.sort {|a,b| (a["resultat_meilleure_solution"] <=> b["resultat_meilleure_solution"]) * -1}.first
			@resultat_meilleure_solution = best_thread["resultat_meilleure_solution"] 
			@meilleure_solution = best_thread["meilleure_solution"]
		end
	end
end


def defi_le_compte_est_bon(nombres_disponibles,resultat_attendu)
	puts "======================================================"
	puts "recherche de la meilleure solution pour #{resultat_attendu} avec " + nombres_disponibles.join(',')
	puts "recherche en cours..."
	start = Time.now
	solver = ChiffreLettre::Solver.new
	begin
	timeout(60){	
		solver.explore_espace_solution(nombres_disponibles,resultat_attendu)
	}
	rescue Timeout::Error
	end
	puts "La recherche a ete complete en %i seconde(s)"%[(Time.now - start).to_i ]
	if solver.meilleure_solution.size > 0 
		puts "La meilleure solution trouvee est: "  + solver.meilleure_solution[0][1].to_s + ' ' + solver.meilleure_solution[1..100].collect {|o,n| o.to_s + ' ' +n.to_s}.join(' ')	
		puts "pour un resultat de : " + solver.calculate(solver.meilleure_solution).to_i.to_s
	else
		puts "aucun resultat trouve"
	end
	puts "======================================================"		
end

# test d'optimisation sur des solutions pré-établie
#defi_le_compte_est_bon([3,7,9,75,2,25],980)
#defi_le_compte_est_bon([100,8,9,4,75,10],750)


15.times {
	resultat_attendu = rand(900) + 100
	numbers = [1,2,3,4,5,6,7,8,9,10,25,50,75,100]
	nombres_disponibles = []
	6.times {		
		nombres_disponibles << numbers.slice!(rand(numbers.size))		
	}
	defi_le_compte_est_bon(nombres_disponibles,resultat_attendu)
}