Adding Rebounds and Turnovers to Super Shot Search

Todo:

1. Integrate the new SQL query for turnovers and rebounds into existing Super Shot Search SQL (SSSSQL). (30 minutes)
2. Display the filtered data on my Super Shot Search (SSS) web site. (20 minutes)
3. If I get that done in a reasonable time, look into getting the rebound data for all teams in tabular form with a quick query. (30 minutes)
4. If that gets done, add a UI for it on SSS.
5. Ignore twitter.
6. Don't spend more time blogging than coding.

Integrating

I just opened up my usual MySql IDE, MySql Workbench, but then remembered there's a much nicer IDE called HeidiSQL which has table and field auto-completion which should really be a standard for any IDE. So let's install that. (Took 2 minutes to install and configure and run...sweet) Oh cool HeidiSQL even shows the size on disk of the tables in your schemas. Wicked....Looking at the code and I should have commented which is the working piece of code and a data set to compare it too...I'm running some of these queries and they are taking a long time which makes me think I need a new computer...So I think I have a working query but I need to compare it to a game...so opening up a play-by-play, and I'll compare my calculated results with what's on paper. Well I couldn't believe there were no rebounds in this game for Toronto, but I checked  the play by play and there were none. Now checking Buffalo's..they have exactly 1 rebound. Well, that's a large enough sample size to check :).

Rebound times for all teams

This was more interesting to me than adding the UI, so I did this yet. First, a note on performance. I went from a query that was wrong, and took 55 s, to a correct query that took 4 s, to an even better query that takes a half of a second, to a query for all teams that takes 51 seconds (performance will be better on a production database). The obvious clue I missed when designing the query was you just have to check the play immediately before a short or goal: if that play was a shot, and the time is less than 3 seconds, that is a rebound.

What teams got the most rebounds last season?

Rebounds	Team
146	Colorado Avalanche
143	San Jose Sharks
140	Philadelphia Flyers
138	Carolina Hurricanes
128	Los Angeles Kings
122	St. Louis Blues
117	Phoenix Coyotes
114	Calgary Flames
114	New Jersey Devils
112	Pittsburgh Penguins
111	New York Islanders
105	Montreal Canadiens
103	Florida Panthers
103	New York Rangers
102	Chicago Blackhawks
99	Winnipeg Jets
94	Minnesota Wild
94	Boston Bruins
93	Ottawa Senators
93	Columbus Blue Jackets
92	Buffalo Sabres
86	Tampa Bay Lightning
84	Nashville Predators
83	Anaheim Ducks
79	Washington Capitals
77	Edmonton Oilers
76	Vancouver Canucks
74	Dallas Stars
72	Toronto Maple Leafs
71	Detroit Red Wings

I don't see much correlation between good teams and getting rebounds...That's all for tonight.

Not on schedule at all

I basically spent a bunch of time messing around with crap I told myself not to mess around with, namely graphics, setting up a virtual server using Windows Azure, playing with that, setting up a local server, exposing that server to the internet, and so forth.

But, here's some things I have decided:

• All the backend work will be done in c#, because fuck php. If I need to pay for a host that will server up .net mvc or webservices, so be it. I'll just do all the development locally anyhow.
• I'll use a MySql database.
• That's as far as I've gotten here.

Tomorrow I might actually write some code!

EDIT: Turns out my host supports Django but it's a bitch to set up: http://www.calebmadrigal.com/django-on-hostmonster/

Was thinking of learning python/django, and that would be useful, but I also just want to get this going as quick as possible. So fuck it, php? I have no idea.

Wasting time

So I just spent an hour or more doing various things, none of which were productive:

• Tried to see if my theninjagreg.com was running and if not, why not
• Wasn't running so attempted to log in to 1and1.com's control panel
• It wasn't accepted my username and password and not even the reset password dealy worked
• Called 1and1 and realized it's because they don't support Chrome, wtf
• Looked into actually paying for a server that would run .Net apps (I love .net btw)
• Looked into installing mono on the server I get free hosting on
• Blah blah blah I wasted time I should have spent coding.

