# 'Dominos' script
# by Phill Sacre - http://phillsacre.me.uk
# Finds the longest possible chain from a list of dominos

import random

class Domino:
	def __init__(self, left = None, right = None):
		if left == None:
			left = genRandomValue()
		self.__left = left
		
		if right == None:
			right = genRandomValue()
		self.__right = right
	
	def getLeft(self):
		return self.__left
	
	def getRight(self):
		return self.__right
	
	def __str__(self):
		return 'Domino [%d, %d]' % (self.getLeft(), self.getRight())
	
	def __eq__(self, domino):
		return (self.__left == domino.getLeft() and self.__right == domino.getRight()) or (self.__left == domino.getRight() and self.__right == domino.getLeft())
		
	def __ne__(self, domino):
		return not self.__eq__(domino)

def genRandomValue():
	return random.randint(0, 12)

def getPath(startValue, dominos):
	# If list of dominos is zero, we cannot form a chain.
	if len(dominos) == 0:
		return []
	
	candidates = []
	
	# Find the candidate dominos we can use to continue the chain. If the start value is None, add all dominos as candidates.
	for domino in dominos:
		if None == startValue or domino.getLeft() == startValue or domino.getRight() == startValue:
			candidates.append(domino)
	
	# If there are no candidates to continue, return an empty chain.
	if len(candidates) == 0:
		return []
	
	chains = []
	
	# For each candidate, attempt to find the next 'chain' and return the one with the maximum length.
	for candidate in candidates:
		if candidate.getLeft() == startValue:
			nextValue = candidate.getRight()
		else:
			nextValue = candidate.getLeft()
		
		nextDominos = dominos[:] # Create a clone of the list using slicing - prevent the current dominos list being modified
		nextDominos.remove(candidate) # Remove the current candidate as it will no longer be available to form part of the chain
		
		# Retrieve the chain down the line from the current candidate
		chain = getPath(nextValue, nextDominos)
		if chain != None:
			# Insert the current candidate into the chain, and add it to the list of chains.
			chain[0:0] = [candidate]
			chains.append(chain)
	
	# We are only interested in the longest chain. If chains are equally long, only the first will be used.
	maxChain = None
	
	for chain in chains:
		if maxChain == None or len(maxChain) < len(chain):
			maxChain = chain
	
	return maxChain

def main():
	dominos = []
	while len(dominos) < 15:
		domino = Domino()
		if not domino in dominos:
			dominos.append(domino)
	
	startValue = genRandomValue()
	
	print 'Starting value: %d' % startValue
	
	for domino in dominos:
		print domino
	
	path = getPath(startValue, dominos)
	
	if path == None:
		print 'No chain!'
	else:
		print '%d-link chain can be made' % len(path)
		for domino in path:
			if domino.getLeft() == startValue:
				print '[ %d | %d ]' % ( domino.getLeft(), domino.getRight())
				startValue = domino.getRight()
			else:
				print '[ %d | %d ]' % ( domino.getRight(), domino.getLeft())
				startValue = domino.getLeft()

if __name__ == "__main__":
	main()