Entrada : una o dos cadenas de '0' y '1'. Si hay 2, están separados por un espacio. Todas las cadenas tienen una longitud de al menos 1.

Salida : si se ingresó una cadena, se emiten 2. Si se ingresaron 2, se emite 1. Las cadenas de salida pueden ser lo que quieras, pero si ejecutar tu programa con la entrada A te da B, entonces ejecutarlo con B debe dar A (si ingresar 111 11da 00000, entonces la entrada 00000debe dar 111 11).

Eso significa que si canaliza su programa a sí mismo, debería recuperar lo que ingresó. Si su programa se llama foo, puede probarlo así:

>echo 101 101|foo|foo
101 101

Para evitar el uso de técnicas de fuerza bruta, su código debe poder ejecutarse con cadenas de 1000 dígitos en menos de 10 segundos. Mi solución de Python para esto toma menos de 1 segundo en cadenas de 10,000 dígitos, por lo que esto no debería ser un problema.

El código más corto gana.

Pitón, 183

Bijection se almacena en caché en el disco.

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]

editar: Vaya, parece que esta no es la primera respuesta inteligente. ¡El mío es consistente entre carreras!

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:]

Ejemplo de entradas / salidas:

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

Perl 5, 197 caracteres

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]}"

Con algunos saltos de línea:

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]}"

Este programa opera componiendo dos biyecciones:

• Se puede asignar un par de números naturales a una cadena binaria convirtiendo uno en un número base-2 y el otro en ceros iniciales extraños. nes esta función y Nes su inverso (excepto que se Nusa $_como parámetro).

• Se puede asignar un par de números naturales a un solo número natural utilizando la función de emparejamiento de Cantor . El primer mapbloque es esta función y el segundo es su inverso.

Por lo tanto, dos cadenas binarias se dividen en cuatro números, se combinan en dos números y luego se combinan en una cadena binaria, o viceversa.

Probado en 100 entradas aleatorias de cada tipo con cadenas de hasta 8 símbolos de largo. He estado buscando muchas maneras de hacer esto un poco más corto, pero voy a parar y publicarlo. Si hay espacio para optimizar aún más, probablemente esté en las expresiones aritméticas.

Perl, 56 caracteres

Se agregó +1 caracteres para el -pinterruptor de línea de comando

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

Python, 394

Estoy seguro de que esto se puede jugar más, pero este monolito utiliza la función de emparejamiento de Cantor y su inverso.

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))])

Explicación

Existe una asociación natural entre una cadena binaria y un par de números naturales: el primer número de la imagen es el número de ceros iniciales, y el segundo es el valor entero del número binario. Sabiendo que tenemos:

S ~ N^2

y con la biyección de Cantor

N ~ N^2

por lo tanto:

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

S ~ S^2

Donde S es un conjunto de todas las cadenas binarias. Esta solución implementa la biyección entre S y S ^ 2.