Byte count assumes ISO 8859-1 encoding.
+%`\B
¶$`:
1
Try it online!
Alternative solution:
+1`\B
:$`:
1
Explanation
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:
^
,
+`,(.)
$`$1,
1
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 1
s at the end, we don't even need to distinguish between 0
s and 1
s 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:
,(.)
$`$1,
Just looking at ,(.)
and $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):
,1011
1,011
_
110,11
___
1101101,1
_______
110110111011011,
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 1
s 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 $`
):
_ __ ___
1101011011
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:
\B
,
+%`,
¶$`
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 1
s 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:
+%`\B
¶$`:
Just for completeness, here are the individual steps of processing 1011
, with an empty line after each step:
1
1:0
10:1
101:1
1
1:0
1
1:0:1
1
1:0
10:1:1
1
1:0
1
1:0:1
1
1:0
1
1:0:1:1
Again, you'll find that the last result contains exactly 11 1
s.
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)?
Related – mbomb007 – 2016-12-05T19:43:30.143
Does the output have to be unsigned or can it be signed? Also, if my language happens to automatically switch between 32-bit and 64-bit integers depending on the length of the value, can the output be signed in both ranges? Eg- There's two binary values that will convert to decimal
-1
(32 1's
and64 1's
) – milk – 2016-12-05T20:47:33.717Also, can the output be floating, do does it need to be an integer? – Carcigenicate – 2016-12-05T21:17:53.117
@Carcigenicate It must be an integer, but it can be of any data type. As long as
round(x)==x
you're fine :)2.000
is accepted output for10
. – Stewie Griffin – 2016-12-05T21:31:46.760Oh sweet. Thanks. – Carcigenicate – 2016-12-05T21:33:57.583
@milk, you may output
+42
instead of42
if you want to. If the language support 64-bit integers without any special type casting or importing then it should behave the same for all numbers from 1 to2^64-1
. – Stewie Griffin – 2016-12-05T21:35:25.393Can I take two parameters (the number of bits, followed by the list of bits)? Otherwise, running a COW program will run for several minutes for anything larger than 1000000 and several hours for anything with only a couple more bits – Gabriel Benamy – 2016-12-06T21:09:49.670
The last number is the date the challenge was posted? The hours and seconds don't correspond with SE's UTC+0 time, it should be
20161205193745*****
:) – RudolfJelin – 2016-12-07T19:52:42.370I knew that comment would come sooner or later... Who cares about UTC+0? :) – Stewie Griffin – 2016-12-08T16:05:11.647