Monthly Archives: August 2013

Poor Treatment of Recursion in Introductory Textbooks, and a Counterexample

In some computer science or software engineering degree programs functional programming plays a very minor role. There may be an elective course, or there may just be a short segment on recursion in CS101. I went through an introductory sequence that was taught in Java, which doesn’t lend itself to recursion. Probably as a direct consequence of the limitations of Java, recursion was only briefly covered as some kind of novelty concept in programming, and some students were quick to dismiss recursion as “useless” or “academic”.

If recursion gets only treated on a surface level it does look like little more than a novelty concept of little use, with the added disadvantage that it “makes code more difficult to understand.” Sure, the unfamiliar is often difficult to grasp, but the elegance of recursive functions should be self-evident. If you think about it, loops are much less natural. Instead of taking one step after another, you first measure how many steps you are going to take and then process data, and hope that the number of steps you initially determined is equal to the number of steps that is required for the data. This is why there are off-by-one errors in iterative programs but not in functional ones.

Many freshmen have a hard enough time understanding loops. Eventually they will view them as reliable, possibly because they don’t notice half their off-by-one errors, i.e. those that don’t throw an exception due to an out-of-bounds error. I think if you taught people functional programming first and only afterwards introduced them to Java or C++, they might view it as a step back. On the other hand, if you let them experience with recursion in a language that is not suited for it, they learn that it’s easy to blow up the stack, which leads to the formation of beliefs like the two following, which mere made by top posters on Stack Overflow. The context was that one guy posted about an issue he was having with Ruby, a multi-paradigm programming language that is hardly ideal if you want to program in a functional style because it can’t handle deep recursive calls well.

If you’re intentionally recusing 10,000 times, you’re doing it horribly wrong and abusing recursion.

In general, unbounded recursion is bad. Most recursion can be rewritten to be iterative.

The cause of the problem, though, was that Ruby is missing tail call elimination. Recursion itself is not the problem. A programming language with support for tail call elimination should handle recursion just fine. Both statements are therefore misguided. I’ve found that it’s not that uncommon that supposedly good programmers, but also university lecturers, hold similar views. Sometimes you really wonder what a CS or software engineering degree is really good for. By the way, recursion and iteration are equivalent, which means that you can theoretically rewrite any recursive function as an iterative function, and vice versa.

I’ve met quite a few people who view recursion as an obscure alternative to simple loops and “something you don’t do in production code”. I was therefore wondering where this view might come from, and skimmed some introductory text books. The index of Bjarne Stroustrup’s Programming: Principles and Practice Using C++ doesn’t mention recursion at all. Y. Daniel Liang’s Introduction to Java Programming has a short chapter on recursion, but you’ll only find very basic examples there. Python is getting more popular as an introductory language, so I had a look at John M. Zelle’s Python Programming: An Introduction to Computer Science. In that book, recursion is covered in the very last chapter, which doubles as an introduction to the analysis of algorithms.

Zelle uses well-worn examples like computing factorials and Fibonacci numbers or checking whether a string is an anagram. Towers of Hanoi is in there, too. Recursion is also mentioned when describing sorting algorithms like merge sort. The problem I see with this is that the simpler examples don’t necessarily show any advantage of recursion. Towers of Hanoi is too specialized, and it’s not quite clear how that knowledge will transfer to any program you might write yourself. Lastly, sorting algorithms are normally presented as pseudo-code, and recursion is just part of some. In other words, this approach doesn’t necessarily invite exploration.

What’s missing are more elaborate and somewhat realistic problems that show how recursion can lead to cleaner code, and code that is much easier to reason about. Typical textbook examples normally don’t provide this. I’m not sure that fractals make a good example either. Sure, if you’re going to write a fractal generator, you might revisit your textbook and check how recursion is used there. However, there isn’t much of an application for it.

In short, none of the introductory textbooks mentioned give the impression that recursion may be a viable programming concept, and that it’s worth thinking about whether a certain problem might better be solved recursively, instead of making iteration the default choice. I was pleasantly surprised, though, to find a few neat problems in Allen B. Downey’s Think Python: How to Think Like a Computer Scientist. This book is quite astounding. It’s free, short, and content-wise it runs circles around your typical 1000+ page tome that is full of filler material.

Here is exercise 12.6, taken from version 2.0.10 (May 2013) of Think Python. Prof. Downey frequently updates that book, so the exercise may be modified, moved, or even removed from the book in the future. Therefore I’ll describe it fully.

