Friday, October 7, 2011
Wednesday, September 14, 2011
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.
Sunday, September 11, 2011
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.
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.
Monday, September 5, 2011
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.
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.
Friday, May 13, 2011
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.
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.
Wednesday, May 11, 2011
Scheme: Image Altering
My code : image-altering.ss
IU scheme library : c211-lib.s
Occasionally I will decide I want to write image altering scheme methods.
Vortex is probably my favorite. Each pixel references a pixel a certain offset away on a radial line, the offset being governed by a quadratic equation that smoothly goes to zero at the edges.
Wave-sin fades in and out red, green, and blue based on a sin wave of the specified wavelength in pixels. I made this in 3 hours while I was waiting for a class.
I also did stuff for c211 including seam carving, image smoothing, and creating images whole cloth like this one I made to visualize power projection on a hexagonal grid when I was fleshing out plans for a Civ5 AI.
IU scheme library : c211-lib.s
Occasionally I will decide I want to write image altering scheme methods.
(vortex 150 5 (read-image "grid.gif"))
(wave-sin 40 (read-image "image.jpg))
Wave-sin fades in and out red, green, and blue based on a sin wave of the specified wavelength in pixels. I made this in 3 hours while I was waiting for a class.
I also did stuff for c211 including seam carving, image smoothing, and creating images whole cloth like this one I made to visualize power projection on a hexagonal grid when I was fleshing out plans for a Civ5 AI.
Subscribe to:
Posts (Atom)