Jamie's Blog

Last weekend I had a few hours to spare, so I decided to work on one of the problems from CodeSprint2, InterviewStreet’s contest to find the best programming talent.

Since I didn’t have long to work, I decided to try to complete the algorithm problem with the highest value. I chose to work on Count Strings (closed now). Given a regular expression, and a string length N, count the number of distinct strings of length N which the regular expression can match.

I looked at the sample test case, spent some time thinking about the problem and decided to try it. Although bounds for test cases were provided, I gave them only a cursory glance. This would turn out to be a mistake.

In my daily work, I typically focus on getting things working rather than spending time on determining the optimal way to do things. It is with this mindset that I decided that I would actually enumerate every string that a regular expression could produce, and then count them. I failed even before I began.

The regular expression language was limited to the alphabet {a, b}, with operators star, union, and concatenation.

I decided to use Haskell, which has the terseness of Ruby or Python, but the performance and type checking of a compiled language. I created a data type to represent the regular expressions. Recursive data types made this representation very straightforward.

data RegularExpression = Symbol Char
  | Concat RegularExpression RegularExpression
  | Union RegularExpression RegularExpression
  | Star RegularExpression
  deriving (Show, Eq)

I had the enumeration part complete fairly quickly. Pattern matching makes everything really intuitive and readable. The star operation required the most code.

listPossibilities (Symbol c) limit
  | limit > 0 = [c]
  | otherwise = []

listPossibilities (Concat r1 r2) limit = combos where
  o1 = listPossibilities r1 limit
  o2 = listPossibilities r2 limit
  combos = [ a ++ b | a <- o1, b <- o2, length (a++b) <= limit ]

listPossibilities (Union r1 r2) limit = possibilities where
  o1 = listPossibilities r1 limit
  o2 = listPossibilities r2 limit
  possibilities = o1 ++ o2

listPossibilities (Star _) 0 = [""]
listPossibilities (Star r1) limit = possibilities where
  opt = listPossibilities r1 limit
  possibilities = "": whileLimit opt limit optSet
  optSet = Set.fromList opt 

  -- | Uses nub right now, really inefficient. probably should use some sort of memoization
  whileLimit :: [String] -> Int -> [String] -> [String]
  whileLimit base lim acc = pos where
    new = List.nub [a++b | a <- base, b <- acc, length (a++b) <= lim]
    pos = if null new || length new < length acc then acc
          else whileLimit base lim (List.nub $ acc ++ new)

The next component I needed was a parser to convert input into these regular expression objects. I used the Parsec parser module to construct the parser. This part actually took a bit longer, as I tried to refine the parser to accept deeply nested expressions.

The regular expression union parser below parses a parenthesized expression or symbol, followed by a pipe, and another parenthesized expression or symbol, returning a RegularExpression object.

reUnion :: GenParser Char st RegularExpression
reUnion = do
  re1 <- pexpr <|> reSymbol
  char '|'
  re2 <- pexpr <|> reSymbol
  return (Union re1 re2)

Once I got the parser working, I glued it together with the enumeration portion, and submitted it to the contest. It immediately failed to compiled due to a dependency on Test.HUnit I had in my code. I reorganized the code so that I could easily remove this dependency, and resubmitted.

This time, it took, but when I went back after a few minutes to check the submission status, it had failed all but 1 of the test cases. It had taken too much time! I went back to the submission guidelines and noted that there was a time limit of 5 minutes.

Originally, I had used an algorithm which enumerated by checking distinctness using a List type. I knew at the time that this was very inefficient, but I focused on finishing the implementation at the time. I went back to this part and used a Set instead. I was optimistic that this would fix my problems and I would be able to knockout at least another test case.

I resubmitted and I failed 10 tests again. Then, I reread the problem, and looks at the boundaries for N. N could be up to 100,000 (IIRC)! Of course enumeration (especially the way I was doing it which would enumerate many strings of less than length N) would fail–I had taken a totally incorrect approach to this problem. I did not need to enumerate–I only needed to give a number of potential strings. This could’ve been done without enumeration. For example, given the expression a*, and a number N, there is only 1 possibility. Given . For example, one of the test cases was , which has 32 possibilities. Another of the expressions was . Since b can only appear once, the possible strings include strings of   a’s and a single b. There are N such combinations (the number of positions b can be in, in an N length string): baa…, aba…, aab…, … . This is the approach I should’ve taken.

