Category Archives: Uncategorized

Back to the N-Queens with Backtracking:

Throughout this semester I have been thoroughly enjoying my artificial intelligence class. While the probability stuff can be a bit much for me at times, I absolutely love learning various searching algorithms. For our first project I implemented a genetic algorithm to find a solution for the Traveling Salesperson Problem — in a language I’d never used, Python. While I did have my ups and downs, I learned to love the cleanliness of the language and the welcoming community it has built up. Naturally, I chose Python for my second project.

The N-Queens problem is rather straightforward; how can we place N number of queens on a NxN board such that no queen can directly attack another? This is rather simple, albeit monotonous, to do by hand on small board i.e.: 4 or 5 queens. But, what about when we have 8, 10, or even 20 queens? Things get a bit more tricky. For simplicity, I chose to solve the problem with a backtracking algorithm.

Here’s a summary of how it works:

  1. Starting from the first column, check every row for a threat from queens above, below, left, right, or diagonal to it. Once you find a safe row for a given column, place a queen there.
  2. Recurs incrementing one column until you have either placed a queen in every column or you are unable to safely place a queen in a column. If latter occurs, you must backtrack to the last known good solution.
  3. Annotate the location of the last queen’s row, remove the queen, and recurs calling on the previous column beginning one row passed where the last queen was.

Before starting to code, I drew out a simple, 4-Queen problem on a white board, step by step, and really thought about what was going on, how I wanted to attack the problem, and tricky cases which would need special care. Doing so greatly reduced the amount of headaches I could have had by going straight to the old code and fix  model. Now, only if the entry level C.S. students in my lab would do the same.

Now, down to the good stuff. This is what I came up with:

import sys
import numpy as np

# override default recursion limit
sys.setrecursionlimit(1000000000)


class NQueens:

    def __init__(self, size_of_board):
        self.size = size_of_board
        self.columns = [] * self.size
        self.num_of_places = 0
        self.num_of_backtracks = 0

    def place(self, startRow=0):
        """ Backtracking algorithm to recursively place queens on the board
            args:
                startRow: the row which it attempts to begin placing the queen
            returns:
                list representing a solution
        """
        # if every column has a queen, we have a solution
        if len(self.columns) == self.size:
            print('Solution found! The board size was: ' + str(self.size))
            print(str(self.num_of_places) + ' total places were made.')
            print(str(self.num_of_backtracks) + ' total backtracks were executed.')
            print(self.columns)
            return self.columns

        # otherwise search for a safe queen location
        else:
            for row in range(startRow, self.size):
                # if a safe location in this column exists
                if self.isSafe(len(self.columns), row) is True:
                    # place a queen at the location
                    self.columns.append(row)
                    self.num_of_places += 1
                    # recursively call place() on the next column
                    return self.place()

                # if not possible, reset to last state and try to place queen
            else:
                # grab the last row to backtrack from
                lastRow = self.columns.pop()
                self.num_of_backtracks += 1
                # recursively call place() from the last known good position, incrementing to the next row
                return self.place(startRow=lastRow + 1)

    def isSafe(self, col, row):
        """Determines if a move is safe.
        args:
            col: column of desired placement
            row: row of desired placement
            self.columns: list of queens presently on the board
        returns:
            True if safe, False otherwise
        """
        # check for threats from each queen currently on board
        for threatRow in self.columns:
            # for readability
            threatCol = self.columns.index(threatRow)
            # check for horizontal/vertical threats
            if row == threatRow or col == self.columns.index(threatRow):
                return False
            # check for diagonal threats
            elif threatRow + threatCol == row + col or threatRow - threatCol == row - col:
                return False
        # if we got here, no threats are present and it's safe to place the queen at the (col, row)
        return True

# set the size of the board
n = 17
# instantiate the board and call the backtracking algorithm
queens = NQueens(n)
queens.place(0)

# convert board to numpy array for pretty printing
board = np.array([[' '] * n] * n)
for queen in queens.columns:
    board[queens.columns.index(queen), queen] = 'Q'

print board

And here is a sample output for a 17-Queen solution:

