# Bijection between binary strings and pairs thereof

Input: Either one or two strings 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 one string was 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 10,000 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!

-
+1 for being a smartass – ardnew Nov 5 '12 at 14:45

# 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 `1`s) seems to crash, and input of the pair `0` and 50 `1`s gives the same result as `0` and 51 `1`s, both of which output 64 `1`s. I think there's some kind of overflow with the number of leading `0`s, 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

# 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