What is the fastest way to get the minimum number of operations by converting x to y? You can: multiply x by 2 divide x by 2 (if even) increment x x can be greater than or less than y Is there a greedy way to do this problem faster than brute force dfs?

algorithm

epiccoder123

Reputation: 49

Minimum number of operations to get from x to y given following operations

What is the fastest way to get the minimum number of operations by converting x to y?

You can:

multiply x by 2
divide x by 2 (if even)
increment x

x can be greater than or less than y

Is there a greedy way to do this problem faster than brute force dfs?

Upvotes: 4

Answers (2)

kcsquared

Reputation: 5409

You can do this in O(log^2 (max(x,y))) time, which is far better than breadth-first search which takes O(max(x,y)) time.

I'll assume that x and y are nonnegative. The key is to find sequences of operations that can't appear in an optimal transformation sequence.

Let P, M, D denote the (Plus_one, Multiply_by_2 and Divide_by_2) operations, respectively. Immediately, we know that MD and DM can't occur as a substring. We also know that MPP doesn't occur (since PM is shorter and equivalent).

Furthermore, after M appears once, D can never occur again. This is true because the first D after an M would have to be immediately preceded by either M or MP, which are both impossible. In fact, after M appears once in our sequence, PP can never occur again either, since it would have to come immediately after an M or a P.

Finally, PPD can't occur (since DP is shorter and equivalent), and in fact D can never appear after PP has appeared once: D can't appear anymore once M has appeared, so for D to appear after PP, it would have to appear immediately after as PPD, which we just showed to be impossible.

Putting these facts together, the optimal transformation sequence has the form:

(D OR PD)* + (P)* + (M OR MP)* where + is string concatenation and * is the Kleene star (i.e. take 0 or more copies). This is the most important part: everything follows from this expression.

As an informal summary: the optimal transformation sequence repeatedly removes the final digit of x (in binary) until it's 'small enough', then adds 1 until x is a prefix of y, then extends x to y by multiplying by 2 (and adding 1, if needed to match up with y).

Here's a typical example, showing the three "phases" of an optimal sequence:

Converting 5838 to 2523
1011011001110 -> 
 100111011011


// Shrinking phase begins: remove last digit using D or PD

1011011001110
101101100111
101101101000
10110110100
1011011010
101101101
101101110
10110111
10111000
1011100
101110
10111
11000
1100
110       // Shrinking has stopped: time to add ones
111
1000
1001      // Adding ones has stopped: we have a prefix of y to expand
10010
10011
100110
100111
1001110
10011100
10011101
100111010
100111011
1001110110
10011101100
10011101101
100111011010
100111011011

By the structure of the third term, (M OR MP)*, our transformed number from x before the occurrence of the first M must be a prefix of y. Furthermore, if u is a prefix of v (as binary strings), then you can easily show by induction that the shortest way to transform u to v uses only M and MP.

The algorithm

The algorithm is as follows: first, we need a function add_until_prefix(a, b) which finds the number of times to add one to a until it is a prefix (in binary) of b. This counts the (P)* term.

Then, we need a function to count the operations M and MP to extend a prefix of y, 'prefix', to y itself. That function is num_bits(y) + num_set_bits(y) - (num_bits(prefix) + num_set_bits(prefix)). This counts the (M OR MP)* term.

Finally, we need to figure out the number of times to repeat the first term (D OR PD)*. Fortunately, we can just try all of the possibilities, since there's only log(x) of them, and each can be checked in O(log x) time. To loop over possibilities, we do:

While x is greater than 0:

Try to add 1 to x until it is a prefix of y, and then extend this prefix to y. If the number of steps required is smaller than our previous best, take this number of steps as our current best.
Remove the last digit of x (with either D or PD), depending on whether x is even or odd, respectively.

Python implementation (which returns the path, too):

def min_ops_sequence(x: int, y: int) -> Tuple[Union[int, float], List[int]]:
    """Returns the minimum number of steps to get from x to y and the path.
    Allowed operations in a step: mult. x by 2, divide x by 2 if even, increment x.
    x and y must be nonnegative integers.
    """

    # Edge cases
    if x == y:
        return 0, []
    if x < 0 or y < 0:
        raise ValueError
    if y == 0 and x > 0:
        return math.inf, []

    # Upper bound; more than enough steps to reduce x to zero then build y in binary
    max_operations_allowed = 5 * (x.bit_length() + y.bit_length() + 1)

    def add_until_prefix(curr_num: int,
                         curr_path: List[int],
                         upper_limit=max_operations_allowed) -> bool:
        """Add one until prefix reached, unless we exceed some limit"""
        assert curr_num <= y

        y_copy = y
        # Find smallest prefix of y that is larger than curr_num
        while y_copy // 2 >= curr_num:
            y_copy //= 2

        best_diff = y_copy - curr_num
        if best_diff > upper_limit:
            return False
        while curr_num < y_copy:
            curr_num += 1
            curr_path.append(curr_num)
        return True

    def complete_prefix_of_y(prefix: int, curr_path: List[int]) -> None:
        """Given a prefix of y (in binary), append to path the numbers encountered
        while transforming the prefix to y by the operations 
        (t->2t, or (t-> 2t -> 2t+1))"""

        smaller = bin(prefix)
        larger = bin(y)
        remaining_digs = list(larger[len(smaller):])
        remaining_digs.reverse()
        while len(remaining_digs) > 0:

            prefix = 2 * prefix
            curr_path.append(prefix)

            if remaining_digs.pop() == '1':
                prefix += 1
                curr_path.append(prefix)
        return

    best_len, best_path = math.inf, []
    before_path = []

    # Repeatedly remove last digit of x (in binary) and test new distance to y
    while True:
        before_path.append(x)
        this_path = before_path[:]
        if x <= y:
            successful = add_until_prefix(x,
                                          this_path,
                                          min(max_operations_allowed,
                                              best_len-len(this_path)+2))
            if successful:
                complete_prefix_of_y(this_path[-1], this_path)
                if len(this_path) < best_len:
                    best_len = len(this_path)
                    best_path = this_path
        if x % 2 == 1:
            if x == 1:
                break
            before_path.append(x + 1)
            x += 1
        x //= 2

    return best_len - 1, best_path

