A Knight’s Tale

I have bad habit of getting a little cocky. The first two challenges, while not necessarily simple, didn’t take long to conceptualize and code. Fresh off my second coding challenge, I was feeling pretty invincible. I was able to take on code that the best minds at Google deemed fitting challenges, and I polished them off with time to spare! What could go wrong? I typed request into the console. So that’s what could go wrong, a significant ramp up in challenge….


The Problem Set Up

Imagine a chessboard. It is an 8 by 8 board that alternates black and white. Now imagine that starting at the top left corner we number from 0 to 63. Here’s a picture to get a better idea:

Picture1

The program passes in two numbers: a start position and an end position. Find the least number of moves it would take to get from the start to the end if you move as a knight, the knight moving in the following L-shapes:

knightsmove


The Solution Design

The absolute most important thing is getting from the start place to the end place as quickly as possible. There are many ways to travel between two spaces, but it might not give the fastest path.

One thing that helps with designing the program is to picture the set of moves as a growing tree. Your start point is the root node of the tree. From the root, it may be possible to have 8 branches off a given node as long as we haven’t already been to that branch before (we don’t want to loop), and the branch doesn’t leave the board. If we were at position 0, there would only be 2 legal moves because all other moves take you off the board.

So, we have tree that we are traversing, we know we can only visit a node once, and that the move has to be within the board. As for tree traversal, there are few options that could be used, the most famous being a Depth First Search (DFS) or a Breadth First Search (BFS).

DFS means you check all the way down a given branch before jumping up and checking the next branch. In this problem, it might not be the right option, because I may not get the first instance of my target showing up. For example, I can go from 0 to 10 immediately, or I can travel 0 to 17 to 27 to 10. As the problem asks us to find the fewest moves, DFS isn’t the best option. BFS searches all of the nodes at a given depth. It will check the root first, then 8 right under the root, then the 64 (8 branches for the 8 branches) underneath the children, and so on until it finds the end point. This method finds the first instance of a node, so it was the method I used.


Lessons Learned

The most obvious was the different ways to traverse a tree and the data structures needed to make it work. The BFS uses a queue (a first in, first out structure) to hold nodes that I needed to visit. I also had to learn how to create a custom “Node” class that held the x-position, y-position, depth, and a method to check if it was equal to the end point.

Compartmentalizing code is also important. There are a few functions that got repeated A LOT like the “Is this position legal on the board?” checker, a method to calculate the x and y coordinates given a number on the board, and method that utilized the node class instead of doing everything from position integers. Planning the code first in psuedocode first helped guide function development and made getting a working program done easier.

I also got to use HashMaps again which was exciting! HashMaps are incredibly important in computer science for a variety of reasons, so an excuse to use these again was not amiss.


The code was submitted with a day to spare! Two levels down, three to go! I’m filled with optimism, but I’m also cautious. These problems are challenging! They’re supposed to be obviously, but my time to wrap my head around the a problem is growing.

We’ll see how level 3 goes, but at least I got a buddy code I could share. Spread the fun just a little further!

19686529_10155463296248524_1657500396_o

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s