Backbone Overview

What is Backbone.js? According to their site: “Backbone.js gives structure to web applications by providing models with key-value binding and custom events, collections with a rich API of enumerable functions, views with declarative event handling, and connects it all to your existing API over a RESTful JSON interface.”

To me, it’s few really well laid out objects that you can extend (make copies of) to fit your needs. There are 3 types.

Models: These are at the heart of the whole thing. Each model represents a singular entry or event, such as a song, a user, or a message.

Views: These are used to represent your models to the user of your app. Which is why they usualy contain a render() function. They are also in charge of collecting input from the user.

Collections: As the name implies, they are a collection of things. What things? Models or views.

Lets go over a fairly simple example of rendering an displaying the contents of an album. For spacial reasons, this album will only have 2 songs on it. Don’t worry, they are quality songs.

backbone_1

A few things to note:
Views either have a collection, or a model, that they reference.
Collections have a model that they reference.
So all views, at some point, will reference a model, either directly, or through a collection

Our album data would look something like [{title: “rockin intro”, length: “0:20″, url:”mysite.com/rockinintro”},{title: “outro”, length: “1:11″,url:”mysite.com/rockinoutro”}]

We passed our album data into the app (which is a model), as we instantiated (loaded) the app. The app then went and made the app view (which is a view). After that we created a new album collection from our album data with something like this: this.set(‘currentAlbum’, new Album(albumJSON)); which got called inside the initialize function.

We would have already told our album collection, that it is a set of songs. So the collection knows that when it gets created and passed a set of data, that the data should represent songs.

The collection then automatically goes and makes a model for each song.

–Will be updated with more, later.

Advertisements

nQueens 2

nQueens – Part 2 – Implementation

Last time we discussed the problem of nQueens and the general logic used to create our algorithm. We are now going to take that solution and implement it in code.

Before we were talking, human to human. We do this a lot, so it’s much easier to get ideas across. Now we will be talking human to computer, which is a bit more difficult, they lack the ability to deal with ambiguity. Which means we need to be more precise, and explicit; both in speech and thought.

Lets take a look at our current logic, though for the sack of less drawing, we are moving from a board of 5×5, to a board of 4×4.  Lets review our logic so far.

  • Pick an available number from the column array, and pick one from the row array.
  • Check the major and minor arrays. C + R = Major index , C – R + 3 = Minor index.  (C for column number, R for row number. We are adding 3, to make the minor index 0 based.)
  • If you get a (o) when you check the major and minor arrays, you are good to go. Place a queen at that chosen spot. Then remove the chosen numbers from their respective column and row arrays. Then mark major and minor arrays as taken (x) at the spots you checked. Section 1 has a more detailed walk-through of this.

Let’s see how this looks on a 4×4 board.
chess_2_1

Step 1: Our empty board, all choices are available.
Step 2: We chose 0,0 as it was the first available spot, no conflicts. We took 0 out of both the Row and Column arrays. We also marked the spots taken in the Major and Minor arrays.
Step 3: You’ll see that the first thing we tried, was to place a queen at [1,1]. This was because the numbers were available to us, so we tried it. We then did a lookup in the Major and Minor array, and found there was a conflict with the Minor array, so we moved onto the [1,2] where we placed our second queen.

You’ll note that we no longer have a valid board. There is only 1 available slot and we need to place 2 more queens to have a valid solution. What do we do now?

As a person I’m sure you would say,”Ummm, I guess we try some different spots?” You, person, are totally right. We try some different spots. But how would we tell a computer this? Also since computers are fast at this kind of problem, how do we tell it to try EVERY possible spot, then tell us which ones work.

Lets try some plain language logic for this. We have a good starting point, Step 1, an empty board. With a bit of trial and error, it turns out that for a 4×4 board, there is no solution that involves starting a piece at [0,0]. That means we should step back to the empty board, and try the next possible spot, [0,1] and go through again. chess_2_2

Above, you can see our logic laid out in a branching fashion. For this first iteration I’ve laid each choice to match it’s row:column value. Diagrams laid out like, because of the branching, are often called trees. Get it? Branches, trees. Yeah, you get it. If  we were to fill the above diagram out fully, the [0,0] circle would have one more child node, [1,3].  [1,3] would have no valid children.

chess_2_3

 

 

 

 

 

 

I’ve changed the positioning a bit, to reflect a more typical tree data structure. The [1,3] choice is also shown. Clearly [0,0] is a dud, we must move onto [0,1]. chess_2_4

 

 

 

 

After choosing [0,1], our first 2 child options end up having diagonal conflicts. The third one, however, was just right. Each successive choice in our algorithm also proves to be valid, and we now have one functioning board that satisfies the nQueens requirements. Awesome!

chess_2_5

A successful board

 

 

 

 

 

 

 

Any time you see data branching, as we did in the above node diagram, that problem is a good candidate for recursion. If are comfortable with recursion, then hopefully this post was useful to you by visualizing the flow of data. If you do not know what recursion is, you should google around for resources on it. But before you do, be confident knowing that what we walked through in this post and the previous one, was recursive. If you understood what we’ve said, you can grasp recursion just fine.

That’s all well and good, but what about some code?

Here is my decently commented solution. I solve it using ‘recursion with side-effects.’ Which just means that there are a few variables that each recursive call can all see, and they can all modify.