Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
add comment

5 Answers

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!

share|improve this answer
    
+1 for being a smartass –  ardnew Nov 5 '12 at 14:45
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Perl, 56 chars

added +1 char for -p command line switch

$s.=1;$h{$h{$_}||=(split>1?$s:"$s $s").$/}=$_;$_=$h{$_}
share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.