Blog Archives

Link ThreeSix – A Logic Game, Written in JavaScript

I have been working on a game called Link ThreeSix for a few weeks now. This is a personal project I built in my free time during lunch and after class at Hack Reactor ends for the day. It’s a challenging, strategy game to play against another person, and I have yet to figure out the optimal way to play it. There are distinct strategies for playing offensive or defensive, and I have mixed results with both.

This project originally started in the classroom at Hack Reactor, when our instructors gave us two days for a “make-up sprint”. These two days were set aside to let us catch up on any topics we felt like we needed more time with. I decided to jump into Backbone.js again to see if building some simple apps would help me learn this JavaScript library a little better. I originally set out to make a simple tic-tac-toe game, and I had a working prototype built in the first 6 hours. I had learned more about Backbone, but now I wanted to take the project further.

Once I had the tic-tac-toe scaffolding built, I began to think of ways to expand this project into a game that I would actually want to play. I started by increasing the board size to 6 x 6 squares. With a board this size, the typical tic-tac-toe rules do not work well, as it is trivial to block your opponent from scoring.

We had recently finished the N-Queens algorithm sprint, and I was interested in exploring this problem further. It made sense to apply similar scoring to my 6×6 board, and so Link ThreeSix was born.

Link ThreeSix

In this game, each player takes turns placing their mark on a single board square, until the board is filled. Your objective is to make links of 3 in a row, or more. Links can be made horizontally, vertically, or diagonally. The game is scored in real time, after every move, and the Game Score board highlights the current game leader.

Scoring is as follows:
3 in a row: 1 point
4 in a row: 3 points
5 in a row: 10 points
6 in a row: 20 points

After each game, the Total Wins board updates to reflect the winner of the current game, and keeps track of the entire match. The first player to win 3 single games, wins the match!

Once I had built out my application architecture using Backbone’s MVP, the biggest challenge of this project was to correctly score each player’s points, as they create connections of 3 or more in any direction. I began by creating two-dimensional arrays for each player, with numerical values representing the position of their marks on the board. These two-dimensional arrays make it easier to keep track of diagonal scores, which are the hardest to solve with an algorithm.

I used Backbone’s built in event listeners to detect when a player makes a move, and then I ran the scoring algorithm for that particular player. This scoring function checks every corresponding row, column, and diagonal for that player, after every move. The hard part was first checking for connections of six, then five, then four, then three in each possible scenario, for each direction, and then breaking out of that function for that particular line and direction once a match was found. However, all of the other lines and directions still have to be checked at that point, because many moves score points in multiple directions.

This scoring function proved to be much more complicated that I originally thought it would be, which is what kept me hacking away at this project in my free time. I would spend a few hours one day making significant progress, then get stuck on an issue. I would usually think of the solution at a random time a day or two later, and I would come back to the code to make more progress.

This game currently only supports 2 player mode, with both players on the same computer. I want to eventually incorporate the Facebook OAuth login with a Node server, to allow players to compete on separate computers from different locations.

I also plan on developing a computer opponent AI to enable single player mode. This will definitely be the next branch of this project, and I plan on learning all about game AI in the process. It would be great to develop the optimal strategy for this game, explore the computer decision tree, and to set up multiple difficulty levels. However, with all of the other projects I am working on, along with my upcoming job search, this will probably have to wait a while.

Let me know what you think about Link ThreeSix! It is open source on GitHub, so feel free to post any issues you find, or fork it on your local machine. I would also be interested in talking with anyone that has experience with programming game logic, or anyone that wants to help with coming up with an optimal strategy to play this game.

Read more

N-Queens, Algorithms, REST, and Ajax – Hack Reactor Week 2

inside Hack Reactor

Inside Hack Reactor


Week 2 at Hack Reactor has come to a close, but the frantic pace of learning continues. We kicked off week 2 by finishing up our Sub-Class and OOP sprint that involved making individual nodes “dance” on the page with any random behaviors we decided to give them. What we ended up with were fancy screen savers with objects that could interact with each other (and explode!). This led us to a discussion of particle systems, which sounds like something I want to devote some time to once this course is over.

We had another guest lecture at the beginning of the week regarding algorithms, complexity analysis, and ways to approach solving interview problems. Solving complex problems like this while under pressure is a skill I need to work on, but luckily there are a few great online resources to help build your skills. Some of my favorites that I’ve used so far are:
Project Euler
TopCoder Algorithm Tutorials