The input is a list containing a good 100,000 words of the English language, and the desired output is the longest word that can be completely reduced. In this context, “reducing a word” means that a given word remains a valid word, i.e. a word contained in the word list, after removing a letter. You can remove a letter from anywhere in the word, but you cannot rearrange letters. The goal is to eventually end up with a one-letter word.

The example in the book is sprite, which leads to the following reduction:

sprite -> spite -> spit -> pit -> it -> i

So, what is the longest word in the English language that can be reduced in this manner? Feel free to grab the text file and try to figure it out yourself.

Prof. Downey gives the following hints:

Write a program to find all words that can be reduced in this way, and then find the longest one. This exercise is a little more challenging than most, so here are some suggestions:

1. You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word.
2. Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible.
3. The wordlist I provided, words.txt, doesn’t contain single letter words. So you might want to add “I”, “a”, and the empty string.
4. To improve the performance of your program, you might want to memoize the words that are known to be reducible.

So, how would you do it? Give it a try, and you might find that recursion allows to write the most important function in a very succinct and elegant way, even though a large part of the program is iterative. Thus, it shows that recursion can be a useful addition to your toolbox, which is an impression you probably won’t get from computing factorials.

In my solution, which is reproduced below, I print out a list of the 20 longest words, but of course you can as well just return the first entry of the list.

def reduce_words():

    def create_dict():
        fin = open('words.txt')
        res = {}
        
        for line in fin:
            word = line.strip()
            res[word] = []
            
        for element in ["a", "i", ""]:
            res[element] = []

        return res

    def add_children(d):
        for key in d.keys():
            children = []
            for i in range(len(key)):
                candidate = key[:i] + key[i+1:]
                if candidate in d and candidate not in children:
                    children.append(candidate)
            d[key] = children
            
        return d

    def recursive_trails(d):
        res = []

        def helper(key, result):
            if d[key] == []:
                return
            if key in ["a", "i", ""]:
                res.append((len(result[0]), result))
            else:
                for entry in d[key]:
                    return helper(entry, result + [entry])
                
        for key,value in d.items():
            helper(key, [key])

        return res

    def top_n(results, n):
        results.sort(reverse = True)
        for i in range(n):
            print results[i]
                    
    d = create_dict()
    add_children(d)
    trails = recursive_trails(d)
    top_n(trails, 20)

reduce_words()

I thought that this was a really neat exercise that showed that you can use recursion in a pretty realistic problem, and end up with pretty elegant code. If only examples like this were included in standard introductory textbooks, or if instructors would use Prof. Downey’s book. But the textbook industry is shady, here is just one example, and the higher education industry complicit, so it may require another two or three financial crises until we see substantial rates of adoption of free high-quality textbooks.

Metacritic and the Legitimacy of Video Game Journalism, Part II

In the last post I wrote about my perception that video game journalism is little more than advertising in disguise. In this post, I’ll discuss numbers that may support my opinion. I use data gathered by the website Metacritic. For those who are not familiar with it: Metacritic collects “expert” reviews of various entertainment media, including video games, normalizes their scores, and posts an average. Users are also able to rate games, which then leads to the games in their database having both an expert and a user average.

One objection you could now voice is that user opinion may be unreliable because it might primarily be people who either dislike a game and give bad reviews, or who love a game and like to see it having many recommendations. Sure, both camps may have their agenda. However, there are PR guys who pose as users, and try to inflate scores, like it happened with the recent Star Trek game. I don’t think any company would pay a PR agency to plant negative reviews, so while you might question the legitimacy of user scores, it’s probably better to view them as slightly inflated due to corporate meddling. Therefore, “true” user scores for big-budget would probably be slightly lower than they are. I do agree that the metrics are hardly reliable, and that it’s questionable whether you could objectively grade a game on a ten scale anyway. People have different tastes, and some people are more forgiving of gameplay flaws than others. Still, as a voice of “the people”, it may be interesting to see how they differ from the alleged experts.

I’ve conducted my analysis with data that was current as of August 2, 2013. Games that were released since then are not considered. Further, there may have been slight changes in some of the user scores, simply due to ratings that were submitted to Metacritic in the mean time. I only focus on Xbox 360 games, but I don’t think there would be a fundamental difference when analyzing ratings for PlayStation 3 or PC games.

Metacritic holds records for 1505 Xbox 360 games. I did start with some rather basic analysis. My aim was to uncover discrepancies between users and “experts”. The first few examples may not be overly interesting, but there is a climax towards the end, so please keep reading.

Here’s a top-level overview of the data:

  • user rating < expert rating: 760 games (50.5 %)
  • user rating > expert rating: 683 games (45.4 %)
  • user rating = expert rating: 63 games (4.1 %)