I left the solution there, and acknowledged my defeat. Source here: https://github.com/jamiely/count-strings

My employer gives us a week off for the holidays, so I’d been trying to decide what to do with all of the time. Although I originally didn’t want to work on any programming projects, I wound up working on a few. One of them was inspired by a play of the iOS game Train Yard. I was paying particular attention to the loading screen when I noticed it had been created using Cocos2d. I’d seen articles about the engine before, so I decided to take another look at the Website. I was curious about what other game engines were in popular use. Besides Unity, I didn’t notice any that were more popular than Cocos2d. I decided to investigate further and found a tutorial on the site.

Before I knew it, I was working through the tutorial. The API was simple, straight-forward, and intuitive, and I was soon done. Still, I wanted to use it for my own project. Unfortunately, the holidays were winding down, and Spring term classes will start soon, so time is very limited.

As a prepubescent child, I played a shareware game where balloons would rise on the screen. You’d use your mouse to draw a bowstring, flying an arrow horizontally through the balloon field, timing the ascent of a balloon. It’s this game that immediately came to mind when I tried to think of simple games. The satisfaction of that balloon popping noise made me long to play. (A satisfaction only outpaced by the sound of popping bubble-wrap.)

So, I decided to work on a game like that other game, and started on making balloons float up. I went to http://openclipart.org and found a great balloon-popping sound at http://soundbible.com. I started out by using CCActions, a CCSequence composed of CCMoveUp and CCCallFuncND to perform cleanup. The balloons would randomly spawn at a certain interval below the screen, and rise to a height above the screen, out of the viewport, and be removed from the layer.

Somewhere along the line, I decided that an bow and arrow would be unnecessary, and that touching a balloon would be enough to pop it. At the same time, I’d target the game at children. I implemented procedures to detect a balloon touch, show a particle effect upon touch, play the popping noise, and remove the balloon from the layer immediately.

Play-testing confirmed this mechanic was a little boring in of itself. I figured that popping balloons should release things stored inside, so you should be able to earn points for popping balloons and touching a “treasure item” dropped from the balloon, things like: diamonds, coins, and treasure boxes. I also added clouds in the background, a timer, and score display, the concept of rounds, and a game over state.

I got this working, but it didn’t seem especially targeted towards children. Lisa, my wife, tried it and confirmed as much. We talked about marking each balloon with a letter, and using the balloons to spell words or elsewise learn about words.

After thinking for a bit, I decided that balloons marked with a letter would release a word starting with that letter. When you touched the word dropped by a balloon, that word would be spoken aloud. I downloaded Audacity, and had Lisa recite a list of words. I spliced them and loaded them into my project Resources folder. Once I got the code working, so that the word sound would play when the word was touched, the audio seemed to low, like it had not been normalized. Even after reducing the volume of the background music and popping sound, the words weren’t loud enough. We’ll have to redo the word sounds at some point.

At this point, I’m mostly done, but may add some more graphics and clean up the code. This project has been a great introduction to Cocos2D and Objective-C programming, in general.

Check out game footage below and the complete source code, including assets, on Github: http://github.com/jamiely/ios-balloon-burst

For our final project for CIS552: Advanced Programming, my partner and I implemented a poetry parser. The program identifies a body of text piped from STDIN as one of: haiku, rhyming poem (aba, or aabba), sonnet, or limerick.

The project source is located at: https://github.com/jamiely/poetry-parser.

The project involved using the CMU Pronouncing Dictionary found here, creating parsers for the dictionary, and base parsers that could be combined for various forms.

For example, we implemented a parser for syllables that allows us to create a haiku parser.

-- | Parses a Haiku
haiku :: PoemParser RhymeMap
haiku = do
  ns 5
  ns 7
  ns 5
  return Map.empty where
  ns = nSyllables

and a rhyming scheme parser that allowed us to recognize limericks:

aabba :: PoemParser RhymeMap
aabba = rhymeScheme "aabba" Map.empty 

