The shortest path between two integers by adding or subtracting?

Question

You are given two integers a and b. You want to find the shortest sequence of operations necessary to transform a into b, where at each step you are allowed to add or subtract 5, 7, or 12. For example, if you are given a = -5 and b = 19, the shortest path is -5 + 12 + 12 = 19. If you were given 1 and 3, the shortest path would be 1 + 7 - 5 = 2. The only way I can think about solving this is using BFS and maybe some more pruning. Is there a better algorithm I could use instead?

Answer 1

Store the following functions / calculations in an array of size 11.

You can use function pointers in C/C++ if applicable.

Array[0] = 12 - 7 - 5 <---- stores a result of zero

Array[1] = 12/(7-5) - 5 <---stores a result of one

Array[2] = 7 - 5 <--- stores a result of 2

Array[3] = Array[2] + Array[1] <-- stores a result of 3

Array[4] = (7-5)*(7-5) <--- stores a result of 4

Array[5] = 5

Array[6] = 12 / (7-5) <--- stores a result of 6

Array[7] = 7 <-- stores a result of 7

Array[8] = Array[7]+ Array[1] <--- stores a result of 8

Array[9] = 7+7-5 <- stores a result of 9

Array[10] = 5 * (7-5) <--- stores a result of 10

Now you can subtract the two input values to get the difference.

From there you use these values stored in the array to determine

a path.

To get the shortest path, you can optimize Array[0] Array[1] and Array[2]