To give credit where credit is due: This problem was taken from the ACMICPC-Northwest Regional Programming Contest. Thank you problem writers.

You are helping an archaeologist decipher some runes. He knows that this ancient society used a Base 10 system, and that they never start a number with a leading zero. He's figured out most of the digits as well as a few operators, but he needs your help to figure out the rest.

The professor will give you a simple math expression, of the form

```
[number][op][number]=[number]
```

He has converted all of the runes he knows into digits. The only operators he knows are addition (`+`),subtraction(`-`), and multiplication (`*`), so those are the only ones that will appear. Each number will be in the range from -1000000 to 1000000, and will consist of only the digits 0-9, possibly a leading -, and maybe a few ?s. If there are ?s in an expression, they represent a digit rune that the professor doesn't know (never an operator, and never a leading -). All of the ?s in an expression will represent the same digit (0-9), and it won't be one of the other given digits in the expression. No number will begin with a 0 unless the number itself is  0, therefore 00 would not be a valid number. 

Given an expression, figure out the value of the rune represented by the question mark. If more than one digit works, give the lowest one. If no digit works, well, that's bad news for the professor - it means that he's got some of his runes wrong. output -1 in that case.

Complete the method to solve the expression to find the value of the unknown rune. The method takes a string as a paramater repressenting the expression and will return an int value representing the unknown rune or -1 if no such rune exists.

~~~if:php
**Most of the time, the professor will be able to figure out most of the runes himself, but sometimes, there may be exactly 1 rune present in the expression that the professor cannot figure out (resulting in all question marks where the digits are in the expression) so be careful ;)**
~~~

Difficulty: MEDIUM
Tags: Mathematics

Ad-hoc

Starter code:
def solve_runes(runes):
	

Solutions:
import re

def solve_runes(runes):
	for d in sorted(set('0123456789') - set(runes)):
		toTest = runes.replace('?', d)
		if re.search('([^\\d]|\\b)0\\d+', toTest):
			continue
		(l, r) = toTest.split('=')
		if eval(l) == eval(r):
			return int(d)
	return -1


def solve_runes(runes):
	for c in sorted(set('0123456789') - set(runes)):
		s = runes.replace('?', c).replace('-', ' - ').replace('+', ' + ').replace('*', ' * ').replace('=', ' == ')
		if not any((e[0] == '0' and e != '0' for e in s.split())) and eval(s):
			return int(c)
	return -1


import re

def solve_runes(runes):
	for d in '0123456789':
		if d not in runes:
			if d == '0' and re.search('(^|[+\\-*=])\\?[?\\d]', runes):
				continue
			expr = runes.replace('?', d).replace('=', '==')
			if eval(expr):
				return int(d)
	return -1


import re

def solve_runes(runes):
	runes = runes.replace('=', '==')
	s = bool(re.search('\\b0\\d', runes.replace('?', '0')))
	for d in map(str, range(s, 10)):
		if d not in runes and eval(runes.replace('?', d)):
			return int(d)
	return -1


def solve_runes(runes):
	for i in sorted(set('0123456789') - set(runes)):
		eval_string = runes.replace('?', str(i)).replace('=', '==')
		try:
			if eval(eval_string) and eval_string[-4:] != '==00':
				return int(i)
		except:
			continue
	return -1


import re

def solve_runes(runes):
	m = re.match('(-?[0-9?]+)([-+*])(-?[0-9?]+)=(-?[0-9?]+)', runes)
	nums = [m.group(1), m.group(3), m.group(4)]
	op = m.group(2)
	for v in range(0, 10):
		if str(v) in runes:
			continue
		testNums = [num.replace('?', str(v)) for num in nums]
		for num in testNums:
			if re.match('(^0|^(-0))[0-9]+', num):
				break
		else:
			if int(testNums[2]) == eval(testNums[0] + op + testNums[1]):
				return v
	return -1


import re

def solve_runes(runes):
	m = re.match('{n}([-+*]){n}={n}$'.format(n='(0|-?[1-9?][0-9?]*)'), runes)
	if not m:
		return -1
	(l, op, r, ans) = m.groups()
	start = any((len(s) > 1 and (s[0] == '?' or s[:2] == '-?') for s in (l, r, ans)))
	check = runes.replace('=', '==')
	return next((i for i in range(start, 10) if str(i) not in runes and eval(check.replace('?', str(i)))), -1)


import operator

