# Solve this puzzle – @memo and dynamic programming

Here’s the situation.  You have a puzzle with 15 round coloured plates arranged in an equilateral triangle, and 14 coloured pebbles on top of them.  One plate does not have a pebble – it is called the hole.  Your goal is to rearrange the pebbles so that they are on the matching coloured plates, in the minimum number of moves possible.  For each move, you can only move one pebble in a straight line to the hole, possibly leaping over other pebbles on the way.

The question is – can you design an algorithm to calculate, for any starting board, the minimum number of moves to solve it?

In fact this describes the game Panguru, recently produced by Second Nature Games and available as a board game and online.  In Panguru, there are two pebbles and plates of each colour, and one additional legal move down the centreline of the triangle.  If my quick description is too wordy, the online game will give you a much better feel for it; there are rules available too.

## A dynamic programming solution, with memoization

Here’s the approach I came up with, which I implemented in python. This was informed by the excellent book Python Algorithms, Mastering Basic Algorithms in the Python Language, by Magnus Lie Hetland, which I highly recommend.

Think of all the possible moves used to solve the puzzle as a tree. Number the positions 0 to 14.  The root node of the tree is the hole position, and child nodes give the position of the pebble that is being moved. So with the hole starting at the top of the triangle (position 0), one path through the tree might be 0-3-5.  (If you think about it, the last move always tells you where the hole finishes up.)

It is easy to measure how close we are to the solved board: we just count how many pebbles have the same colour as their plates.  When we hit 14, we are done!

In fact we can turn it around.  Let’s assume we have a solution (14 matching pebbles) after m moves. How did we get here?  Clearly, we must have had 13 matching pebbles the move before. (Because you only move one pebble at a time, each move can only increase or decrease the number of matching pebbles by one, or leave the number unchanged.)

And the move before that, we must have had either 12 or 13 matching pebbles. And so on.

This sounds like induction and lends itself to a recursive solution, like this. First define the tree structure via the `Node` class. The core of this is the `__init__` method which keeps track of the node’s parent. I’ve also added `original_pos` to help us later, and two extra methods to display nodes nicely on the command line (`__repr__`) and to make it easier to access the node’s ancestry (`__getitem__`).

```class Node():
def __init__(self, parent, move, num_matching):
self.parent = parent
self.move = move
self.num_matching = num_matching

def original_pos(self, pos):
"""
Return the original position of the pebble now at position pos.
"""
if not self.parent:
return pos
if pos==self.move:
prev_pos = self.parent.move
elif pos==self.parent.move:
prev_pos = self.move
else:
prev_pos = pos
return self.parent.original_pos(prev_pos)

def __getitem__(self, key):
"""
If m is a node which you think of as the last move in a sequence,
m[-3] is the third last move as a Node.
m[-3].move is the third last move as an integer (which position was moved)
"""
if key>=0:
raise IndexError, "You must index moves from the end, e.g. m[-1] for the last move."
if key==-1:
return self
else:
try:
return self.parent[key+1]
except TypeError:
raise IndexError, "Out of range."

def __repr__(self):
return "%s%d" % ((self.parent and ("%s-" % str(self.parent)) or ""),
self.move)
```

Then the puzzle-solving approach could be implemented like this:

