Number conversion

Assume that there is a number a. In every conversion of that number, the number can either convert itself to its value plus the value of one of its digits, or convert itself to its value minus the value of one of its digits.

In this situation, find the minimum number of conversions one has to make in order to get to the number b. If b cannot be reached, output -1.

Input

Input one line containing the integers a and b (where 1 <= a, and b <= 10^6).

Output

Output a line containing one integer, which represents the minimum amount that one has to convert the number.

Example input and output (s)

Input:  1 10
Output: 5


Why?

   1
-> 1+1=2
-> 2+2=4
-> 4+4=8
-> 8+8=16
-> 16-6=10
=> 10


The shortest program wins, as this is a code golf question.

• You should make sure to specify a winning condition. This seems like it would fit under code-golf but it is unclear. – Theo Jun 21 at 15:05
• Nice challenge! It would probably be good to also provide a test case where b cannot be reached, and the function/program should return -1. – ArBo Jun 21 at 15:34
• I would suggest guaranteeing that a solution can always be reached. – Shaggy Jun 21 at 15:35
• Or allow any behaviour, other than outputting a non-negative number, if it’s not possible to reach b – Luis Mendo Jun 21 at 16:56
• Also, this needs a few test cases, including one with output 0 – Luis Mendo Jun 21 at 16:57

JavaScript (ES6), 98 bytes

Takes input as (a)(b). Can be very slow if there's no solution, but it should eventually return $$\-1\$$ (at least in theory).

a=>h=(b,k=0)=>(g=(v,n)=>n--?[...v+''].some(x=>g(+x+v,n)|g(v-x,n)):v==b)(a,k)?k:k<a+[b]?h(b,k+1):-1


Try it online!

• Can this handle cases where a>b? I'm not sure if those cases are allowed by the author of the question. – fəˈnɛtɪk Jun 21 at 17:09
• @fəˈnɛtɪk Yes, I've added a test case. – Arnauld Jun 21 at 17:13
• Thanks. I just wasn't sure because the tests I tried caused it to timeout. They were for cases where it should return -1 – fəˈnɛtɪk Jun 21 at 17:14

05AB1E, 38 37 bytes

3Ýo*Êß8LIå*i®ë¹¸[DIå#¼Ùvy©v®y+®y-}})}¾


Can definitely be golfed a bit more..

Explanation:

3Ý             # Push the list [0,1,2,3]
o            # For each value, take 2 to the power that value: [1,2,4,8]
*           # Multiply each by the first (implicit) input
Êß         # Check that the second (implicit) input is NOT in this list
8L             # Push the list [1,2,3,4,5,6,7,8]
Iå           # Check that the second input is in this list
*i             # If both are truthy:
®            #  Push -1
ë             # Else:
¹¸           #  Push the first input again, and wrap it into a list
[          #  Start an infinite loop:
D         #  Duplicate the list at the top of the stack
Iå       #  If the second input is in this list:
#      #   Stop the infinite loop
¼        #  Increase the counter variable by 1
v        #  Loop over each number y in the list:
y©      #   Store the current number y in variable ® (without popping)
v     #   Inner loop over each digit y2 of y
®y+  #    Add digit y2 to integer ®
®y-  #    Subtract digit y2 from integer ®
}}       #  After the nested loop:
)      #  Wrap all values on the stack into a list for the next iteration
}¾         # After the infinite loop: push the counter variable
# (and output the top of the stack implicitly as result)


Jelly, 33 29 bytes

0ịD;N\$+Ɗ;@€)ẎL<¥Ƈȷ7Ʋ=⁴¬ȦƊ¿ẈṪ’


Try it online!

A full program that takes [[a]] as the left argument and b as the right argument.

More efficient version (36 bytes)

Python 2, 104999693 95 bytes

f=lambda a,b,i=0:i*(b in a)-(0<b<9<i)or f({x+int(c+d)for x in a for d inxfor c in' -'},b,i+1)


Try it online!

This function takes a as a list (or set, or any other collection really), which is not ideal, but the Jelly answer does something similar it seems. My original approach with varargs couldn't be used because I needed the i parameter, with a default value, to return -1 if no answer can be found.

@tsh's prerequisites for there not being an answer are partially used. However, instead of the expensive and highly unpractical (for golfing) second part of that condition, we simply let the recursion run for a little while to see if an answer is found anyway.

Explanation

f=lambda a,b,                       # a and b are as defined in the
i=0:                       #  challenge; i is a counter
i*(b in a)                          # Return the counter if b is found
-(0<b<9<i)                          # This is the only code needed for the
#  existence problem
or f(                               # Recursively call the function
{x+int(c+d)                        # All possible numbers in the next step
for x in a                        # All numbers in this step
for d inx                       # All digits of those numbers
for c in' -'},                    # Either positive or negative (making
#  good use of the fact that int()
b,i+1)                             # Increase the counter


C# (Visual C# Interactive Compiler), 217 bytes

Correctly returns -1 now if b can't be reached, thanks to @tsh for the formula

(a,b)=>{var l=new List<int>(){a};int r=-1,z;if(!(b<9&!(b==a|b==2*a|b==4*a|b==8*a)))for(r=0;!l.Any(x=>x==b);r++)l.ToList().ForEach(x=>(x+"").ToList().ForEach(y=>{z=y-'0';l.Remove(x);l.Add(x+z);l.Add(x-z);}));return r;}


Try it online!

• Does this just check every possible branch? – fəˈnɛtɪk Jun 21 at 16:07
• This doesn't return if there is no valid path to the number. If you put a=1 and b=3 it runs forever. – fəˈnɛtɪk Jun 21 at 16:30
• OP hasnt even specified what to return in such scenario – Innat3 Jun 21 at 16:55
• "If b cannot be reached, output -1." – fəˈnɛtɪk Jun 21 at 17:01