Archive

Monthly Archives: October 2012

Often people shouldn’t reinvent the wheel, however in my learning at Hacker School I feel that for certain areas it is likely important to try and think up a solution for a well known (and most likely solved) problem and see what you come up with.

Today, I was thinking of a problem that would appear in a possible project that Sitong suggested. The project involved creating a type of “heat” map which would represent the minutes to a destination given walking and public transportation options. In mulling over this in my head it presented one of the classic problems in algorithms… the shortest path problem. I have little experience with algorithms so I thought this would be a great problem to come up with a personal solution before checking for the optimal solution. Hopefully my solution will turn out to be the optimal.

In this problem, you are given a graph with nodes and connections with values, in this case the values for the connections represent minutes of travel between each node. The nodes will represent travel options between two points on a map and the goal is to find the shortest path from an initial starting node and a chosen end node.

In my haze of sleep I began to think of solutions for a quick optimization of finding the shortest path and began to envision the graph node network as a net that is malleable. If one picks the starting node and ending node in each hand and stretches, the shortest path will appear as it will be the first path that can no longer stretch between the two hands (ignoring of course all physical tangling of the net). The problem I face is to quickly calculate the distance from every node on a map to another node, and if this act of “lifting” up the node from the net instantly reveals the shortest node it may be somehow translatable in code.

My currently train of thought brings me to trees. Given a graph network, it may be possible to translate that graph into a tree and stretch it out until you find the shortest path between the two nodes…

~ Hacking in Progress 😛 ~

After doing some reading and implementing Dijkstra’s algorithm in Ruby, I see the parallels of my visual thoughts and the mathematical explanations. Creating a even set of sub-nodes and traveling down all parallel paths until you hit nodes is analogous to lifting a net and having all connections lift off a table until node by node the solution appears. I find this connection between my thoughts and the derivation fascinating and really do wonder if there are other things out there that I could find novel solutions to. Looking forward to more late-night epiphanies and other sparks of inspiration!

Advertisements

Getting started with this book isn’t quite easy for someone who hasn’t worked too much in setting up a machine in these databases. I’m going to log my steps so that in the future people (or myself) can quickly reference my steps and see what worked for me!

Using Ubuntu 12.04

First step is to install the postgresql packages which comes in two pieces, the client and the dev package with the additional add-ons that the book requires:

sudo apt-get install postgresql-client
sudo apt-get install postgresql-contrib

Postgresql creates a postgres user which manages the server if you run it locally. Ideally you should create a user for yourself:

# Opens psql as the postgres superuser
sudo -u postgres psql
# Creates a user for yourself
createuser --superuser [user]
# Create a password for your user
\password 

Exit the psql dashboard and return to terminal. Now I can create and log into my server by using the psql command and install the extensions:

# Create DB
createdb book
# Open the newly created DB
psql book
# Install the extensions needed for the exercises in 7 Databases in 7 Days
create extension tablefunc
create extension dict_xsyn
create extension fuzzystrmatch
create extension pg_trgm
create extension tablefunc

Another link which was quite helpful for getting psql setup and running:
https://help.ubuntu.com/community/PostgreSQL