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
    Sep 15 at 22:29
  • 5
    \$\begingroup\$ @xigoi I guess you could say that your presentation and this challenge were... adjacent :P \$\endgroup\$ Sep 16 at 3:20
7
\$\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
    Sep 15 at 15:14
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\$ Sep 15 at 15:16
  • 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\$ Sep 15 at 15:26
  • 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
    Sep 15 at 15:39
  • \$\begingroup\$ @m90 Nice observation! Actually saves 2 more bytes, because the ε`+ can simply be a sum of inner lists with O. \$\endgroup\$ Sep 15 at 15:51
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\$ Sep 15 at 14:31
  • \$\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
    Sep 15 at 15:26
  • \$\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
    Sep 15 at 17:43
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\$
1
\$\begingroup\$

Python 3, 51 bytes

f=lambda x,s="":x and f(round(x/2))+".+.-"[x%4]or""

Try it online! Outputs using . for 0, + for 1 and - for -1. Explanation: Port of @tsh's JavaScript solution, except that Python has Banker's rounding which saves a byte in Python 3. Or I could have just use Python 2 I guess.

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

Charcoal, 23 bytes

NθWθ«←§.+.-θ≔÷⁺¬﹪⊕θ⁴θ²θ

Try it online! Link is to verbose version of code. Outputs using . for 0, + for 1 and - for -1. Explanation: Another port of @tsh's JavaScript solution.

Nθ

Input the number to convert.

Wθ«

Repeat until it is zero.

←§.+.-θ

Output the previous digit using cyclic indexing. The digits are output right-to-left so that the final output is in the correct order.

≔÷⁺¬﹪⊕θ⁴θ²θ

Divide by two, rounding to even.

\$\endgroup\$
1
  • \$\begingroup\$ I quite like the RTL output trick! Nice usage of a language specific feature :) \$\endgroup\$ Oct 1 at 17:23

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.