require 'yaml'
require 'bmp'

class MatchFinder
	def initialize(filelist)
		@filelist = filelist
		@imgdata = {}
	end

	def read_borders
		(@filelist - @imgdata.keys).each { |n|
			@imgdata[n] = [[], []]
			i = Bmp.load n
			w = i.width-1
			(i.height-1).times { |h|
				@imgdata[n].first << i.pix(0, h)
				@imgdata[n].last  << i.pix(w, h)
			}
		}			
	end

	def grey(c)
		(0.299*c[0] + 0.587*c[1] + 0.114*c[2]).to_i
	end
	
	def get_affinity(set1, set2)
		set1.zip(set2).map { |a, b| (grey(a)-grey(b))**2 }.inject { |a, b| a+b }
	end
		
	def calc_affinity
		@affinity = Hash.new
cur = 0
max = @filelist.length
		@filelist.each { |n1|
$stdout.print "#{(cur+=1) * 100 / max}%     \r" ; $stdout.flush
			@affinity[n1] = {}
			@filelist.each { |n2|
				@affinity[n1][n2] = get_affinity(@imgdata[n1].last, @imgdata[n2].first)
			}
		}
	end

	def dump(f)
		File.open(f, 'w') { |fd| fd.puts YAML.dump(@affinity) }
	end

	def load(f)
		@affinity = YAML.load File.read(f)
	end
	
	def solve
		read_borders
		calc_affinity
	end

	def solution(hint = nil)
		nxt = Hash.new
		@affinity.each { |n1, v1|
			m = v1.keys.first
			mv = v1[m]
			v1.each { |n2, v2|
				if v2 < mv
					m = n2
					mv = v2
				end
			}
			nxt[n1] = m
		}
		
		seen = Hash.new
		passed = Hash.new
		sol = [[]]
		@filelist.each { |n|
			passed[n] = true
			next if seen[n]
			pred = nxt.index n
			next if pred and not passed[pred]
			while n and not seen[n]
				sol.last << n
				seen[n] = true
				n = nxt[n]
			end
			sol << []
		}
		sol.pop

		sol.each { |ssol|
			if ssol.grep(/#{hint}/)
				loop do
					break if ssol.first =~ /#{hint}/
					ssol.unshift ssol.pop
				end
			end
		} if hint
			
		sol
	end

	def create_solution(sfn, *a)
		system "convert #{solution(*a).flatten.join ' '} +append #{sfn}"
	end
end

raise "Usage: findsol [1st] f1.bmp f2.bmp f3.bmp..." if ARGV.empty?

hint = ARGV.shift if ARGV.first =~ /^\d+$/

mf = MatchFinder.new ARGV

DmpFile = 'sol.dmp'
if File.exist? DmpFile
	mf.load DmpFile
else
	mf.solve
	mf.dump DmpFile
end

p mf.solution(hint)
mf.create_solution 'solution.bmp', hint