Competitions
Since I haven’t had much to post about as of late, I’ll provide you with an update of what I’ve been doing lately:
UPE Programming Competition
From 2-5:30 PM today I participated in the UPE Programming Competition sponsored by Morgan Stanley and hosted by the Rensselaer Student Chapter of the Association for Computing Machinery. The competition consisted of 9 puzzles for participants to solve using C, C++, or Java.
Here’s a .zip of the problems, along with example inputs and outputs, grading code, and solutions. My solutions aren’t particularly well-written, so I’m not going to post them here.
I solved four puzzles and took home first place, which was a $1,000 Amazon gift certificate. The puzzles I solved were:
account (submitted 3:12:45)
Given a list of users’ last names, this puzzle required you to generate logins for a system such that each login name was the shortest unique substring of the name with an optional numeral afterwards.
maze (submitted 3:47:20)
Given a maze, output the path from the center to the exit. This consisted of parsing the input into a data structure, locating the exit, then running a pathfinding routine.
pool (submitted 4:29:02)
Given the (x, y) coordinates of a ball on a pool table along with its vertical and horizontal velocities, determine which rails the ball will collide with and which pocket it ends up in. This required a bit of algebra to solve. I worked it out mostly on paper before coding up a solution.
symtab (submitted 5:25:08)
Given a list of strings, find the shortest combination such that each input string is found in the output, and print their indices in the output string. This took me the least amount of time to solve, but the timestamp is almost an hour after pool — I implemented it very quickly, then thought a recursive solution would find a more optimal output. After wrestling with ostringstream for a while, I finally got it to work — but it exceeded the 30 second time limit. I had to spend a few minutes longer backpedaling to my iterative solution.
Information Security Talent Search 6
On March 28 and 29, my computer security team, RPISEC, participated in ISTS6 hosted by RIT. The team, consisting of Alex Radocea, Henry Filgueiras, Rob Escriva, and myself, took third place and each of us brought home a 4 GB Cruzer Professional flash drive.
The competition consisted of 5 hours of setting up a server and three attack computers. The server had to run a variety of services for the other teams to attack, such as FTP and SMTP. Points were awarded for keeping your services up or knocking your opponents’ services down. (I contacted one of the organizers for our score but they have not replied.)
I previously participated in the iCTF wargame. Other members of RPISEC participated in Polytechnic University’s CSAW 2007 wargame and took 4th place and earned the distinction of “Best Undergraduate Team.”
April 13th, 2008 at 1:59 pm
What kind of pool table has balls moving “vertically?”
Maybe I misunderstand “symtab”, but isn’t it just an implementation of “IndexOf” (in Javascript terms)? Is there a programming library out there that doesn’t already have that built in?
April 13th, 2008 at 3:27 pm
One of the examples included forming a symbol table out of
watermelon#,melon#, andhoneydew#(where#represents a NULL byte). The shortest concatenation of these is eitherwatermelon#honeydew#orhoneydew#watermelon#; becausemelon#is contained inwatermelon#, there’s no point in including it twice.After you have strung them together into the symbol table, it becomes a very simple
IndexOf()problem. I used STL, so it was just callingstring::find()for each of the inputs.April 14th, 2008 at 8:24 pm
$1,000 ought to be enough for anybody.
April 15th, 2008 at 6:10 pm
Don’t go near my server.