class Cypher
	protected
		attr_reader :encrypter, :decrypter
	public

	def initialize(encrypter = Array.new(26), decrypter = Array.new(26) )
		@encrypter = encrypter
		@decrypter = decrypter
	end

	def Cypher.fromString(phrase)
		encrypter = []
		decrypter = []
		phrase = phrase.upcase + "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
		i = ?A
		phrase.each_byte { |b|
			if !encrypter.member?(b.chr) && b != ?\  then
				encrypter << b.chr
				decrypter[b - ?A] = i.chr
				i += 1
			end
		}

		Cypher.new(encrypter, decrypter)
	end

	def shift!(positions = 1)
		rotate(@encrypter, positions)
		rotate(@decrypter, -positions)
	end

	def merge(cypher)
		encrypter = []
		cypher.encrypter.each_with_index { |char, i| 	
			if (char && @encrypter[i] && char != @encrypter[i])
				raise "Cyphers are incompatible"
			end

			encrypter << (char || @encrypter[i])
		}

		decrypter = cypher.decrypter.clone

		Cypher.new(encrypter, decrypter)
	end


	def build(encrypted, decrypted)
		if (CanonicalMap.new << decrypted != CanonicalMap.new << encrypted) 
			raise "Strings are not isomorphic"
		end

		encrypted = encrypted.upcase
		decrypted = decrypted.upcase

		for i in 0..decrypted.length - 1 do
			d = decrypted[i]
			e = encrypted[i]
			
			if d == ?\ || e == ?\ || e == ?\' || d == ?\' and d != e
				raise "Strings are not isomorphic"  
			end

			if d != ?\ && e != ?\ && d != ?\' && e != ?\' then
				if @decrypter[e - ?A] && @decrypter[e - ?A] != d.chr or 
				   @encrypter[d - ?A] && @encrypter[d - ?A] != e.chr
					raise "Phrase is incompatible with current cypher"
				end

				@decrypter[e - ?A] = d.chr
				@encrypter[d - ?A] = e.chr
			end
		end

		self
	end

	def to_s
		@encrypter.collect { |e| e ||= '.' }.to_s
	end

   private
	def rotate(array, positions)
		positions = positions % array.length;

		if positions > 0
			(array << array.slice!(0, array.length - positions)).flatten!
		end
		if positions < 0
			(array << array.slice!(0, -positions)).flatten!
		end
	end
end


class CanonicalMap
	def initialize
		@map = {}
		@currentIndex = 64
	end

	def <<(chars)
		result = ""
		chars.each_byte { |char|
			index = @map[char] ||= (@currentIndex += 1)
			result << index
		}
		result
	end
end

class Parser
	PATTERN = Regexp.new("^((.+), (.+?)[ ]?(\\([IVXL]+\\))?)\t(.+?) \\(([0123456789]+)\\).*") 

	def initialize(file)
		@file = file
	end
	
	def each
		last = nil
		File.foreach(@file) { |line|
			result = PATTERN.match(line)
			if result 
				name = (result[3] + " " + result[2]).upcase
				if name != last
					yield name
					last = name
				end
			end
		}
	end
end

class Person
	def initialize
		@encrypted = nil
		@alternatives = []
		@canonical = nil 
		@pair = nil
		@name = nil
		@cypher = Cypher.new
	end

	attr_reader :encrypted, :alternatives, :pair, :name
	attr_writer :encrypted, :alternatives, :pair, :name

	def canonical
		@canonical ||= CanonicalMap.new << encrypted 
	end


	def cypher
		result = Cypher.new
		result.build(@encrypted, @name)
	end
end

def load(file)
	names = {} 
	File.foreach(file) { |line|
		name = Person.new
		name.encrypted = line.chomp
		names[name.canonical] = name 
	}
	names
end

def analyze(namesFile, encryptedNamesFile)
	people = load(encryptedNamesFile)
	parser = Parser.new(namesFile)
	parser.each { |name|
		person = people[(CanonicalMap.new << name)]

		if person
			person.alternatives << name
		end	
	}

	people
end

def match(men, women)
	result = []
	men.values.each { |man|
		man.alternatives.each { |manName|
			women.values.each { |woman|
				woman.alternatives.each { |womanName|
					decryptedMap = CanonicalMap.new
					decryptedString = decryptedMap << manName
					decryptedString << (decryptedMap << womanName)
					
					encryptedMap = CanonicalMap.new
					encryptedString = encryptedMap << man.encrypted
					encryptedString << (encryptedMap << woman.encrypted)

					if decryptedString == encryptedString 
						man.name = manName
						woman.name = womanName

						result << [man, woman]
					end
				}
			}
		}
	}
	result
end 


begin
	file = File.new("men.dat")
	men = Marshal.load(file)
	file.close
	puts "men.dat found"
rescue
	puts "men.dat not found... rebuilding"
	men = analyze("actors.list", "men.txt")
	file = File.new("men.dat","w")
	Marshal.dump(men, file)
	file.close
end


begin
	file = File.new("women.dat")
	women = Marshal.load(file)
	file.close
	puts "women.dat found"
rescue
	puts "women.dat not found... rebuilding"
	women = analyze("actresses.list", "women.txt")
	file = File.new("women.dat","w")
	Marshal.dump(women, file)
	file.close
end

begin
	file = File.new("matches.dat")
	matches = Marshal.load(file)
	file.close
	puts "matches.dat found"
rescue
	puts "matches.dat not found... rebuilding"
	matches = match(men, women)
	file = File.new("matches.dat","w")
	Marshal.dump(matches, file)
	file.close
end

menTranslations = File.new("menTranslations.txt", "w")
womenTranslations = File.new("womenTranslations.txt", "w")
movies = File.new("movies.txt")
movies.each { |movie|
	movie.chomp!
	cypher = Cypher.fromString(movie)

	matchingEntry = nil	
	catch (:done) do
		for i in (0..25) do
			matches.each{ |entry|
				begin
					# attempt to merge the movie cypher with the actor cypher
					# if an exception is thrown (i.e. cyphers are incompatible)
					# try with the next actor
					# otherwise, we found a match, so bail out and 
					# continue with the next movie
					cypher.merge(entry[0].cypher)
					matchingEntry = entry
					throw :done
				rescue
				end
			}
			# if we've tested all actors, shift the movie cypher by 1 position 
			# and try again
			cypher.shift!
		end
	end
	if matchingEntry
		puts "#{cypher.to_s}\t#{movie}: #{matchingEntry[0].name}/#{matchingEntry[1].name}"

		menTranslations << "#{matchingEntry[0].encrypted}\t#{matchingEntry[0].name}\n"
		womenTranslations << "#{matchingEntry[1].encrypted}\t#{matchingEntry[1].name}\n"
	end
}
menTranslations.close
womenTranslations.close