13
\$\begingroup\$

Consider a form of binary where digits can be any of \$1\$, \$0\$ and \$-1\$. We'll still call this "binary" because we convert the digits from base two. For example,

$$\begin{align} [1, 0, -1, 1]_2 & = 1 \times 2^3 + 0 \times 2^2 + -1 \times 2^1 + 1 \times 2^0 \\ & = 8 - 2 + 1 \\ & = 7 \end{align}$$

We'll call a representation of a number in this format a "non-adjacent form" if no non-zero digits are adjacent. \$[1, 0, -1, 1]_2\$ is not a non-adjacent form of \$7\$, as the last two digits are adjacent and non-zero. However, \$[1,0,0,-1]_2\$ is a non-adjacent form of \$7\$.

You should take a positive integer and convert it to a non-adjacent form. As every number has an infinite number of these forms (but only by prepending leading zeroes), you should output the form with no leading zeros. If the standard binary format of the input is a non-adjacent form (e.g. \$5 = 101_2\$), you should output that. You can output a list of integers, or a single string, or any other format the clearly shows the output. You may optionally choose to use any three distinct characters in place of 1, 0 and -1.

This is , so the shortest code in bytes wins.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ May we output in reverse order? \$\endgroup\$
    – Arnauld
    Sep 14 at 21:46
  • \$\begingroup\$ @Arnauld No, the output should have the least significant bit last \$\endgroup\$ Sep 14 at 22:39
  • 1
    \$\begingroup\$ I literally just read a presentation about non-adjacent binary before seeing this challenge… coincidence? \$\endgroup\$
    – xigoi
    2 days ago
  • 4
    \$\begingroup\$ @xigoi I guess you could say that your presentation and this challenge were... adjacent :P \$\endgroup\$ 2 days ago
6
\$\begingroup\$

K (ngn/k), 19 12 bytes

-/'2\-2!3 1*

Try it online!

Uses Prodinger's algorithm on Wikipedia:

Input   x
Output  np, nm
xh = x >> 1;
x3 = x + xh;
c = xh ^ x3;
np = x3 & c;
nm = xh & c;

And then the last three steps are not used because the & c part of np and nm erases the 1 bits where both are 1, but we're doing -/' so it doesn't matter. (Observation thanks to @m90)

How it translates to K:

-2!3 1*    given x, create (3x,x) and floor-divide both by 2
           which gives (x3,xh)
2\         convert to base 2, which gives a two-column matrix
           with lsb being the last row
           1st column is np, 2nd column is nm, but both-1 bits not handled
-/'        evaluate np - nm to get a vector of -1, 0, 1s
\$\endgroup\$
1
  • 4
    \$\begingroup\$ The whole >/1=/'\ part can be removed -- the & c only changes (1,1) to (0,0), which makes no difference if you're subtracting them. \$\endgroup\$
    – m90
    2 days ago
6
\$\begingroup\$

Jelly, 13 9 bytes

;0+HBU_/U

Try it online!

-4 bytes (^/&$ removed) thanks to @m90's observation that we don't need to clear shared 1 bits.

Look ma, no Unicode!

Literal translation of Prodinger's algorithm. x3 goes before xh, and U is used twice to align the binary representations of the two.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Well, technically, these are still in Unicode, they just happen to also be in ASCII :P \$\endgroup\$
    – user
    Sep 14 at 23:38
4
\$\begingroup\$

JavaScript, 35 bytes

f=n=>n?f(n+n%4/3>>1)+'OPON'[n%4]:''

Try it online!

Output O for 0, P for 1, N for -1.

-2 bytes by Arnauld.


Alternatively, as suggested by Arnauld, using 1 for 1, 2 for 0, 0 for 0, and, 3 for -1:

JavaScript, 31 bytes

f=n=>n?f(n+n%4/3>>1)+n%2*n%4:''

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I think you can save 2 bytes with n+n%4/3>>1. \$\endgroup\$
    – Arnauld
    Sep 15 at 6:28
  • \$\begingroup\$ 32 bytes by using 1, 2, 3. \$\endgroup\$
    – Arnauld
    Sep 15 at 6:35
