def solve(watermarks, patterns):
	"""Given patterns and watermarks, find all possible mappings
	and print possible encodings."""

	# Each pattern potentially generates multiple mappings.
	# When we have two lists of mappings, we generate
	# a combined list of mappings that is compatible
	# with both input mappings lists.
	import mapping
	mappings = None
	for p in patterns:
		pattern_mappings = mapping.MappingSet()
		# Note that we try to find mappings for this
		# pattern in ALL watermarks before reconciling
		# with previous mapping.  This is because the
		# good mapping may only be found in one watermark.
		# If we start with a "bad" watermark and find
		# bad mappings, then, if we reconcile immediately,
		# we may come to the conclusion that there is no
		# solution, when, in fact, the good mapping will
		# be found if we keep looking.
		for w in watermarks:
			m = p.find_all_mappings(w)
			if m:
				pattern_mappings.extend(m)
		mappings = mapping.reconcile(mappings, pattern_mappings)

	# Loop over each mapping and try to apply it to all
	# watermarks.  If it resolve more than some threshold
	# fraction of all watermarks, print the results.
	threshold = 0.40
	for m in mappings:
		results = {}
		for w in watermarks:
			pv, wv, count = m.decode(w, '_')
			# d = decoded message,
			# count = number of unconverted values
			if count / float(len(pv)) > threshold:
				break
			results[w] = (pv, wv)
		else:
			print("Possible mapping:")
			for pv, wv in results.values():
				_print_pair(pv, wv)
			print('')

def _print_pair(pv, wv):
	i = 0
	total_width = 0
	pl = []
	wl = []
	max_line_width = 72
	while i < len(pv):
		p = repr(pv[i])[1:-1]
		w = repr(wv[i])[1:-1]
		width = max(len(p), len(w))
		pl.append(p.ljust(width))
		wl.append(w.ljust(width))
		total_width += width
		if total_width > max_line_width:
			print(''.join(pl))
			print(''.join(wl))
			total_width = 0
			pl = []
			wl = []
		i += 1
	if total_width > 0:
		print(''.join(pl))
		print(''.join(wl))

if __name__ == "__main__":
	import given
	from watermark import DNAWatermark
	from pattern import StringPattern
	watermarks = [ DNAWatermark(s) for s in given.watermarks ]
	patterns = [ StringPattern(h) for h in given.hints ]

	from mapping import add_mapping
	add_mapping("CCC", "-")
	add_mapping("GAA", "'")
	solve(watermarks, patterns)