Bijection between binary strings and pairs thereof

Question

Input: Either one or two strings consisting of '0's and '1's. If there are 2, they are separated by a space. All strings are of length at least 1.

Output:

• If a single input was given as input, 2 are output.
• If 2 were input, 1 is output.

The output strings can be whatever you like, but if running your program with input A gives you B, then running it with B must give A (if inputting 111 11 gives 00000, then inputting 00000 must give 111 11).

That means if you pipe your program to itself, you should get back whatever you input. If your program is called foo, you can test that like this:

>echo 101 101|foo|foo
101 101

To prevent the use of brute force techniques, your code should be able to run with 1000 digit strings in under 10 seconds. My Python solution for this takes less than 1 second on 10000 digit strings so this shouldn't be a problem.

Shortest code wins.

Answer 1

Python, 183

Bijection is cached on disk.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]

edit: Oops, looks like this isn't the first smartassed answer. Mine's consistent between runs!

Answer 2

Python, 326

s=lambda i,l:bin(i)[2:].zfill(l)
f=lambda n:2**n*(n-3)+4
g=lambda n:2**n-2
i=raw_input()
if' 'in i:
 a,b=i.split();n=len(a+b);r=f(n)+int(a+b,2)*(n-1)+len(a)-1;l=1
 while g(l+1)<=r:l+=1
 print s(r-g(l),l)
else:
 n=len(i);r=g(n)+int(i,2);l=2
 while f(l+1)<=r:l+=1
 r-=f(l);p=r%(l-1)+1;w=s(r/(l-1),l);print w[:p],w[p:]

Example inputs/outputs:

     input | output
-----------+-----------
         0 | 0 0
       0 0 | 0
     10 10 | 10101
     10101 | 10 10
0000000000 | 101 0100
  101 0100 | 0000000000

Answer 3

Perl 5, 197 characters

sub n{'0'x$_[0].sprintf'%b',$_[1]}sub N{/0*(?=.)/;length$&,oct"0b$'"}$_=<>;print/ /?n map{($a,$b)=N;($a+$b)*($a+$b+1)/2+$b}split:"@{[map{$w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y}N]}"

With some line breaks:

sub n{'0'x$_[0].sprintf'%b',$_[1]}
sub N{/0*(?=.)/;length$&,oct"0b$'"}
$_=<>;print/ /?n map{
  ($a,$b)=N;($a+$b)*($a+$b+1)/2+$b
}split:"@{[map{
  $w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y
}N]}"

This program operates by composing two bijections:

• A pair of natural numbers may be mapped to a binary string by converting one to a base-2 number and the other to extraneous leading zeroes. n is this function and N is its inverse (except that N uses $_ as its parameter).

• A pair of natural numbers may be mapped to a single natural number using the Cantor pairing function. The first map's block is this function and the second is its inverse.

Thus two binary strings are split into four numbers, combined into two numbers, and then combined into one binary string — or vice versa.

Tested on 100 random inputs of each type with strings up to 8 symbols long. I've been finding lots of ways to make this a little bit shorter, but I'm going to stop and post it. If there's room to optimize further, it's probably in the arithmetic expressions.

Answer 4

Perl, 56 chars

added +1 char for -p command line switch

$s.=1;$h{$h{$_}||=(split>1?$s:"$s $s").$/}=$_;$_=$h{$_}

Answer 5

R, 209 bytes

Note that this code will fail for numbers outside R's native numeric range; the approach should be valid for any number, though, and this could be solved using arbitrary-precision calculations (for instance, with the R GMP library).

function(x,z=2^nchar(x)+strtoi(x,2)-1,s=function(v,l=log2(v+1)%/%1)paste((v+1)%/%2^(l:1-1)%%2,collapse=''),d=sum(cumsum(0:z)<z),y=z-sum(0:(d-1)))`if`(length(x)>1,s(sum(0:(sum(z)-2))+z[2]),sapply(c(d+1-y,y),s))

Try it online!

How does it work?

First, we convert each string x of 0s & 1s into an integer value z, corresponding to its lexicographical index. The code for this is:

z=2^nchar(x)+strtoi(x,2)-1

And at the end of the bijection, we'll convert this back to a string using the opposite function:

s=function(v,l=log2(v+1)%/%1)paste((v+1)%/%2^(l:1-1)%%2,collapse='')

Using this scheme, the following strings correspond to the integer values 1 to 20:

sapply(1:20,string)
 [1] "0"    "1"    "00"   "01"   "10"   "11"   "000"  "001"  "010"  "011"  
[10] "100"  "101"  "110"  "111"  "0000" "0001" "0010" "0011" "0100" "0101"

Now, to get a single number from a pair of numbers, we consider each number pair to be x and y coordinates of a grid, and we sequentially number each position in the grid by moving along the diagonals (so the linear sequence gradually fills the two-dimensional space): This function calculates the number for each pair of coordinates:

num=function(c)sum(0:(sum(c)-2))+c[2]

Which leads to the following mapping:

matrix(apply(which(matrix(T,6,6),T),1,num),6,6)
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    3    6   10   15   21
[2,]    2    5    9   14   20   27
[3,]    4    8   13   19   26   34
[4,]    7   12   18   25   33   42
[5,]   11   17   24   32   41   51
[6,]   16   23   31   40   50   61

The 'bijection' function just rolls all these steps together.

Answer 6

Python, 394

I'm sure this can be golfed further, but this monolith uses the Cantor Pairing Function and its inverse.

import math
s=lambda n:n*(n+1)/2
p=lambda a:'0'*a[0]+bin(a[1])[2:]
q=lambda t:t.index('1')
B=raw_input().split()
def f(x,y):r=x+y+1;return s(r)-[y,x][r%2]-1
def g(z):r=int(math.ceil((2*(z+1)+1/4.)**(1/2.)-1/2.))-1;d=s(r+1)-z-1;return [(d,r-d),(r-d,d)][r%2]
if len(B)<2:a=[g(q(B[0])),g(int(B[0],2))];print p(a[0])+' '+p(a[1])
else:print p([f(q(B[0]),int(B[0],2)),f(q(B[1]),int(B[1],2))])

Explanation

There is a natural association between a binary string and a pair of natural numbers: the first number of the image is the number of leading zeros, and the second is the integer value of the binary number. Knowing that we have:

S ~ N^2

and with the Cantor bijection

N ~ N^2

therefore:

S ~ N^2 ~ N^4 ~ S^2

S ~ S^2

Where S is set of all binary strings. This solution implements the bijection between S and S^2.