```class Puzzle():
def __init__(self, plates, pebbles, allowed_moves):
"""
Set up a puzzle instance for solving.
Args:
plates is a string of 15 chars representing colours
e.g. "WCBRBOGYGPCORPY"
pebbles is the same, with "-" for the hole
e.g. "-PCBRYOGYGBCORP"
allowed_moves is a list s.t.
allowed_moves[i] = list of positions that a pebble at pos i can move to
= list of positions that can move to this position, if it is the hole
e.g. [[1, 2, 3, 4, 5, 6, 9, 10, 12, 14],
[0, 2, 3, 4, 6, 8, 10, 13],
[0, 1, 4, 5, 7, 9, 11, 14],
[0, 1, 4, 5, 6, 7, 10, 12],
[0, 1, 2, 3, 5, 7, 8, 11, 12, 13],
[0, 2, 3, 4, 8, 9, 12, 14],
[0, 1, 3, 7, 8, 9, 10, 11],
[2, 3, 4, 6, 8, 9, 11, 12],
[1, 4, 5, 6, 7, 9, 12, 13],
[0, 2, 5, 6, 7, 8, 13, 14],
[0, 1, 3, 6, 11, 12, 13, 14],
[2, 4, 6, 7, 10, 12, 13, 14],
[0, 3, 4, 5, 7, 8, 10, 11, 13, 14],
[1, 4, 8, 9, 10, 11, 12, 14],
[0, 2, 5, 9, 10, 11, 12, 13]]
"""
self.plates = plates
self.pebbles = pebbles
self.allowed_moves = allowed_moves
self.num_pebbles = len(filter(lambda x: x not in ["-"], self.pebbles))
self.num_matching = sum(plates[i] == pebbles[i] for i in range(len(pebbles)))
hole_pos = self.pebbles.find('-')
self.root = Node(None, hole_pos, self.num_matching)

def matching_nodes(self, turn, num_matching):
"""
Return all the series of moves (as BoardNodes with parents)
that have 'num_matching' matching spots after 'turn' turns.
"""
if turn==0:
if num_matching==self.num_matching:
return [self.root]
else:
return []
result = []
for change in (-1,0,1):
for prev_node in self.matching_nodes(turn-1, num_matching+change):
for move in self.allowed_moves[prev_node.move]:
pebble_colour = self.pebbles[prev_node.original_pos(move)]
# was the moved pebble on a matching plate already?
old_pos_match = (self.plates[move]==pebble_colour)
# does the prev board's hole plate match the moved pebble?
new_pos_match = (self.plates[prev_node.move]==pebble_colour)
# did the move change how many positions were matching,
# by exactly the number we're looking at?
if (old_pos_match-new_pos_match)==change:
result += [Node(prev_node, move, num_matching)]
return result

```

The interesting recursion here is going on in the `matching_nodes` method.  It just implements the idea that the solutions that have, say, 10 matching positions at turn 10, must have had either 9,10 or 11 matching positions at turn 9. It then works back to turn 0, at which point we know how many matching positions there were.

On top of this, we need a further method which finds the right question to ask. It could start by saying – give me all the solutions after 0 moves. If there are none, find all the solutions after 1 move. And keep trying until you find some solutions, e.g.:

```    def optimal_moves(self, stop_at=20):
"""
Return a tuple (fewest possible number of moves, [optimal moves for this board]).
"""
num = 0
result = []
while not result and num<=stop_at:
result = self.matching_nodes(num, self.num_pebbles)
num += 1
return (num, result)

```

The code above will work, but it will be slow and inefficient, because `matching_nodes` will often recurse through territory it has already covered. And that’s where Hetland’s memo decorator comes to the rescue. (This is only a few lines of code which you can find by searching at Google books.) This will cache the results of the decorated method, so that it does not need to be recalculated.  To use it, simply apply `@memo` to the `def matching_nodes` line, like so:

```@memo
def matching_nodes(self, turn, num_matching):```

And that’s it!

You can see this code in action when you ask for a hint in the online game. Each time you press the hint button, the javascript sends off an ajax query which triggers the server to run the above code on the player’s board, and return which moves would come next if the player plays optimally.

In fact, to get around annoying ever-expanding memory problems on the server, I’m running this asynchronously using Celery and Redis (as covered in an earlier blog post), and restarting the celery worker after every request.  But that’s another story…

I hope that has been of interest, and please let me know if you have any comments or improvements.

# Better than jQuery.ajax() – Django with Angular

I have built a website for my games company Second Nature Games using Django.  Django brings lots of benefits like a nice admin panel where my partner can upload new game boards and add new content to the site.

However, to write games on the web you can’t rely too much on a server-side framework like Django. You are going to have to write some javascript as well.  I was keen for the challenge, having used some jQuery before.