I really like .net, that's what I code in at work, but the free hosting I have is a LAMP server, so I guess I'll stick with php for now.

Game of Thrones Video Board Game of Thrones Game

I'm a big fan of Game of Thrones (read all the books twice, watched all the seasons twice), I'm a big fan of global domination games like Risk and Diplomacy, and I'm a medium fan of programming stuff. So I want to put all these things together and create an easy to play online Game of Thrones game.

I know that HBO is working on a MMORPG version of GOT, but I have no interest in that kind of game.

I've started and failed to complete many computer games in the past, and the hardest thing for me on any game is the graphics. So rather than spend hours and hours trying to make things look nice, I'll just get the server side end done well enough and throw together a crappy UI for the time being.

One goal achieved

Back flip.

Now I guess the hard part will be working up the courage to do it on grass, wood, concrete...

2011

Some things I did in 2011.

Here's a video of me doing a front tuck on grass.

Back tuck on trampoline

Me dead lifting 315 pounds, and a great shot of my ass. I don't have a video of the 365 pound one.

Reflective Serializer for C#

Reflection would have been a nice feature to have when I was writing MFC C++ back in the day. Anyways, here's an easy way to auto serialize a class. Just have it derive from this class:


    public class ReflectiveSerializer : ISerializable
    {
        public ReflectiveSerializer()
        {
        }


        protected ReflectiveSerializer(SerializationInfo info, StreamingContext context)
        {           
            Type t = GetType();
            foreach (FieldInfo fi in t.GetFields())
            {
                fi.SetValue(this, info.GetValue(fi.Name, fi.FieldType));
            }
        }


        public void GetObjectData(SerializationInfo info, StreamingContext context)
        {            
            Type t = GetType();
            foreach (FieldInfo fi in t.GetFields())
            {
                object o = fi.GetValue(this);
                info.AddValue(fi.Name, fi.GetValue(this));
            }
        }
    }


And then add this constructor to the class:


        protected MyClass(SerializationInfo info, StreamingContext context) : base(info, context)
        {
        }


That class gets called automatically when serializing. The class will then be automatically serialized, provided all of its members can be serialized.

Smoke some trees, yo

A tree is an acyclic graph where each node has one or zero parents and zero or more children.

Binary trees

Number of children is always two.

Ordered binary trees

All nodes left of a given node, n, are <= n; all nodes right of n are > n.

Traversal

Pre-order:

1. visit root
2. go left
3. go right

In-order:

1. go left
2. visit root
3. go right

Post-order:

1. go left
2. go right
3. visit root

Level-order (breadth first search) (needs a queue)

1. enqueue root in q
2. while q is not empty
1. n = q.dequeue()
2. visit n
3. if n.left, enqueue(n.left)
4. if n.right, enqueue(n.right)

Note: changing the queue above to a stack will result in pre-order search (also have to swap the order of 2.3 and 2.4)

Of course, rather than using recursion, you can replace the call stack with an actual stack, and then mark the nodes as visited or not.

Sorting? Awesome fun for whole family

Bubble sort is dumb. Let's look at quick sort and merge sort.

Quick sort:

• O(nlogn) best and average.
• Worst case is O(n^2)
• divide and conquer mother fucker
• probably not stable (same keys may change order)
• pick a pivot, p, in the array (usually in the middle)
• partition into two arrays, one with all values <= p, the other with all values >= p
• the partition step can be done in place
• call quicksort on the two arrays
• if the array size is zero, you're done

