11
\$\begingroup\$

A variable number of bits is an array of 0 or more bits. So [0, 1] is a variable number of bits, but so is [].

Write a function or program that, given an nonnegative integer returns a variable number of bits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the binary digits of the integer. In such a system 5 becomes [1, 0, 1] (or 0b101), but it's not one-to-one, because 0b0101 or [0, 1, 0, 1] also means 5.

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable bit array is also not one-to-one. You must map to every possible variable bit array, including [].


Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ May we return a string of 0's and 1's? \$\endgroup\$ – xnor Feb 12 '16 at 21:18
  • \$\begingroup\$ @xnor Yes, a string of 0s and 1s is fine. \$\endgroup\$ – orlp Feb 12 '16 at 21:19
4
\$\begingroup\$

Jelly, 3 bytes

‘BḊ

Same idea as xnor: maps 0 1 2 3 4 ... to [] [0] [1] [0 0] [0 1] ...; the code is basically increment → binary → remove first.

Try it out online.

\$\endgroup\$
10
\$\begingroup\$

Python, 20 bytes

lambda n:bin(~n)[4:]

Test:

>> [bin(~n)[4:] for n in range(16)]
['', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111', '0000']

Doing lambda n:bin(n+1)[3:] increments the input, then takes the binary representation with the first symbol removed ([3:] because the prefix 0b is two chars chars). Since any positive number starts with 1 in binary, this uniquely gives a binary representation.

A byte is saved by instead using the bit complement ~n to get the negation -(n+1), and removing the negative sign by chopping off one more symbol.

\$\endgroup\$
  • 1
    \$\begingroup\$ Inverse: lambda s:int('1'+s,2)-1. \$\endgroup\$ – orlp Feb 12 '16 at 21:45
2
\$\begingroup\$

Pyth, 5 bytes

t.BhQ

Simply a translation of xnor's answer into Pyth.

Q is eval()'d input(), h increments it, .B converts it to a binary string, and t takes the "tail" (which is everything except the first character).

\$\endgroup\$
2
\$\begingroup\$

Haskell, 41 38 30 29 bytes

l="":[b:x|x<-l,b<-"01"]
(l!!)

Usage example: (l!!) 4 -> "10".

Starting with the empty list as the first element, walk lazily through the list and append the current element with 0 and with 1 in front of it.

Edit: @xnor saved 3 11 bytes. Thanks!

\$\endgroup\$
  • \$\begingroup\$ Interesting idea. The iterated function can be written [(0:),(1:)]<*> \$\endgroup\$ – xnor Feb 12 '16 at 22:20
  • \$\begingroup\$ @xnor: Oh, you showed me the <*> trick before, but I forgot about it. Thanks again! \$\endgroup\$ – nimi Feb 12 '16 at 22:26
  • \$\begingroup\$ Ooh, you can define the whole list lazily: l=[]:[b:x|x<-l,b<-[0,1]];(l!!). \$\endgroup\$ – xnor Feb 12 '16 at 22:53
  • \$\begingroup\$ @xnor: Great! Thanks a lot! Oh, switching to strings saves one more byte. \$\endgroup\$ – nimi Feb 13 '16 at 1:01
  • \$\begingroup\$ I feel like there should be some shorter way to express [b:x|x<-l,b<-"01"] with a product or concat-map, but the product expression (:)<$>[0,1]<*>l goes in the wrong order, first prepending 0 to everything, never getting to 1 because the list is infinite. Do you have any ideas? \$\endgroup\$ – xnor Feb 13 '16 at 3:03
1
\$\begingroup\$

JavaScript (ES6), 29 bytes

x=>(~x).toString(2).slice(2)

Same idea as xnor.

f=x=>(~x).toString(2).slice(2);
[...Array(100)].map((v,x)=>A.textContent+=x + ': ' + f(x) + '\n')
<pre id=A></pre>

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

Jolf, 4 bytes

Try it here!

wBhj
  hj  input + 1
 B    converted to binary
w     with first removed.

Very simple strategy, also happens to be the shortest.

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

Haskell, 35 bytes

h 1=[]
h n=mod n 2:h(div n 2)
h.(+1)

Haskell doesn't have a binary built-in, so the (reversed) conversion is done manually. To remove the initial 1, the base case has 1 transform to the empty list.

Edit: Saved a byte by conjugating by the +1 instead.

h 0=[]
h m=1-mod m 2:h(div(m+1)2-1)
\$\endgroup\$
1
\$\begingroup\$

C, 40 bytes

f(n){if(++n/2)putchar(n%2+48),f(n/2-1);}

Converts the input to bijective base 2 (with symbols 0 and 1), like the other answers.

ideone it!

\$\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.