38
\$\begingroup\$

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'
Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Shouldn't there be two possible outputs for each input (i.e. the bitwise not of the current output)? \$\endgroup\$
    – wizzwizz4
    Commented Mar 5, 2016 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
    Commented Mar 5, 2016 at 17:28
  • 6
    \$\begingroup\$ You're too suspicious of the coin. Just flip the thing ;) \$\endgroup\$
    – Geobits
    Commented Mar 5, 2016 at 20:32
  • 2
    \$\begingroup\$ @IGoBest I'm not so sure :-D \$\endgroup\$
    – Luis Mendo
    Commented Mar 6, 2016 at 4:10
  • 1
    \$\begingroup\$ @DonMuesli Man, the list of caveats in that paper is impressive :P \$\endgroup\$
    – Geobits
    Commented Mar 7, 2016 at 2:22

38 Answers 38

Reset to default
1
2
1
\$\begingroup\$

DOS/Windows Batch, 201 162 bytes

@echo off
set/pi=
:a
for /f "tokens=2" %%a in ("%i%") do goto l
exit/b
:l
for /f "tokens=1,2" %%a in ("%i:~0,4%") do if %%a neq %%b echo %%a
set "i=%i:~4%"
goto a

Input is a space seperated string, for example 1 0 0 1 1. Start from cmd, otherwise the screen exits immediately

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

beeswax, 45 35 bytes

I could golf it down by 10 bytes—not too bad.

pgy~1z;L?gAF1<<?V_
>&?@yg&?~@ KQd{b

I took the reading a full string of coin tosses approach, which makes the program pretty large. Just reading single integers one by one would make the program smaller—maybe around 22 bytes or so—but also very inconvenient to use.

Examples:

julia> beeswax("FairCoin.bswx")
s1110
1
Program finished!

julia> beeswax("FairCoin.bswx")
s11000110
01
Program finished!

julia> beeswax("FairCoin.bswx")
s1100011
0
Program finished!

julia> beeswax("FairCoin.bswx")
s00

Program finished!

julia> beeswax("FairCoin.bswx")
s10101001010111111100000010011001110100010110101110100001011
1110001010000111100
Program finished!

My beeswax GitHub repository.

My beeswax examples on Rosetta Code.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 4 bytes

²ıUṫ

Try it online!

Port of Dennis's Jelly answer.

Explanation

²ıUṫ  # Implicit input
²     # Split into pairs
 ı    # Map over this list:
  U   #  Uniquify the pair
   ṫ  #  Remove the last character
      # Implicit output
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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;}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

GNU sed, 19 bytes

#!/bin/sed -rf
s/11|00|(.?)./\1/g

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C#, 83 bytes

int[]M(int[]x)=>x.Select((v,i)=>i%2>0&&x[i-1]!=v?x[i-1]:2).Where(v=>v<2).ToArray();

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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})
Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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