Problem with Python program (Solved)

[Picuino]

I have created a Python program that calculates the numbers from 1 to 100 as combinations of the figures for the year 2022.
After a few seconds and several results, the program freezes and begins to consume RAM memory until a memory error appears.

Can anyone help me find the error?

Program:

Code: [Select]

import copy

class Stack():
    def __init__(self, numbers=[2, 0, 2, 2]):
        self.stack_rpn = []
        self.stack_oper = []
        self.numbers = numbers
        self.operations = ['+', '-', '*', '/', '^', 'J', '!']

    def __str__(self):
        return f"stack={self.stack_rpn}, operations={self.stack_oper}, numbers={self.numbers}"
       
    def append_operation_to_stack(self, i):
        item = self.operations[i]
        error = False
        if item in ['+', '-', '*', '/', '^', 'J'] and len(self.stack_rpn) < 2:
            error = True
        elif item == '!' and (len(self.stack_rpn) < 1 or self.stack_rpn[-1] not in [0, 3, 4, 5, 6]):
            error = True           
        elif item == '^' and self.stack_rpn[-1] < 0:
            error = True           
        elif item == '/' and self.stack_rpn[-1] == 0:
            error = True
        elif item == 'J' and ( type(self.stack_oper[-1]) != int or type(self.stack_oper[-2]) != int ):
            error = True

        if not error:
            self.stack_rpn.append(item)
            self.stack_oper.append(item)
            self.evaluate()
            return True
        else:
            return False
       
    def append_number_to_stack(self, i):
        item = self.numbers[i]     
        self.stack_rpn.append(item)
        self.stack_oper.append(item)
        self.numbers = self.numbers[:i] + self.numbers[i+1:]

    def evaluate(self):
        operation = self.stack_rpn[-1]

        if operation == '!':
            self.stack_oper = self.stack_oper[:-2] + [f"({self.stack_oper[-2]}!)"]
            self.stack_rpn = self.stack_rpn[:-2] + [factorial(self.stack_rpn[-2])]

        elif operation == '+':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} + {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] + self.stack_rpn[-2]]

        elif operation == '-':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} - {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] - self.stack_rpn[-2]]

        elif operation == '*':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} * {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] * self.stack_rpn[-2]]

        elif operation == '/':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} / {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [to_int(self.stack_rpn[-3] / self.stack_rpn[-2])]

        elif operation == '^':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} ^ {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] ** self.stack_rpn[-2]]

        elif operation == 'J': # Join 2 figures
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]}{self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] * 10 + self.stack_rpn[-2]]
   

def to_int(num):
    if num == int(num):
        return int(num)
    return num


def factorial(n):
    if n < 2:
        return 1
    return factorial(n-1) * n


def combine(stack):
    if len(stack.stack_rpn) == 1 and len(stack.numbers) == 0:
        yield stack.stack_rpn[0], stack.stack_oper[0]
    else:
        for i in range(len(stack.operations)):
            new_stack = copy.deepcopy(stack)
            if new_stack.append_operation_to_stack(i):
                yield from combine(new_stack)

        for i in range(len(stack.numbers)):
            new_stack = copy.deepcopy(stack)
            new_stack.append_number_to_stack(i)
            yield from combine(new_stack)


def main():
    stack = Stack(numbers=[2, 0, 2, 2])
    results = {}
    for result, operations in combine(stack):
        if type(result) == int and result <= 100 and result >= 0:
            if result in results:
                continue
            else:
                results[result] = operations
                print(result, ' -> ', operations)

    print('\n\n')
    for i in range(101):
        if i in results:
            print(i, ' -> ', results[i])


main()


Results:

Code: [Select]

