Algorithm for fewest moves in 1's, 10's, 100's, etc

Question

I'm building a math application (not homework) and I want to build a component that allows players to drag-and-drop 1's, 10's, 100's, etc to complete problems and a bonus reward if they do it in the fewest moves possible--How can I calculate this? e.g.

50 + X = 96

where X is a randomly generated integer and the player is modifying X during play. So, the player needs to make X=46, but starts at 121. For example,

if X is initially 121, and player needs to get to 46

player thinks, "cool, i'll just subtract 75"

remove 7x 10's, remove 5x 1's - 12 moves

but it turns out, there's a faster way to do it:

remove 1x 100's, add 2x 10's, add 5x 1's - 8 moves

Is there an existing algorithm for this? It would be helpful to calculate this for anything up to 10,000 where I can calculate the minimum number of moves required.

Answer 1

You can construct a graph with vertices $0,1,2,3,4,\dots,10000$, two vertices are adjacent if you can construct a number with a single operation from another one. A single operation is either adding or subtracting $1,10,100,1000,\dots$. For example,$N(46) = \{45, 47, 36, 56, 146, 1046,\dots\}$. Then the minimum number of operations required to construct a number $x$ is the shortest path from $x$ to 0. Since graph is undirected, you can run a single one to all algorithm (Dijkstra,BFS) and obtain all distances from 0 to any other vertex. Also the graph is pretty sparse, hence Dijsktra with heap will nail it. An implementation might no need to construct the whole graph, since neighborhoods are small and easily computable on the fly.

EDIT: if you take Dijkstra code from Geeks, you can construct graph as

for(int v1 = 0; v1 < V; ++v1)
   for(int v2 = v1+1; v2 < V; ++v2)
      if(v2 - v1 == 1 || v2 - v1 == 10 || v2 - v1 == 100)
         g.addEdge(v1,v2,1);
 g.shortestPath(46); // gives 8 to 121

Answer 2

Let's consider digits one by one, starting by the rightmost digit answering recursively the question:

Is it better to reach it by addition or subtraction ?

Let's take your example 121 => 46, starting with 1=>6, you can either:

• use 5 "+1" steps leading to the 12 => 4 problem
• use 5 "-1" steps leading to the 11 => 4 problem.

In the same way, the 12 => 4 problem leads to:

• use 2 "+10" steps leading to the 1 => 0 problem
• use 8 "-10" steps leading to the 0 => 0 problem

and so on ... Until you reached the digit before the leftmost one. This will eventually adds an additional digit with something like {-1, 0, 1} => 0, but here just keep the way done in one step.

You build a binary tree with at most $d+1$ depth, with $d$ the number of digits of the largest of your two initial numbers. Just keep the leaf using the least steps. If you limit numbers to 10000, there are at most $2^6 = 64$ branchs to evaluate.

Answer 3

With integral modifications at least twice the next lower and at most half the next higher, this should be trivial: representing the difference necessary as a "balanced" positional number (uniform base $b$ or not, digit $d_i \in [\lceil-(b_i-1)/2)\rceil .. \lceil(b_i/2)\rceil]$) gives the fewest moves possible (with an odd base, there are equivalent cases: two in balanced ternary is $1\overline1$, $1+1$ amounts to same using no more digits).

Starting with the least modification no less than the absolute difference $\lvert D\rvert$ always choose the amount giving the accumulated sum closest to $D$, the lower value in case of a tie (possible only with even $b_i$).

This does not seem to warrant a name.
It may or may not be enough of a challenge for a bonus.

Answer 4

I have divided this answer into a short answer and a long answer:

SHORT ANSWER:

THE FOLLOWING IN AN OPTIMAL STRATEGY FOR THE GAME:

1) Let diff be the difference between current value and target value. For example,

current value: 550
target value:  834
diff: 834 - 550 = 284

2) Look at only the ones and tens place of diff. If the ones and tens greater than or equal to 56, overshoot using 100s. Else, undershoot using 100s.

For our running example,

 `diff` is `284`
