# Minimum operations to get from one number to another

Let's define a simple language that operates on a single 8-bit value. It defines three bitwise operations (code explanation assumes 8-bit value variable):

• ! Negate the least significant bit (value ^= 1)
• < Wrapping left-shift (value = value << 1 | value >> 7)
• > wrapping right-shift (value = value >> 1 | value << 7)

## Input:

Two 8-bit numbers, a and b. As they are 8-bit, you can alternatively take them as characters.

## Output:

The shortest way to get from a to b, with the three operations defined above. You can return a string or an array of characters, or define a constant, distinct values for each operation and return an array of those (yes, you could also say < means > and > means <), but please explain your output format in your answer.

If there are multiple, equally long ways, you can output any or all of them.

## Rules:

• You can submit a program or function
• Standard loopholes apply
• The submission with fewest bytes in each language wins (no answer will be accepted)

Solutions without brute-forcing (or at least not only brute-forcing) might get my upvote.

## Test cases:

12, 13 => '!'
1, 2 => '<'
254, 253 => '<'
5, 5 => ''
98, 226 -> '<!>'
64, 154 -> '!>!>>>!>'
177, 164 -> '!>>!>>>!'
109, 11 -> '>>!>!>>'
126, 92 -> '!>!>!>!<' or '!>!>>!<!'
26, 85 -> '<!<<!<!<' or '<!<<!<!>' or '<!<<<!>!'
123, 241 -> '!>!<<!' or '>!<!<!'
236, 50 -> '<<!<!>' or '<<<!>!'
59, 246 -> '<<!>'
132, 95 -> '!<<!<!<!'
74, 53 -> '!>>>!>!'
171, 127 -> '<<!<<!<'
109, 141 -> '!>>>'
185, 92 -> '!>'
166, 201 -> '!<!>>>' or '<!>!>>'
77, 155 -> '<!'
124, 181 -> '!<<<<!>>' or '!>>>>!>>'
108, 85 -> '!<<<!<!<!<' or '!<<<!<!<!>' or '!<<<!<<!>!' or '!>>>!>!>!<' or '!>>>!>!>!>' or '!>>>!>>!<!'
185, 144 -> '<!<<!<!'
70, 179 -> '<<<!<!>' or '<<<<!>!' or '>>>>!>!'


Here is a program to generate a few more.

## JavaScript (ES6), 10096 86 bytes

f=(a,b,[c,d,...e]=[a,''])=>c-b?f(a,b,[...e,c^1,d+1,c/2|c%2<<7,d+2,c%128*2|c>>7,d+0]):d
<div oninput=o.textContent=f(a.value,b.value).replace(/./g,c=&gt;&lt;!&gt;[c])>a: <input type=number min=0 max=255 value=0 id=a> b: <input type=number min=0 max=255 value=0 id=b><pre id=o>

Somewhat slow breadth-first search without double-checking. Slightly more efficient 114-byte version:

f=(a,b,c=[],[d,e,...g]=[a,''])=>c[d]?f(a,b,c,g):d-b?f(a,b,c,[...g,d^1,c[d]=e+1,d/2|d%2<<7,e+2,d%128*2|d>>7,e+0]):e
<div oninput=o.textContent=f(a.value,b.value).replace(/./g,c=&gt;&lt;!&gt;[c])>a: <input type=number min=0 max=255 value=0 id=a> b: <input type=number min=0 max=255 value=0 id=b><pre id=o>

Both versions encode <!> as 012 but the snippets decode this for you. Edit: Saved 10 utterly useless bytes thanks to @RickHitchcock.

• @wastl Thanks, I'd misremebered what the third symbol was.
– Neil
Commented Jun 10, 2018 at 21:22
• Brilliant, and I think you can save 10 bytes: f=(a,b,[c,d,...e]=[a,''])=>c-b?f(a,b,[...e,c^1,d+1,c/2|c%2<<7,d+2,c%128*2|c>>7,d+0]):d Commented Jun 12, 2018 at 10:03
• @RickHitchcock Wow, those must be the most useless 10 bytes I've ever had in a single answer...
– Neil
Commented Jun 12, 2018 at 15:30

# Jelly, 32 bytes

ṃ“ṙ1“ṙ-“¬8¦”
+⁹BḊ€0ÇẎv¥⁼ƭƒ@¥1#ḢÇ


Try it online!

<: ['ṙ', '1']
>: ['ṙ', '-']
!: ['¬', '8', '¦']

Note: This is a function, that's why the footer is there.

Brute force. :(

# Python 2, 111 bytes

l=[input()+('',)]
for(a,b,i)in l:a==b>exit(i);l+=[(x,b,i+y)for x,y in zip((a*2%256|a>>7,a/2|a%2<<7,a^1),'<>!')]


Try it online!

• Since functions have to be reusable, I don't think you can use exit to produce output. Commented Jun 10, 2018 at 20:35
• @Dennis I thought this would be covered by functions can output in the same way as full programs, but exiting isn't part oft the output, I guess. Does this mean functions can't output via exit code?
– ovs
Commented Jun 10, 2018 at 20:40
• I think so. Allowing functions to output as full programs can doesn't override (imo) the rules for function submissions. Commented Jun 10, 2018 at 20:46

# JavaScript (ES6), 105 bytes

Takes the 2 bytes in currying syntax (a)(b).

Returns a string with:

• 0 = !
• 1 = >
• 2 = <

or an empty array if a is equal to b.

a=>g=(b,m=1)=>(h=(n,s=[])=>n^b?s[m]?0:h(n^1,s+0)+h(n/2|n%2<<7,s+1)+h(n%128*2|n>>7,s+2):r=s)(a)?r:g(b,m+1)


Try it online! (with codes translated back to !<>)

# C (gcc), 201199198196 193 bytes

• Saved two bytes thanks to ceilingcat; golfing a/2+a*128 to (a+2*a*128)/2 to a*257/2.
• Saved a byte; golfing a*2+a/128 to (a*2*128+a)/128 to (257*a)/128 to 257*a>>7.
• Saved two five bytes thanks to ceilingcat, golfing the return type.

# C (gcc), 193 bytes

*P,D,Q,j;f(a,b,d){if(a&=255,Q&&a==b)for(Q=j=0;++j<D;printf("%d",j[P]));Q&&++d<D&&f(a^1,b,d,P[d]=1)&f(257*a>>7,b,d,P[d]=2)&f(a*257/2,b,d,P[d]=3);}F(a,b){for(D=Q=1;Q;D++){int p[D];f(a,b,0,P=p);}}


Try it online!