Running:

print(min_ops_sequence(48, 64)[1])
print(min_ops_sequence(5, 18)[1])
print(min_ops_sequence(11, 28)[1])

gives:

[48, 24, 12, 13, 14, 15, 16, 32, 64]
[5, 6, 7, 8, 9, 18]
[11, 12, 13, 14, 28]

Upvotes: 3

John Alexiou

Reputation: 29244

This is the logic to reach this goal.

If x==y then end the algorithm
If x>y then
- If x is even then half
- otherwise, increment
If 2*x<=y then double
otherwise increment

Here is an example

Reach 18 from 5.

Step         Op           x
1            Double       10
2            Increment    11
3            Increment    12
4            Increment    13
5            Increment    14
6            Increment    15
7            Increment    16
8            Increment    17
9            Increment    18
10           End          18

The logic here is to get x to be between y/2 and y and then increment up to the target value (since decrement isn't allowed). If x is over then half (if possible), and if x is smaller than y/2 then double.

To count the operations, the majority is in the final increments that bring x to the target once inside the range of (y/2,y) is reached.

Code [C#]

public enum Operation
{
    End,
    Increment,
    Double,
    Half
}

static class Program
{
    static readonly Random rng = new Random();

    static void Main(string[] args)
    {
        int target = rng.Next(20);
        int start = rng.Next(20);
        int count = 0;
        Console.WriteLine($"Reach {target} from {start}.");
        Console.WriteLine();
        Console.WriteLine($"{"Step",-12} {"Op",-12} {"x"}");
        foreach (var step in Algorithm(target, start))
        {
            count++;
            Console.WriteLine($"{count,-12} {step.op,-12} {step.x}");
        }
    }

    /// <summary>
    /// Algorithm that iterates <see cref="Strategy(int, int)"/> until 
    /// target is reached.
    /// </summary>
    /// <param name="target">The target value.</param>
    /// <param name="start">The start value.</param>
    public static IEnumerable<(Operation op,int x)> Algorithm(int target, int start)
    {
        Operation op;
        int current = start;
        do
        {
            op = Strategy(target, current);
            current = Process(current, op);
            yield return (op, current);
        } while (op!=Operation.End);            
    }

    /// <summary>
    /// Process the current value based on the <see cref="Operation"/> specified.
    /// </summary>
    /// <param name="current">The current value.</param>
    /// <param name="op">The operation specified.</param>
    public static int Process(int current, Operation op)
    {
        switch (op)
        {
            case Operation.End:
                return current;
            case Operation.Increment:
                return ++current;
            case Operation.Double:
                return 2*current;
            case Operation.Half:
                return current%2==0 ? current/2 : throw new ArgumentException("value must be even for halving.", nameof(current));
            default:
                throw new NotSupportedException(op.ToString());
        }
    }

    /// <summary>
    /// Implement strategy to reach goal.
    /// </summary>
    /// <remarks>
    /// If value is more than target then half.
    /// If value is less then half the target then double.
    /// Otherwise increment to reach target.
    /// </remarks>
    /// <param name="target">The target value.</param>
    /// <param name="current">The current value.</param>
    public static Operation Strategy(int target, int current)
    {
        if (current==target)
        {
            return Operation.End;
        }

        if (current>target)
        {
            if (current%2==0)
            {
                return Operation.Half;
            }
            else
            {
                return Operation.Increment;
            }
        }
        if (2*current<=target)
        {
            return Operation.Double;
        }
        return Operation.Increment;
    }
}

Code analysis

You can estimate the steps roughly by taking how many half/double operations are needed n using the log(x/y) and the approximate number of increments by estimating you will land halfway between y/2 and y in the last steps of the algorithm.

var n = (int)Math.Abs( Math.Log(start, target) );
var m = target/4;
Console.WriteLine($"Estimated Step {n+m}");

The results are decent, at least within the correct order of magnitude in a general sense.

Upvotes: -1

Minimum number of operations to get from x to y given following operations

Answers (2)

Code [C#]

Code analysis

Related Questions