This doesn’t look like much of a discrepancy, though, so I adjusted my parameters to check how the picture changes if I define “equal” to be a difference of +/- 5 %:

  • user rating < expert rating: 494 games (32.8 %)
  • user rating > expert rating: 443 games (29.4 %)
  • user rating = expert rating: 568 games (37.8 %)

Since this wasn’t particularly revealing either, I then moved on to have a look at the average user and “expert” ratings, considering all 1505 games:

  • expert average: 69.0
  • user average: 68.3

The difference looks miniscule. However, the video game industry is focussing on “AAA games”, i.e. games that cost a lot of money to make, and whose advertising budget is even higher than their astronomical production costs. Since I had the impression that it is primarily this category of games that receives inflated ratings, I changed my script to only consider games that were rated with at least 90 by the “experts”. This applies to just 33 games. Suddenly, the picture gets much more interesting:

  • expert average: 93.3
  • user average: 81.1

I’ll let you draw your conclusions about that when you consider that as a whole the difference between user and expert ratings is 0.7. It seems that as soon as big advertising money comes into play, the “experts” identify greatness where users see just another okay game. A difference of 12.2 points is quite staggering.

If I run the same script but limit the scope so that it only counts games that were rated with 85 or more by the “experts”, a total of 137 games, the discrepancy is still quite startling:

  • expert average: 89.3
  • user average: 79.5

A difference of about 10 points is not to be ignored either, but not quite as damning as the previous subset of games. Let’s now have a look at those fabulous 37 games that the “experts” thought were marvels of digital entertainment. The columns have to be interpreted the following way:

  • column 1: user rating minus expert rating
  • column 2: expert rating
  • column 3: user rating
  • column 4: game title

To make it perfectly clear what the data means, look at this line: “-38 93 55 Mass Effect 3”. This means that the users gave the game a 55, the experts a 93, and that the user score is 38 lower than expert score.

Here is the entire list:

-38 93 55 Mass Effect 3
-33 94 61 Call of Duty: Modern Warfare 2
-20 93 73 Street Fighter IV
-19 98 79 Grand Theft Auto IV
-18 94 76 Halo 3
-17 93 76 Gears of War 2
-15 91 76 Gears of War 3
-15 91 76 Super Street Fighter IV
-14 91 77 Halo: Reach
-13 92 79 Forza Motorsport 3
-12 93 81 Pac-Man Championship Edition DX
-12 93 81 Rock Band 3
-12 96 84 The Elder Scrolls V: Skyrim
-11 91 80 Forza Motorsport 4
-11 92 81 Guitar Hero II
-11 92 81 Rock Band
-11 94 83 Gears of War
-11 95 84 Portal 2
-10 94 84 Call of Duty 4: Modern Warfare
-9 92 83 Rock Band 2
-9 94 85 Batman: Arkham City
-8 92 84 The Walking Dead: A Telltale Games Series
-8 93 85 BioShock Infinite
-8 93 85 Fallout 3
-8 96 88 BioShock
-7 93 86 Braid
-7 94 87 The Elder Scrolls IV: Oblivion
-7 96 89 Mass Effect 2
-7 96 89 The Orange Box
-6 91 85 Far Cry 3
-6 95 89 Red Dead Redemption
-5 92 87 Batman: Arkham Asylum
-4 91 87 Mass Effect

It turned out that across the board users were less impressed than professional reviewers, and oftentimes dramatically less. Maybe you have played some of those games and asked yourself why they don’t live up to their glowing reviews. For instance, I was thoroughly unimpressed by Halo 3, and Grand Theft Auto IV I view as a game with many issues, but with plenty of fun moments nonetheless. The “experts” give the game a 98, the users a 79. The user score is closer to my perception of that game’s quality. The Gears of War games have a ham-fisted plot and okay gunplay, and don’t think they deserved the praise it got. The third part had some really great moments, though, but also much more ham. The by far best third person shooter I played on the Xbox 360 was Binary Domain. The critics gave it a 74, the users an 81.

If you wonder whether you should trust video game reviews, then you now have some good justification why you shouldn’t. Nowadays I ignore mainstream reviews and look for the consensus in niche communities, like on message boards for people who play STGs. This is much more helpful than the writeup of some “expert reviewer” who is forcing himself to type a few hundred words about a game he may not even have finished or hasn’t even understood the controls of. My personal consequence is that I buy fewer games, and if I want to play some “AAA title”, I wait until I can pick it up for cheap to minimize the amount of money I might potentially waste. If there are more people like me, then the money hatting strategy of the big publishers might not be as effective as the MBA types who dreamt it up think. The rise of indie games might suggest that people are getting fed up with “AAA gaming”.

