# Bijection between binary strings and pairs thereof

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.

## Python, 183

Bijection is cached on disk.

x=raw_input()
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!

• You can replace if x not in d: with if(x in d)-1: and save a byte. – Jonathan Frech Sep 11 '17 at 19:07

# 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


### 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. • The input of 1111111111111111111111111111111111111111111111111111111111111111 (64 1s) seems to crash, and input of the pair 0 and 50 1s gives the same result as 0 and 51 1s, both of which output 64 1s. I think there's some kind of overflow with the number of leading 0s, so a solution might be to get the output N value from a Cantor pairing of input N values, and the n value from a pairing of n values (or vice versa for the inverse). I'm a perl noob though, so I might have just done something wrong. – cardboard_box Nov 3 '12 at 17:51 • Yes, this program is not going to work for binary strings whose 1-containing part is too big for Perl to work with as integers. I felt that was a reasonable implementation limitation in exchange for the elegance of the algorithm. In principle, all of the numeric operations could be replaced with bigint ones. – Kevin Reid Nov 3 '12 at 19:02 ## Perl, 56 chars added +1 char for -p command line switch $s.=1;$h{$h{$_}||=(split>1?$s:"$s$s").$/}=$_;$_=$h{\$_}

• Maybe I wasn't clear enough. I want your program to take some input, print some output, and then terminate. Then running the program again with the output as input should give back what you first input. – cardboard_box Nov 3 '12 at 1:39
• @cardboard_box the mapping should persist between multiple runs? you should really add that to the problem description – ardnew Nov 3 '12 at 2:10

# 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.

# 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.

• Just noticed that this fails on any input that is all 0's, I'll fix it tomorrow, I'm tired of python right now -_- – scleaver Nov 5 '12 at 22:15