Dude, thanks for that! I really enjoyed the closed form solution, though there is absolutely no way I could have come up with that under time-pressure in a codesprint.
My solution was rather trivial:
The base case is 2 bit numbers, which are 00,01,10 and 11. The total number of one-bits is 0+1+1+2 = 4.
From then on, I just used recursion.
3 bit numbers are really 2 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 8 3 bit numbers, so you are tacking on the '1' 8/2 = 4 times. So 4 + twicetwobits = 4+2 x 4 = 12.
4 bit numbers are really 3 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 16 4 bit numbers, so you are tacking on the '1' 16/2 = 8 times. So 8 + twicethreebits = 8+2 x 12 = 32
If you write out the recurrence relation, it looks like:
f(n) = 2^(n-1) + 2 x f(n-1)
This seems silly since you can neither define f(n) nor recursively call f(n-1) in Blockly just yet. But if you memoize the f(n-1) results in a list, the recurrence is computable by straight iteration - which is exactly my Blockly solution.
My solution was rather trivial: The base case is 2 bit numbers, which are 00,01,10 and 11. The total number of one-bits is 0+1+1+2 = 4.
From then on, I just used recursion.
3 bit numbers are really 2 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 8 3 bit numbers, so you are tacking on the '1' 8/2 = 4 times. So 4 + twicetwobits = 4+2 x 4 = 12.
4 bit numbers are really 3 bit numbers with a '0' prefixed half the time, '1' prefixed the other half of the time. There are 16 4 bit numbers, so you are tacking on the '1' 16/2 = 8 times. So 8 + twicethreebits = 8+2 x 12 = 32
If you write out the recurrence relation, it looks like:
f(n) = 2^(n-1) + 2 x f(n-1)
This seems silly since you can neither define f(n) nor recursively call f(n-1) in Blockly just yet. But if you memoize the f(n-1) results in a list, the recurrence is computable by straight iteration - which is exactly my Blockly solution.