0  ->  (((2 + 0) - 2) * 2)
1  ->  ((((2 + 0) - 2)!) ^ 2)
2  ->  (((2 + 0) + 2) - 2)
3  ->  ((((2 + 0) - 2)!) + 2)
4  ->  (((((2 * 0)!) + 2)!) - 2)
5  ->  ((((2 * 0)!) + 2) + 2)
6  ->  (((2 + 0) + 2) + 2)
7  ->  (((2 + (0!))!) + ((2 - 2)!))
8  ->  (((2 + 0) + 2) * 2)
9  ->  ((((2 * 0)!) + 2) ^ 2)
10  ->  ((((2 + (0!))!) + 2) + 2)
11  ->  (((20) + 2) / 2)
12  ->  ((((2 + 0) + 2)!) / 2)
13  ->  ((((2 + 2)!) / 2) + (0!))
14  ->  ((((2 + (0!))!) * 2) + 2)
15  ->  (((2 + 2) ^ 2) - (0!))
16  ->  (((2 + 0) + 2) ^ 2)
17  ->  (((2 + 2) ^ 2) + (0!))
18  ->  ((((2 + (0!))!) ^ 2) / 2)
19  ->  ((20) - ((2 - 2)!))
20  ->  (((20) + 2) - 2)
21  ->  ((20) + ((2 - 2)!))
22  ->  ((((2 + 0) + 2)!) - 2)
23  ->  (((2 * 0)!) + (22))
24  ->  ((2 + 0) + (22))
25  ->  (((2 * 0)!) + ((2 + 2)!))
26  ->  ((((2 + 0) + 2)!) + 2)
27  ->  ((2 + (0!)) + ((2 + 2)!))
28  ->  (((2 + (0!))!) + (22))
30  ->  ((((2 + (0!))!)!) / ((2 + 2)!))
32  ->  ((2 ^ (((0!) + 2)!)) / 2)
34  ->  ((((2 + (0!))!) ^ 2) - 2)
36  ->  (((((2 * 0)!) + 2)!) ^ 2)
38  ->  (((20) * 2) - 2)
42  ->  (((20) * 2) + 2)
43  ->  (((22) * 2) - (0!))
44  ->  ((2 + 0) * (22))
45  ->  (((22) * 2) + (0!))
46  ->  (2 * ((0!) + (22)))
47  ->  ((((2 + 2)!) * 2) - (0!))
48  ->  ((((2 + 0) + 2)!) * 2)
49  ->  ((((2 + 2)!) * 2) + (0!))
50  ->  (2 * ((0!) + ((2 + 2)!)))
60  ->  ((((2 + (0!)) + 2)!) / 2)
62  ->  ((2 ^ (((0!) + 2)!)) - 2)
64  ->  ((((2 + (0!))!) + 2) ^ 2)
66  ->  ((2 + (0!)) * (22))
72  ->  ((((2 + (0!))!) ^ 2) * 2)
80  ->  (((20) * 2) * 2)
81  ->  (((2 + (0!)) ^ 2) ^ 2)
100  ->  (((20) / 2) ^ 2)

[brucehoult]

Wild guess .. it applies factorial to something that is a large number. Possibly the result of an earlier factorial. Or tries to raise something to a large power.

2^(220!) would be bad. Or (2^220)!

[Picuino]

The problem was a very large power.

Solved:

Code: [Select]

import copy

class Stack():
    def __init__(self, numbers=[2, 0, 2, 2]):
        self.stack_rpn = []
        self.stack_oper = []
        self.numbers = numbers
        self.operations = ['+', '-', '*', '/', '^', 'J', '!', '']

    def __str__(self):
        return f"stack={self.stack_rpn}, operations={self.stack_oper}, numbers={self.numbers}"
       
    def append_operation_to_stack(self, i):
        item = self.operations[i]
        error = False
        if item in ['+', '-', '*', '/', '^', 'J'] and len(self.stack_rpn) < 2:
            error = True
        elif item == '!' and (len(self.stack_rpn) < 1 or self.stack_rpn[-1] not in [0, 3, 4, 5, 6]):
            error = True           
        elif item == '^' and (self.stack_rpn[-1] < 0 or self.stack_rpn[-1] > 100):
            error = True           
        elif item == '/' and self.stack_rpn[-1] == 0:
            error = True
        elif item == 'J' and ( type(self.stack_oper[-1]) != int or type(self.stack_oper[-2]) != int ):
            error = True
        if item == '':
            error = True

        if not error:
            self.stack_rpn.append(item)
            self.stack_oper.append(item)
            self.evaluate()
            return True
        else:
            return False
       
    def append_number_to_stack(self, i):
        item = self.numbers[i]     
        self.stack_rpn.append(item)
        self.stack_oper.append(item)
        self.numbers = self.numbers[:i] + self.numbers[i+1:]

    def evaluate(self):
        operation = self.stack_rpn[-1]

        if operation == '!':
            self.stack_oper = self.stack_oper[:-2] + [f"({self.stack_oper[-2]}!)"]
            self.stack_rpn = self.stack_rpn[:-2] + [factorial(self.stack_rpn[-2])]

        elif operation == '+':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} + {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] + self.stack_rpn[-2]]

        elif operation == '-':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} - {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] - self.stack_rpn[-2]]

        elif operation == '*':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} * {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] * self.stack_rpn[-2]]

        elif operation == '/':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} / {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [to_int(self.stack_rpn[-3] / self.stack_rpn[-2])]

        elif operation == '^':
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]} ^ {self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] ** self.stack_rpn[-2]]

        elif operation == 'J': # Join 2 figures
            self.stack_oper = self.stack_oper[:-3] + [f"({self.stack_oper[-3]}{self.stack_oper[-2]})"]
            self.stack_rpn = self.stack_rpn[:-3] + [self.stack_rpn[-3] * 10 + self.stack_rpn[-2]]
   

