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: interview

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(r'([^\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(r'\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):
    # Sorted set subtraction returns a list of elements in the first set that weren't in the second
    for i in sorted(set('0123456789')-set(runes)):
        # Prepare string for eval
        eval_string = runes.replace('?', str(i)).replace('=','==')
        # Python 3 gives an error if an int starts with 0.
        # We use it for our advantage. Also check that result is not 00
        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(r'(-?[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]
        
        # 0起始校验
        for num in testNums:
            if re.match(r"(^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(r'{n}([-+*]){n}={n}$'.format(n=r'(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 = []                # more lists to the god of lists!!!!!!!!!!!
    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)

                                                # hate
    if dig_1[0] == '-':
        if 1 in massD1_ind:
            if len(massD1)>1:                 
                if 0 in ex:
                    ex.remove(0)
    else:
        if 0 in massD1_ind:
            if len(massD1)>1:
                if 0 in ex:
                    ex.remove(0)
                                                # minuses                    
    if dig_2[0] == '-':
        if 1 in massD2_ind:
            if len(massD2)>1:               
                if 0 in ex:
                    ex.remove(0)
    else:
        if 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)
    else:
        if 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:                         # rofl-master
                return i                  # 3 hours
    return -1                             # ------   o,o   -------    -_-

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(r'([^\d]|\b)0\d+', var): 
          continue
        expr,result = var.split("=")
        if eval(expr) == eval(result): 
          return int(i)
    return -1