For a more uplifting conclusion that supports the view that fan feedback can be very valuable with regards to games that are under-appreciated by professional reviewers, let’s now look at 20 titles fans enjoyed but critics despised:

33 48 81 Otomedius Excellent
33 44 77 Warriors Orochi 2
31 52 83 Samurai Warriors 2
30 57 87 World of Outlaws: Sprint Cars
29 53 82 Tetris Splash
29 42 71 Venetica
27 49 76 Dynasty Warriors: Gundam 2
26 63 89 Triggerheart Exelica
26 53 79 Samurai Warriors 2 Empires
26 49 75 Puzzle Arcade
25 58 83 Vigilante 8: Arcade
25 53 78 Ecco the Dolphin
24 64 88 Project Sylpheed: Arc of Deception
24 61 85 Dynasty Warriors 5 Empires
24 60 84 Sonic Adventure 2
23 63 86 Serious Sam 3: BFE
23 62 85 WRC 3
23 54 77 Rise of Nightmares
22 53 75 Warriors Orochi

I recognize two STGs, Otomedius Excellent and Triggerheart Exelica, plenty of samurai games, and a couple of classic games, or reinterpretations of classic games. People seem to have a lot of fun with those, even though the “experts” don’t get them. As a cynic, I’m tempted to conclude from those data that it doesn’t make a lot of sense to let hats full of money go around when the game you’re about to release only appeals to a more “hardcore” audience, and its sales potential is comparably low. On the other hand, if you are marketing Halo, then you can be a bit more generous and discredit video game journalism even more. Just look at Geoff Keighley:

Geoff Keighley, a paragon of integrity in video games journalism

Geoff Keighley, a paragon of integrity in video games journalism

But, hey, the man’s got to eat, too! Who knows, maybe he’ll one day figure out how to play a video game despite having one hand buried in a bowl full of Doritos, and holding a Mountain Dew in the other.

Metacritic and the Legitimacy of Video Game Journalism, Part I

I recently bought an Xbox 360 since I was interested in playing a couple of recent games. Some of my buying choices were influenced by reviews on websites. Games like Red Dead Redemption were great, but others didn’t quite live up to my expectations. I’ve now had about a handful of experiences were the glowing reception of the games by reviewers didn’t at all match my subjective experience. Thus, I wondered how legitimate video game journalism really is.

I also noticed that some games I tremendously enjoyed, such as Vanquish, received a rather lukewarm reception. Also, I couldn’t help but notice that gaming websites are plastered with ads, so the obvious assumption is that those sites don’t want to bite the hand that feeds them and therefore promote “AAA titles”, while they spend little attention to games that cater to a niche audience. It’s also quite obvious that many mainstream reviewers don’t understand particular genres or, well, just plain suck at playing video games.

Here is a prime example: the Destructoid review of Vanquish by Platinum Games, written by Jim Sterling. He gave the game a 5 out of 10, and every single word he wrote indicates that he just didn’t get how to play this game. Vanquish isn’t a “cover-based shooter” in the vein of Gears of War but instead puts heavy emphasis on offensive play. The game is a bit more complex than in, say, Call of Duty, but you’ll get amply rewarded if you spend a few minutes to learn the controls. This was seemingly too much effort for Jim Sterling, so he wrote:

Sam [the protagonist] actually needs energy to punch his opponents, and once he’s landed a single successful punch, he can’t glide away since the energy meter completely drains. Several times, I punched an enemy, failed to kill it thanks to Sam’s inability to aim his punches properly, and was killed because I could neither defend myself or swiftly escape.

The issue is that the energy meter that enables you to perform more powerful attacks depletes as you do your little tricks. However, there is a risk/reward mechanism built in. If you completely replete the energy meter, your combat suit overheats. You then have to allow it to cool down, which makes you vulnerable to enemy attacks since you can neither defend yourself properly nor quickly evade. The core mechanic is therefore to find a rhythm for your attacks. This is not as bad as it may sound since the energy meter replenishes very quickly. I found the game mechanic to be highly satisfying, and with some practice, it’s quite easy to get into a state of flow. Frankly, I thought that Vanquish was absolutely fantastic and that it reaches a high-water mark for action games. Enthusiastic reception of this game by actual players, like on NeoGAF, seems to indicate that I’m not the only one who had been very impressed by it.

