Skip to content

Python Minesweeper Programming Problem

At an interview, I was asked to build a python program, using TDD, which would output the results of a minesweeper game.  Not a fully functional game, just a small program that would take an array of bomb locations and print out a map of the board with all values exposed.

So, if you have a 3×3 board, and there is a bomb in each corner, it would print out something like this:

x 2 x
2 4 2
x 2 x

Or if you have a 3×3 board and there is only a bomb in the upper left corner, it would print out something like this:

x 1 0
1 1 0
0 0 0

I did not complete the task in the allotted time, but it was a fun programming exercise and I hope illuminating to the interviewers. I actually took it home and finished it up. Here’s the full text of the program:

class Board:
        def __init__(self, size = 1, bomblocations = []):
		self._size = size
		self._bomblocations = bomblocations
    	
	def size(self):
		return self._size
    	
	def _bombLocation(self,location):
                for onebomblocation in self._bomblocations:
                	if onebomblocation == location:
				return 'x'

	def _isOnBoard(self,location):
		if location[0] =self._size:
		    	return False
		if location[1] >=self._size:
		    	return False
		return True

	def whatsAt(self,location):
		if self._bombLocation(location) == 'x':
			return 'x'
		if not self._isOnBoard(location):
			return None
		return self._numberOfBombsAdjacent(location)

	def _numberOfBombsAdjacent(self,location):
		bombcount = 0
		# change x, then y
		currx = location[0] 
		curry = location[1] 
		for xincrement in [-1,0,1]:
			xtotest = currx + xincrement
			for yincrement in [-1,0,1]:
				ytotest = curry + yincrement
				#print 'testing: '+ str(xtotest) + ', '+str(ytotest)+ ', '+str(bombcount)
				if not self._isOnBoard([xtotest,ytotest]):
					continue	
				if self._bombLocation([xtotest,ytotest]) == 'x':
					bombcount += 1
		return bombcount

	def printBoard(self):
		x = 0
		while x < self._size:
			y = 0
			while y < self._size:
				print self.whatsAt([x,y]),
				y += 1
			x += 1
			print
				
def main():
	board = Board(15,[[0,1],[1,2],[2,4],[2,5],[3,5],[5,5]])
	board.printBoard()

if __name__ == "__main__": 
	main()

And the tests:

import unittest
import app

class TestApp(unittest.TestCase):

    def setUp(self):
    	pass

    def test_board_creation(self):

        newboard = app.Board()
        self.assertIsNotNone(newboard)

    def test_default_board_size(self):
     	newboard = app.Board()
        self.assertEqual(1, newboard.size())	

    def test_constructor_board_size(self):
     	newboard = app.Board(3)
        self.assertEqual(3, newboard.size())	

    def test_board_with_bomb(self):
     	newboard = app.Board(3,[[0,0]])
        self.assertEqual('x', newboard.whatsAt([0,0]))	

    def test_board_with_n_bombs(self):
     	newboard = app.Board(4,[[0,0],[3,3]])
        self.assertEqual('x', newboard.whatsAt([0,0]))	
        self.assertEqual('x', newboard.whatsAt([3,3]))	

    def test_board_with_bomb_check_other_spaces_separated_bombs(self):
     	newboard = app.Board(4,[[0,0],[3,3]])
        self.assertEqual(1, newboard.whatsAt([0,1]))	
        self.assertEqual(1, newboard.whatsAt([1,0]))	
        self.assertEqual(1, newboard.whatsAt([1,1]))	
        self.assertEqual(0, newboard.whatsAt([1,2]))	
        self.assertEqual(0, newboard.whatsAt([2,1]))	
        self.assertEqual(1, newboard.whatsAt([3,2]))	
        self.assertEqual(1, newboard.whatsAt([2,3]))	
        self.assertEqual(1, newboard.whatsAt([2,2]))	

    def test_check_other_spaces_contiguous_bombs(self):
     	newboard = app.Board(4,[[0,1],[0,0]])
        self.assertEqual(1, newboard.whatsAt([0,2]))	
        self.assertEqual(2, newboard.whatsAt([1,0]))	
        self.assertEqual(0, newboard.whatsAt([2,1]))	

    def test_off_the_board(self):
     	newboard = app.Board(3,[[0,0],[1,2]])
        self.assertEqual(None, newboard.whatsAt([3,3]))	

This was written in python 2.7, and reminded me of the pleasure of small, from the ground up software (as opposed to gluing together libraries to achieve business objectives, which is what I do a lot of nowadays).

