Google Blockly - a visual programming language
code.google.com
code.google.com
It was pretty fun.
JS generated isn't so bad..
var n;
var A;
var i;
var x;
var j;
n = 100;
A = [];
for (i = 0; i <= n; i++) {
A[i - 1] = true;
}
var i_end = Math.sqrt(n);
for (i = 2; i <= i_end; i++) {
if (A[i - 1] == true) {
j = Math.pow(i, 2);
while (j <= n) {
A[j - 1] = false;
j = (j || 0) + i;
}
}
}
for (x = 2; x <= n; x++) {
window.alert([x,': ',A[x - 1]].join(''));
}As an aside, Lua also uses 1-based indexing.
Unsurprisingly, it still works (it just loops a few too many times).
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
.... 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(''));
}
Does Blockly support turning JavaScript into blocks? That could be useful for visualizing minified or unfamiliar source code.
for (n = 1; n <= 20; n++) {
window.alert(n << (n-1))
}
(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.)
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.
Next setup Maze.MAP matrix with value 1 for empty cell, 0 for path and 2/3 for start/finish positions.
Now run loadMazeMap() to load your new challenge ;)
Edit: Here's my old Actionscript library in case anyone is interested. https://github.com/trun/flashblocks
It was presented at JSConf last year: http://blip.tv/jsconf/jsconf2011-dethe-elza-5942746
Waterbear isn't a language like Scratch, it's a toolkit to create a Scratch-like visual programming interface to any language you like. There is active development on wrappers for Javascript, Java robotics, and Arduino.
I am so freaking proud.
This might change your idea: http://day.scratch.mit.edu/
It's not finished yet, but it sure beats MIT's attempt to port Scratch from Squeak Smalltalk to Adobe Flash...
Definitely worth watching.
"Google blocky" > 50% brand.
IMO, yes, elegant code is fantastic, but don't lose track of why we write code in the first place.
Edit: consolidating from post below.
Here's a minimal solution with optimal logic (for this map) without hard coding. It also ensures that there is a forward step in every iteration of the while loop.
Basically it's just an order of precedence:
Turn right > turn left > go straight
I actually found a similar bug in yours: you will get trapped in a square and be unable to exit, as you will constantly keep hugging the column along the left, without ever deciding to finally exit off to the right. S=Start, G=Goal, O=Empty
S-O-O
| |
O-O-GGeneral solutions for mazes (graphs really) generally follow a depth, breadth or hybrid approach. I'm actually surprised that all of the general solutions have been depth and none breadth. It's a bit more convoluted in this case as you'd have to traverse backwards, but conceptually, it's no more different than using a FIFO or LIFO.
In any case, with the tools given for this particular "challenge," a general graph search is impossible as you can't record previous states. It's simple to construct a map which causes an infinite loop.
A good analogy of my approach would be using a knowledge based finite state machine over a genetic algorithm or neural net. Is it less elegant? Sure is. However, it's also clearly defining a particular problem / solution pair with certain limitations and expectations.
Alternatively, you can spend a bunch of time proving to yourself that you have a solution that takes advantage of properties of this specific maze that gets you down to 10 blocks. However, as the result now has multiple levels of nesting and is littered with comparisons and jumps, it is going to take more time to execute and get to the end of the maze. I'd even go so far as to claim it is no longer an "optimal solution".
As you said yourself: "yes, elegant code is fantastic, but don't lose track of why we write code in the first place". I can understand spending the time to build something complex if you at least solve the general problem, but to spend more time in development to end up with a slower-to-execute answer that looks like a general solution but isn't seems to fall into your own trap ;P.
In any case, the points I'm trying to make are simple:
1) Solid program execution is much more important than line reduction.
2) Defining a problem space / limitations allows for better code / reuse.
3) When the implementation trade off is sufficiently small, it's better to increase the scope of the solution for possible reuse.
One of the big ideas in programming is abstraction/modularity/reuse, and I don't see how that fits in here.
(I found the "procedure" block, but I don't see anything that fits inside it other than "break out of loop", which doesn't make any sense. And I don't see how to call the procedure.)
So I find myself looking at the samples everyone's demonstrating here and finding they're harder to read than real well-organized code.
/**
* Execute the user's code. Heaven help us...
*/ while (true) do
if not (wall to the left) then
(turn left)
while (wall ahead) do
(turn right)
(move forward)
while (true) do if(wall ahead) then turn left else move forward turn left if(wall ahead) turn right
O-O-O
| |
O S-O-G
| |
O-O-O while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
turn(RIGHT)
while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
if not wall(RIGHT):
turn(RIGHT)Edit: I didn't know that an else was possible, so I had to do it this way.
while !wall(AHEAD):
move forward
turn left
while wall(AHEAD):
turn right while true:
turn left
while wall(AHEAD):
turn right
move forward
Imagine a 5x5 square race track, with spokes coming from the outside of the wheel to the center, where there was a flag. Your algorithm (and my modified one) would just spin clockwise around the track without ever realizing it should take a right towards the center.
Here's one with same amount of code and optimal logic (for this map) without hard coding. It also ensures that there is a forward step in every iteration of the while loop.
Basically it's just an order of preference:
Turn right > turn left > go straight
Back in the day I was looking at Sprog for some client-facing project so probably worth looking back at it again. Here's a nice example of Data Munging with Sprog - http://www.perl.com/pub/2005/06/23/sprog.html
As evidenced by this thread a 'Share' button would be great.
I'd love to be able to duplicate blocks by shift-click-n-drag.
http://en.wikipedia.org/wiki/App_Inventor_for_Android#Histor...
I can see some use for example in one application where we are importing data from other systems. Something like this could be used to create a quite nice user interface for creating simple programs that would manipulate and filter the incoming data.
Whilst working out the while loop however, I put the code to loop outside the block instead of inside, thereby making an infinite loop. Now the Chrome browser window is completely unresponsive, and won't even close, so it seems I have to kill chrome to get rid of it.
Other than that, cool!
[1]: It also only allows variables to be specified from an extendable set, preventing certain problems with unbound or misspelled variables. I can see the possibility of also preventing type errors by constraining shapes further, e.g. all integers could be circular while booleans are hexagonal, so and would have two hexagonal spaces while + would have two circles. If I'm not mistaken, Scratch does something like this, although I do not know how far it is taken there. It would be interesting to see how far this can be developed to constrain the space of possible incorrect programs.
My suggestion based on no evidence what-so-ever is that I'd like to see something like this in a richer environment.
To give a bad example, VB. The original VB had forms (maybe it still does). You'd make a form. Double click the button and add code for "onclick" basically. I guess maybe that was inspired by Hypercard.
In any case it was really easy to see how to make a useful program because of the structure a form plus code snippets gave. If those code snippets were Blockly that might be better for learning.
A maybe better example is Unity3D. You add a 3d object, attach a Script and start editing code to move that object by supplying an Update() function or something along those lines. Maybe a Step() where you can define state change code snippets?
All I'm saying is a language like Blockly that removes the syntax errors, attached to a larger framework (games, graphics, or webapps), seems like it would make it far more approachable. You could actually make something useful or fun in a less steps.
http://u3d.as/content/neo-pax/antares-universe-vizio-free/29...
Fun puzzle!
Given sufficient resource and polish something like this could be awesome.
I'd love to do Trémaux's algorithm if they'd add the full list of block types to the maze.
if not wall right then turn right
instead.