The tens and ones place only are `84` 
Since `84` is greater than or equal to `56`, 
your first move(s) are to add 3 X 100s to the current value. 

If we wanted to ***under***shoot,
then we would only add only 2 x 100s to the current value.

3) Now, let diff be the new difference between current value and target value. For our running example,

current value: 850
target value:  834
diff: 16

4) if the ones place is greater than or equal to 5, then ***over***shoot using tens. If the ones place is les than or equal to 4, ***under***shoot using tens

diff: 16
the ones place, 6, is greater than or equal to 5
we overshoot using 10s
we use two moves to subtract 2x10.
we then add 4 pennies.

RESULT:

starting value: 550
target value:  834

add 3x100
sub 2x10
add 4x1

9 total moves

The number of the left represents the difference between the player's current value and the target value. The number on the right represents the minimum number of moves required to make the current value equal to the target value.

(0, 0)
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 6)
(6, 5)
(7, 4)
(8, 3)
(9, 2)
(10, 1)
(11, 2)
(12, 3)
(13, 4)
(14, 5)
(15, 7)
(16, 6)
(17, 5)
(18, 4)
(19, 3)
(20, 2)
(21, 3)
(22, 4)
(23, 5)
(24, 6)
(25, 8)
(26, 7)
(27, 6)
(28, 5)
(29, 4)
(30, 3)
(31, 4)
(32, 5)
(33, 6)
(34, 7)
(35, 9)
(36, 8)
(37, 7)
(38, 6)
(39, 5)
(40, 4)
(41, 5)
(42, 6)
(43, 7)
(44, 8)
(45, 10)
(46, 9)
(47, 8)
(48, 7)
(49, 6)
(50, 5)
(51, 6)
(52, 7)
(53, 8)
(54, 9)
(55, 11)
(56, 9)
(57, 8)
(58, 7)
(59, 6)
(60, 5)
(61, 6)
(62, 7)
(63, 8)
(64, 9)
(65, 10)

LONG ANSWER:

Your problem is related to making change using the smallest number of coins possible.

For example, suppose that you owe a customer 72 cents. How do you make 72 cents using the smallest number of coins possible? Assuming that ($25¢, 10¢, 5¢,$ and $1¢$) are the only types of coins available to you. Notice that you first get as close as possible using the largest denomination (quarters), then get as close as possible using the second largest denomination (dimes), and so on... 2 quarters, 2 dimes and 2 pennies is optimal. That uses 6 coins in total.

---

Unlike the traditional coin-change problem, your problem allows negative value coins. That is, you allow the user to subtract 100, 10, or 1, in addition to adding 100, 10, or 1.

Your "coins" come in the following denominations sizes: ${100¢, -100¢, 10¢, -10¢, 1¢, -1¢}

---

First observation:

If you are going to add tens, then there is no point in subtracting tens also. Those would be wasted moves.

For example, instead of adding 5 tens and subtracting 3 tens, you would simply add 2 tens, and not subtract any tens.

---

A second observation is that it makes sense to work with 100s first, then 10s then 1s. you get as close as possible to the target value using "coarse" resolution, then get even closer using "fine" resolution afterwards.

---

If you add 100s, "overshoot," then subtract 10s later, what's the optimal amoutn of overshoot by? If you are currently using 100s, then you get as close to the target value that 100s will get you. After you are done adding or subtracting 100s, you always want to be less than 100 away from the target value; after you're done adding and subtracting 10s, you will always be less than 10 away from the target value, and so on...

For example, suppose the current value is 0 and the target value is 283. You either add 2*100, and underachieve the target of 283 by 83 points,or you add 3*100 and overshoot the target by 17 points. You have no incentive to overshoot by 117 points, or 217 points. There's no incentive to be more than 100 away from the target value after you are done adding and subtracting 100s. This is because takes fewer steps to jump 100 units using a step length of 100 units than a step length 10. You might as well make logn strides will using 100s, rather than using 10s to make up the distance later.

---

We are very close now to knowing the optimal strategy.

Let // denote integer division. For example 5//2 is 2 not 2.5

