2
\$\begingroup\$

The exercise is as follows:

Given K digits, show all the arithmetic expressions that yield a requested value (N), using four basic arithmetic operations. Each number should be used exactly one time, and the order of the digits may be changed. Don't use parenthesis.

Example:

K = 1, 6, 7, 9

N = 10

One possible solution: 1 * 7 + 9 - 6

Another one: 9 + 7 - 6 / 1

My code:

import itertools
from typing import (Sequence, Iterable, Iterator,
                    Union, Optional,
                    List, NamedTuple)

ALLOWED_OPERATORS = ('*', '/', '+', '-')  # , '**)
REPEAT_NUMBERS = False
DigitsSequence = Union[str, Sequence[Union[str, int]]]


class Answer(NamedTuple):
    solution: Optional[int]
    expression: str


def normalize_input(digits: DigitsSequence) -> List[str]:
    try:
        new_digits = list(map(str, digits))  # type: ignore
        if not all(map(str.isdecimal, new_digits)):
            raise TypeError
    except TypeError:
        print("Digits must be an iterable containing strings.")
        return []
    return new_digits


def any_order(items: Sequence, length: int=None, allow_repeats: bool=True) \
              -> Iterable:
    if length is None:
        length = len(items)

    if allow_repeats:
        yield from itertools.product(items, repeat=length)
    else:
        yield from itertools.permutations(items, r=length)


def zip_to_str(expression: Iterable) -> str:
    return ''.join(''.join(i) for i in expression)


def get_answer(digits: List[str], operators: Sequence) -> Answer:
    expression = zip_to_str(zip(digits, operators)) + digits[-1]
    try:
        return Answer(solution=eval(expression), expression=expression)
    except ZeroDivisionError:
        return Answer(solution=None, expression=expression)


def solver(digits: DigitsSequence, solution: int) -> Iterator[str]:
    assert isinstance(solution, int), "Solution must be a number."
    all_digits = normalize_input(digits)

    for operators in any_order(ALLOWED_OPERATORS, length=len(all_digits)-1):
        for digits_option in any_order(all_digits, allow_repeats=REPEAT_NUMBERS):
                answer = get_answer(digits_option, operators)
                if answer.solution == solution:
                    yield answer.expression


if __name__ == '__main__':
    for solution in solver('1679', solution=27):
        print(solution)
\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

solution, Answer, and get_answer()

Your terminology is confusing. Consider the penultimate line:

for solution in solver('1679', solution=27):

You've used "solution" to mean two different things: a target value, and an expression that would evaluate to that value.

Also consider:

class Answer(NamedTuple):
    solution: Optional[int]
    expression: str

What's the difference between an "answer" and a "solution"? Most people would consider those terms to be synonymous.

In any case, I think that the entire Answer class is overkill. All of the expressions of interest will evaluate to a certain value, and you don't need a data structure to help you discard the expressions that miss.

A function that is named get_…() sounds like it should be retrieving something that already exists. Your get_answer() function, though, is actually constructing an object.

normalize_input()

This function seems to exist mainly to validate that all of the digits are indeed digits, and also to stringify them all, if necessary. In the solution below, I accomplish that with a one-liner:

numbers = [str(int(str(n), base=10)) for n in numbers]

I think that manually calling raise TypeError is more awkward than letting it occur naturally in an attempted conversion. Furthermore, I don't think that printing a diagnostic message and returning an empty list is an appropriate way to handle such a failure. It would be more appropriate to handle the exception near the code where the input came from.

By the way, nothing about the implementation requires that the numbers be single digits. You could just as readily call solver([1, 16, 7, 9], 1), and the code should work. Therefore, I recommend changing the terminology from "digits" to "numbers".

any_order()

I don't see much point in creating one overloaded function with two modes. You would be better off eliminating this function altogether

zip_to_str()

This function is awkward to use:

zip_to_str(zip(digits, operators)) + digits[-1]

Not only do you have to call zip() to form the parameter, you also have to awkwardly append digits[-1]. To address the latter issue, you can use itertools.zip_longest(…, fillvalue='').


Suggested solution

Getting rid of the problematic code results in a much simpler implementation. (Feel free to add back the type annotations, if you prefer.)

from itertools import permutations, product, zip_longest

def arithmetic_expressions(numbers, operators):
    # Cast to int for validation, then to str for composing the expression
    numbers = [str(int(str(n), base=10)) for n in numbers]
    for ops in product(operators, repeat=len(numbers) - 1):
        for nums in permutations(numbers):
            yield ''.join(
                num + op
                for num, op in zip_longest(nums, ops, fillvalue='')
            )

def solver(numbers, solution):
    for expression in arithmetic_expressions(numbers, '+-*/'):
        try:
            if eval(expression) == solution:
                yield expression
        except ZeroDivisionError:
            pass

if __name__ == '__main__':
    for expr in solver([1, 16, 7, 9], 1):
        print(expr)
\$\endgroup\$
2
\$\begingroup\$

The logic in normalize_input() is a bit bizarre. First, to your credit, you are doing DbC (design by contract) and enforcing a pre-condition. I would rather see the not all test performed immediately upon entry, rather than after computing new_digits. But then your error check raises and immediately catches. Please don't do that. Just use an if instead. Returning an exception to the caller might be better than returning an empty list. If we're going down the type safety route, I guess I'm wondering why a DigitsSequence would let a bad input to sneak in in the first place. I'm a little sad that we need to admit potentially non-numeric str, and can't make that type the output of some validation function.

You wrote "Digits must be an iterable containing strings." where "Digits must be a numeric string." seems more accurate. A different test would have been to assert str(int(digits)) == digits. You're using defensive programming, but it's not clear just who you're defending against.

I'm looking at any_order. I am relatively new to PEP484 annotations. I feel allow_repeats: bool=True completely makes sense, but OTOH length: int=None seems a bit odd, as None clearly doesn't appear on the number line. Would a sentinel of -1 instead of None maybe be a better idiom here? Or should I be viewing this in terms of the java int vs Integer distinction, where potentially we can always have a null object? If None is the appropriate pythonic way to phrase it (definitely true before PEP484), then should we maybe dispense with annotations for that particular parameter?

The specification is fairly clear:

Each number should be used exactly one time,

therefore I recommend deleting the REPEAT_NUMBERS global, and inverting the allow_repeats default value.

expression = zip_to_str(zip(digits, operators)) + digits[-1]

This is insane. I think you're making the observation that len(digits) = 1 + len(operators), but the code never enforces that. I would much much rather see zip(digits[:-1], operators) and then tack on the last element. Say what you mean and mean what you say.

solver() has a 2nd parameter of solution. For consistency, I would prefer to see Answer have a 2nd parameter of solution.

I have my doubts about DigitsSequence: (1) maybe it's the sort of thing that offers false assurances, which gives type systems a bad name, or (2) maybe what we really wanted was to pass in the results of list(map(int, digits)).

I am reading this line:

for operators in any_order(ALLOWED_OPERATORS, length=len(all_digits)-1):

I have no idea why the signature of any_order mentions length: int=None. That makes no sense to me. I recommend no default for that parameter.

I am reading this line:

    for digits_option in any_order(all_digits, allow_repeats=REPEAT_NUMBERS):

It essentially asks for permutations of all_digits. I'm not understanding how digits_option reflects that; it appears to me to be an ill-chosen name. I recommend digit_permutation instead.

It appears to me that Answer is not quite an accurate name - PotentialAnswer or CandidateAnswer seem closer. To retain the current name, we'd have to push the if answer.solution == solution test down into that class.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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