-- | The stress pattern of a limerick
-- note: syllable requirement is implicit
limerickStress :: PoemParser RhymeMap
limerickStress = do
  stressLine [D,U, D,D,U, D,D,U]
  stressLine [D,U, D,D,U, D,D,U]
  stressLine [D,U, D,D,U]
  stressLine [D,U, D,D,U]
  stressLine [D,U, D,D,U, D,D,U] 

limerick :: PoemParser RhymeMap
limerick = limerickStress <&> aabba

For example, we can determine the type of the following poem:

An old silent pond…
A frog jumps into the pond,
splash! Silence again.
- Basho

by running the program thusly:

> ./Main < extra/basho.haiku

with the result:

Opened file
Poem:
An old silent pond...
A frog jumps into the pond,
splash! Silence again.

Dictionary: 

A  AH0
AGAIN  AH0 G EH1 N
AN  AE1 N
FROG  F R AA1 G
INTO  IH0 N T UW1
JUMPS  JH AH1 M P S
OLD  OW1 L D
POND  P AA1 N D
POND'S  P AA1 N D Z
SILENCE  S AY1 L AH0 N S
SILENT  S AY1 L AH0 N T
SPLASH  S P L AE1 SH
THE  DH AH0

Type: Haiku

And the following poem:

something something fox
apple jacks
word here pox

by running the program thusly:

> ./Main < extra/fox.rhyming

with the result:

Opened file
Poem:
something something fox
apple jacks
word here pox

Dictionary: 

APPLE  AE1 P AH0 L
FOX  F AA1 K S
HERE  HH IY1 R
JACKS  JH AE1 K S
POX  P AA1 K S
SOMETHING  S AH1 M TH IH0 NG
WORD  W ER1 D

Type: Rhyming poem: aba

I tried setting up Rubygame on Snow Leopard this time last year. I had many difficulties setting up SDL. I had some time to kill so I tried to set it up again, this time on my new MacBook Air running Lion.

This old blog post from 2005 helped me this time around: http://inquirylabs.com/blog2005/?p=21 to nail down the requirements. Instead of following the installation instructions here, I used Homebrew to set things up.

One of the key requirements is rubysdl, ruby bindings for the SDL multimedia library, and the rsdl gem. The following Gist is a rubysdl Homebrew formula that will help install the required packages: https://gist.github.com/1394440. The SGE formula is not part of the included formulas. I forked the following Gist to provide SGE: https://gist.github.com/1394414/.

# install the sge graphics lib
wget https://gist.github.com/raw/1394414/4a6bfa4a8bab179ebe263b1d044a4322c7628f60/sge.rb
brew install sge

# install rubysdl ruby sdl bindings
wget https://raw.github.com/gist/1394440/8a71160306ad277f08fbad3eaf028b2e8700f2f1/rubysdl.rb
brew install rubysdl

# install the required gem
gem install rsdl
gem install rubygame

Afterwards, most of the rubygame samples ran fine, but the ones requiring opengl had issues. I installed ruby 1.9.2 using rbenv, compiled a new dynamic library libruby.dylib, based on the 1.9.2 source. Then, I cloned this repo providing an upgraded ruby-opengl gem: https://github.com/theymaybecoders/ruby-opengl.

# clone the repo
git clone https://github.com/theymaybecoders/ruby-opengl
cd ruby-opengl

# make sure that the libruby.1.9.1.dylib compiled from the
# ruby 1.9.2 source is present in the gcc class path. For
# me, it was ~/.rbenv/versions/1.9.2-p290/lib/libruby.dylib
# use build option --enable-shared

rake

# build the gem
rake gem

# install the gem
gem install pkg/ruby-opengl-0.60.1.gem

Afterwards, the rubygame opengl samples compiled fine.

I’ve only been taking one class this semester. It’s an advanced programming course focusing on the functional language Haskell. While I was familiar with some functional concepts such as map, fold, and currying from using Javascript, and lazy-evaluation from dabbling with Clojure, this class has introduced a number of new, intriguing concepts.

Not necessarily a functional feature, pattern matching in Haskell is an incredible feature that has really come to make a lot of sense to me. Given a type constructor with two definitions:

