Convierta un número ma n con operaciones mínimas. Las operaciones permitidas fueron la resta por 1 y la multiplicación por 2.

Por ejemplo: 4 y 6. La respuesta es 2. 1.a operación: -1 -> 4-1 = 3. 2.a operación: * -> 3 * 2 = 6.

Estoy usando el enfoque BFS para una entrada particular (src = 26, dst = 5) que está tomando mucho tiempo. ¿Estoy haciendo algo mal?

from queue_class import queue


class node:

    def __init__(self, value, level, parent):
        self.level = level
        self.value = value
        self.parent = parent

    def get_minimum_distance(src, target, q):
        if src == target:
            return 0
        seen_list = []
        data = node(src, 0, -1)
        q.enqueue(data)
        while not q.isempty():
            data = q.dequeue()
            if data == "sentinel":
                break
            if data.value == target:
                # let's print what has got me here
                while data.parent != -1:
                    print(data.value)
                    data = data.parent
                return "finally reached"
            if data.value in seen_list:
                continue
            seen_list.append(data.value)
            # two operations are allowed i.e. -1 and multiplication by 2
            # check if two numbers have opposite sign and if they have
            # then check if the current number being subtracted from is a negative
            # number. If it is, then there is no point subtracting 1 from that
            if ((data.value ^ target) < 0 and data.value > 0) or (data.value ^ target >= 0):
                q.enqueue(node(data.value - 1, data.level + 1, data))
                q.enqueue(node(data.value * 2, data.level + 1, data))
        return -1

q = queue(1 << 20)
print(get_minimum_distance(26, 5, q))

La implementación de la cola está hechaaquí.

Gracias a Paul: A continuación se muestra el código que se me ocurrió a continuación en Python y funciona perfectamente.

def get_minimum_operations(src, dst):
    step = 0
    operations = []
    if src == dst:
        return 0
    if dst < src:
        return src-dst
    while dst > src:
        if dst & 0x01:
            step += 1
            operations.append("-1")
        dst = (dst+1) >> 1
        operations.append("*2")
        step += 1
    for i in range(0, src-dst):
        operations.append("-1")
    return (((src - dst) + step), operations)

src = 38
dst = 100
output = ""
(steps, operations) = get_minimum_operations(src, dst)
print(steps)
try:
    while operations:
        i = operations.pop()
        if i == "*2":
            if output == "":
                output += "(" + str(src) + "*2" + ")"
            else:
                output = "(" + output + "*2" + ")"
        if i == "-1":
            if output == "":
                output += "(" + str(src) + "-1" + ")"
            else:
                output = "(" + output + "-1" + ")"
except IndexError:
    pass
print(output)