Reverse Polish Notation

I came up with an algorithm to convert infix expressions to rpn at work the other day while trying to think about how to create and store logical expressions and upon not immediately finding any Ruby gems that do rpn conversions I decided to make it my FIRST EVER GEM omgroflbbq.

Anyway, it turned out my original idea of storing an insert point doesn't work when you have things like operator precedence, so I punted to wikipedia and found this:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

One hour later I had a fully speced gem covering converting simple algebra.

https://rubygems.org/gems/rpn-converter
https://github.com/kwstannard/rpn-converter

The tower defense

Let's say you are playing a tower defense with multiple lanes. This is going to be a simple tower defense with 3 lanes. Each lane sends out a baddie with a certain amount of health every second. In each lane you must put one tower. The baddies will be something like as follows:

Lane 1 - 250 health

Lane 2 - 150 health

Lane 3 - 50 health

You have several choices for towers. 3 of them deal a certain amount of dps, but can hit any lane. I will call these pool towers since they pool their damage. The 4th tower deals an infinite amount of dps, enough to kill any baddie, but can only deal damage in its lane. Let's say the towers are as follows:

Lava - infinite dps, 70 gold/second - its lane only 

Lightning - 400 dps, 155 gold/second - pool tower

Ordnance - 90 dps, 65 gold/second - pool tower

Plasma - 45 dps, 45 gold/second - pool tower

Conduit - 0 dps, 20 gold/second - pool tower

Now, the point of this tower defense is not just to survive, which would be easy, but to do so in the most cost efficient way possible, so while you might want to put down an infinite dps tower in every lane it probably isn't your best choice.

This is a simple problem and you probably already solved it. But, what if there was a million lanes? What if there was a restriction on the conduit towers so that you can only use one of them per lightning or plasma tower? What if there was even more towers that act like the lightning tower but with different prices and dps?

Here is the way that I solved this in O(nlog(n)) time. First you need to create a list of baddies sorted by health with lowest health first. This is the log(n) of the nlog(n). If the list is already given to your sorted, all the better.

Now place Lava towers on every lane and record the total cost somewhere and call it the cheapest known cost.

What we are going to do next is work our way down the lane list, replacing one lava tower at a time with a pool tower and keeping a running total of bad guy health and the total dps of the pool towers. If you can replace the lava tower with the cheapest available tower without the total bad guy health exceeding the pool dps then pick that, and if not then pick the most cost efficient pool tower.

In this simple example, this gives you the choice of either the conduit or the lightning towers. In a more complex game, the conduit tower might not be available due to restrictions and the cheapest possible tower to place might be a plasma.

After each tower replacement check the new total cost against the cheapest known cost. If it is cheaper then record the new cheapest known cost and keep moving down the list.

Eventually you will reach a point where adding a new lightning tower may not deal enough damage to maintain tower damage above the total baddie health. You are now done with trying to replace lava towers. Take the final cheapest known tower configuration, total damage, and total baddie health in lanes with pool towers and move on. In the simple example above you would end up with 2 conduits and a lightning for your towers, 400 damage, and 400 baddie health.

Your next step is to determine whether you can trade a lightning tower for an ordnance or maybe a plasma tower while still being able to kill all the baddies. If you can, then do so. In the example above this is not possible.

The final step is only needed if there was a restriction on the conduit towers and you might end up in a situation where you can replace two plasma towers for an ordnance and a conduit. If so then do that.

Congratulations, you now have the cheapest possible tower configuration.

Manual Quicksort

I was working in the warehouse yesterday and I was given the task of sorting a stack of about 150 order form papers alphabetically. So naturally as a budding computer programmer I decided to use quicksort, though I used my previous knowledge of the alphabet to pick good pivots instead of using the first paper. I recurred on the higher lettered stack in a split first so that A's would end up on top and also used a stack of stacks to hold paper stacks that I wasn't currently recurring on. I got it done in no time.

2d6 odds calculator

