How can I interchange between multypling and dividing by 2 different numbers?

Question

I'm given integers X, Y, and Z. In each step, I can either multiply or divide, by either 2 or 3. I need to transform X to Z in exactly Y steps ... or determine that it's not possible.

For Example:

X is 9,
Y is 8,
Z is 4.

9 can become 4 by: 9/3/3x2x2x2x2/2/2 = 4 As you can see I made 8 operations.

How can this be done in Python?

Answer 1

First of all use descriptive variable names, such as start, target, and steps.

No, there isn't an easy way to do this, but there are straightforward ways.

First, you need to find the necessary change. Break down both start and target into factors of 2, factors of 3, and anything else. If this "anything" else" doesn't match, then you can't solve the problem at all.

For instance, look at your given problem: going from 9 to 4. Breaking down each number:

9 = 3*3    # no 2's, no other stuff
4 = 2*2    # no 3's, no other stuff

Since the "other" stuff matches (i.e. 1), you can make the transition. You need to remove 2 factors of 3, and add 2 factors of 2. That's 4 steps. From there, all you have to do is add pairs of *3/3 or *2/2 until you have 8 steps.

Let's try with changing 56 into 126:

 56 = 2*2*2*7   # no 3's, other = 7
126 = 2*3*3*7   # other = 7

To make the transition, you need to remove two 2's and add two 3's. That's four steps; you adjust to the desired number as before.

There's your attack; can you code that?

Answer 2

Just for fun, here is a brute-force approach that scales horrifically -- O(y^4),

def bruteforce(x, y, z, acc="", accv=None):
    if accv == z and len(acc) == y*2:
        return acc
    if accv is None:
        accv = x
    if len(acc) == y*2:
        return
    m2 = bruteforce(x, y, z, acc+'*2', accv*2)
    m3 = bruteforce(x, y, z, acc+'*3', accv*3)
    d2 = bruteforce(x, y, z, acc+'/2', accv/2)
    d3 = bruteforce(x, y, z, acc+'/3', accv/3)
    return m2 or m3 or d2 or d3

In action:

In [49]: exp = bruteforce(9, 8, 4)

In [50]: exp
Out[50]: '*2*2*2*2/2/2/3/3'

In [51]: eval('9'+exp)
Out[51]: 4.0

In [52]: exp = bruteforce(13, 8, 4)

In [53]: exp

In [54]: exp = bruteforce(9, 7, 2)

In [55]: exp
Out[55]: '*2*2*2/2/2/3/3'

In [56]: eval('9'+exp)
Out[56]: 2.0

Will be buggy because of floating-point inaccuracy...