Computing the "closure" of the attributes of an object given functions that change the attributes

Question

I have an object obj and a number of functions

    def func1(obj):
    #...

    def func2(obj):
    #...

    def func3(obj):
    #...

that each change the values of the attributes of obj.

I want my input to be something like

obj = MyObject()
obj.attr=22

This should be passed to a function closure() that computes all possible applictions of the functions above, meaning func1(func2(obj)), func3(func1(func1(obj))) etc. up to a certain stopping condition (e.g. no more than 20 function compositions).

The output should be a list of all possible outputs together with all paths leading there. So if, say 104 and 93 are the one possible final outputs if obj.attr=22, and there are two ways to arrive at 104 and one to arrive at 93. Then

print closure(obj)

should be something like

[22, 64, 21, 104] #first path to 104 through , func1(obj),func1(func1(obj)), func1(func1(func3(obj)))

[22, 73, 104] #second path to 104 through , func3(obj),func3(func2(obj)), 

[22, 11, 93] #the only path to arrive at 94

How could I implement this? As was suggested in the comments, this is best done with trees, but although I tried 2 days I almost didn't make any progress implementing that (I'm new to Python/programming)!
My example is so simple that instead of func(obj) we could directly use func(22) but the example I need to work on is more complicated, where I definitely will need to use objects, so this would only be a minimal working example for that.

The tree will probably not be a full n-ary tree, since each function application will contain a test whether it can be applied to the current state (of the attributes) of obj and in some cases the test will fail leaving (the attributes of) obj unchanged.

Answer 1

Here's a simple example that tries to find whether a number (goal) is a predecessor of another (inital_state) when applying the rule in the Collatz conjecture.

In your example, obj is the state, and [func1, func2, ...] is functions in my example. This version will return a path to a final output, minimizing the number of function applications. Instead of searching, you can list all states by removing the goal test and returning prev_states after the loop finishes.

from collections import deque

def multiply_by_two(x):
    return x * 2

def sub_one_div_three(x):
    if (x - 1) % 3 == 0:
        return (x - 1) // 3
    else:
        return None # invalid


functions = [multiply_by_two, sub_one_div_three]

# find the path to a given function
def bfs(initial_state, goal):
    initial_path = []
    states = deque([(initial_state, initial_path)])     # deque of 2-tuples: (state, list of functions to get there)
    prev_states = {initial_state}                       # keep track of previously visited states to avoid infinite loop

    while states:
        # print(list(map(lambda x: x[0], states)))      # print the states, not the paths. useful to see what's going on
        state, path = states.popleft()

        for func in functions:
            new_state = func(state)

            if new_state == goal:                       # goal test: if we found the state, we're done
                return new_state, path + [func]

            if (new_state is not None and           # check that state is valid
                new_state not in prev_states):      # and that state hasn't been visited already
                states.append((new_state, path + [func]))
            prev_states.add(new_state)              # make sure state won't be added again
    else:
        raise Exception("Could not get to state")

print(functions)
print(bfs(1, 5))

# prints (5, [<function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function sub_one_div_three at 0x000002E7493C9400>]). You can extract the path from here.