Using JSONP For Angular Requests

screen photo
Photo by Neil T

I was writing an angular app (source) that was accessing the Best Buy API, just to play around and get more familiar with Angular.  All of my previous apps had been to APIs that I controlled, and could thus use CORS to set headers.  Obviously, not so with the Best Buy API.

Whoops.

Luckily Angular makes accessing data via JSONP almost exactly the same as accessing data via XMLHttpRequest/CORS.  Rather than use $http.get, you use $http.jsonp. You have the same promise returned, and can handle the results in the same way. I didn’t dive into error handling (but if Angular follows jQuery’s lead, it looks like there’s none), and obviously JSONP can only be used to read information, but the guts of injecting a script, etc, are all handled for you.

 

RSS Pick: Dion Almaer

dion almaer photo
Photo by marcosfernandez

I think that the RSS reader is such a fantastic invention. It lets me monitor many bloggers and news sites, and see new content.  This lets you have an eye on lots of writers, including some that haven’t written for a long time.  I’m going to be highlighting blogs that I follow, one per month.

The first is Dion Almaer’s, who, unfortunately, has moved most of his writing to Medium.  But Dion is a great technologist.  He currently is employed at WalmartLabs Mobile.  He’s written such gems as:

Your coding voice:

When people ask me about Java and why I don’t often write applications in it, my answer is not that I think “Java sucks”. I think the JVM is amazing technology, and there are a ton of fantastic APIs. Using Java is a great answer for many situations. However, the least amount of fun that I have had programming has been when using the Java language. It isn’t just that it feels frustratingly verbose, although that is part of it.

and Browsers are Finally Catching Up (in 2009):

But, the browsers are finally changing. The new crop come with technologies that show that the browser vendors are thinking about building a platform for desktop quality applications. The Chrome comic book was full of this.

Remember the Chrome Comic Book?

Dion, thanks for sharing your knowledge, please resurrect your blog!  (Dion, I know this is an old photo–feel free to send me a new one and I’ll update this post.)

Avoiding “Module ‘XXX’ is not available” Errors in AngularJS

headbang photo
Photo by Nirazilla

As I continue to build applications with AngularJS, I see how strong the ecosystem is.  While there aren’t quite as many plugins for Angular as there are for JQuery, many of the JQuery plugins have been wrapped up as Angular directives.

One of the issues I banged my head against a couple of times when using a new directive was how many places I had to modify code, and the totally non intuitive error messages that were displayed.

Here are the places you need to modify if you want to use a directive:

  • a module definition (your app or a controller).  You need to add the directive to the list of dependencies: var controllers = angular.module("controllers", [ "localytics.directives",'ngModal' ]);.
  • the index.html file. You need to add links to the javascript files and css that the directive uses. If you are using bower to manage these components, you can find the files under the directory managed by bower.
  • the karma.conf.js file. This file sets up the environment for your unit tests. You want to set up the files attribute to point to the javascript files you added to the index.html page above.

If you don’t add the correct module name to your dependency list, misspell it, or don’t add the javascript to the index.html or your karma configuration file, you will see this error message in your console:

Uncaught Error: [$injector:modulerr] Failed to instantiate module app due to:
Error: [$injector:modulerr] Failed to instantiate module controllers due to:
Error: [$injector:modulerr] Failed to instantiate module ngModall due to:
Error: [$injector:nomod] Module ‘ngModall’ is not available! You either misspelled the module name or forgot to load it. If registering a module ensure that you specify the dependencies as the second argument.
http://errors.angularjs.org/1.2.25/$injector/nomod?p0=ngModall
at http://192.168.0.200:8000/app/bower_components/angular/angular.js:78:12

And the app won’t start.

Hope this helps someone else avoid some head banging.

Cassandra Dev Day Denver

data photo
Photo by justgrimes

Most of my datastore experience is with RDBMS like mysql, oracle and postgresql (though I did work with some key value stores like berkleydb back in the day). So when a full day, free intro to Cassandra was offered, I jumped on it, even though it was in Centennial. You can view the schedule, speakers and talk synopses for the day. There were two tracks, beginner and advanced. Since I didn’t know anything about Cassandra, I followed the beginner track.

First, though, it was amazing how many people were there. The two main companies behind the talk, Pearson Education and DataStax, a vendor providing a commercial, supported version of Cassandra, ended up having to provide two overflow rooms, and it was still standing room only for some of the talks. Quite a nice turnout, and I think the sponsors were pleasantly shocked. I was also surprised by the number of folks from Boulder. I happened to sit next to two folks from Westminster and Superior, and ended up having a common friend or colleague with each. Small world.