Our discussion of algorithms led us into our next project, and my favorite project of the week, called N-Queens. This goal of this project is to find how many ways n queen chess pieces can fit on an nxn chessboard without being able to attack each other. So, if you have a 4×4 chessboard, how many different ways can you fit 4 queen chess pieces on the board so that all 4 queens are safe from being attacked by the other queens? The answer for the 4×4 board is 2 different arrangements of queens. For a more in-depth explanation, check out the wikipedia entryfor the 8 queens solution.

Currently, the largest board that all solutions have been found for is a 26×26 board. At this time, 27×27 is too large of a solution to be handled by today’s computer processors with the current algorithms. However, some students in the senior Hack Reactor class are tackling this problem with an app called supercomputer.js that leverages many networked computers, each solving a small portion of the entire algorithm (similar to the Playstation 3 Folding@Home project out of Stanford).

We spent much of the first day building a JavaScript algorithm for finding single solutions to this problem, and testing it on small chess boards (less than 8×8). We ran through a series of tests written in Jasmine to ultimately come to an algorithm that would successfully find every solution for a given n. However, our first attempt was a brute-force solutions that used 2-dimensional arrays to build every possible configuration of n queens on the board. We then tested every one of these board layouts to determine if it was a valid arrangement where the queens couldn’t attack one another. The boards that passed our test were put into a results array, and then counted. This solutions was very inefficient and took a tremendous amount of computer processing power to complete. This first attempt could not find a solution to any n over 7, because the browser would time out before the JavaScript was done running.

Now that our algorithm was finding all of the correct solutions, it was time to optimize it so that we could find solutions to chess boards above 8×8. Our first optimization involved making our tests for evaluating correct boards more efficient. With these improvements, we were able to find all 92 solutions to n=8 in just over 20 seconds on a Mac mini. From there, we decided to trim down the number of chess boards our algorithm generated.

Instead of creating a large tree data structure of all possible solutions, we started checking early on in the board building process if the piece we just placed was in conflict. So, once we placed a queen on the first row, we knew no other queens could be placed on that row, thus moving on to second row right away. We also knew that the first queen placed on the second row cannot be placed in the same column as the piece on the first row, thus “pruning” our data tree of all possible iterations below that conflicting node. We also checked for diagonal conflicts before placing each piece. The result of this “pruning” was allowing our algorithm to find all solutions on an 8×8 board in about 2.5 seconds!

