#!/usr/bin/env python

class DecatingError(Exception):
	pass

def get_borders(cpos, size, direction=0):
	'''Returns all possible borders in a grid

	direction encompasses all 6 possible directions
	which are ...
		0: right top
		1: right
		2: right bottom
		3: left bottom
		4: left
		5: left top
	eg. (1, 1), 3, 5, 0 => (1, 5)
	'''
	x, y = cpos
	a, b = size

	if direction == 0:
		return (x, b)
	elif direction == 1:
		return (a, y)
	elif direction == 2:
		while x != a and y != 0:
			x, y = (x + 1), (y - 1)
		return (x, y)
	elif direction == 3:
		return (x, 0)
	elif direction == 4:
		return (0, y)
	elif direction == 5:
		while x != 0 and y != b:
			x, y = (x - 1), (y + 1)
		return (x, y)
	else:
		raise DecatingError, 'No valid direction parameter'

def valid_possibilities(p, cpos=None):
	'''Returns all valid possibilities of the input list'''
	# remove equivalents
	p = list(set(p))
	# remove identicals
	if cpos != None:
		while p.count(cpos) > 0:
			try:
				p.remove(cpos)
			except ValueError:
				pass
	return p

# recursion
def valid_solutions(solutions):
	'''Returns all valid solutions of the input solutions

	eg. [(1,0), (3,4), (1,0), (2,1)] is [(1,0), (2,1)]
	'''
	# remove cycles ((a, b, a, c) => (a, c))
	for i in solutions:
		if solutions.count(i) > 1:
			pos1 = solutions.index(i)
			pos2 = solutions.index(i, (pos1+1))
			result = solutions[0:pos1+1] + solutions[pos2+1:]
			return valid_solutions(result)
	return solutions

def avoid_cycle(way, possibilities):
	'''Removes all possible ways which have already been visited'''
	for i in way:
		try:
			possibilities.remove(i)
		except ValueError:
			pass
	return possibilities

# recursion
def found(items, search):
	'''Find search item in list

	eg. found([(1, 0), (2, 3), (4, 5)], 5) is True
	eg. found([(1, 0), (2, 3), (4, 5)], 6) is False
	'''
	for i in items:
		if type(i).__name__ in ('dict', 'list', 'tuple', 'set'):
			return found(i, search)
		if i == search:
			return True
	return False

def get_shortest(liste):
	'''Returns shortest list

	eg. ((1,2,3), (4,5)) return (4,5)
	'''
	try:
		return min(liste, key=len)
	except ValueError:
		raise DecatingError, 'problem not solvable'

def describe_solution(sol, stats):
	'''Tries to describe a solution literally

	sol: the solution to describe
	stats: contains different information about the grid
		width: width of the grid
		height: height of the grid
		search: the search item
	'''

	def get(liste, index):
		'''Get element of list without exception (bool instead)'''
		if index < 0:
			raise IndexError
		if liste.count(index) > 0:
			return liste[index]
		return False
	def io(text):
		'''Append newline at end of string'''
		return text + "\n"

	width, height = stats
	answer = ''

	for num in xrange(1, len(sol)):
		prev, cur = sol[num-1], sol[num]
		empty = io('Truncate container %d.')
		fill = io('Fill up container %d.')
		move = io('Move content of container %d to %d.')

		# (> and >, < and <, = and =) is not possible
		if prev[0] > cur[0] and prev[1] == cur[1]:
			answer += empty % 1
		elif prev[0] < cur[0] and prev[1] == cur[1]:
			answer += fill % 1
		elif prev[0] == cur[0] and prev[1] > cur[1]:
			answer += empty % 2
		elif prev[0] == cur[0] and prev[1] < cur[1]:
			answer += fill % 2
		elif prev[0] > cur[0] and prev[1] < cur[1]:
			answer += move % (1, 2)
		elif prev[0] < cur[0] and prev[1] > cur[1]:
			answer += move % (2, 1)
		else:
			raise DecatingError, 'this is not a valid ' \
				+ 'solution (more than one operation described?'
	return answer.strip()


# eXtreme recursion
def backtrack(pos, depth, way, size, search, max_depth):
	'''Backtracking function

	pos: previous and current position in grid (dynamic)
	depth: current depth in grid (dynamic)
	way: list of current chosen way (dynamic)
	size: width and height of grid (static)
	search: search element (static)
	max_depth: maximum iteration depth in grid (static)
	'''

	global SOLUTIONS, SILENCE

	origin, cpos = pos
	width, height = size
	cway = way[:]
	cway.append(cpos)
	p = []

	# find possible ways
	#	6 ways to the borders
	for i in xrange(6):
		p.append(get_borders(cpos, size, i))
	#	remove the way you are coming from
	try:
		p.remove(origin)
	except ValueError:
		pass
	#	remove doubles/equivalents and identicals
	p = valid_possibilities(p, cpos)
	#	remove ways which will result in cycles
	p = avoid_cycle(cway, p)


	# if EndOfWay
	if max_depth == depth:
		if SILENCE > 2:
			print 'max_depth reached.'
		return False
	if len(p) == 0:
		if SILENCE > 2:
			print 'No additional possibilities.'
		return False
	#if found(poss, search): # not recommended
	if search in cpos:
		if SILENCE > 2:
			print 'found item.'
		if SILENCE > 0:
			print valid_solutions(cway)
		SOLUTIONS.append(tuple(cway))
		return True

	# backtrack all possibilities
	for i in p:
		if SILENCE > 1:
			print (depth * ' ') + str(i)
		backtrack((cpos, i), (depth+1), cway, \
			(width, height), search, max_depth)

if __name__ == '__main__':
	# input
	width  = int(raw_input('maximal elements in container 1: '))
	height = int(raw_input('maximal elements in container 2: '))
	search = int(raw_input('You want to fill up a container with: '))

	# a * b and 4 frame borders
	max_depth = (width * height) + 4

	# global SOLUTIONS
	SOLUTIONS = []
	SILENCE = 0 # 0 (silent), 1, 2 or 3 (loud)

	# Backtracking
	start = (0, 0)
	backtrack((start, start), 0, [], (width, height), search, max_depth)

	print
	print get_shortest(SOLUTIONS)

	print 
	print '== Description of the solution =='
	print describe_solution(get_shortest(SOLUTIONS), (width, height))