#! /usr/bin/env python

"""Solves the Fido Puzzle (<http://digicc.com/fido/>) by brute force. This works, and works quickly enough, but doesn't tell us anything about why!

(c) 2006 Tom Anderson <twic@urchin.earth.li>

Redistribution and use in source and binary forms, with or without modification, are permitted.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

"""

def explode(n, l=None):
	"Turns a number xyz into the sequence [x, y, z]; optionally, l gives the minimum length of the digit string."
	digits = []
	while (n > 0):
		digit = n % 10
		digits.insert(0, digit)
		n = n / 10
	if (l != None):
		while (len(digits) < l):
			digits.insert(0, 0)
	return digits

def implode(digits):
	"Turns a sequence [x, y, z] into the number xyz."
	n = 0
	for digit in digits:
		n = n * 10 + digit
	return n

def permutation(l, i):
	"Makes the ith permutation of the sequence l."
	l_ = list(l); l_.reverse()
	m = []
	for j in xrange(len(l_)):
		m.append(l_.pop((i % len(l_))))
		i = i / (len(l_) + 1)
	m.reverse()
	return m

def factorial(n):
	if (n == 1): return 1
	else: return n * factorial((n - 1))

def permute(l):
	"Returns an iterator over the permutations of l."
	for i in xrange(factorial(len(l))):
		yield permutation(l, i)

def fido(key):
	"Finds the circled digit given the other digits, collectively referred to as the key, by performing an exhaustive search of possible solutions."
	if (isinstance(key, int)):
		key = explode(key)
	key.sort()
	numDigits = len(key) + 1
	# this really just follows the definition of the problem
	for i in xrange(1, (10 ** numDigits)): # i is the number you thought of
		di = explode(i, numDigits)
		for dj in permute(di):
			j = implode(dj) # j is a shuffling of it
			h = abs((i - j)) # h is the result of the subtraction
			dh = explode(h, numDigits)
			for g in xrange(numDigits): # g is the index of the digit to circle
				if (dh[g] == 0):
					continue
				lock = list(dh) # the key has to fit the lock, izerntit
				del lock[g]
				lock.sort()
				if (key == lock):
					return dh[g]