Algorithm to find minimum number of moves to transform one number to another

user_17714584 0
Viewed 406

Suppose we are given two positive integers, a and b. Each move we are allowed to divide a by 2 (but only if a is even), multiply a by 2, or add 1 to a. How many moves does it take to change a to b? Find either a direct formula or an efficient algorithm (i.e. one that runs in logarithmic time).

Some progress that I have made: We can think of it as writing b=(2^k)a + something, where this "something" can be expressed by the sum of powers of 2 (including negative exponents). Clearly we'd want to choose k so that k is a large as possible while maintaining (2^k)a<b, and we'd want k to be the total difference between the ×2s and the ÷2s. However I'm not too sure how to go from here. Does someone have solution?

combinatorics binary algorithm operators
2 Answers

One approach I can think of is to maintain a tree, with the root node as the initial number. Every node has three children, each of which resembles one operation (double, half, increment), unless of course the number is odd, in which case the half operation won't be counted. You can do a simple BFS in order to find the first instance in which the target value is seen. Here is some sample code in C++ (p1 is the initial value, p2 is the target):

unordered_set<uint64_t> set; // Resembles the previous layer
unordered_set<uint64_t> visited; // Visited set. If we already came across a node, then there isn't any point in evaluating it again
set.insert(p1); // First layer contains the initial value
visited.insert(p1);
int count = 0;

while (!set.count(p2)) { // Loop until you reach the target value
    unordered_set<uint64_t> new_set; // Build the new layer

    for (uint64_t elem : set) {
        if ((elem & 1) == 0) { // Divide by two if it's even (>> 1 is the same as divide by 2)
            if (!visited.count(elem >> 1)) {
                new_set.insert(elem >> 1);
                visited.insert(elem >> 1);
            }
        }

        if (!visited.count(elem + 1)) {
            new_set.insert(elem + 1);
            visited.insert(elem + 1);
        }
                
        if (!visited.count(elem << 1) && elem < p2) {
            new_set.insert(elem << 1);
            visited.insert(elem << 1);
        }
    }

    set = new_set; // Update current layer
    count++;
}

cout << count << endl;
user_131736330

Here's my take, done in C#.

var a = 2;
var b = 15;

var found = new HashSet<int>() { a };

var operations = new (string operation, Func<int, bool> condition, Func<int, int> projection)[]
{
    ("/2", x => x % 2 == 0, x => x / 2),
    ("*2", x => x <= int.MaxValue / 2, x => x *2),
    ("+1", x => true, x => x + 1),
};

IEnumerable<(int count, string operations, int value)> Project((int count, string operations, int value) current)
{
    foreach (var operation in operations)
    {
        if (operation.condition(current.value))
        {
            var value = operation.projection(current.value);
            if (!found.Contains(value))
            {
                found.Add(value);
                yield return (current.count + 1, $"{current.operations}, {operation.operation}", value);
            }
        }
    }
}

var candidates = new[] { (count: 0, operations: $"{a}", value: a) };

while (!found.Contains(b))
{
    candidates =
        candidates
            .SelectMany(c => Project(c))
            .ToArray();
}

var result = candidates.Where(x => x.value == b).First();

Console.WriteLine($"{result.count} operations: {result.operations} = {result.value}");

That outputs:

5 operations: 2, +1, *2, +1, *2, +1 = 15

Basically, this is starting with a at the zeroth step. It then takes this generation and produces all possible values from the operations to create the next generation. If it produces a value that it has already seen it discards the value as there is an equal or faster operation to produce the value. It keeps repeating until b is found.

user_2597690
Related