News for hackers. Stuff that matters.
Re:Google Blockly - a visual programming language by dxbydt on Thursday May 31, 2012 @10:47PM (#4051680)
i solved a problem featured on the yc company interviewstreet.com codesprint.

the problem: Count the number of one-bits from 0 to 2^n - 1, for n from 1 to 20.

my solution: http://i.imgur.com/hUxt0.png

when you run the solution:

     Number of one-bits in 1 bit numbers from 0 to 1 = 1
     Number of one-bits in 2 bit numbers from 0 to 3 = 4
     Number of one-bits in 3 bit numbers from 0 to 7 = 12
     Number of one-bits in 4 bit numbers from 0 to 15 = 32
     Number of one-bits in 5 bit numbers from 0 to 31 = 80
     Number of one-bits in 6 bit numbers from 0 to 63 = 192
     Number of one-bits in 7 bit numbers from 0 to 127 = 448
     ....
JS:

    var list;
    var x;
    var prev;
    var onebits;
    var doubleatprev;

    list = [];
    list[0] = 1;
    list[1] = 4;
    for (x = 2; x <= 20; x++) {
    prev = x;
    onebits = Math.pow(2, prev);
    doubleatprev = list[x - 1] * 2;
    list[1 + x - 1] = onebits + doubleatprev;
    }
    for (x = 1; x <= 20; x++) {
      window.alert(['Number of one-bits in ',x,' bit numbers    from 0 to ',Math.pow(2, x) - 1,' = ',list[x - 1]].join(''));
    }
Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!
Re:Google Blockly - a visual programming language by nitrogen on Friday June 01, 2012 @12:48AM (#4052031)
Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!

Does Blockly support turning JavaScript into blocks? That could be useful for visualizing minified or unfamiliar source code.

Re:Google Blockly - a visual programming language by nonsequitur on Friday June 01, 2012 @03:46AM (#4052414)
Take some of that time to figure out the math and the code becomes trivial:

  for (n = 1; n <= 20; n++) {
    window.alert(n << (n-1))
  }
A short explanation: http://mathbin.net/98435
Re:Google Blockly - a visual programming language by gjm11 on Friday June 01, 2012 @05:53AM (#4052682)
A shorter explanation with no binomial coefficients in it: Write down those 2^n numbers once in order, and once in reverse order, and pair them off. Note that each x gets paired with 2^(n-1) XOR x. So each number and its partner have exactly n 1-bits between them. In other words, twice the number we're looking for is 2^n.n; so the number we're looking for is 2^(n-1).n.

(More informally: Each bit is 0 half the time and 1 half the time, because you can pair off x and 2^(n-1) XOR x. Therefore the total number of 1-bits is half the total number of bits, QED.)

Re:Google Blockly - a visual programming language by dxbydt on Friday June 01, 2012 @10:27AM (#4053516)
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.