Update to Assignment 1

I kept thinking about the assignment and found the negative weight search problem so interesting that I went back and spent another hour or so on it. I now have a full solution to the standard and both bonus assignments that includes solutions for graphs with negative weights.

Main fixes

1. Fixed an error in my implementation of the Bellman-Ford algorithm. I misread the bounds of the inner loop: I thought it looped through all the edges in the current node, but rather, it loops through all the edges of the entire graph. I was able to simplify the code considerably once I realized my error.
2. I also realized that for the bonus questions, any negative weight node can be used in a cycle, and this will break the Bellman-Ford algorithm. For example:
1. Input is: 
2. "B1"
3. "3 3 1,1 2,3"
4. "1 -10 2"
5. "5 2 -1"
6. "2 1 3"
7. There is a cycle between nodes (1,2), and (2, 3). The Bellman-Ford algorithm cannot handle this case.
3. To solve this challenge, I implemented a brute force exhaustive search that tries searching all nodes to all nodes recursively. This is not elegant but solves the problem quickly enough for small data sets. My solution is more of a proof of concept than anything and could use some heavy optimization. The best way to do this would be to profile the code, and see where the hotspots are.
4. Fixed a potential array index out of bounds error when inputting start and end nodes.

The code is available here.

Shortest Path Assignment

The first part of the assignment works as specified, including negative weights.

For the bonus, I ran into a bug where in some cases the shortest path is not found when using negative weights. A valid path is found, but it is not always the shortest. Given more time, I could definitely figure this out, but I have reached the deadline. Please see my Bonus1GraphTest.TestNegativeSearch() for a failing test.

To use:

1. Download the zip file from here: http://ninjagreg.slashdothost.com/assignment1/CylindricalMatrix.zip

2. Extract the zip file

3. The app and unit test source code is in the CylindricalMatrix and CMTests folders, respectively.

4. The code is in C#.

Design:

I originally intended to write this assignment using Dijkstra's algorithm to compute the shortest path in the matrix, until I realized negative weights were valid; I therefore switched to the Bellman-Ford algorithm because it can work with negative weights. To model the graph search problem, I created a graph, node and edge classes.

The general workflow is: 

The InputParser parses the input, and returns a matrix, and start and end nodes. A graph is then created from the matrix, and the shortest path is computed. The results are output to the user.

• The InputParser class reads input from any TextReader stream. The TextReader stream can be stdin, for user input, or a mocked stdin to aid in testing and debuggin.
• The Matrix class I modeled after the Data Transfer Object (DTO) pattern. Future programmers may want to search for the shortest path using a non-graph algorithm, therefore I thought it best to keep the Matrix class "dumb" and only use it to be passed to other modules.
• The graph classes do the meat of the assignment including the transform of matrix to graph, and searching.
• There is a BaseGraph class that has default graph building and searching functionality.
• The StandardGraph class is derived off  BaseGraph and implements features specific to the Standard portion of the assignment, such as there being no start or end row defined.
• Bonus1Graph is derived off BaseGraph and extends the graph building functionality to search in all cardinal directions.
• Bonus2Graph is derived off Bonus1Graph to implement "torus" wrapping.

Enjoy!

Pong++

I started working on this project Sunday afternoon and finished Monday evening. It's the old arcade classic Pong, with a few extra twists!

Use the mouse to control your paddle.

Players can either be computer-controller (CPU) or controlled by you (Human).

Source code is here: http://ninjagreg.slashdothost.com/pong/



It was a fun little project, and most importantly it was a project I finished.

I used the Model-View-Controller pattern when creating it:

1. Paddles and Balls each have a model class, with basic data properties. Like radius, or width. These classes are derived off event dispatcher so that a "data changed" event can be sent when ever a property changes.
2. I created a PaddleView and BallView class, derived off of Sprite, to visually represent the model class. These Views can only be created by passing a model into their constructor. The View listens to the Models "data changed" event and updates their view correspondingly when something changes.
3. Finally we have a PaddleController and ModelController. These must be instantiated by passing a view into the contructor, or through a factory function which creates a model and view for the controller automatically. The Controller listens to events sent from the View, like UI events, and interprets what to do with them. In the case of the ball, the controller is responsible for adjusting the ball's path as it hits corners and paddles. The PaddleController controls the paddle's direction and AI.

The AI is very basic. It finds the ball with the closest current position and moves along the y-axis to match the ball's position. There is a slight heuristic so that the paddle favors balls that are closer to it along the horizontal axis, as the paddle can move quicker up and down rather than waiting for the ball to come to it. In the future I would like to have the paddle move toward the future position of the ball (based on its current angle and speed) rather than the present position of the ball.

Enjoy! I appreciate any feedback.

To actually finish a project

If you're anything like me you start many projects but rarely if ever finish them. That's why the latest project I've started is ridiculously simple, and I can actually complete it in a reasonable time. The project is the 30+ year-old video game Pong.

I created it in flash. It took about eight hours to complete.

I will upload it as soon as I figure out how.

Editting blog posts on the iphone is brutal BTW. I wonder if there's an app for that?