Suppose that for any integer x, SIGN(x) returns the sign of x. For example, SIGN(-342) = -1

Suppose that the current number is CURRENT and the target value is TARGET DIFF = TARGET - CURRENT

So far, our strategy is as follows:

1. Add DIFF//100 or DIFF//100 + SIGN(DIFF) one-hundreds to CURRENT
2. Re-compute DIFF using the new current value, CURRENT
3. Add DIFF//10 or DIFF//10 + SIGN(DIFF) tens
4. Re-compute DIFF using the new current value, CURRENT
5. Add DIFF ones.

For any given target value, we have 4 strategies. One of those 4 will be the optimal one. The choices revolve around getting close by undershooting or overshooting. For example, suppose the current value is 0 and the target value is 283. You either begin by adding 3*100, and overshoot the target value by 17 points. Or, you add 2*100, and underachieve the target of 283 by 83 points. Those are the only 2 sensible choices for your first action. After that, you either under-shoot or over-shoot using tens. In the end, you have 4 possible stragegies:

1. (undershoot using 100s, undershoot using 10s, add pennies)
2. (undershoot using 100s, OVERshoot using 10s, subtract pennies)
3. (OVERshoot using 100s, subtract 10s, subtract pennies)
4. (OVERshoot using 100s, subtract too many 10s, add pennies)

---

As a reminder, the denominations are $\{100, -100, 10, -10, 1, -1\}$

Question:

You would think that the more total cents there are, the more coins you're going to have to use. For positive integers x < y, is it always at least as easy to make change for x than for y? For example, is it easier to make change for 44 cents than 49 cents?

Answer:
No. The best way to make change for 44 cents is to use 4 positive dimes and 4 positive pennies, for a total of 8 coins used.

The best way to make change for 49 cents is to use 5 positive dimes and 1 negative penny, for a total of 6 coins used.

Making change for 49 cents uses fewer coins than making change for 44 cents.

---

Why ask the earlier question? It means that there exist (current value, target value) pairs such that the following strategy is non-optimal:

1. add or subtract 100s until abs(current - target) is minimized
2. add or subtract 10s until abs(current - target) is minimized
3. add or subtract 1s until abs(current - target) is minimized

---

Suppose current value is 0. For target values between 0 and 99, When does "overshooting" with 10s require fewer coins than "undershooting"?

If we undershoot, what will the coin count be?
coin count will be (count of original tens) + (count of original pennies)

    under(44) = 4 + 4
              = 8

If we overshoot, what will the coin count be?

(original tens + 1) + (10 - original pennies)

over(44) = (4 + 1) + (10 - 4) 
         = 5 + 6
         = 11

For what X in {0, 1, 2, 3, ..., 99} is over(x) < under(x)?