Jim Sterling’s review of Vanquish may be an egregious example, but the average games journalist is hardly an expert. Especially when it comes to niche games they don’t seem know what they are looking at. For instance, one of my favorite genres are shooting games (STGs). No, not the Call of Duty kind, but the modern descendants of Space Invaders. While most games strive to be “entertainment”, and therefore offer at best a moderate challenge, STGs are designed for repeated play throughs, with the goal being mastery so that you can eventually clear the entire game on just one credit. Depending on your skill level, this may take many months, and with the harder games you may never even get there because you’re just not good enough. This can be a humbling experience, but if you master a game like that, you’ll feel a sense of achievement which you just don’t get from games that hold your hand all the way through. Sure, it’s not for everyone, but those games have enthusiastic fans. Yet, the typical mainstream reviewer is quick to dismiss those games because you can just hit “start” again and “see everything in 15 minutes”. The thread Amusingly bad reviews on shmups.com collects statements like that. You can only shake your head.

I’ve now mentioned some examples of games or genres that tend to get short shrift by mainstream reviewers. Now let’s look at games that receive lavish praise, and whose faults either get ignored or justified. One prime example is one of the greatest commercial successes in recent years: Grand Theft Auto IV. It sold 25 million copies, and it’s the top rated Xbox 360 game on Metacritic. I think it’s a decent game, but it has its flaws, like a repetitive mission structure, poor driving, and clunky weapon mechanics. It’s not a bad game, but hardly the masterpiece it is claimed to be. Less than a quarter of the people who bought the game finished it. The other three quarters probably got bored or frustrated.

Another example is Resident Evil 5. It’s probably not a bad game once you get into it, but it doesn’t make it easy for you to like it. My main gripe is that your character controls like a tank. One of the very first scenes has you enter a shack. Then zombies start attacking you from two and then three sides. They first come running at you, but before they reach you, they seem to hit an invisible wall that makes them stop. From this point onward, they take turns attacking you, which results in incredibly awkward gameplay. This isn’t my idea of having fun, so I have yet to return to this game. When Resident Evil 5 came out, reviewers were defending the controls as “traditional Resident Evil gameplay”, and hordes of obnoxious gaming fanboys were eager to tell anybody who dared to criticize their favorite franchise a variation of “the controls are fine, maybe you just suck at the game.”

Seeing that some of the biggest games have quite startling flaws, I ended up wondering whether “AAA games” that are backed by multi-million advertising campaigns get much more praise than they deserve, and not because they are so great, but because “money hatting” buys good review scores. The big games normally don’t dare to be challenging, so even your average video game reviewer can play them. On the other hand, it seems that many journalist lack the knowledge and skills to appraise niche games, and are therefore quick to dismiss them. A glance at review scores on Metacritc, which contrasts user and “expert” opinions seemed to support this hypothesis. Looking for hard facts, I then made use of my programming skills and analyzed their data. I will share the results with you in the next post.

Backtracking Search in Python with Four Queens

The final project of Coursera’s Introduction to Systematic Program Design – Part 1 was to write a solver for the four queens problem. The goal is to place four queens on a 4 x 4 chess board so that the queens do not obstruct each other. This problem is a simplification of the eight queens problem, and it’s a good exercise for backtracking search. Please note that the Coursera course was using a Lisp dialect as its teaching language. Due to the Coursera honor code I cannot share that solution. However, since some students attempted to rewrite their solution in Python and discussed their approaches on the forum, I decided to port my solution to Python as well and present it here.

Given the limited problem space, there are other approaches to the four queens problem that may be more effective. Those may not teach you about constraint programming or backtracking search, though, and they probably don’t scale that well either. Just have a look at a 4 x 4 chess board: If you have the insight to put the first queen on the second square, then the problem basically solves itself!

To make it a bit easier to transition between the problem description and the eventual Python code, I’ll describe the positions on the board as integers, and not as a letter-integer pair as you’d see it on the chess board. The board therefore turns into:


 0  1  2  3
 4  5  6  7
 8  9  10 11
 12 13 14 15 

Let’s assume you want to implement a proper backtracking algorithm. Say, you start with an empty board. What would you then do? The key idea is to check every square and if this turns out to be unfeasible further down the line, discard that branch of the emerging solution tree and continue from a point that has not yet been explored. Concretely, this means that after the very first iteration of the program, when given an empty board, you’ve created a list of 16 boards, each containing a queen on a different square. The first board in the list has the queen on position 0, the second on position 1, and so on.

