Find the minimum number of operations to convert 1 into n, and print the sequence of numbers Here is my solution for the following task: Given an integer n, print the minimum number of operations needed to obtain the number n starting from the number 1, and the sequence of numbers towards the number n. The allowed operations are: multiply by 2; multiply by 3; add 1:

def min_operations(x, y):
    visited = set()
    sequences = [[x]]

    while True:
        new_sequences = []
        for s in sequences:
            val = s[-1]

            if val == y:
                return s

            val_times_2 = val * 2
            if val_times_2 &lt;= y and val_times_2 not in visited:
                visited.add(val_times_2)
                new_sequences.append(s + [val_times_2])

            val_times_3 = val * 3
            if val_times_3 &lt;= y and val_times_3 not in visited:
                visited.add(val_times_3)
                new_sequences.append(s + [val_times_3])


            val_plus_1 = val + 1
            if val_plus_1 &lt;= y and val_plus_1 not in visited:
                visited.add(val_plus_1)
                new_sequences.append(s + [val_plus_1])

        sequences = new_sequences


if __name__ == '__main__':
    y = int(input())
    mo = min_operations(1, y)
    print(len(mo) - 1)
    print(mo)


Examples:

&gt; 1
0
1

&gt; 5
3
1 2 4 5

&gt; 96234
14
1 2 6 7 21 22 66 198 594 1782 5346 16038 16039 32078 96234


Is there a more efficient and/or maintainable way of doing that? Perhaps usual algorithms for doing this and similar tasks? Is the code alright?
Given the problem description, I'm not entirely sure why x is a parameter of min_operations. Could you not hard-code 1?



        val_times_2 = val * 2
        if val_times_2 &lt;= y and val_times_2 not in visited:
            visited.add(val_times_2)
            new_sequences.append(s + [val_times_2])

        val_times_3 = val * 3
        if val_times_3 &lt;= y and val_times_3 not in visited:
            visited.add(val_times_3)
            new_sequences.append(s + [val_times_3])


        val_plus_1 = val + 1
        if val_plus_1 &lt;= y and val_plus_1 not in visited:
            visited.add(val_plus_1)
            new_sequences.append(s + [val_plus_1])


There's some common code here which could certainly be refactored. Perhaps

        for successor in [val + 1, val * 2, val * 3]
            if successor &lt;= y and successor not in visited:
                visited.add(successor)
                new_sequences.append(s + [successor])




However, the approach of storing the full path for each visited element doesn't scale particularly well. All you really need is to find the predecessor: provided you store all of the predecessors, you can work your way back up the chain. One way to do that would be a dictionary (which could also take the place of visited).

def min_operations(y):
    predecessors = dict()
    new_elements = [1]

    while True:
        next_new_elements = []
        for e in new_elements:
            if e == y:
                return unchain(e, predecessors)

            for successor in [val + 1, val * 2, val * 3]
                if successor &lt;= y and successor not in predecessors:
                    predecessors[successor] = y
                    next_new_elements.append(successor)

        new_elements = next_new_elements

def unchain(e, predecessors):
    chain = [e]
    while e in predecessors:
        e = predecessors[chain[-1]]
        chain.append(e)
    return list(reversed(chain))


An alternative way of doing it would be to use lru_cache to find the predecessors on the fly, handing off the caching to the library. Here it is necessary to track the depth as well as the predecessor.

@lru_cache(maxsize=None)
def predecessor(y):
    if y == 1:
        return (0, 0)

    candidates = []
    (decr, _) = predecessor(y - 1)
    candidates.append((decr + 1, y - 1))

    for divisor in [2, 3]:
        if y % divisor == 0:
            (divided, _) = predecessor(y // divisor)
            candidates.append((divided + 1, y // divisor))

    return min(candidates)


Then min_operations is essentially unchain but calling predecessor instead of doing a lookup in a map. This is arguably slightly more elegant, but does run into problems with stack overflow if y is too large.