template  void qs2 (vector&; arr, int left, int right)
{
 if (left >= right)
  return;

 int i = left, j = right;

    int pivot = arr[(left + right) / 2];
     
    while (i <= j) {
        while (arr[i] < pivot)
                i++;
        while (arr[j] > pivot)
                j--;
        if (i <= j) {
  swap(arr[i], arr[j]);
                i++;
                j--;
        }  
    };

 qs2(arr, left, i - 1);
 qs2(arr, i + 1, right);
}

Now let's try some mergesort:

• worst case is O(nlogn)
• better for using slower data access things like files, tape drives
• don't have to store everything in memory

template  void mergeSort (vector& v)
{
 if (v.size() < 2) return;
 // first divide in two, until only size 1 left
 int n = v.size(); 
 int middle = n / 2;
 vector left;
 left.insert(left.begin(), v.begin(), v.begin() + middle);

 vector right;
 right.insert(right.begin(), v.begin() + middle, v.end());

 mergeSort(left);
 mergeSort(right);

 v.clear();

 // then reconstitute such that the new result is in order
 while (left.size() > 0 || right.size() > 0)
 {
  if (left.size() > 0 && right.size() > 0)
  {
   if (left[0] <= right[0])
   {
    v.push_back(left.front());
    left.erase(left.begin());
   }
   else
   {
    v.push_back(right.front());
    right.erase(right.begin());
   }
  }
  else if (left.size() > 0)
  {
   v.insert(v.end(), left.begin(), left.end());
   left.clear();
  }
  else if (right.size() > 0)
  {
   v.insert(v.end(), right.begin(), right.end());
   right.clear();
  }
 }
}

Studying: Day Two

When we last left off I was working on stacks. I'm gonna implement it with a linked list by deriving off my linked list class. On the way I am also going to change the class to use generics. It turns out it's super easy to create generic classes in Java:

class LinkedListNode 
{
    public LinkedListNode(T newData)
    {
        data = newData;
    }

    LinkedListNode next = null;
    T data; 
};

public class LinkedList  {
// etc
};

I'm told that generics in Java are sorta bad because they use type erasure. This is when the compiler "erases" the types of generic classes, so it's compatible with any old non-generic classes. This means if a class has type T, you cannot reference T anywhere in your code, like you could with C++ templates. In fact, the other day one of my coworkers was complaining that they have to duplicate code that creates a new class of a generic type just for this reason.

public class Stack  extends LinkedList 
{
    public Stack()
    {
        super();
    }

    public void push(LinkedListNode node)
    {
        node.next = _root;
        _root = node;        
    }

    public LinkedListNode pop()
    {
        LinkedListNode ret = _root;
        _root = _root.next;

        return ret;
    }
} 

and then a queue is trivial:

public class Queue  extends LinkedList
{
    public void enqueue (LinkedListNode node)
    {
        insert(node);
    }

    public LinkedListNode dequeue ()
    {
        LinkedListNode ret = _root;
        _root = _root.next;
        return ret;
    }
}

Study time

In preparation for an interview I have with a certain Mountain View, California software company, I am reviewing and practicing all the basic data structures and algorithms that I learned in second year. I will be live-blogging this. Excited yet? Fuck ya.

Linked list: 

Probably the simplest data structure. Used for lists of shit.

The basic structure is a node (in Java) with a pointer reference to its next node.

class LinkedListNode
{
    public LinkedListNode(String text)
    {
        data = text;
    }

    LinkedListNode next = null;
    String data; // or whatever interesting thing the list holds
};

Some design considerations:

• Should there be a LinkedList class to perform insert/delete/retrieve operations, or should the LinkedListNode do these itself? 
• Probably makes more sense from an OOP perspective to have a separate class absract these ops, so I will write that.
• I should be recording how long I am spending on this. So far it's been at least 15 minutes.
• Apparently I don't know Java that well because I've already fucked up how Java copies references, and had a typo and shit...
• Forgot to update the previous node's next node after deleting
• I forgot to update the root after deleting the root node
• Forgot case where deleting the tail...wait no that's handled automatically
• A lot (all) of these functions could have been written recursively, whatever.

