You have a coin that produces 0 or 1. But you suspect the coin may be biased, meaning that the probability of 0 (or 1) is not necessarily 1/2.

A well known procedure to "transform" a biased coin into a fair coin (i.e. to obtain equally likely results), as proposed by von Neumann, is as follows. Produce (non-overlapping) blocks of two coin tosses until the two values of a block differ; and output the first value in that block (the second value would also do, but for the purposes of this challenge we choose the first). Intuitively, 1 may be more likely than 0, but 01 and 10 will be equally likely.

For example, the input 1110... would discard the first block, then produce a 1 from the second block, ...

This procedure is expensive, because several coin tosses are consumed to generate a single result.

The challenge

Take a finite sequence of zeros and ones, representing tosses of the original coin, and produce the maximum number of results according to the above procedure, until all the input is consumed.

The last block may be incomplete, if the number of input values is odd. For example, the input sequence 11111 would produce no result (the first two blocks have equal values, and the third block is incomplete).


The input can have any non-negative number of values, not necessarily positive or even.

The input format may be:

  • an array of zeros and ones;
  • a string of zeros and ones with an optional separator.

Output format may be:

  • a string of zeros and ones, with or without separators;
  • an array of zeros and ones;
  • strings containing a single zero or one, separated by newlines;
  • any similar, reasonable format that suits your language.

Code golf. Fewest bytes wins.

Test cases

Input and output are here assumed to be strings.

Input         -->  Output

'1110'        -->  '1'
'11000110'    -->  '01'
'1100011'     -->  '0'
'00'          -->  ''
'1'           -->  ''
''            -->  ''
'1101001'     -->  '0'
'1011101010'  -->  '1111'
  • \$\begingroup\$ Shouldn't there be two possible outputs for each input (i.e. the bitwise not of the current output)? \$\endgroup\$ – wizzwizz4 Mar 5 '16 at 17:23
  • 1
    \$\begingroup\$ @wizzwizz4 You can take one or the other, but not both (because then they wouldn't be statistically independent). In this challenge I arbitrarily chose the first \$\endgroup\$ – Luis Mendo Mar 5 '16 at 17:28
  • 6
    \$\begingroup\$ You're too suspicious of the coin. Just flip the thing ;) \$\endgroup\$ – Geobits Mar 5 '16 at 20:32
  • 2
    \$\begingroup\$ @IGoBest I'm not so sure :-D \$\endgroup\$ – Luis Mendo Mar 6 '16 at 4:10
  • 1
    \$\begingroup\$ @DonMuesli Man, the list of caveats in that paper is impressive :P \$\endgroup\$ – Geobits Mar 7 '16 at 2:22

35 Answers 35

1 2

Java 117 bytes

(or 10 if we consider numerical system with base 117)

String z(char[]s){String r="";for(int i=0,x=-1;++x<s.length/2;i+=2)r+=(s[i]==s[i+1]?"":s[i]=='0'?"0":"1");return r;}

GNU sed, 19 bytes

#!/bin/sed -rf

Simple and boring translation of Martin Büttner♦'s Retina solution. Except that I used 11|00 in place of .(\1) (for the same score). 18 bytes of code, plus one for the -r.


C#, 83 bytes


First, replace odd-numbered items which are not equal to their predecessors with the predecessor, while setting all the rest to 2, then drop all items equal to 2.


Ruby, 66 bytes

initial attempt; likely room for improvement. Run with "ruby -n" and then enter input followed by enter key.

$_.chomp!;i,s=0,'';(s<<$_[i] if $_[i]!=$_[i+1];i+=2)until !$_[i+1];p s

Python, 72 bytes

This definitely won't be the shortest, but hopefully it'll at least give someone a headache.

lambda s:hex(int('110'+s[::-1],4))[:3:-1].translate({48:'',53:'',52:48})
1 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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