2
\$\begingroup\$

05AB1E, 21 15 bytes

0‚¬2÷+2вí`(0ζRO

-6 bytes thanks to @m90, thanks to his observation that & c only changes [1,1] to [0,0], which doesn't matter when we're subtracting them.

Try it online or verify some more test cases.

Explanation:

0‚        # Pair the (implicit) input with 0
  ¬       # Get the first item of this pair (the input) without popping
   2÷     # Integer-divide it by 2
     +    # Add it to both the input and 0 in the pair
          # (we now have the pair [input+input//2, input//2])
      2в  # Convert both inner values to a binary-list
í         # Reverse each inner list
 `        # Pop and push both lists separated to the stack
  (       # Negate all values in the top list
   0ζ     # Zip the two lists together with 0 as filler
     R    # Reverse the list of pairs back again
      O   # Sum each inner pair together
          # (after which the resulting list is output implicitly)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I wonder if a port of my naive attempt would be shorter. Essentially it gets the Cartesian power of [1,0,-1] for each \$1 \le i \le n\$ (\$n\$ being the input), then gets the first one that is both a non-adjacent form, and that, when converted from base 2, equals \$n\$ \$\endgroup\$ 2 days ago
  • 1
    \$\begingroup\$ @cairdcoinheringaahing It appears to be 21 bytes as well, haha. :D Will add it to my answer as well. Maybe someone sees something to golf in either or multiple of the approaches. \$\endgroup\$ 2 days ago
  • 1
    \$\begingroup\$ The second one can be shortened to 0‚¬2÷+2вí`0ζRε`-, using the observation that the & c only changes (1,1) to (0,0), which makes no difference if one is subtracting them. \$\endgroup\$
    – m90
    2 days ago
  • \$\begingroup\$ @m90 Nice observation! Actually saves 2 more bytes, because the ε`+ can simply be a sum of inner lists with O. \$\endgroup\$ 2 days ago
2
\$\begingroup\$

Python 3, 176 103 bytes

Literal translation of Prodinger's algorithm. By no means the shortest python 3 answer that should be attainable. it's been a while on here so looking forward to getting back into it!

x=int(input())
h=x>>1
t=h+x
c=h^t
p=bin(t&c)
m=bin(h&c)
n=[]
j=len(p)-2
k=len(m)-2
for i in range(j):n.append(int(p[i+2]))
for i in range(k):n[j-k+i]=-int(m[i+2])*(m[i+2]==0)or 1
print(n)

If anyone can help shorten it I'd appreciate it, there must be an easier way to concatenate the two positive and negative value lists.

Using m90's answer it can be shortened vastly predominately by using zip!

enter code x=int(input())
print([*[int(x)-int(y)for x,y in zip(*[f".{x//2+z:0{len(bin(x*3))-3}b}"for z in[x,0]])]])
\$\endgroup\$
3
  • \$\begingroup\$ I'm not too good at Python either, but here it's already a bit shorter: 142 bytes. \$\endgroup\$ 2 days ago
  • \$\begingroup\$ Some different improvements make it 103 -- including using the observation that the & c only changes (1,1) to (0,0), which makes no difference if one is subtracting them. \$\endgroup\$
    – m90
    2 days ago
  • \$\begingroup\$ @m90 I knew there had to be a better way to combine them all together, that's a great answer, I think my biggest failure was not really understanding the maths behind it. \$\endgroup\$
    – george
    2 days ago
1
\$\begingroup\$

C (clang), 103 \$\cdots\$ 96 94 bytes

m;i;f(n){int r[n];for(i=!n,n+=*r=m=n/2;n;n/=2,m/=2)r[i++]=n%2-m%2;for(;i--;)putchar(r[i]+49);}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Inputs positive integer \$n\$.
Outputs \$n\$ converted to its non-adjacent form using \$2\$ for \$1\$s, \$1\$ for \$0\$s, and \$0\$ for \$-1\$s.

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

Ruby, 41 40 bytes

f=->n{n>0?f[(n-w=n%2*(2-n%4))/2]+[w]:[]}

Try it online!

\$\endgroup\$

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.