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
, all strings of more than 1
0 are greater than
 but less than
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.
This is code-golf so answers will be scored in bytes with fewer being better.
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.
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]
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