Let’s stick with the very first board for the time being. In the second iteration you’d create another list of boards that all contain one queen on square 0, and the second queen on one of the squares 6, 7, 9, 11, 12, 14. Pick any of those boards, put a third queen on them, and you’ll find that it is impossible to place a fourth queen. Seeing that it’s not possible to solve the 4-queens problem if you start with a queen on square 0, you then move on to the next square and try to solve the problem. This is indeed one of the solutions, so the algorithm should present a valid board at the end.

Having illustrated the problem, let’s now talk about one way to code up the solution in Python. I tend to avoid overly terse expressions, apart from a list comprehension here or there, so it should be readable with just a bit of commentary.

To make life a bit easier and the resulting code more readable, I made the following definitions:

B = False
Q = True
all_positions = range(16)

The variable “all_positions” is nothing but a veneer to make the code more legible. It represents the idea that the board is a list with 16 entries.

You might think that it’s silly to define B (for blank) as False and Q (for Queen) as True. However, you can then define a board more succinctly in list form. Here’s what the empty board looks like:

BD0 = [B, B, B, B,
       B, B, B, B,
       B, B, B, B,
       B, B, B, B,]

This list gets evaluated to a list with sixteen “False” entries, but the shorthand introduced above saves some typing and allows for easier illustration of the problem.

A queen attacks in three directions over the whole extent of the board, i.e. horizontally, vertically, and diagonally. Since the board is represented as a list of boolean values, and Python allows for index-based list access, the following definitions can be used to traverse the board easily and check whether there are any collisions:

rows = [ [  0,  1,  2,  3 ],
         [  4,  5,  6,  7 ],
         [  8,  9, 10, 11 ],
         [ 12, 13, 14, 15 ] ]

columns = [ [ 0,  4,  8, 12 ],
            [ 1,  5,  9, 13 ],
            [ 2,  6, 10, 14 ],
            [ 3,  7, 11, 15 ] ]

diagonals = [ [  1,  4 ],
              [  2,  5,  8 ],
              [  3,  6,  9, 12 ],
              [  7, 10, 13 ],
              [ 11, 14 ],
              [  2,  7 ],
              [  1,  6, 11 ],
              [  0,  5, 10, 15 ],
              [  4,  9, 14 ],
              [  8, 13] ]

Please note that this solution does not scale well. It works fine on a 4 x 4 board, but to extend it to an 8 x 8 board, you’d either have to expand the lists with fitting numerical values, or find a way to represent rows, columns, and diagonals as sequence definitions that can be generated automatically, but that’s a problem to look into later. Currently, I’m primarily concerned with an illustration of that particular search problem.

With the preliminaries behind us, I’ll now focus on a general strategy for solving the problem, before filling in the blanks and showing you the source code. The following also serves as a blueprint if you want to go ahead and write the program yourself. I prefer to decompose functions so that they, ideally, achieve one task only. This leads to a greater number of functions, but it makes it easier to reason over code, to debug, and to extend the program later on.

Following the description above, the main steps are something like this:

  • 1. enter a starting position (board)
  • 2. if that board is solved, return the board
  • 3. else: generate a list of boards with all valid subsequent positions, and continue with 1)

This gives rise to the question when a board is valid. To make the code a bit cleaner, I’ll assume that the set of inputs only consists of well-formatted lists, according to the previous specification. A board is valid if there is at most one queen in every column, row, and diagonal, which can be expressed like this:

def board_valid(board):

    def check_entries(entries):
        for entry in entries:
            if number_of_queens(board, entry) > 1:
                return False
        return True
    
    return all([ check_entries(x) for x in [ rows, columns, diagonals ] ])

The function number_of_queens() is defined separately:

def number_of_queens(board, positions):
    return sum([ 1 for pos in positions if board[pos] ])

A board is solved if it is a valid board and if there are exactly four queens on the board:

def board_solved(board):
    return isinstance(board, list) and board_valid(board) \
            and number_of_queens(board, all_positions) == 4 

With those functions in place, everything is set up to solve the problem. I tend to prefer a bottom-up approach when programming, and I visually represent this by putting the most general function last.

# find all empty squares
def get_positions(board):
    return [ x for x in range(len(board)) if not board[x] ]

def get_next_boards(board, positions):
    result = []
    for pos in positions:
        temp = copy.deepcopy(board)
        temp[pos] = True
        result.append(temp)
    return [ board for board in result if board_valid(board) ]

def solve_board(board):
    if board_solved(board):
        return board
    else:
        return solve_board_list(get_next_boards(board, get_positions(board)))
        
def solve_board_list(board_list):
    if board_list == []:
        return False
    else:
        check = solve_board(board_list[0])
        if board_solved(check) != False:
            return check
        else:
            return solve_board_list(board_list[1:])

