Rewrite strings without changing their order

Question

Lexicographic Ordering

For this challenge we will be talking about the lexicographic ordering of strings. If you know how to put words in alphabetical order you already understand the basic idea of lexicographic ordering.

Lexicographic ordering is a way of ordering strings of characters.

When comparing two strings lexicographically, you look at the first character of each string. If one of the strings is empty and has no first character that string is smaller. If the first characters are different then the string with the smaller first character is smaller. If the characters are equal we remove them from the strings and compare the rest of the strings

Here is a Haskell program that implements this comparison

compare :: Ord a => [a] -> [a] -> Ordering
compare [] [] =
 EQ
compare [] (y : ys) =
 LT
compare (x : xs) [] =
 GT
compare (x : xs) (y : ys) =
 if
 x == y
 then
 compare xs ys
 else
 compare x y

Lexicograpic ordering has some interesting properties. Just like integers, every string has a next biggest string. For example after [1,0,1,0] there is [1,0,1,0,0], and there is nothing in between. But unlike integers there are strings which have an infinite number of strings between each other. For example [0] and [1], all strings of more than 1 0 are greater than [0] but less than [1].

Challenge

In this challenge you will write a program or function (from now on just called "function"), which maps binary strings (that is, strings made of an alphabet of two symbols) to ternary strings (strings made of an alphabet of three symbols).

Your function should be bijective, meaning that every string gives a unique output, and every ternary string is the output for some input.

Your function should also be monotonic, meaning that it preserves comparisons when applied

$$ x < y \iff f(x) < f(y) $$

Where \$<\$ is the lexicographic ordering of the strings.

Scoring

This is code-golf so answers will be scored in bytes with fewer being better.

IO

You may take input and produce output as a string with chosen characters for the sets of 2 and 3 symbols, or as a list / array / vector of integers.

Testing

It's rather hard to make test cases for this. However it should be noted that when given a string of only 0s your code must give back the same string. So I can give the following test cases

[] -> []
[0] -> [0]
[0, 0, 0] -> [0, 0, 0]

However this doesn't go very far in terms of testing.

So I recommend you also run a random battery of strings checking that

• The monotonicity property holds
• Your function preserves the number of 0s on the end

• Greg Martin: Is there more than one such function?
• Nitrodon: This should be an order-preserving non-identity bijection between the set of binary strings and itself: 0^n -> 0^n, 00w -> 0w, 010^n -> 10^n, 01w -> 10w, 10^n -> 110^n, 1w -> 11w (where w ranges over all strings with at least one 1)
• Wheat Wizard: @Nitrodon Nice! With that we can show there are in fact \$\beth_1\$ solutions, or an unaccountably infinite number of them.

Answer 1

Haskell, 41 bytes

f x|sum x<1=x
f(0:y:x)=y:f x
f(1:x)=2:f x

Try it online!

Here's a solution. Just to show that this is possible and give a potential starting point for others.

Explanation

The first thing we can notice is that any valid \$f\$ must preserve the number of zeros at the end of the input in the output.

The proof of this is pretty simple. Lets say we have some string \$x\$. We know that there are no strings between \$x\$ and \$x\mathbin{|}0\$ (here \$\mathbin{|}\$ represents appending a character to a string). Thus there can be no strings between \$f(x)\$ and \$f(x\mathbin{|}0)\$. If there were some string \$y\$ such that \$f(x) < f(y) < f(x\mathbin{|}0)\$, then it would have to be that \$x < y < x \mathbin{|} 0\$. So since there are no strings between \$f(x)\$ and \$f(x\mathbin{|}0)\$, then \$f(x\mathbin{|}0) = f(x)\mathbin{|}0\$.

So this allows us to write the first line of our program

f x|sum x<1=x

Which says if we get a list of only \0ドル\$s then output that list intact.

It might be tempting to say that all zeros should be preserved in the output, not just trailing ones. However this ends up not being possible, I will leave the proof of this as an exercise for the reader.

Now the task is to translate strings with no trailing zeros, while preserving order. The way I chose to do this is pretty simple. We go left to right replacing certain sequences with the correct symbols. If we see a zero we replace read it as the next symbol (and skip over that symbol), there must be a next symbol since otherwise there would be a trailing \0ドル\$.

f(0:y:x)=y:f x

If the symbol is \1ドル\$ we read it as \2ドル\$.

f(1:x)=2:f x

Haskell, (削除) 52 (削除ここまで) 48 bytes

4 bytes saved by ovs

f(0:x)=0:f x
f(1:x)|sum x>0,z:y<-x=1+z:f y
f x=x

Try it online!

This is a different bijection discovered by a friend of mine and golfed by me.

• ovs: 48 bytes on the second bijection by using the base case of f x=x for [1, 0, ..., 0].

Answer 2

Jelly, 10 bytes

2ḢḢ?;ßƊ1Ẹ?

A monadic Link that accepts a list (of \$\{0,1\}\$) and yields a list (of \$\{0,1,2\}\$).

Try it online!

How?

Results in the same mapping as used by Wheat Wizard.

2ḢḢ?;ßƊ1Ẹ? - Link: list, A
 Ẹ? - if: any?
 Ɗ - then: last three links as a monad - f(A):
 Ḣ? - if: head (leftmost element of A (or 0 if empty);
 changes A in place)
2 - then: literal two
 Ḣ - else: head (leftmost element of augmented A (or 0 if empty);
 changes A in place again)
 ß - call this Link again -> f(augmented A)
 ; - concatenate
 1 - else: identity (yield A)

• Nick Kennedy: Nice. Might be better to start the footer with F since otherwise you lose most of the input part of the output before it gets displayed
• Jonathan Allan: @NickKennedy oops, thanks!

Answer 3

JavaScript (Node.js), 34 bytes

s=>s.replace(/0(?=.*2)./g,t=>t/2);

Try it online!

Wheat Wizard♦'s idea using the allowance of custom char

Answer 4

Retina, 20 bytes

/0*$/%`1(.)
$.(1ドル*__

Try it online! Explanation: Uses @WheatWizard's friend's mapping.

/0*$/%`

Match trailing zeros and temporarily exclude them from the following substitution.

1(.)
$.(1ドル*__

Match a 1 followed by a digit and replace it with 1 more than the digit, i.e. 11 becomes 2, 10 (in the middle) becomes 1, but other digits are unaffected.

Answer 5

Charcoal, 20 bytes

≔I⪪⮌S1υWΣυ¿⊟υ2I⊟υFυ0

Try it online! Link is to verbose version of code. Explanation: Uses @WheatWizard's mapping.

≔I⪪⮌S1υ

Reverse the input, split it into digits, and cast the digits to integer.

WΣυ

Repeat while there are still 1s left in the input...

¿⊟υ2

... if the current digit is a 1 then print a 2...

I⊟υ

... otherwise print the next digit.

Fυ0

Print any trailing zeros.