Byte count assumes ISO 8859-1 encoding.
Try it online!
This will probably be easier to explain based on my old, less golfed, version and then showing how I shortened it. I used to convert binary to decimal like this:
The only sensible way to construct a decimal number in Retina is by counting things (because Retina has a couple of features that let it print a decimal number representing an amount). So really the only possible approach is to convert the binary to unary, and then to count the number of unary digits. The last line does the counting, so the first four convert binary to unary.
How do we do that? In general, to convert from a list of bits to an integer, we initialise the result to
0 and then go through the bits from most to least significant, double the value we already have and add the current bit. E.g. if the binary number is
1011, we'd really compute:
(((0 * 2 + 1) * 2 + 0) * 2 + 1) * 2 + 1 = 11
^ ^ ^ ^
Where I've marked the individual bits for clarity.
The trick to doing this in unary is a) that doubling simply means repeating the number and b) since we're counting the
1s at the end, we don't even need to distinguish between
1s in the process. This will become clearer in a second.
What the program does is that it first adds a comma to the beginning as marker for how much of the input we've already processed:
Left of the marker, we'll have the value we're accumulating (which is correctly initialised to the unary representation of zero), and right of the value will be the next bit to process. Now we apply the following substitution in a loop:
Just looking at
$1,, this moves the marker one bit to the right each time. But we also insert
$`, which is everything in front of the marker, i.e. the current value, which we're doubling. Here are the individual steps when processing input
1011, where I've marked the result of inserting
$` above each line (it's empty for the first step):
You'll see that we've retained and doubled the zero along with everything else, but since we're disregarding them at the end, it doesn't matter how often we've doubled them, as long as the number of
1s is correct. If you count them, there are
11 of them, just what we need.
So that leaves the question of how to golf this down to 12 bytes. The most expensive part of the 18-byte version is having to use the marker. The goal is to get rid of that. We really want to double the prefix of every bit, so a first idea might be this:
The problem is that these substitutions happen simultaneously, so first bit doesn't get doubled for each bit, but it just gets copied once each time. For input
1011 we'd get (marking the inserted
_ __ ___
We do still need to process the input recursively so that the doubled first prefix is doubled again by the second and so on. One idea is to insert markers everywhere and repeatedly replace them with the prefix:
After replacing each marker with the prefix for the first time, we need to remember where the beginning of the input was, so we insert linefeeds as well and use the
% option to make sure that the next
$` only picks up things up the closest linefeed.
This does work, but it's still too long (16 bytes when counting
1s at the end). How about we turn things around? The places where we want to insert markers are identified by
\B (a position between two digits). Why don't we simply insert prefixes into those positions? This almost works, but the difference is that in the previous solution, we actually removed one marker in each substitution, and that's important to make the process terminate. However, the
\B aren't character but just positions, so nothing gets removed. We can however stop the
\B from matching by instead inserting a non-digit character into this place. That turns the non-word boundary into a word boundary, which is the equivalent of removing the marker character earlier. And that's what the 12-byte solution does:
Just for completeness, here are the individual steps of processing
1011, with an empty line after each step:
Again, you'll find that the last result contains exactly 11
As an exercise for the reader, can you see how this generalises quite easily to other bases (for a few additional bytes per increment in the base)?