15
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 100 96 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.

\$\endgroup\$
  • \$\begingroup\$ @wastl Thanks, I'd misremebered what the third symbol was. \$\endgroup\$ – Neil Jun 10 '18 at 21:22
  • \$\begingroup\$ 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 \$\endgroup\$ – Rick Hitchcock Jun 12 '18 at 10:03
  • \$\begingroup\$ @RickHitchcock Wow, those must be the most useless 10 bytes I've ever had in a single answer... \$\endgroup\$ – Neil Jun 12 '18 at 15:30
2
\$\begingroup\$

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. :(

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Since functions have to be reusable, I don't think you can use exit to produce output. \$\endgroup\$ – Dennis Jun 10 '18 at 20:35
  • \$\begingroup\$ @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? \$\endgroup\$ – ovs Jun 10 '18 at 20:40
  • \$\begingroup\$ I think so. Allowing functions to output as full programs can doesn't override (imo) the rules for function submissions. \$\endgroup\$ – Dennis Jun 10 '18 at 20:46
1
\$\begingroup\$

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 !<>)

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 201 199 198 196 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 bytes thanks to ceilingcat.
int*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!

\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks. Was also able to golf the other expression. \$\endgroup\$ – Jonathan Frech Jun 20 '18 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.