import time

def displayJugs(arr):
	print("J8:", 'O'*arr[0])
	print("J5:", 'O'*arr[1])
	print("J3:", 'O'*arr[2])


BEST = 999 #Effectively infinity

def jugSolver(j8, j5, j3, depth):
	global BEST

	print("Depth: %d" % depth)
	print("Best: %d" % BEST)
	displayJugs([j8,j5,j3])
	print("------------")

	#Base Case / Stopping Condition
	if j8 == 4 or j5 == 4:
		print("\033[32m^Solution Found^\033[0m")
		if (depth < BEST):
			BEST = depth
		time.sleep(.5)
		return

	#No need to waste time exploring paths that are suboptimal
	if depth == BEST or depth > 9:
		return

	if j8 > 0:
		if j5 < 5:
			x = 5 - j5 #Amount j5 can be given
			y = max(0, j8 - x) #Don't let j8 be negative
			z = j8 - y #Amount j8 can give to j5
			jugSolver(y, j5 + z, j3, depth+1)
		if j3 < 3:
			x = 3 - j3
			y = max(0,j8 - x)
			z = j8 - y
			jugSolver(y, j5, j3 + z, depth+1)

	if j5 > 0:
		if j8 < 8:
			x = 8 - j8
			y = max(0, j5 - x)
			z = j5 - y
			jugSolver(j8 + z, y, j3, depth+1)
		if j3 < 3:
			x = 3 - j3
			y = max(0, j5 - x)
			z = j5 - y
			jugSolver(j8, y, j3 + z, depth+1)

	if j3 > 0:
		if j8 < 8:
			x = 8 - j8
			y = max(0, j3 - x)
			z = j3 - y
			jugSolver(j8 + z, j5, y, depth+1)
		if j5 < 5:
			x = 5 - j5
			y = max(0, j3 - x)
			z = j3 - y
			jugSolver(j8, j5 + z, y, depth+1)

jugSolver(8,0,0, 0)

print("Fastest Solution Requires %d Moves" % BEST)