public class LinkedList {
    LinkedListNode _root = null;

    public void insert(LinkedListNode node)
    {
        LinkedListNode current = _root;
        if (_root == null)
        {
            _root = node;
            return;
        }

        while (current != null && current.next != null)
        {
            current = current.next;
        }

        current.next = node;        
    }

    public LinkedListNode find(String data)
    {
        LinkedListNode found = _root;
        while (found != null && !found.data.equals(data))
        {
            found = found.next;
        }
        return found;
    }

// Version 1. delete using 1 extra pointer    public void delete1(String data)
    {        
        LinkedListNode found = _root;
        LinkedListNode prev = null;
        while (found != null && !found.data.equals(data))
        {
            prev = found;
            found = found.next;
        }
        if (found != null)
        {
            if (prev != null)
            {
                prev.next = found.next;
            }
            else
            {
                _root = found.next;
            }

        }
    }

// Version 2. delete without using 1 extra pointer    public void delete2(String data)
    {
        LinkedListNode found = _root;
        // special case where the head is what we're looking for
        if (found.data.equals(data))
        {
            _root = found.next;
            //delete( found); (if we were using c/++)
            return;
        }
        while (found != null)
        {
            if (found.next != null && found.next.data.equals(data))
            {
                found.next = found.next.next;
                //delete( found); (if we were using c/++)
                break;
            }
            found = found.next;
        }
    }
}

Insert: O(n). Access: O(n). Delete: O(n). Some variants are double-linked list (where nodes point back to their next and previous nodes, and circular, where the head points to the tail.

A popular interview question is to reverse a linked list. Here goes:

public void reverse()
    {        
        reverseEx(_root, null);
    }

    private void reverseEx(LinkedListNode node, LinkedListNode prev)
    {
        if (node.next != null)
        {
            reverseEx(node.next, node);
        }
        else
        {
            _root = node;
        }
        node.next = prev;
    }

The above took me a long time, and you can do it without recursion. For some reason I wasn't thinking about doing it moving forward in the list:

public void reverse2()
   {
        LinkedListNode current = _root;
        LinkedListNode prev = null;
        LinkedListNode next = null; // this is necessary, at first I thought it wasn't, i'm retarded

        while (current != null)
        {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }        

        _root = prev; // i fucked this up, previously I had _root = current, but at this point, current == null. but then again, I just wrote it then debuged it...hopefully i would read it over a couple times in an interview!
    }

Stacks


Stacks are the basic LIFO structure. You can create them with any data structure you like, but typically arrays or linked lists are used. The array implementation was obvious to me:

#define MAXSIZE 2

template  
class Stack
{
 int _size;
 int _allocated;
 t* _data;

public:
 Stack::Stack() : _size(0), _data(new t[MAXSIZE]), _allocated(MAXSIZE)
 {    
 }

 t pop()
 {
  if (_size < 1)
  {
   throw new exception("stack underflow");
  }
  return _data[--_size];
 }

 void push(t d)
 {
  if (_allocated <= _size)
  {
   _allocated += MAXSIZE;
   t* newData = new t[_allocated];
   memcpy(newData, _data, sizeof(t) * _size);
   delete _data;
   _data = newData;
  }

  _data[_size++] = d;
 }

 Stack::~Stack()
 {
  delete [] _data;
 }
};

• I wanted to try having dynamic memory for some reason, that could grow past whatever, to test I set the maxsize to 2 which is obviously way low
• also wanted to  use templates
• when using a template function, it's just template  <class t> void MyFunction(){..}
• but when using a template class, it's template <class t> class MyClass {...}
• also I played around with std::stuff, I can't believe Fekete doesn't use it! MFC sucks compared to it.

So of course you can also create a stack with linked list:

For tomorrow:

Linked lists stacks, queues, priority queues, trees, sorting! Basic shit motherfucker.

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?