def solve_runes(runes):
	r = [x for x in runes]
	print(runes)
	a = []
	b = []
	c = []
	d = ['+', '-', '*', '=']
	s = []
	cntr = 0
	scntr = 0
	for i in r:
		if r.index(i) == 0 and r[0] == '-' and (scntr == 0):
			a.append(i)
			scntr += 1
		elif r.index(i) != 0 and i not in d:
			a.append(i)
		elif r.index(i) == 0 and i not in d:
			a.append(i)
		elif r.index(i) != 0 and i in d:
			s.append(i)
			break
		elif i in d and scntr != 0 and (i == '-'):
			s.append(i)
			break
		cntr += 1
	cntr2 = 0
	r1 = r[cntr + 1:]
	for i in r1:
		if r1.index(i) == 0 and r1[0] == '-':
			b.append(i)
		elif r1.index(i) != 0 and i not in d:
			b.append(i)
		elif r1.index(i) == 0 and i not in d:
			b.append(i)
		elif r1.index(i) != 0 and i in d:
			break
		cntr2 += 1
	r2 = r[cntr + cntr2 + 2:]
	for i in r2:
		if r2.index(i) == 0 and r2[0] == '-':
			c.append(i)
		elif r2.index(i) != 0 and i not in d:
			c.append(i)
		elif r2.index(i) == 0 and i not in d:
			c.append(i)
		elif r2.index(i) != 0 and i in d:
			break
	number = list(range(0, 10))
	number2 = list(range(1, 10))
	op = {'+': operator.add, '-': operator.sub, '*': operator.mul}
	alist = [a, b, c]
	ilist = []
	for i in alist:
		for x in i:
			if x == '-' and i.index(x) == 0:
				if i[1] == '?':
					ilist.append('nZero')
					break
			elif x == '?' and i.index(x) == 0 and (len(i) != 1):
				ilist.append('nZero')
				break
			else:
				ilist.append('yZero')
				break
	num = []
	num2 = []
	print((a, b, c))
	for i in number:
		if str(i) not in a and str(i) not in b and (str(i) not in c):
			num.append(i)
	for i in number2:
		if str(i) not in a and str(i) not in b and (str(i) not in c):
			num2.append(i)
	if 'nZero' in ilist:
		for n in num2:
			a1 = [str(n) if x == '?' else x for x in a]
			b1 = [str(n) if x == '?' else x for x in b]
			c1 = [str(n) if x == '?' else x for x in c]
			a1 = int(''.join(a1))
			b1 = int(''.join(b1))
			c1 = int(''.join(c1))
			if op[s[0]](a1, b1) == c1:
				return n
	if 'nZero' not in ilist:
		for n in num:
			a1 = [str(n) if x == '?' else x for x in a]
			b1 = [str(n) if x == '?' else x for x in b]
			c1 = [str(n) if x == '?' else x for x in c]
			a1 = int(''.join(a1))
			b1 = int(''.join(b1))
			c1 = int(''.join(c1))
			if op[s[0]](a1, b1) == c1:
				return n
	return -1


def solve_runes(runes):
	massV = []
	massV_ind = []
	massD1 = []
	massD2 = []
	massD1_ind = []
	massD2_ind = []
	ex = []
	mat = []
	(expr, value) = runes.split('=')
	if expr.find('*', 1) != -1:
		ind = expr.index('*', 1)
		dig_1 = expr[:ind]
		dig_2 = expr[ind + 1:]
		sign = '*'
	elif expr.find('+', 1) != -1:
		ind = expr.index('+', 1)
		dig_1 = expr[:ind]
		dig_2 = expr[ind + 1:]
		sign = '+'
	else:
		ind = expr.index('-', 1)
		dig_1 = expr[:ind]
		dig_2 = expr[ind + 1:]
		sign = '-'
	for i in range(len(value)):
		if value[i] == '?':
			massV_ind.append(value.index(value[i], i))
			massV.append('0')
		else:
			massV.append(value[i])
	for i in range(len(dig_1)):
		if dig_1[i] == '?':
			massD1_ind.append(dig_1.index(dig_1[i], i))
			massD1.append('0')
		else:
			massD1.append(dig_1[i])
	for i in range(len(dig_2)):
		if dig_2[i] == '?':
			massD2_ind.append(dig_2.index(dig_2[i], i))
			massD2.append('0')
		else:
			massD2.append(dig_2[i])
	for i in range(0, 10):
		for q in range(len(massD1_ind)):
			massD1[massD1_ind[q]] = str(i)
		for w in range(len(massD2_ind)):
			massD2[massD2_ind[w]] = str(i)
		for e in range(len(massV_ind)):
			massV[massV_ind[e]] = str(i)
		d1 = int(''.join(massD1))
		d2 = int(''.join(massD2))
		val = int(''.join(massV))
		if sign == '*':
			if d1 * d2 == val:
				ex.append(i)
		if sign == '-':
			if d1 - d2 == val:
				ex.append(i)
		if sign == '+':
			if d1 + d2 == val:
				ex.append(i)
	if dig_1[0] == '-':
		if 1 in massD1_ind:
			if len(massD1) > 1:
				if 0 in ex:
					ex.remove(0)
	elif 0 in massD1_ind:
		if len(massD1) > 1:
			if 0 in ex:
				ex.remove(0)
	if dig_2[0] == '-':
		if 1 in massD2_ind:
			if len(massD2) > 1:
				if 0 in ex:
					ex.remove(0)
	elif 0 in massD2_ind:
		if len(massD2) > 1:
			if 0 in ex:
				ex.remove(0)
	if value[0] == '-':
		if 1 in massV_ind:
			if len(massV) > 1:
				if 0 in ex:
					ex.remove(0)
	elif 0 in massV_ind:
		if len(massV) > 1:
			if 0 in ex:
				ex.remove(0)
	for i in runes:
		if i in '1234567890':
			mat.append(int(i))
	mat = set(mat)
	if len(ex) == 0:
		return -1
	else:
		for i in ex:
			if i in mat:
				continue
			else:
				return i
	return -1


import re

def solve_runes(runes):
	for i in sorted(set(''.join([str(i) for i in range(10)])) - set(runes)):
		var = runes.replace('?', i)
		if re.search('([^\\d]|\\b)0\\d+', var):
			continue
		(expr, result) = var.split('=')
		if eval(expr) == eval(result):
			return int(i)
	return -1