In my first attempt, the boards were rendered by Django on the server, and then the javascript on the client-side would manipulate the document object model (DOM) as the game was played. As I described in an earlier post, I used jQuery’s \$.ajax() command to alert the server when the game was finished, and then the javascript would update scores and stats as required.

But this is not easily scalable:  as I added a leaderboard and more stats, more and more things needed to be updated, and I got into a tangle.

The solution is to use a javascript MVC framework like Backbone, Angular or Ember (or Meteor even more so).  I chose to use Angular. There is a great website, To Do MVC, which shows the same To Do application written in many different frameworks, so you can make an informed choice if you’re facing the same decision.

Using one of these frameworks changes how you view the server: the server just sends data and the client renders it. This is known as “data on the wire”.  The effect is to turn the server into an API. (Unfortunately for Django fans, I suspect Django is really overkill for this. But having developed the rest of the site with Django, I stuck with it.)  Meanwhile, whenever the data updates, the javascript framework will update the DOM for you.

Here is a sample template for the Panguru leaderboard, using Angular:

```<div class="info">
<ul>
<span class="name">{{ entry.name }}</span>
<span class="score">{{ entry.score }}</span>
</li>
</ul>
</div>
</div>
```

You can see it’s pretty straightforward and elegant. The code to load it from the API is:

```\$scope.updateLeaderboard = function() {
var that = this;
})
});
}
```

As you may have noticed, Angular and Django both use the double-parentheses notation. You don’t want to have them both try to interpret the same file.

One approach is to use Django’s `{% verbatim %}` tag. I think it’s nicer to separate the Django-rendered templates from the Angular-rendered templates completely, into two separate directories. Django templates stay in their app’s `templates` directory. I put Angular’s html files into the app’s `static/partials` directory. If the server needs to provide data to the javascript, I let Django render it in its template, and pick it up in the static html file. One example is to pass the csrf token. Another example arises because I’m using the staticfiles app, so Django renames all the static files. Unfortunately this includes the locations of all the partial html files and images you need. E.g. in my Django `templates/game_page.html`:

```<html lang="en" ng-app="panguru">
<title>Panguru Online</title>
...
{% addtoblock "css" %}{# if you are using sekizai #}</pre>
<style type="text/css">
</style>
<script type="text/javascript">
csrf_token = '{{ csrf_token }}';
container_url = '{% static "partials/container.html" %}';
...
</script>

<body>
<div panguru-container></div>
</body>
</html>
```

This part I’m not especially proud of, and would love to hear if you have a better solution.

You can then either use a Django API framework like TastyPie to serve the `api/leaderboard/` URL, or you can write one yourself. I did this starting from a JSON response mixin like the one in the Django docs, or this one by Oz Katz, developed for use with Backbone. Then, in Django `views.py`, I put:

```class LeaderboardApi(JSONViewMixin, View):
"Return the JSON representation of the leaderboard"
def get(self, request, *args, **kwargs):
return self.json_response(Score.as_list(limit=20))
```

That just requires a method on your model which returns the object in an appropriate format, e.g.

```class Score(models.Model):
user = models.ForeignKey(User)
score = models.PositiveIntegerField(default=0)
class Meta:
ordering = ['-score']
@classmethod
def as_list(cls):
return [score.as_dict() for score in cls.objects.all()]
def as_dict(self):
return {'name': self.user.username, 'score': self.score }
```

There’s just one more thing, which is an inconsistency in how Django and Angular apply trailing slashes to URLs. Unfortunately if you use Angular’s `\$resource` approach to interacting with the API, it will strip off any final slash, and then Django will redirect the URL to one with a slash, losing any POST parameters along the way. There’s a fair bit of discussion about this online. My approach has been to just turn off Django’s default behavior in `settings.py`:

`APPEND_SLASH = False`

Get ready to thoroughly test your app when you make this change, especially if you are also using Django-CMS, as I am. I uncovered a few places where I had been a bit sloppy in hardwiring URLs, and was inconsistent in my use of slashes in them.

The full result is the logic puzzle game Panguru, which you can play online or buy as a physical boardgame.  Please check it out and let me know what you think!