Project Euler Problem #18 - Maximum Path Sum
I had a good time working on this today and I wanted to write about how I tackled it. Many of the Project Euler problems require an efficient algorithm in order to run in a reasonable amount of time, and this is a good example of just that!

Problem

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Analysis

The brute force approach to this problem would involve tracing every path and computing the maximum path cost. The time complexity of this algorithm is O(2n) where n is the number of rows in the triangle (minus the first). For our triangle of 15 rows, 214 = 16384 paths to compute. This is acceptable, but Problem #67 poses a much larger version of the same problem with a 100 row triangle! Testing 299 paths is an intractable problem so a more efficient algorithm is required.

That efficient algorithm, or at least one of them, is to use the dynamic programming approach. By splitting up the triangle into small sub-triangles, and working from the bottom-up, we can compute the maximum path in a single pass. For each cell in the triangle we find the max of the two cells below it and add that to the cell value. This algorithm has time complexity O(n), where n is the number of cells, a vast improvement over brute force!

Code

Here is my Python solution. I represent the triangle as a list of lists, each inner list is a row. Starting at the second last row and moving upwards, for each cell in this structure I compute cell(i,j) += max(cell(i+1,j), cell(i+1,j+1)). The cell at the top of the triangle will contain the maximum path cost.

import time
# a list to represent the triangle
triangle = []
# read the data file
data_file = open("triangle.txt", "r")
# for each line in the data file, append a row (list) to the triangle
for line in data_file:
    row = [int(i) for i in line.split(" ")] # convert the line to a list
    triangle.append(row)

# time.clock() measures cpu time not actual time
start_time = time.clock()

# for each cell in the triangle, add the max of the cells below-left and
# below-right. the cell at the top will contain the greatest sum from bottom
# to top
for i in range(len(triangle)-2,-1,-1):
    for j in range(i+1):
        triangle[i][j] +=  max([triangle[i+1][j],triangle[i+1][j+1]])

elapsed_time = time.clock() - start_time

print "maximum path cost: %d" % (triangle[0][0])
print "time elapsed: %f ms" % (elapsed_time * 1000)

Results

I've spoilered the answer to each problem in case you want to find it for yourself.

For the 15 row triangle in Problem #18:

maximum path cost: 1074
time elapsed: 0.198637 ms

and the 100 row triangle in Problem #67:

maximum path cost: 7273
time elapsed: 8.080979 ms



Day Of Defeat Server Setup With AWS

My recreational plans were dashed today and I was left with a free afternoon to fill with something fun. I've been playing Day of Defeat again lately, a favourite old game of mine that still has a lively online community, and I figured this presented a good opportunity to have a crack at using Amazon Web Services (AWS) to host a dedicated server. So off I went, and here is a brief write up of my experience.

Part 1: AWS/EC2 Setup

The first step towards using AWS is, you guessed it, signing up for an account. This is a straight-forward process with a verification step, I won't elaborate. After you have an account, you can sign in to the AWS Management Console to administrate your new part of the cloud.

Click on the EC2 option in the list of web services. EC2 allows you to setup virtual servers. Hit the Launch Instance button. You can select your operating system and a few other advanced options. I chose Windows Server 2008, but there's plenty of others including various flavours of Linux. You will need to generate a key-pair (.pem) file which will contain your administrator password. I haven't had any experience with the resource demands of running a game server and I have chosen the least powerful instance options so I can remain in the free tier. I'll see how it goes and update this post accordingly.

Once it is launched, you'll want to connect to your new server instance. Select Instances from the menu at the left and click on your new instance. Now click on Actions and select Retrieve Windows Admin Password. Browse for your .pem file, click on Decrypt Password and note your password for future reference. You can also download a Remote Desktop Connection shortcut. When you're ready to rock, click on this shortcut, enter your admin password and voila, welcome to your new Windows server!

Part 2: Source Dedicated Server Setup

Interestingly, you do not require Steam to run a Source Dedicated Server. Instead, I followed the steps over at srcds and installed hldsupdatetool which manages downloading the games. After running the tool and installing Day of Defeat, and then setting up a launcher for srcds with the appropriate options, you're almost good to go, but not quite!

While you're still fooling around on your server, go to Control Panel and open up Windows Firewall. You need to add access for the srcds program.

Part 3: Static IP and Port Forwarding

Open up your AWS Management Console again, select EC2 and then the Security Groups option from the menu at the left. Select the security group that your instance is using. We'll add two rules, the first is a new Custom TCP Rule for port range 27000-27300 with the default source option, and the second is a new Custom UDP Rule for port range 27000-27300. Apply the rule changes. Now the game, and game clients can communicate via ports in that range.

You'll also want to set a static IP for your server so that it doesn't get changed. You can do this very easily by allocating an Elastic IP from the EC2 management console and associating it with your instance.

Part 4: Running the game server

Go back to your server and you can run the launcher for srcds and get this game going! The console output will let you know your public IP address, it's the same as the Elastic IP you just made, and the port number. When you have the server up, open Day of Defeat on your own computer, drop the developer console down and type connect xx.xx.xx.xx:xxxxx and replace the xx's with your IP and port number. You should soon find yourself in a game hosted on your very own EC2 server! Tell your friends the server address and enjoy the ensuing battle!

Note, this guide will work with for any of the Source games - Half-Life, Day Of Defeat, Counter-Strike and Team Fortress 2. Good luck out there!



Follow Me

This is a DJ mix I put together a few years ago with Ableton Live and features a few of my favourite old records. I still like listening to it so here it is if you're so inclined.




Hello World
I've been working through Udacity's CS253 - Web Application course, taught by Steve Huffman (Reddit) using Python and Google App Engine.

We covered many topics including HTML basics, HTTP requests and responses, forms, input validation, escaping HTML, persistence, authentication, cookies, hashing, rendering and parsing XML and JSON, SOAP web services, scalability and caching! We also looked at various python libraries such as jinja2 (templating), memcache (db caching) and minidom (xml).

This website is the result! I'll be working on adding more features and showing off a few of my projects in the coming months.


queried 0 seconds ago