ShortAccountsMakeLongFriend

ShortAccountsMakeLongFriend_.py

import sys
from copy import deepcopy


def debug(*kwargs):
    return print("!", *kwargs, file=sys.stderr)


OPERATORS = {
    'add': lambda a, b: a + b,
    # 'sub': lambda a, b: a - b,
    'mul': lambda a, b: a * b  # ,
    # 'div': lambda a, b: int(a / b)
}


class Token:
    def __init__(self, index, is_operator=False, is_number=False):
        self.index = index
        if is_operator and not is_number:
            self.is_operator = True
            self.operator = OPERATORS[index]
        elif is_number and not is_operator:
            self.is_operator = False
            self.number = numbers[index]
        else:
            raise ValueError("is_number=" + str(is_number) + ' is_operator=' + str(is_operator))

    def __repr__(self):
        if self.is_operator:
            return self.index + "()"
        else:
            return '[' + str(self.index) + ']:' + str(self.number)


class ReversePolandNotation:
    def __init__(self, tokens=None, calc=None):
        if tokens is None:
            tokens = []
            calc = []
        if len(tokens) >= 2 and (tokens[0].is_operator or tokens[1].is_operator):
            raise ValueError("tokens=" + str(tokens))
        self._tokens = tokens

        self.num_operators = len(list(filter(lambda x: x.is_operator, self._tokens)))
        self.num_numbers = len(self._tokens) - self.num_operators
        self.is_correct = self.num_numbers == (self.num_operators + 1)
        self.calc = calc

    def __repr__(self):
        return '"' + " ".join(list(map(str, self._tokens))) + '" correct=' + str(self.is_correct)

    def add_token(self, new_token):
        if len(self._tokens) < 2 and new_token.is_operator:
            return False
        if not new_token.is_operator:
            for self_token in self._tokens:
                if new_token.index == self_token.index:
                    return False

        if new_token.is_operator and self.num_numbers == self.num_operators + 1:
            return False

        result_calc = ReversePolandNotation.calculate(self.calc, new_token)
        if not result_calc:
            return False

        result_tokens = deepcopy(self._tokens)
        result_tokens.append(new_token)
        return ReversePolandNotation(result_tokens, result_calc)

    @staticmethod
    def calculate(prev_calc, new_token):
        stack = deepcopy(prev_calc)
        if new_token.is_operator:
            if len(stack) < 2:
                return False
            b = stack.pop()
            a = stack.pop()
            if (new_token.index == 'div' and (b == 0 or a % b != 0)) or (new_token.index == 'sub' and a < b):
                return False
            stack.append(new_token.operator(a, b))
        else:
            stack.append(new_token.number)

        return stack


# target_result = int(input())
# numbers = [int(i) for i in input().split()]
target_result = 999
numbers = [int(i) for i in '1 2 2 3 3 1'.split()]

available_tokens = [Token(x, is_operator=True) for x in OPERATORS]
available_tokens.extend([Token(i, is_number=True) for i in range(len(numbers))])
debug(available_tokens)

closest_result = abs(numbers[0] - target_result)

Q = [ReversePolandNotation()]
step = 0
while len(Q) > 0:  # and step < 100500:
    step += 1
    current_rpn = Q.pop()
    if step % 1000 == 0:
        debug("step=", step, 'queue=', len(Q), 'current_rpn=', current_rpn)
    for avail_token in available_tokens:
        new_rpn = current_rpn.add_token(avail_token)
        if new_rpn:
            if new_rpn.is_correct:
                calculated = new_rpn.calc
                if not calculated:
                    continue
                if len(calculated) == 1:
                    if calculated[0] == target_result:
                        print("POSSIBLE")
                        print(new_rpn.num_operators)
                        sys.exit(0)
                    else:
                        new_diff = abs(calculated[0] - target_result)
                        closest_result = min(closest_result, new_diff)

            Q.append(new_rpn)

print("IMPOSSIBLE")
print(closest_result)