-- Given the type below
data Shape = Rectangle Float Float Float Float | Circle Float Float Float

area :: Shape -> Float
-- We can pattern match below, to change the defn depending on the constructor
area (Rectangle x1 y1 x2 y2) = (y1 - y2) * (x1 - x2) :: Float
-- Use _ to discard matches
area (Circle _ _ radius) = pi * radius * radius

In Haskell, tuples are a basic data type. You can pattern match to unpack a tuple, like this:

tmp = (1, (2, (3, 4)))

unpackTmp1 :: (Int, (Int, (Int, Int)))
unpackTmp1 (_, (_, rtn)) = rtn
unpackTmp1 tmp
-- rtn = (3,4)

unpackTmp2 :: (Int, (Int, (Int, Int)))
unpackTmp2 (_, (_, (_, rtn))) = rtn
unpackTmp2 tmp
-- rtn = 4

So, pattern is something really new to me that I haven’t seen in other languages before. It makes dealing with tuples easy, and you can also use it with lists:

x = [1..10]
secondItem (_:i:_) = i
secondItem x
-- returns 2

thirdItem (_:_:i:_) = i
thirdItem x
-- return 3

tail' (_:rest) = rest
tail' x
-- returns [2..10]

Intro

For the last assignment for CIS564, we created a simple tag/hide-and-seek game using path-finding, and the behavioral steering from the last assignment.

A*

A* (A-star) is a path-finding algorithm which finds an optimal path between two nodes given a cost function which yields the distance from the start and a good heuristic estimating the distance to the goal. The game field is divided into a grid of 1600 squares. Each square is marked as open or obstructed, based on the presence of a mushroom obstacle. Obstacles may be placed dynamically by holding ALT and LEFT-clicking with the mouse. In Path-finding mode, Lenguins will plan a path around the mushrooms to the target.

Mushroom obstacle

The algorithm was implemented in C++ and compiled in XCode to a OSX Bundle for use with Unity. I turned out to be the only one to work on OSX. Since a Visual Studio project was required, I ported the code over to Windows after I was sure it worked. I’ve noticed interesting differences in the way the code works in OSX versus Windows–or it could be a difference in compilation between XCode and Visual Studio. For example, I was using a route where I subsampled a list of vectors that represented an agent path. I had something like:

std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
    int i = 0;
    for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ++it) {
        if(i % factor == 0) {
			    path.remove(*it);
        }
        i++;
    }
    return path;
}

This seemed to work fine on OSX, but Windows threw a fit. Unity would immediately crash when I ran the game. I traced the problem to this function and a little investigation shed some light on the matter. When you call remove, it invalidates the iterator–makes sense. So I changed the code to the following:

std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
    int i = 0;
    for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ) {
        if(i % factor == 0) {
			it = path.erase(it);
        }
		else {
			++it;
		}
        i++;
    }
    return path;
}

Freeze Tag

Clicking the “Hide & Seek” button will enable the Freeze Tag mode.

Game Options

You control a player and may select various camera control schemes.

Camera Modes

The AI-controlled Lenguin agents head towards various hiding spots placed on the map. New hiding spots may be placed using SHIFT + LEFT-click. They appear as blue spots on the map. Each Lenguin will head towards the nearest hiding spot. Once a Lenguin reaches a hiding spot, it will claim that spot, and other Lenguins which were seeking that spot will acquire a new target. The process repeats while there are empty hiding spots.

When the player comes into an agent’s line of sight, the agent will flee away from it. If the player is able to tag the agent, it freezes in place.

Frozen Lenguin

Non-frozen Lenguin agents will attempt to tag the closest frozen agent. If the tag happens, the Lenguin is unfrozen. The game ends when the player freezes all the agents. Then, the game restarts and play continues.

Game Field

Demo Video

Downloads

• Source – will be available someday, when I am done the program
• OSX Universal (13.1 MB)
• Win 32-bit (3.1 MB)

Progress Log

Here’s a progress log that I started but neglected to finish:

