36
3
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).
Rules
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'
Shouldn't there be two possible outputs for each input (i.e. the bitwise not of the current output)? – wizzwizz4 – 2016-03-05T17:23:09.783
1@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 – Luis Mendo – 2016-03-05T17:28:15.640
No, I mean in the question body you say we could take the first or second number, but your test-cases just take the first. – wizzwizz4 – 2016-03-05T17:29:27.643
@wizzwizz4 I've edited to clarify: only the first. Thanks for the heads-up – Luis Mendo – 2016-03-05T17:33:30.000
6You're too suspicious of the coin. Just flip the thing ;) – Geobits – 2016-03-05T20:32:23.697
2
@IGoBest I'm not so sure :-D
– Luis Mendo – 2016-03-06T04:10:11.1631@DonMuesli Man, the list of caveats in that paper is impressive :P – Geobits – 2016-03-07T02:22:21.933