We were pretty excited about our 10x improvement in speed, but we decided to see if we could make it even faster. Up until this point we represented our solutions using 2-dimensional arrays, which take a lot of iterations to traverse all of the elements. We decided to represent our boards using a simple 1-dimensional array instead. For example, a 3×3 array normally looks like [[1,0,0],[0,1,0],[0,0,1], with the 1 representing a queen (not an actual solution obviously). Instead, we can represent this same array with [0,1,2] , with each index of the array representing a row, and the value of that index representing where in that row the queen is located. Once we implemented this new storage mechanism, our time for finding the n=8 solution was reduced to 49 milliseconds! It was very satisfying to see such huge speed gains from each improvement we made in our code. Here is our final JavaScript solution:

window.countNQueensSolutions = function(n){
  var startTime = new Date();
  if (n===0){return 1;} //0 queens fit on a 0x0 board 1 time
  var solutionCount = 0;
  var rNQueens = function(tempBoard){
    if(tempBoard.length === n){
      checkQueenSolution(tempBoard) && solutionCount++;
    for(var i = 0; i < n; i++){
      var boardCheck = tempBoard.concat(i);
      if (checkQueenSolution(boardCheck)){
      } else {
  var endTime = new Date();
  console.log('Number of solutions for ' + n + ' queens:', solutionCount, 'in', endTime - startTime, 'milliseconds');
  return solutionCount;

window.checkRookSolution = function(matrix) {
  return _.uniq(matrix).length !== matrix.length ? false : true;

window.checkQueenSolution = function(matrix) {
    return false;
  for(var i = 0; i < matrix.length; i++){
    for(var j = i+1; j < matrix.length; j++){
      if(i - j === matrix[i] - matrix[j] || i - j === -matrix[i] + matrix[j]){
        return false;
  return true;

The remainder of week 2 was spent learning about HTTP requests, REST, and how to use Ajax with the service from Parse. We lumped this all together to create a real-time chat room client that all of the Hack Reactor students could use. Once everyone was up and running with the chat client, we implemented features like preventing script attack hacks, creating friends lists, and allowing the user to create and join new chat rooms.

This week was intense, but the instructors are warning us about the start of week 3, which involves us diving into Backbone.js. I’m running through some Codeschool tutorials on Backbone right now to get prepared for next week!

Read more

Hack Reactor Week 1 in Review

Week number one at Hack Reactor is over, I had my first day off since moving to SF, and we’re back at it for week 2. The pace this first week was crazy, and I can’t believe how much material we covered in such a short amount of time. I found myself getting home most nights about 11pm this week, simply because there was so much material to digest and work out in my code.

I also finally got my bike shipped out to me, which has been so much better than taking public transportation everywhere. My ride to school in the morning is about 5 miles, and I have been able to find a route that has as few hills as possible because it’s a single speed bike. Getting some exercise in the morning really gets me brain working correctly for the day, and I’ve been much more alert since starting that routine.


After re-building our pre-course assignments, we dove head first into quite a few basic computer science lessons and how to implement them in JavaScript. We also had a guest talk from a former senior team lead  at Facebook, and I attended my first JavaScript meetup. Here is a run-down of the major topics we covered in just the first 6 days:

  • Git workflow and command line
  • JavaScript basics like functions, methods, callbacks, closures, objects and scope
  • Recursion and as an example we re-built the getElementByClassName native JS function
  • The debugger command and the process of finding errors with Chrome dev tools and the console
  • JavaScript prototype chains
  • jQuery basics – used to make a simple Twitter clone
  • JavaScript classes and shared methods with functional, functional shared, prototypal, and pseudoclassical instantiation
  • Test Driven Development with Jasmine and Mocha
  • Object Oriented Programming: isolation, modularity, loose coupling, makers, mixins, subclassing, etc.
  • JavaScript event systems
  • Data Structures: hash tables, linked lists, trees, binary trees, sets, and big O notation

Wow, that is a ton of material now that I have it all together in one place. We implemented all of these bullet points in different sprints and projects this first week. I just hope I can retain it all in the weeks to come.

We also got to see the personal project presentations of all the students in the senior class, which is 6 weeks ahead of us in the Hack Reactor course work. Some of the web apps that were presented were very impressive, and I can’t wait to start applying some of my new knowledge to a project of my own. There seemed to be a few students that tried to tackle a project that was too ambitious for the time they had to work on it, and as a result we had to sit through presentations of projects with limited or incomplete functionality. I talked with a few of the senior students and they stressed the importance of limiting the scope of your project to start, then adding more features as time permits. Seems like a good engineering code to live by, in general.

Some resources I came across this week:
Coderbyte – small JavaScript problems with timers and scoring to practice your skills. A lot of fun and a good boost when you some a problem quickly.
HTML5 Conference Slide Decks – One of the presenters at the meetup this week, Dan Lynch, has his deck here, but it looks like tons of interesting content. I want to check it out when I have more time.
Fancy.js – A mashup of underscore.js and functional.js. Love the poker-themed demo.

Read more

JavaScript Basics and the Keyword “this”

I just finished day 3 of Hack Reactor and thought I would go over some of the topics I’ve learned so far. I will not have much free time from here on out, but I want to get down all of the important ideas I learn every few days.

Our main instructor, Marcus, has spent much of the last two days going over the basic building block of JavaScript in great detail. I’ve been using some of these JS structures for about a month now, but it’s been great to learn more about each one, and how they relate to other elements. We spent quite a bit of time on objects and methods, along with data types.

Null vs. Undefined
The two value types that cause the most confusion where undefined and null. What I took away is:

null: The language has checked, and this does not exist.
undefined: The language does not know anything about the object you are asking about.

Here is a deeper explanation of null vs undefined on StackOverflow:

Ternary Operators
Another topic I learned a lot about that I had never seen before is JavaScript ternary operators. It is another way to succinctly express an if/else statement in just one line. The basic ternary operator framework:

test ? option1 : option2

Test is any boolean expression that will be true or false. Option1 is an expression that will be returned if the test is true, while option2 will be returned if the test is false.

The JS this keyword is often misunderstood, but is very useful when constructing objects and methods. Basically, the keyword “this” is bound dynamically to the object found to the left of the “.” at call time. There a a couple exceptions to this, but if you look to the left of the “.”, you can easily see what this will refer to. A quick example:

person = {
  location: ‘SF’,
  locate: function(){
person.locate(); //alerts “SF

In this example, it is plain to see how “this” inside of the method relates to the person object when the method was called on line 7.

The first major exception to watch out for with “this” is instances where there is no “.” before the function or method call. In this case, “this” refers to the global object, which is the window. The next exception is when it is called with the “new” keyword, in which case “this” will be undefined (ex. new person.located //alerts undefined). The third exception is when it is used in conjunction with .apply or .call, both which are specifically designed to bind a function to whatever argument they are passed.

We also spent the last couple days going over our pre-course projects and the refactored solutions to see the best methods for completing each assignment. It was very eye-opening to see an experienced programmer solve these problems in real time in just a few minutes, instead of the many, many hours it took me to complete each one. I now have something to strive for!

Read more