I think this is quite readable. If the flow of execution is not quite clear, please refer to the description of the problem at the start of the article. Congratulations! You’ve now solved the four queens problem using backtracking search.

The entire code, with test cases and some further helper functions, like a visualizer, a generator for all valid starting positions, and a function that outputs all possible solutions, is available on my github page. Look for the file “4_queens.py”.

Review: Algorithms: Design and Analysis, Part 1 — Coursera

Udacity’s Algorithms: Crunching Social Networks is a neat course, but does focus heavily on graphs, as the title suggests. I was therefore looking for a more thorough treatment of algorithms, and Tim Roughgarden’s Coursera course Algorithms: Design and Analysis, Part 1 provided exactly that. I originally intended to write a review after finishing part 2, but there was so much content in the first part already that I dropped that idea.

Algorithms: Design and Analysis consisted of, as Prof. Roughgarden put it, “a selection of greatest hits of computer science.” It’s material any programmer or computer scientist should be familiar with. It is relevant whenever you work with algorithms and data structures, and also satisfying to study.

Here is the entire curriculum:

I. INTRODUCTION (Week 1)
II. ASYMPTOTIC ANALYSIS (Week 1)
III. DIVIDE & CONQUER ALGORITHMS (Week 1)
IV. THE MASTER METHOD (Week 2)
V. QUICKSORT – ALGORITHM (Week 2)
VI. QUICKSORT – ANALYSIS (Week 2)
VII. PROBABILITY REVIEW (Weeks 2-3)
VIII. LINEAR-TIME SELECTION (Week 3)
IX. GRAPHS AND THE CONTRACTION ALGORITHM (Week 3)
X. GRAPH SEARCH AND CONNECTIVITY (Week 4)
XI. DIJKSTRA’S SHORTEST-PATH ALGORITHM (Week 5)
XII. HEAPS (Week 5)
XIII. BALANCED BINARY SEARCH TREES (Week 5)
XIV. HASHING: THE BASICS (Week 6)
XV. UNIVERSAL HASHING (Week 6)
XV. BLOOM FILTERS (Week 6)

I particularly enjoyed the lectures on the master method, since they cleared up a few things for me. Some time ago I was working with matrix multiplication. From linear algebra I knew that this should lead to cubic runtime. However, my impression was that the algorithm ran faster than that, so I did some research and found out about Strassen’s algorithm. This one was covered in the lectures as well. What I viewed as mysterious back then was not only how Strassen came up with it in the first place — those strokes of genius are rarely explained — but also how one could make a statement as precise as that the algorithm was in O(n ^ 2.8074). Well, thanks to the master method I know now.

All the topics listed above you can find in your typical algorithms textbook. What you don’t get when working through a textbook, however, is the fabulous presentation of the material. The lectures are full of proofs and serious discussions, but Prof. Roughgarden knows how to keep your attention with a dry remark, or by quickly traversing language levels. In one second he’s speak of the raison d’être of an algorithm, and in the next he advises you “to bust out the Pythagorean Theorem” for one part of a proof. At that point I did rewind the video because I thought there was no way he could have said that.

The lectures overall were surprisingly entertaining. This was particularly the case whenever Prof. Roughgarden was discussing implications of analyses or the “big picture”. Here is a good example, taken from a brief lecture that discussed the necessity of knowing your data structures and their respective features well:

Levels of knowledge regarding data structures

Levels of knowledge regarding data structures

Level 1 was, according to Prof. Roughgarden, “cocktail party conversation competence, but of course I am only talking of the nerdiest of cocktail parties”. The sense of humor may not be to your liking, but if it is, you’ll be in for a treat. I don’t think I ever enjoyed listening to a lecturer in a technical subject that much.

Let’s talk some more about the presentation. I have gone through courses, both online and on-campus, that presented the material as if it had been received from God in its final form, with hardly any motivation or explanation, and instead just a litany of formulae and definitions. Prof. Roughgarden eventually also ends up with lengthy equations and formal definitions, but he develops the material as he goes along, not unlike Salman Kahn does it in his mathematics videos at Khan Academy. Here is a slide from one of the lectures on Dijkstra’s algorithm to illustrate this:

Dijkstra in color

Dijkstra in color

The many colors give a hint at the stages this drawing went through, but if this is too hectic for you, you can download the lecture slides as PDFs as well. Even typed versions were provided. Occasionally, there were optional PDFs with lengthy formal proofs for those with a greater interest in theory.