def to_int(num):
    if num == int(num):
        return int(num)
    return num


def factorial(n):
    if n < 2:
        return 1
    return factorial(n-1) * n


def combine(stack):
    if len(stack.stack_rpn) == 1 and len(stack.numbers) == 0:
        yield stack.stack_rpn[0], stack.stack_oper[0]
    else:
        for i in range(len(stack.operations)):
            new_stack = copy.deepcopy(stack)
            if new_stack.append_operation_to_stack(i):
                yield from combine(new_stack)

        for i in range(len(stack.numbers)):
            new_stack = copy.deepcopy(stack)
            new_stack.append_number_to_stack(i)
            yield from combine(new_stack)


def main():
    stack = Stack(numbers=[2, 0, 2, 2])
    results = {}
    for result, operations in combine(stack):
        if type(result) == int and result <= 100 and result >= 0:
            if result in results:
                continue
            else:
                results[result] = operations

    print('\n\n')
    for i in range(101):
        if i in results:
            print(i, ' -> ', results[i])


main()


Results (51 lines):

Code: [Select]

0  ->  (((2 + 0) - 2) * 2)
1  ->  ((((2 + 0) - 2)!) ^ 2)
2  ->  (((2 + 0) + 2) - 2)
3  ->  ((((2 + 0) - 2)!) + 2)
4  ->  (((((2 * 0)!) + 2)!) - 2)
5  ->  ((((2 * 0)!) + 2) + 2)
6  ->  (((2 + 0) + 2) + 2)
7  ->  (((2 + (0!))!) + ((2 - 2)!))
8  ->  (((2 + 0) + 2) * 2)
9  ->  ((((2 * 0)!) + 2) ^ 2)
10  ->  ((((2 + (0!))!) + 2) + 2)
11  ->  (((20) + 2) / 2)
12  ->  ((((2 + 0) + 2)!) / 2)
13  ->  ((((2 + 2)!) / 2) + (0!))
14  ->  ((((2 + (0!))!) * 2) + 2)
15  ->  (((2 + 2) ^ 2) - (0!))
16  ->  (((2 + 0) + 2) ^ 2)
17  ->  (((2 + 2) ^ 2) + (0!))
18  ->  ((((2 + (0!))!) ^ 2) / 2)
19  ->  ((20) - ((2 - 2)!))
20  ->  (((20) + 2) - 2)
21  ->  ((20) + ((2 - 2)!))
22  ->  ((((2 + 0) + 2)!) - 2)
23  ->  (((2 * 0)!) + (22))
24  ->  ((2 + 0) + (22))
25  ->  (((2 * 0)!) + ((2 + 2)!))
26  ->  ((((2 + 0) + 2)!) + 2)
27  ->  ((2 + (0!)) + ((2 + 2)!))
28  ->  (((2 + (0!))!) + (22))
30  ->  ((((2 + (0!))!)!) / ((2 + 2)!))
32  ->  ((2 ^ (((0!) + 2)!)) / 2)
34  ->  ((((2 + (0!))!) ^ 2) - 2)
36  ->  (((((2 * 0)!) + 2)!) ^ 2)
38  ->  (((20) * 2) - 2)
42  ->  (((20) * 2) + 2)
43  ->  (((22) * 2) - (0!))
44  ->  ((2 + 0) * (22))
45  ->  (((22) * 2) + (0!))
46  ->  (2 * ((0!) + (22)))
47  ->  ((((2 + 2)!) * 2) - (0!))
48  ->  ((((2 + 0) + 2)!) * 2)
49  ->  ((((2 + 2)!) * 2) + (0!))
50  ->  (2 * ((0!) + ((2 + 2)!)))
60  ->  ((((2 + (0!)) + 2)!) / 2)
62  ->  ((2 ^ (((0!) + 2)!)) - 2)
64  ->  ((((2 + (0!))!) + 2) ^ 2)
66  ->  ((2 + (0!)) * (22))
72  ->  ((((2 + (0!))!) ^ 2) * 2)
80  ->  (((20) * 2) * 2)
81  ->  (((2 + (0!)) ^ 2) ^ 2)
100  ->  (((20) / 2) ^ 2)

Thanks.