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(''));
}
Interesting that in the initialization loop it sets A[0 - 1] to true, yet in your blocky code it appears to be iterating from 0 to n. In fact it always seems to be offsetting by one in array access ... 1 based indexing maybe?
Correct, you should see the looks on non-programmers' faces when you tell them that the first element in a Java list is #0, the second is #1, etc. It's approximately the same look as you see on programmers' faces when you tell them that the first element in a Blockly list is #1, the second is #2, etc.
Still, the blocky code reads "count with i from 0 to (get n)", but the loop generated is accessing A[0-1]..A[n-1]. JavaScript is forgiving here, but A[0..n] is not the same as A[-1..(n-1)] (at least I'm not familiar enough with JavaScript to think otherwise).
If they are mapping index 1 to index 0, then it makes sense that 0 would map to -1 since it is one less than the first index. The bug is in the blockly sieve.
I understand why they are offsetting the index, it just makes things somewhat unintuitive. In most programming languages A[-1] is the same as A[len(A)-1] (assuming zero based indexing) ... so in Blocky is A[0] expected to mean the same thing as A[len(A)-1]? Nothing here is a show stopper, just a detail that could use a bit of tightening up.
The name of this language immediately made me think of the blocky.io (http://blocky.io/) visual programming language, which was written in Common Lisp by David O'Toole before this language was developed. Blocky.io is very similar to this language, in more then just name, it even has its own MIT scratch like interface: http://blocky.io/blog/wp-content/uploads/2012/03/Screenshot-....
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!
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.
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.)
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.
Hey, you can create new maze puzzles for your fun from the JavaScript console (WebKit Inspector, Firebug,...)! First create a new function to paint the custom map by pasting this code into the console: https://gist.github.com/2848451
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 ;)
Ah scratch. Some years ago I wanted to show what cool stuff you can do with computers to a 10y old boy. Found scratch and actually got hooked myself for a bit ^^. Ended up with this (slightly embarassing thing): http://scratch.mit.edu/projects/DeepDuh/941811. After programming a bit, the limitations become apparent big time. Google's idea to implement this as a Javascript parser is probably a good idea, this way some kids may make the bridge to the actual program. Also, it's probably way way better performing.
If you like visual programming, have a look at subtext. IMO this is the best idea for a visual programmig style, I hope it gets traction http://www.subtextual.org/.
That website is glorious :). Yeah, I think this might go a bit far. Scratch's community sadly isn't so big, further fragmentation won't help that much I think. And the platform doesn't make a very solid impression to me. That's why I like google's idea, I hope they pour some money into this.
Yep it seems like it has grown quite a bit since I've looked at it last time. I still think a platform like this should be bigger - as in a substantial fraction of school children big. Every child should try playing with something like scratch, just to see whether (s)he might like it and go into programming. When I was a child I went straight from some learning program for children with some graphical macro editor (poor man's hypercard) to VB6 and it led me to what I am now. That's why I think it's really important what toys we give to our children.
Indeed. I wrote a similar framework in Actionscript / Flex a few years ago, actually with a lot of input from the Scratch team. I've been thinking about porting it to JS recently. Glad to see someone beat me to it :)
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.
Google also had App Inventor similar to that. I don't understand why they are building this. Didn't they just kill App Inventor because they wanted to "focus" or something? So why this now?
This seems to be done by an extraordinarily smart guy - Neil
Fraser. He's behind "google-diff-match-patch" [1] project,
which is AFAIK the machinery behind realtime collaboration
on google docs.
I've worked with Neil, and he is indeed extraordinary. I'd say he's who I want to be when I grow up except it's not clear he's grown up. See, for example, the centrifuge in his living room (http://neil.fraser.name/hardware/centrifuge/).
Not a big fan of what amounts to fairly typical coding via drag and drop, but this is a fantastic resource. I have a project in my queue that will need Google Doc collab functionality so this is very useful. Cheers.
I should note that the appearance of Blockly is very similar to App Inventor[1]. It seems that visual programming languages with imperative and sequential semantics converge to one direction: "blocky" combining core primitives and custom primitives. In this sense I think it's THE future of domain-specific languages.
I noticed something interesting and disturbing after reading some of the answers: people are more concerned with the length of the code rather than the optimal solution (no extra turns / backtracking). This reminds me of interviewing at MS about 12 years ago and all they cared about was the ability to write recursive code.
IMO, yes, elegant code is fantastic, but don't lose track of why we write code in the first place.
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.
So, I'm more disturbed that most of the answers people are posting aren't general solutions: they happen to solve this maze, but don't handle corner-cases (hah! I guess that's a pun ;P) of other mazes. You may as well just hardcode the answer to this one.
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
Keep in mind that I specified that this is an optimal solution for this particular map. General solutions are great, but if you have additional information for leverage, you use it. In fact, as stated in explanation of the solution, the solution solves maps which the following precedence preference: Right > Left > Straight. Just FYI, it's not a bug if you understand the limitations of a solution.
General 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.
Then, as I said, "you may as well just hardcode the answer to this one". It takes 15 blocks to hardcode an answer with the optimal solution and almost no time thinking. This solution not only takes 15 blocks to build but executes in exactly that much time.
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.
You're assuming the fallacy that it takes less time for an explicit solution. The solution took less than 2 minutes and most of that time was spent trying to figure out how to manipulate the puzzle pieces. Now if you're talking execution time, yes conditionals and loops add to the complexity of the execution, but for any non-trivial graph, the implementation time of a non-pattern recognizing solution would be much greater.
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.
The puzzle-piece representation of structure is neat, but at a 2-minute glance it seems not to scale to real complexity.
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.
while (true) do
if not (wall to the left) then
(turn left)
while (wall ahead) do
(turn right)
(move forward)
This uses the general maze-solving logic of following the outer wall in one direction until you find the exit. It never turns then turns back or runs into a wall.
After I placed turn left after move forward, what was my first instinct? Same as yours, I wanted to right-click move forward and place the copy after turn left.
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.
An "else" would help; you can add one by hitting the + symbol on the if. With the else, you can get the shortest program that'll solve the maze (transcribing using approximate notation in lieu of a screenshot):
while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
turn(RIGHT)
However, the addition of one more if makes the solution much faster and look more sensible, by not turning to the right and immediately back to the left:
while True:
if wall(AHEAD):
turn(LEFT)
else:
move(FORWARD)
if not wall(RIGHT):
turn(RIGHT)
Weird, that looks like you're manipulating blocks of text with the mouse. How is that a "visual programming language"? It just seems to be a fancy text editor.
If you started off facing a wall your code would just not do anything. You can both simplify it and fix this bug by reorganizing the loop.
while true:
turn left
while wall(AHEAD):
turn right
move forward
However, while this algorithm happens to work on this maze, it will not work against other mazes (if you care).
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.
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
This past weekend at the Vancouver Polyglot Conference there was a session with the author of Waterbear (http://waterbearlang.com/) that got a fairly good turnout. It looks remarkably similar.
There isn't. I had to enclose the algorithm in a while (true) loop and if you reach the goal the program stops automatically. Here is a screenshot: http://imgur.com/0mape
This could become pretty interesting, especially if there is a platform aspect. Meaning I could easily extend this with my own elements and commands.
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.
I like it a lot, and look forward to trying it out on my girlfriend to see how a non-coder responds to it.
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.
I've always thought it would be cool to have a backend environment similar to labVIEW (but faster!). I use labview in my research and it is the best solution I've found for encouraging / allowing for code re-use. This Google Blockly, to some extent, seems to be heading that way - I'm looking forward to seeing how it develops.
Possibly, but as far as I can see, all it adds to the mix (that textual teaching languages, e.g. LOGO, don't have) is the certain impossibility of certain syntax errors by only allowing certain parts to click together[1]. The semantic model behind the system is otherwise identical to BASIC or some other ALGOL-ish programming language, with loops and subroutines and mutable variables and so forth. It is quite probable that this might make some tasks easier, especially to a wholly inexperienced programmer, but what I assert are the real challenges of learning to program—algorithmic thinking, code organization, reasoning about program state, &c—remain just as difficult.
[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.
Looks good, but I just crashed my chrome after putting a "repeat while>and" block in between one of the move functions. Might want to watch out for new users accidentally crashing their browsers while trying to do something innocent.
I remembered a trick about mazes: if you keep your hand on the right wall, you'll eventually reach the end of the maze (assuming that the beginning and end share a contiguous wall)
Love this idea for teaching kids. Reminds me of the visual programming in Click N Create / Multimedia Fusion / Games factory which was/is very advanced and powerful.
Given sufficient resource and polish something like this could be awesome.
interesting attempt; things on my mind; what if I colorize my python code based on block depth or what if we do a 3D version of this; and what if we do a game of "angry blocks" to program.
I want something to code on my smartphone, without having to type more than is necessary. I expected this kind of thing to arrive. I hope they become more than a little toy.
Interestingly, that causes an "Aw, snap!" in Chrome (beta channel) for me. (Fresh load of the maze demo; right-click on the only block on the screen, click "add comment".)
It was pretty fun.
JS generated isn't so bad..