Find the minimum number of operations to convert 1 into n, and print the sequence of numbers

Question

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 <= 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 <= 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 <= 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:

> 1
0
1
> 5
3
1 2 4 5
> 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?

• Janne Karila: It's a good idea to use the python tag alongside python-3.x to catch the attention of people browsing by tag. Added.

Answer 1

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 <= 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 <= 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 <= 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 <= 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 <= 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.