For what X in {0, 1, 2, 3, ..., 99} is [(x//10) + 1] + [10 - (x%10)] < (x//10) + (x%10) ?

combine constant terms (+1) and (+10)
(x//10) + 11 - (x%10) < (x//10) + (x%10)

subtract (x//10) from both sides
11 - (x%10) < + (x%10)

11 < 2(x%10)

4.5 < (x%10)

Note that (x%10) is an integer. 5 <= (x%10)

When using tens, overshooting X with is better than undershooting X if and only if (x%10) => 5

Below is some code written Python to help us:

def undershoot_dimes(total_cents):
    # make `total_cents`  non-negative by taking the absolute value
    pos_total_cents = abs(total_cents)
    if pos_total_cents == 0:
        pos_total_cents = 1
    sign = total_cents / pos_total_cents

    dimes = pos_total_cents // 10
    pennies = pos_total_cents % 10

    # `//1` converts float into integer
    return (sign*dimes//1, sign*pennies//1)

def overshoot_dimes(total_cents):
    # make `total_cents`  non-negative by taking the absolute value
    pos_total_cents = abs(total_cents)
    sign = total_cents / pos_total_cents

    dimes = 1 + (pos_total_cents // 10)
    pennies = (pos_total_cents % 10) - 10

    return (sign*dimes//1, sign*pennies//1)

def coin_breakdown_dimes(total_cents):
    """
    A `total_cents` is an integer, such
    as `42` or `83`

   This function returns (number of dimes, number of pennies)

    4 types of coin may be used: {-1, +1, -10, +10}
    Note that in addition to positive dimes and pennies,
    we allow negative dimes and negative pennies
    """
    if abs(total_cents) % 10 >= 5:
        return overshoot_dimes(total_cents)
    #end if
    return undershoot_dimes(total_cents)
# end function definition


def print_coin_breakdown_dimes(total):
    dimes, pennies = coin_breakdown_dimes(total)
    print(total, "total cents can be made using", end = " ")
    print(dimes, "dimes and", pennies, "pennies.")

for total in [19, 82, 87]:
    print_coin_breakdown_dimes(total)

# 19 total cents can be made using 2 dimes and -1 pennies.
# 82 total cents can be made using 8 dimes and 2 pennies.
# 87 total cents can be made using 9 dimes and -3 pennies.

Question:

When do we want to overshoot with 100s and when to we want to undershoot with 100s?

overshooters = list()
for cents in range(0, 100):
    CC_undershoot = CC_dimes(cents)
    CC_overshoot = CC_dimes(100 - cents)
    if 1 + CC_overshoot < CC_undershoot:
        overshooters.append(cents)
print(overshooters)

If cents is 56 or greater, we want to overshoot using 100s.

def undershoot_dollars(total_cents):
    assert(total_cents >= 0)
    dollars = total_cents // 100
    leftovers = total_cents % 100
    return (dollars, leftovers)

def overshoot_dollars(total_cents):
    assert (total_cents >= 0)
    dollars = 1 + (total_cents // 100)
    leftovers = (total_cents % 100) - 100
    return (dollars, leftovers)

def coin_breakdown_dollars(total_cents):
    # INPUT:
    # an integer, such as `42` or `83`
    # 
    # OUTPUT:
    # (number of dollars, number of dimes, number of pennies)
    # 
    # 6 denominations of coin may be used: {-1, +1, -10, +10, -100, +100}
    # In addition to positive dimes and pennies,
    # we allow negative dimes and negative pennies
    assert (total_cents >= 0)
    if (total_cents % 100) <= 55:
        dollars, leftovers = undershoot_dollars(total_cents)
        dimes, pennies = coin_breakdown_dimes(leftovers)
    else:
        dollars, leftovers = overshoot_dollars(total_cents)
        dimes, pennies = coin_breakdown_dimes(leftovers)
    return (dollars, dimes, pennies)


def CC(total_cents):
    """
    `CC` stands for `coin count`
    This function does use 100s
    6 denominations of coin may be used: {-1, +1, -10, +10, -100, +100}  
    """
    coin_spec = coin_breakdown_dollars(total_cents)
    return sum(map(abs, coin_spec))//1

def print_coin_breakdown_dimes(total):
    dol, dimes, pennies = coin_breakdown_dollars(total)
    print() # new line
    print(total, "total cents can be made using", end = " ")
    print(dol, "dollars", dimes, "dimes and", pennies, "pennies.")
    print(CC(total), "coins total.")

for total in [219, 882, 487]:
    print_coin_breakdown_dimes(total)


# 219 total cents can be made using 2 dollars 2.0 dimes and -1.0 pennies.
# 5.0 coins total.
#
# 882 total cents can be made using 9 dollars -2.0 dimes and 2.0 pennies.
# 13.0 coins total.
#
# 487 total cents can be made using 5 dollars -1.0 dimes and -3.0 pennies.
# 9.0 coins total.

So, your videogame has a target_value and a current_value. You want to know the minimum number of steps the player must use to reachtarget_valuefromcurrent_value. The answer, using our python code, isCC(abs(target_value - current_value))`

You can pre-compute these values:

diff_to_min_moves = dict()
for difference in range(0, 100):
    diff_to_min_moves[difference] = int(CC(difference))

print('\n'.join(map(str, diff_to_min_moves.items())))