Solution found! The board size was: 17
5374 total places were made.
5357 total backtracks were executed.
[0, 2, 4, 1, 7, 10, 14, 6, 15, 13, 16, 3, 5, 8, 11, 9, 12]
[['Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q']
 [' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'Q' ' ' ' ' ' ' ' ']]

Now, you may have noticed these lines:

# override default recursion limit
sys.setrecursionlimit(1000000000)

After developing a working solution I started receiving: “RuntimeError: maximum recursion depth exceeded in cmp” on boards with more than 13 queens. I found this surprising and did some research. After some digging, I discovered Python has a rather conservative default recursion limit to help avoid infinite recursive calls. My resolution was rather hackish but allowed me to bump the solvable board size to 17 queens by manually setting the recursion limit. This was more than good enough for my class project.

If time permits, I would like to go back and mimic the recursive nature of this with a stack and see how large of a solution would be able to solve. If time permits.

More to follow … maybe?

“To understand recursion, you must understand recursion.”

-H.

Tagged , , , , , ,

Software Engineering Project Take Two:

A lot of the costs for any software project are associated with post-delivery maintenance. This really shouldn’t come as a surprise. However, what might come as a surprise is just how much of the costs — seventy-five percent! So what’s the best way to mitigate the amount of post-delivery maintenance? How about we do things right from the start.

As Project GOOB continues to move forward I have been preparing our requirement/specification document for review. The more I work on it the more I come to realize how easy it is to think like a developer and not as a client without these documents.

The purpose of a requirements document is to provide a bridge between the client and the developer. Our goals are to understand the client’s business model, discern their needs versus wants, and express in a natural language what we as developers need to design to in order to integrate them. In short, we’re building a road map between our client’s business and the software that will help make it more productive.

Functional requirements are the things that our application must be able to do in the most simplistic terms possible. For example, with Project GOOB one of the functional requirement is to create a new alarm. Another functional requirement is to modify an existing alarm. We use these functional requirements to build use cases which graphically represent scenarios where agents (i.e.: users, databases, or even other systems) interact with the system and model behavior from the agents point of view.

Drawing some simple graphical representation to create a new alarm or modify an existing alarm should be simple right? Not exactly. Both of these functional requirements seem to have very similar use cases. Namely: set time, set date, set sound, and set challenge type. But, this is the beauty behind representing functional requirements as use cases. It allows us to spot and redesign potential pit falls, or redundancy, very early in the development process.

You might be thinking, so what. How important is identifying things like this early on? Well, look back up at the staggering statistic: 75% of all project costs are associated with post-delivery maintenance. So, let’s all take a moment, step back from the code we are all so eager to dive into, and think about exactly what it is our client really needs and how we can actually help them do so.

“Code and fix is bad, mmk.” — Some Professor

-H.

Software Engineering Project Take One:

This semester I will be participating in my first group software project. I think it’s going to be a lot of fun, a lot of work, and a great learning experience. My team, PBR Code, consists of two close friends I have worked with extensively over the past three semester and another peer who seems to have a solid work ethic.

After a few weeks analyzing and digesting various software development life cycles we were given a mission: Come up with a need for a specific application. After confirming that I had free creative reign, I came up with The Story of Bob.

  • From: S.M.D. Industries:
    To: PBR Code
  • Gentlemen, we have an issue with one of our employees, Bob, that we were hoping you would be able to help us with. Bob is a likeable character. He has a good work ethic, he is innovative, and is fun to talk to. In short, everyone likes Bob. However, Bob has one problem; he always arrives late to work in the morning.After several such occurrences we asked Bob why this was. “I just can’t seem to stop hitting my snooze button.” replied Bob. Of course each of was able to relate. The snooze button is about as tempting as a late night pizza and PBR. Regardless, this is an issue. We can’t just allow our employees to show up whenever they see fit to do so, right?As previously stated, we all like Bob very much. Therefore, we have decided to send out a request for a new alarm clock application that will help alleviate the issue. We believe that if Bob was required to complete some mental challenge in order to disable or snooze his alarm he would be alert enough to make the right decision and G.O.O.B. (get out of bed). We need this challenge to be something quick enough to not leave Bob irritated and upset before work but at the same time awake enough to make clear decisions.

    The ideal alarm clock would be able to be installed on Bob’s android phone so he can take with him on business trips. Additionally, making this alarm able to run on various versions of the android operating system would be nice. You see, we like Bob but he’s also our guinea pig. If the alarm clock application proves successful with Bob, we will be issuing it to the rest of our employees.

    PBR Code, can you help us with this? We would love to hear your thoughts and ideas on possible solutions. Be creative!

    V/R

    Joseph Dirte
    CEO, S.M.D. Industries

Nothing is better than when you can mix a little humor into your work, right? The team as well as my professor had a good laugh when they read it. From this we will be building our requirements and specifications document for the alarm application. But, that will have to wait until Take Two.

“Choose a job you love, and you will never have to work a day in your life.” – Confucius

-H.

Tagged , ,

Hold on — I need to check my phone

While preparing for the final debate in my Computer Science ethics class today, I was unnerved by a personal revelation. But, let me start from the beginning.

It was case study #24, or ‘Brain’ as dubbed by my professor. In the synopsis there was an odd set of instructions. He gave  the link to a New York Times article,  directions to write down each time and by what I was distracted, and wrote a little blurb about how he had his teenage daughter conduct the same experiment.

To my surprise, it was the most interesting case study I had read in the class. It discussed the decreasing ability of students to focus because of the mass of electronics and information at their fingertips. As instructed I kept a brief journal of each time I was distracted. I noticed something intriguing while reading the article. Like clockwork, I had glanced at my phone every five minutes to see if I had received a text or an email. Similar to how we train ourselves to wake up at a given time each morning this seemed more automated than anything. And what’s worse? I’m still doing it while writing this review even though I’m now aware of it.

On numerous occasions, I have heard it takes 21 times to make an action habitual. I wonder how many times I told myself to glance at my phone for updates before I stopped realizing I was doing it. I also wonder how I ‘glance’ at various things to check for something. More importantly, I wonder how much time I have lost as a result of losing my focus throughout each day. Oh, and remember my professor’s daughter? She sent 337 texts while ‘reading’ the article.

Time to turn off the phone.

-H.

Tagged , , , ,

An Exorcise in Masochism: My first programming competition

Last Saturday I attended my first programming competition. It was the ACM Mid-Atlantic regional competition held at Duke. It went terribly.

Toward the beginning of the semester, the president of my local ACM chapter mentioned the then upcoming completion and asked if anyone was interested. Seeing this as another opportunity to hone my algorithm writing skills I put my name down on a list at started thinking of potential teammates.

I suppose it was natural to choose two friends from my classes that I had worked with quite a bit over the past several semesters. I knew “Bob” and “Sue” were both smart, hard working, and pretty good at coding. Sounds good enough, right? Wrong.

First of all, we didn’t practice. Not even one time. Shortly after getting approval from the department we had a regional ‘qualifier’ to test our skills. The day of the qualifier “Bob” says he wont’ be to make it and “Sue” is going to be late if she comes at all. So, I spent two and a half hours working my hardest and knocked out two problems by myself. To my surprise, I couldn’t even figure out how to start any of the remaining problems. Time to reassess things, right? Also wrong.

Bolstered with false-confidence after knocking out two problems solo, I told myself, “Well, even if we can’t find time to practice I should be able to get some problems at the real competition by myself.” Wrong, wrong, wrong.

The problems competitors are given require a wide set of skills and the ability assess difficult issues, design algorithms to solve them, implement them quickly, and account for huge data sets and odd edge cases. I love “Bob” and “Sue”; however, we all have very similar skill sets. As such, we weren’t the best choice for a strong, versatile team even if we had practiced. Not practicing just made things much, much worse.

Facing eight problems to solve, with one computer, and a time crunch was like riding the Titanic down after the life boats had already departed. To be completely honest, we worked poorly together, got stumped on simple stuff, and spent entirely too much time on all of the wrong things. After five hours of bashing our heads against desks and a whiteboard we walked out to greet the other teams with our heads hung low. Normally, this would be enough for someone to vow never to enter a similar competition, right? Still wrong.

I will be back for round two next year. I will also go better prepared. Many mistakes were made and many lessons learned.

First, a well rounded team is a must. Ideally, I would like my team to consist of: A very strong, experienced programmer, a master of data structures and well known algorithms, and a math-lover. Second, practicing problems that are similar to what is to be expected is vital. I don’t think this is because we will ‘learn’ solutions but rather, we will learn how to tackle problems together. Finally, I will not be blinded by false confidence or delusions of how easy, or difficult, the problems will be.

I can’t lie, the results of the competition have been hard to swallow. Failing is not something I do very often. But, I have come out of everything with a renewed passion for knowledge and a better student.

“We learn from failure, not from success!” – Bram Stoker, Dracula.

-H.

Internships, Interviews, and Mentors

Internships — Lots of people seem to have opinions about internships but very few people I have spoken with have had one. Last summer I had an internship with a local software company, ideacode. Yes, it starts with a lowercase ‘i’. While, I only worked part time (20-ish hours/week), as I was also taking courses over the summer, I was exposed to new software, development environments, programming languages,  and most importantly real software engineers coding real world applications.

But, it could have just easily not happened.  I actually met my mentor, Bishop, by happenstance. I was pulling some hiking gear out of storage for a trip when I saw a mass of programming books on a bookshelf. I could have walked by but I didn’t. Instead, I struck up a conversation. After giving my elevator speech and shaking hands I had a business card and a chance. The first thing I did upon returning from my trip was email him my resume and shortly thereafter I had an interview lined up. What is the moral of this story? Never skip an opportunity.

Interviews — There is a lot of thought about how to prepare for and act in an interview. However, after numerous military boards my interview was a nice treat in comparison. I should take a moment to emphasize that by ‘treat’ I meant enjoyable, not easy. I met Bishop and John, a coding guru, at a local Barnes & Noble. The setting was informal and we were seated at a square table surrounded by a dozen or so other customers who were reading or chatting amongst each other. Perhaps one of them was in an interview as well.

I was well dressed and I thought well prepared. However, the opening salvo of questions Bishop shot my way was not what I expected. He wasn’t trying to determine how well I knew my data structures or programming languages (at least not yet) he was trying to get a feel for who I was. He wanted to know if I would ‘fit’ well with the company. I answered to the best of my ability and tried not to sweat.

He continued with a series of situational questions, asked my thoughts on business organization and best practices, and finished by having me slap together some basic data structures on the table with sticky pads. After all of that they thanked me for my time, we shook hands, and went our separate ways.

A week later I received my first contract offer in the software development field. It felt great. If I could lend any advice from my limited experience it would be this, relax. Start by doing some research on the company you are applying for, review relevant material you think you might be asked about and above all be friendly and honest. Anyone can lie their way into a position but in the end all they will have accomplished is wasting their and their eventual ex-employers time and resources.

Mentors – Bishop was a great one. Clarifying what I mean by ‘great’ is easy when someone gives you many instances to draw from. First off, Bishop had a way of always asking questions that rode that fine line between what I know and what is too far beyond my ability to learn quickly. By asking these questions, the right questions, my knowledge in several expanded rapidly. Within a month of work I was zooming around a Linux server remotely, writing test cases in PHP, and creating advanced bash scripts to manipulate hundreds of source files simultaneously.

For the most part, I worked remotely and foresaw communication being a potential issue. But, Bishop quickly put my mind at ease. He continually responded to my emails/IMs quickly and always giving me just enough information to nudge me in the right direction without explicitly giving me an answer. This is exactly what I needed and exactly why I grew so much in such a short amount of time.

But there are two main things I will take away from my work with Bishop and ideacode. First, programming is an art as well as a science and problems should be taken on with compassion as well as deep thought. And finally, it gave me an appreciation for how beautiful complex code repositories can be. Just as whorls of tree trunks tell stories not just about the age of a tree but also climate, forest fires, and floods; peeling back the layers of code tell a story of their own.

Thank you, Bishop.

“Shallow men believe in luck. Strong men believe in cause and effect.” — Ralph Waldo Emerson

-H.

Tagged , , , ,

Well, it’s about time…

After a long back and forth battle with myself I’ve decided to go ahead and just start blogging. This past June I was fortunate enough to attend a Google Scholar’s retreat in San Francisco. While there I met many like minded individuals, attended fascinating tech talks, and explored Google’s amazing headquarters. In short, it was the one of the best adventures I’ve had thus far in my short existence.

Almost every time I tell people about the trip they want to know what Google was like. To keep my explanation as concise as possible I normally say something along the lines of, “It’s like if an engineer and an artist had a baby with all of their talents and a seemingly endless bank account.” This by no means does justice to how magnificent what I saw was. Imagine going to work being given the room to pursue your interests, explore routes to solutions for assigned problems, and access to unlimited coffee. Good coffee. Oh, now surround yourself with nothing but other smart, like minded people who WANT to be there. That’s how I picture Google. I will work there.

One of the individuals I met there, a fellow Harry, was a great inspiration to me. He has accomplished so much while giving so much back and maintains a humble, professional, and warm demeanor. He recommended I start blogging. So, Harry, this may be a bit late but here we go none the less.

Whether this turns out to be something useful/interesting to others is yet to be determined.

“Hello, world.” — Countless programmers

-H.