• Started work on A* algorithm  20100625 10:00 AM.
• A* code written but untested  1:00 PM.
• Difficulties debugging. An hour lost trying to setup some sort of debugging via Igloo.  3:00 PM.
• Formal debugging abandoned. A* code rewritten to be more clear using a AStarNode class 6:00 PM
• Started to test A* code with new class approach 6:00 PM
• Debugging slow and awkward. Results written to file. 8:00 PM
• Code finally works without sigaborts by eliminating pointer issues. More debugging. Logs seem to be increasing exponentially for some reason. 10:00 PM
• Debugging problem fixed. Stringstream used for debugging was not cleared each time it was used, resulting in exponential increase in log size. Lenguins move but in wrong direction. 11:30 PM
• In a stroke of insight, I try reversing the condition used in the priority queue (the A* open list). Things magically work after that. 20110626 12:30 AM
• More testing, creation of mazes, videos, showing path finding. Implemented code sent by TA to prevent agents stuck on obstacles. 2:00 AM
• Work started on camera and player actions 12:30 PM
• Issue with third-person control resolved by raising player slightly above map. Issue with camera enabling resolves player control with perspective camera. Mario-style camera hooked up to player. 2:15 PM
• Got freeze behavior working along with some game mechanics. There are some issues with collisions. 3:45 PM
• And then I stopped keeping track…

My most recent assignment for the Game Design class I’m taking is to implement some behavioral animation steering behaviors. The task was to implement steering behaviors such as: seek, flee, separation, avoid, follow the leader, and flocking.

We were provided a framework featuring Lenguin characters

A gaggle of lenguins

and a menu like this:

The in-game menu to choose steering behaviors

and entry points to call a C++ dll that would return force and torque vectors given agent properties and world data. It was a really interesting exercise, and it’s always tricky and fun implementing algorithms. One of the more difficult ones was the avoid behavior, which allows agents to go around obstacles

Lenguins avoiding obstacles while seeking

This is done by detecting a collision with an object, and adding a tangential velocity to the agent’s current velocity, allowing it to walk around an object, hugging its radius. This was both an exercise in implementing algorithms and using Unity’s native plugin capability. Although the Framework was provided for Visual Studio, it was fairly straightforward to port it to XCode, and Unity allows OSX users to compile native plugins into Bundles.

One of the weirdest things I found is when I went to port my XCode c++ back to Visual Studio, I was getting crazy velocities back. It took me a couple hours to discover that the default constructors for the vec3 structures, which store the values in a float array, did not initialize the array values. It’s odd because this worked fine on XCode/OSX, and I’m wondering if XCode did something special with the array values, like initialize them to 0.

Here’s a short video of the Lenguins in action:

Here are links to executables if you’re interesting in trying yourself. Use ctrl-click to move the target, and click on the Behavior menu to change the behavior.

• OSX Universal (12.7 MB)
• Win 32-bit (3.1 MB)

I don’t have much time for a post, so I just wanted to post an assignment I completed for CIS 564 – Game Design, which was to implement a classic game using the Unity Game Engine. Source is available upon request, and here’s a link to the a web version (Unity Player is required). It uses cfxr for the 8-bit sounds, and I did a little bit of modeling in Maya. The scripting was done using C# in MonoDevelop, which had a really nice interface. Unity was a pleasure to use.

If you’d like to try it on your own machine, here are some native binaries:

• OSX Universal (11.7MB)
• Win 32-bit (3.1MB)

The second semester is over, and with that I am almost 1/3 of the way complete my Master’s degree in CS. I won’t lie, even though I only had one class, it’s been a difficult semester. Theory of Computation has kicked my ass all over the place, despite frequently attending office hours, and spending huge amounts of time on the homework. Even though I was excited about getting back into theory, after long stints working on the most practical of problems in my daily work, I feel as if I was ill-prepared. Undergraduate lessons in automata, mathematics, and compiler theory helped ease the difficulty, but this was new territory. Indeed, the professor commented that this was the first semester of a new direction for the course, focusing more on complexity than automata than in previous semesters. Despite the difficulty, the class was fascinating, and, if nothing else, has given me new reasons to feel humble.

Final Exam Rage

• Sir Ken Robinson discusses the diversity of human talent and the need for a revolution in learning http://bit.ly/irNqnO #