If you now said that this sounds as if the presentation was a bit whimsical, then I would agree with you. However, this does not mean that Algorithms: Design and Analysis wasn’t a thorough course. The problem sets and programming assignments required you to have a solid grasp on the material from the lectures. In particular the programming assignments required a good understanding of not only your programming language of choice but also of the algorithms and their supporting data structures. The difference between a good and a poor implementation could easily amount to several orders of magnitude. In one case, you get the answer almost instantly, and in the other your program might run for hours if not an entire day. Just imagine using repeated linear search over an array when the problem called for a hash table instead!

Overall, the programming assignments were a highlight of the course. Here’s a complete list, arranged by weeks:

  • Counting inversions
  • Quicksort
  • Karger’s algorithm
  • Computing strongly connected components
  • Dijkstra’s algorithm
  • 2 sum problem & Median maintenance

The first problem piggybacks on mergesort. The others were normally as straight-forward as they sound. However, the files that had to be processed were often quite large, which required some care when implementing the algorithms. Weeks 3 and 4 were the most challenging and also the most interesting problems. How well you’ll fare with the assignments may also depend on the language you chose. The grader only checks the numerical answer. How you get there is entirely your problem. You can chose any language you want, but some may be better suited than others.

The theory questions normally related to the homework in some way. I found it therefore helpful to only tackle them after I had successfully submitted the programming assignments. For some questions it may help to consult the optional text books. Prof. Roughgarden gives references for four textbooks, one of which is available for free online. The books were Cormen et al., Introduction to Algorithms, Dasgupta et al., Algorithms, Kleinberg and Tardos, Algorithm Design, and Sedgewick and Wayne, Algorithms. I found the free resource, Dasgupta, to be sufficient for the course.

In this offering, the problem sets and programming assignment counted 30 % each for the final grade, and the final exam made up the remaining 40 %. The final exam was fair, but not necessarily easy. However, it felt somewhat superfluous since the problem sets covered the material already, and some of the questions in the problem sets were more challenging. But partly this could have been because some topics were new for me back then, and when encountering them again in the final exam I was familiar with them already.

While I tremendously enjoyed the course, there were some problems, too, and most are related to the forums. Algorithms: Design and Analysis is not an introductory course. If you’ve gone through a solid CS101 course, and a survey course in data structures, maybe like Stanford’s free CS106A and CS106B, you should be well-prepared. If you lack this knowledge, then do yourself the favor and work on the basics first. However, quite a few people seemed to not have read the course description, according to which this course is appropriate for junior or senior level CS students. As a consequence, I mostly avoided the forums in the beginning because they were filled to the brim with basic or superfluous questions, and often with poor grammar and vocabulary. I couldn’t help but wonder why it almost always were people using Java who didn’t have a proper grasp of programming, the course content, and the English language. As the course progressed, fewer and fewer of those people were left, which increased the value the forums provided substantially.

Weak forum moderation is by far my biggest gripe with MOOCs. I think a sub-forum for beginners would have been a good idea. Forum moderators could then simply move all distracting threads there. An even better idea would have been some kind of entrance exam that checked basic competency. There certainly were some good discussions in the forum. Yet, the signal to noise ratio was at times as bad as on any “social media” site. In other words: the few good contributions were drowned by a myriad of barely legible or superfluous “me too” posts because people were too lazy to check whether a similar issue had been discussed already.

Speaking of the course material, one negative aspect was that no test cases for the programming assignments were provided. However, the text files we were given were normally so large that a manual check was not feasible. This was where the forum shined as some people posted test cases to work with. This was a good alternative to testing your algorithm on a 70mb text file. I’m sure many would have appreciated if the course staff had provided a number of test cases as this would have ensured a smoother experience.

Further, there was an issue that some people managed to implement algorithms that were able to process the small test cases, but which choked on larger files. When I took an algorithms course at university, we were given two or three input files per assignment. To pass the assignment it was sufficient if your algorithm could process the smallest input size. This was a fair approach since you showed that you could implement the algorithm. On the other hand, in Algorithms: Design and Analysis, your only choice was to correctly process the often very large input file. Therefore, I think that people were unfairly being punished for implementing an inefficient but principally correct algorithm. They are no better off than somebody who didn’t manage to implement the algorithm at all. But shouldn’t the former group at least have had a chance to earn partial credit?

While there were some minor issues with this course, I nonetheless think that Algorithms: Design and Analysis, Part 1 was great. Especially for an autodidact it’s probably a better solution to go through this course than any of the standard textbooks on your own. I highly recommend it, and I’m eagerly waiting for part 2.