2
\$\begingroup\$

Kata: https://www.codewars.com/kata/find-the-unknown-digit/train/python

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.


My Solution

import re, operator as op

parse_op = re.compile(r"(-?[0-9?]+)([-+*])(-?[0-9?]+)(=)(-?[0-9?]+)")  #For parsing the LHS.
ops = {"*": op.mul, "+": op.add, "-": op.sub}

def solve_runes(s):
    search = set("0123456789") - set(c for c in s if c.isnumeric())
    n = [0]*3
    n[0], op, n[1], x, n[2] = parse_op.search(s).groups()
    if any(len(x) > 1 and x[0] == "?" for x in n):
        search -= {"0"}
    for digit in sorted(search):
        v = [int(x.replace("?", digit)) for x in n]
        if ops[op](v[0], v[1]) == v[2]:
            return int(digit)
    return -1

Sample Test Case

test.assert_equals(solve_runes("1+1=?"), 2, "Answer for expression '1+1=?' ")  
test.assert_equals(solve_runes("123*45?=5?088"), 6, "Answer for expression '123*45?=5?088' ")  
test.assert_equals(solve_runes("-5?*-1=5?"), 0, "Answer for expression '-5?*-1=5?' ")  
test.assert_equals(solve_runes("19--45=5?"), -1, "Answer for expression '19--45=5?' ")  
test.assert_equals(solve_runes("??*??=302?"), 5, "Answer for expression '??*??=302?' ")  
test.assert_equals(solve_runes("?*11=??"), 2, "Answer for expression '?*11=??' ")  
test.assert_equals(solve_runes("??*1=??"), 2, "Answer for expression '?*11=??' ")  
\$\endgroup\$
1
\$\begingroup\$

In this code, I find it misleading that n is first assigned zeros, and then its content is replaced with strings.

n = [0]*3
n[0], op, n[1], x, n[2] = parse_op.search(s).groups()

I think it would be more clear this way:

num1, op, num2, _, num3 = parse_op.search(s).groups()
nums = [num1, num2, num3]

Notice that I replaced x with _. It's a common convention when a variable is unused.

Some doctests with example inputs and expected outputs would be great too, making the code easier to digest, and play with.

\$\endgroup\$
  • \$\begingroup\$ I'll add the sample tests from the provided kata. \$\endgroup\$ – Tobi Alafin Mar 8 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.