eclipse project, code, and executable jar file

This is something I whipped up in between posting resumés everywhere yesterday and today. It started on Friday night when I was playing some Settlers of Cataan with my friends and one of them remarked that it was incredibly unlikely that a 12 wasn't rolled more often over the course of the game and asked me what the odds of that happening were, so I wrote a quick program to calculate exactly that and it turned out that there is only a 75% chance of a 12 being rolled when rolling 50 times.

I hadn't done any programming in a few weeks since I was generally tired from my warehouse job so I decided that I wanted to flesh this thing out with a full GUI and multiple variables that you could input and get some more practice with making my GUIs more user friendly.

The cool things of note, beyond the calculation, is that I set up the text boxes with focus listeners that would automatically select the text in it. Then if a text box doesn't contain an integer the program will automatically shift to the offending box and a message will be displayed.

Edit: I was talking to my IT friend about the program and he was impressed by the fact that I was able to do the calculations using nothing but algebra, so I figured I should mention them here. As a physics major and CS minor, I have become pretty good at spotting patterns and I realized that the odds of rolling a number 'N' on 2d6 is equal to:

(6 - |N - 7|) / 36

Once you know that then you just need to set up the correct recursion and you are done.

Robot Game

Robot Project original code

 I went from only having experience in pseudocode to getting an A+ and winning a programming contest in my Introduction to Computer Science class, so the next semester I decided to kick it up a notch and do the honors version of the sebsequent class. This turned out to be great since we did some very interesting stuff including a few games like mine sweeper and a simple web style game and it was incredibly rewarding.

The final project took up the last 6 weeks of class and introduced things that we would use in the business world like Subversion, internet communication, and design specifications. The first 4 weeks was completely done according to design specs that would be given to us, and the final 2 weeks were for a few hard additions to the project and adding anything that we wanted for the end of semester competition.





The game itself is fairly simple: you have a robot that must navigate a board in order to pick up packages and then deliver them elsewhere, all of this must be done via an AI with no human intervention. In addition to this, your robot must communicate with a server, which maintains the game state, and tell the server what it is going to during it's turn.

Though the whole thing was fun, my baby in the project was creating a pathfinding algorithm using Dijkstra's algorithm, as opposed to the simple breadth first search that was assigned earlier in the project. While there was another two groups that used Djikstra, I managed to go a step further and added in the ability to see if doing nothing was the best possible move to make, which allowed our robot to dominate on boards that included conveyor belt tiles.

Overall it was a great project and I want to commend my partners Kevin and Anne for their awesome work and our professor Suzanne Menzel for being a great mentor.

Non-deterministic Finite State Automaton

FSA files

Today I am going to talk about my finite state automaton project that I did for my data structures class. I am pretty proud of this one since I started this class with no C++ experience and ended it by being the first person in my study group to get it finished. In case this is a recruiter reading this who doesn't know what an FSA does, http://en.wikipedia.org/wiki/Finite-state_machine

I started off by experimenting with how I wanted to handle the edges and nodes as constructs. Then I set about planning how I wanted the FSA to get constructed by writing up simple ones on a whiteboard and experimenting with connecting them. From that I decided I was going to work my way from a single accept node back to a single start node by creating simple FSAs and pointing the end nodes to the previously constructed FSA and the start node of the last FSA becomes the start node of the entire thing.

In order to actually run the FSA, I went with an input loop that first has a loop to fully explore all epsilon connections from a list of starting nodes, adding nodes with non-epsilon connections to a second list and then having a second loop to test each node in the second list for edges that match the next character.

I use breadth first search for both printing out a text representation of the FSA and for deleting it since in both situations depth first will lead to infinite loops. Deletion is done by first putting pointers to every node in a separate list and then traversing the list and deleting everything.

Graphical representation was done via third party program Graphviz.

 

Edit: Thanks to Gavin, Chris, Carlos, Julian, and everyone in the Burrow that helped me learn C++ despite having homework to do themselves.