Making a coin fair

Retina, 16 14 bytes

(.)\1|(.)?.
$2

Try it online!

Explanation

This is fairly simple. The code defines a single regex substitution replacing all (non-overlapping) matches of (.)\1|(.)?. with whatever the second group captured. This combines three different cases into one:

(.)\1 --> <empty>

If two repeated digits are equal, we remove them from the string (because group 2 is unused).

(.).  --> $2

Otherwise, if we can match two characters, remove the second one, by replacing both of them with the first. If that's not the case the ? will omit the group:

.     --> <empty>

This only happens if there is an unpaired trailing character, which is also removed.

Labyrinth, 21 12 bytes

"(. :
""*$,@

A rare example of a compact Labyrinth program that also has no no-ops. The | in the previous version was completely unnecessary, and removing it massively reduced the size of the program. In fact, Lab's beating Retina!

Try it online!

The bottom-left " can also be a space, but having it there greatly simplifies the explanation.

Explanation

This one's a little trickier, so it's accompanied by images. But first, a quick primer:

• Labyrinth is a stack-based 2D language. Memory consists of a main stack and an auxiliary stack.
• Labyrinth's stacks are bottomless and filled with zeroes, so performing operations on an empty stack is not an error.
• At each junction, where there are two or more paths for the instruction pointer to go, the top of the main stack is checked to figure out where to go next. Negative is turn left, zero is straight ahead and positive is turn right. If a turn fails, the pointer tries to turn in the other direction.

Setup

The program starts at the top-left ", which is a no-op. Then we perform:

(        Decrement a bottom zero to -1. Since -1 is negative we try to turn 
         left at this junction, fail, and turn right instead.
"        No-op junction, turn left
*        Multiply top of stack (-1) with a 0 at bottom of stack, giving 0.
         This makes us go straight ahead at this junction.
$        Bitwise xor (of 0 and 0)

This leaves the stack with a single 0 on it, which is as good as empty for the purposes of Labyrinth.

Reading input and termination

, reads a char from input, returning 48 or 49 for 0 or 1 respectively, and -1 on EOF. Since this is nonzero, either way we turn into the :, which duplicates the top of the stack.

The : is at a dead-end, so we turn around and execute , once more. Now if the last input was EOF, then we turn left and terminate with @, else we turn right, with the stack looking like [a a b] (where a, b are the two chars).

Interpreting the coin toss

If we didn't terminate, our next move is to execute $ (bitwise xor) again. This yields 0 if the input chars were the same, 1 otherwise. We then multiply a with this result, giving either 0 or a. Since the * is at a junction, this top stack value determines what happens next.

In the 0 case, we go straight ahead and execute three " no-ops, before perform a ( decrement. Like the setup, this makes us turn and execute "*$, leaving us ready to read more chars.

Otherwise, in the a case, we turn right at the junction since a is positive (48 or 49). . outputs the char, leaving the stack empty, and ( decrements the top of the stack, turning a 0 to -1. Once again, this makes us turn left, executing "*$ like in the setup, also leaving us ready to read more input.

CJam, 10 8 bytes

l2/{)-}%

Test it here.

Explanation

This is a very simple solution: in each pair, remove all instances of the last character. Repeated digits and unpaired trailing digits will be removed, as will be the second digit in any pair of unequal digits:

"0"  --> ""
"1"  --> ""
"00" --> ""
"01" --> "0"
"10" --> "1"
"11" --> ""

This leaves only the digits we're looking for. Here's how the code computes this:

l     e# Read input.
2/    e# Split into pairs. Odd inputs will yield a single-character string at the end.
{     e# Map this block over the pairs...
  )   e#   Pull the last character off the string.
  -   e#   Remove all occurrences of that character from the remainder (which is either
      e#   an empty string to begin with or a single-digit string).
}%

When the list is auto-printed at the end of the program, the empty strings are simply omitted.