I learned a ton about Cassandra, from its internals, to its topology (the ring’s the thing) to abstractions that let you query it (CQL, which is a subset of SQL) to data modeling to using the java driver, which makes accessing Cassandra almost as easy as using JDBC. While there are some SQL concepts that appear to map fairly well to Cassandra, I put quotes around them below to remind myself of the fact that a Cassandra ‘table’ isn’t the same as a RDBMS table, ditto for ‘row’, ‘primary key’ and other important concepts.

I think the biggest takeaway for me was that Cassandra is a “write many, read once” system. Because you can only query efficiently on one or two keys, if you have multiple queries, you want to write the data multiple times in a denormalized system, one ‘table’ for each query. Because of this, Cassandra shines in use cases where you are doing a lot of inserts, have known queries, and need speed and availability (sensor data was mentioned several times).

How does this actually work? Here’s an example (as best I understand it–here are some others from people who actually have experience using this technology):

If you have click stream data, in standard apache format, and you want to be able to have it stored in a database and highly available for a few specific queries, Cassandra might be a good choice. Here’s a line of my clickstream, from my blog:

157.55.39.40 - - [15/Oct/2014:08:03:30 -0600] "GET /wordpress/archives/date/2007/07 HTTP/1.1" 200 66258 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"

This is time based data, and has some valuable information, and some not so valuable information. What things might I be interested in querying on? Well, I might care about the user agent, request time, ip address, status code, or URL path requested. I probably don’t care about the HTTP method, HTTP version or the bytes served. But, for the sake of this example, let’s say my application needs to show the location of the most recent 1000 users for a given country, for a fancy widget for my website. I will use maxmind or a similar service for mapping ip addresses to country. That’s all I care about. (Yes, I know this is contrived–I had to revise this example a couple of times to make it fit with Cassandra’s usage model.) I would set up in this ‘table’ in Cassandra.


CREATE TABLE IF NOT EXISTS location (
country text,
time timestamp,
user_agent text,
status_code int,
path text,
PRIMARY KEY (text, time)
)

In this table, country is the partition key, and time is the clustering key. That means that this query: select location from location where country = 'USA' limit 1000; will be screaming fast. If I wanted to look at paths requested by time, I would not add an index to this table, but instead create another whole table, say request_path. Then my insertion code would write to both location and request_path. And then clients that wanted path information would use the specific table. Yup, denormalization is the name of the game.

This means that Cassandra has certain specific use cases, and that trying to use it as a general purpose data storage and query engine is foolish. Several presenters mentioned that Cassandra plus Apache Spark for general queries was a good solution.

Denormalization as standard operating procedure isn’t the only mind bending facet of Cassandra. Others:

  • the presenters also talked about the high availability and replication of Cassandra–you can actually configure it to be data center aware so that it automatically replicates data across different data centers.
  • For each keyspace (a set of tables, so similar to a schema), you specify how a replication factor–how many times each piece of data is stored.
  • For every read or write, you specify how many nodes must either agree or accept the data, respectively.
  • Adding nodes is the preferable way to deal with scale. You can add a node easily, and Cassandra will auto partition data and spread existing data across the new node.
  • The biggest Cassandra setup they mentioned was 75K nodes.
  • Each ‘row’ can have up to 2 billion records. If a row stretches across nodes, you’ll kill performance.
  • There’s a process called ‘compaction’ which is similar to Java’s garbage collection, and just like GC, you have to pay attention to how compaction works, because it will affect performance.

All in all, very interesting day, and I appreciated the experience. One more (interesting) tool to add to the toolbox.

Parents In Tech Interview

baby photo
Photo by paparutzi

A few months ago I was contacted by Morgan who read a comment I’d made on Hacker News about reshuffling my work life balance.  He was starting a site for parents who work in technology, and was looking to interview such people for tips on parenting.  After a flurry of emails, we finally found a time that worked for both of us and were able to skype for an half hour.

My interview is up here.  Morgan doesn’t do a ton of editing, so it is a little rough, but you get a sense of my thought process:

M: Has having a Baby changed your worldview, beliefs, or how you treat other people? How so?

 

D: Sometimes I wonder how my parents can take me seriously, given that they saw me as an infant. You put it nicely, getting some empathy, starting out as something that just cries, poops and sleeps.

Full post here.

If you are a parent who works in technology and want to chat with Morgan, let me know and I’ll do an intro.