Fun with Graphs

According to BoingBoing, Metawebis getting 15 million in funding. So of course they are hiring. The applicant is required to answer a few questions, one of which is:

2. Imagine a graph that consists of directional links between nodes identified by small non-negative integers <> 2 succeeds, but inserting a second link 2 -> 1 would fail, since it would close the cycle 1 -> 2 -> 1.

In your favorite programming language, declare data structures to represent your graph, and give code for an "insert link" function that fails if a new link would close a cycle. What, roughly, is the space- and time-complexity of your solution?

I thought it sounded like fun:

class Node:
 def __init__(self,name):
   self._name = name
   self._adjNodes = {}

 def AddEdge(self,Node,EdgeVal):
   if not Node.FindNode(self):
     self._adjNodes[Node] = EdgeVal;
   else:
     print "Error: edge creates cycle. (%s to %s, weight: %s)"        % (self._name, Node._name, EdgeVal)
   
 def FindNode(self,Node):
   for k,v in self._adjNodes.iteritems():
     if k is Node or k.FindNode(Node):
       return True
   return False


# test it out.
n1 = Node("Node 1")
n2 = Node("Node 2")
n3 = Node("Node 3")
n4 = Node("Node 4")

n1.AddEdge(n4,10)  # Legal
n2.AddEdge(n3,20)  # Legal
n2.AddEdge(n1,30)  # Legal
n4.AddEdge(n3,40)  # Legal

n4.AddEdge(n2,50)  # Illegal
n3.AddEdge(n1,60)  # Illegal

n2.AddEdge(n4,70)  # Legal

# another example
b1 = Node("b1")
b2 = Node("b2")
b1.AddEdge(b2,10)
b2.AddEdge(b1,234)

Maybe if I find time to prove the space- & time-complexity, and finish the other questions I'll apply for an intership.

Go Game

Last weekend Dan and I programmed a working GO game in less than 24 hours for SpartaSoft.

We didn't finish the network gameplay, and any type of AI for Go is almost useless, but the basic rules/functionality is complete. Here is what it will do:

- Stones must have liberties (empty adjacent points) to remain on the board.

- Stones connected by lines are called chains, and share their liberties.

- When a stone or a chain of stones is surrounded by opponent stones, so that it has no more liberties, it is captured and removed from the board.

- If a stone has no liberties as soon as it is played, but simultaneously removes the last liberty from one or more of the opponent's chains, the opponent's chains are captured and the played stone is not.

- "Ko rule": A stone cannot be played on a particular point, if doing so would recreate the board position that existed after the same player's previous turn.

We build it in VS2005. It requires you have .NET 2.0 installed.

Download it here

saving any possible bits from this dying harddrive

Xamlon

I'm talking about Xamlon . Check out their website and dont forget to read this part:

Create WinForms applications in C# or VB .NET to deploy anywhere on the web via the Macromedia® Flash® Platform. No previous experience with Flash® is necessary to develop completely portable web-based applications!

That sounds pretty sweet and I intend to check out the software.

what up

first post!