Programming Contest

This year's problems for the ICPC:
http://www.acmgnyr.org/year2009/problems.shtml

SVN Part 2

Now that we can log in automatically (SVN Part 1), we can do some cool stuff. This summer I managed a SVN server for a company that has multiple programs, each of which had different developers working on them. Each of these programs is stored as a repository in SVN. For example, developer A needs access to repository 1 and 2 and developer B needs access to repository 1 and 3, etc. To make it even trickier, in repository 1, developer A should have access to the entire repository, while developer B should only have access to the directory devB in repository 1. Also, every time a developer makes a change to a file, the change needs to be logged with their username.

This is where the RSA keys come in. Each repository should be owned by a different user. For example, /usr/bin/svnserver/repository1 is owned by user repo1, /usr/bin/svnserver/repository2 by repo2, etc. Put any developer who needs access to [repo]'s RSA pubkey in the /home/[repo]/.ssh/authorized_keys file, where [repo] is the name of the repository's owner (repo1, repo2). Configure authorized_keys like:

command="/usr/bin/svnserve -t -r /var/svn/ --tunnel-user=[developer's username]",no-port-forwarding,no-pty,no-agent-forwarding,no-X11-forwarding ssh-rsa [developer's RSA pubkey]== [developer's username]

This enables developers to check out [repository] using: svn+ssh://[repo]@[server]/[repository]. While we are sending the information over SSH, the developer does not have a SSH account and can do nothing but use SVN to check out (svn co) and update (svn ci) repositories owned by a user (repo1, repo2) whose authorized_keys file contains the developer's pubkey. The last column in the authorized_keys file is the comment line. SVN automatically uses this line as the comment when a developer commits code to the SVN repository.

The last part, giving only partial access to a repository, coming in Part 3.

SVN Part 1

Subversion is another awesome piece of software for keeping files in sync across multiple computers. Not quite suited for backing up pictures or anything like that -- but hey, its great for big coding projects! Usually with big projects, there are different levels of access. For example, Bob's algorithm may be super secret and only he and Bill should be able to see the code for it. But, Barry may be logging in to the same SVN server and need access to other code. There's an app for that. I mean, there's a feature for that. Also, perhaps not everyone should have access to the server's file, or even an account on the server. Well, there's a feature for that, too. Anyway, here's the procedure/setup I came up with after lots of research/trial-and-(hopefully not catastrophic) error.

Make sure at least YOU can ssh into the server (or better yet, be sitting in front of it and skip the next few steps). Its handy to use an RSA key so you can log in automatically and don't have to type your password every time you want to execute a subversion command. So:

sh-keygen -t rsa

will generate you a key. Then:

rsync -a ~/.ssh/id_rsa.pub server:~/.ssh/

Before we switch over to the server, if you're using a non-standard port, in /etc/ssh/ssh_config, add:

Host [server]
Port [port #]
Host * [this line should be there already, it just tells you where to put the 2 preceeding lines]

Next, ssh over to the server and:

cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys
rm ~/.ssh/id_rsa.pub

The >> instead of just > puts the key at the END of the file instead of overwriting, so if you already have a computer set up in your authorized_keys file, this will preserve that setup.

Now you should be able to log in with no password using ssh [server].

Part 2 coming soon! :P

Testing my feed to Drupal

http://drupal.org/handbook/customization/tutorials/beginners-cookbook

Looks very powerful, easy to use and cool! And best of all, its GPL'd.

http://maxsobell.com/drupal/

http://pingv.com/videos/1/what-drupal-57-seconds

Kmeds Algo

This is the final project for a bioinformatics class I took last semester:

http://err.bio.nyu.edu/courses/index.php/V22.0480_Final_Project

I worked on Project 1. The goal was to find a scalable algorithm to cluster large data sets (something that couldn't all fit into memory) with arbitrary dimensions. We wrote a SQLite adapter to grab n data points at a time (based on k, the number of expected clusters), and then ran a clustering algorithm on those n points, storing the results in memory (if the data set was large enough to require it, we could write them back to the SQLite DB). After num.iter iterations, we run the algorithm again on the result set to get our final medoids. From there, its relatively easy to assign each point to a medoid, forming the final clusters.

rsync

The rsync utility is very cool. Its cool because its fast, effective and the syntax for the command is relatively simple. Its a great way for the uber-paranoid to avoid the Cloud. [Side note: if you are not uber-paranoid and do not mind the Cloud, check out Dropbox <-- shameless referral link. But you get extra space with that link, too! 2 GB -> 2.25 GB]

You can get rsync to do automatic, incremental backups for you, although I'm still working on that part. The best I have so far is to sync 1 or more computers with your server computer (I sync my computers at home using my dad's computer in San Francisco [static IP] as the server computer).

To do it (assuming the server is running an rsync deamon [more on that here], and your server name is in the /etc/hosts file), each computer (except for the server computer) needs 2 identical scripts. Mine are:


rsync \
--verbose \
--archive \
--compress \
--update \
coffee:~max/test1 ~/rsync/


and


rsync \
--verbose \
--archive \
--compress \
--update \
~/rsync/test1 coffee:~max/

This keeps the folder "test1" in my home directory on coffee (the server computer) and my ~/rsync directory on my home computers. The options are:
--verbose = tell me whats going on as its happening!
--archive = this is a cocktail of options: recurse into the directories, copy symlinks as symlinks and preserve permissions.
--compress = use compression to speed up the transmission, but use up more CPU
--update = don't overwrite newer files on the receiver (server) computer

The rest of the syntax is the same as a copy command. If you use a remote computer, preface its directory structure with the name of the computer followed by ":".

Another very very useful option when testing all this is --dry-run. rsync will go through all the steps it would have taken to make the sync without actually transferring any files. Especially useful if you use the --delete flag, which deletes files on the server computer that are no longer present on the source computer. Because of rsync's trailing slash issues, its easy to delete the contents of an entire directory with one wrong "/".

Here's a simple script if you're just using rsync to backup:

#!/bin/sh
BUNAME=$(date +%A)
rsync \
--verbose \
--archive \
--compress \
--update \
--backup \
--backup-dir=~max/$BUNAME/ \
~/rsync/test1/ coffee:~max/test1/


Because of the --backup and --backup-dir=... options, when rsync is going to change a file, it first makes a copy of the file to the directory specified by $BUNAME (which is defined as the day of the week i.e. Thursday) and then overwrites the file in the main directory (test1, in this case). This way, if you accidentally change a file you didn't mean to, you have backups of it. You could go so far as to make hourly directories within the day-of-the-week directories with some simple shell scripting...

Computer Science Showcase

Well, finals are almost over, but mid-week there was a Computer Science Showcase in the Courant building at NYU. Our Robotics class had a corner where the Rovios were playing soccer and the 3πs were following lines. My Rovio, someone else's 3π:

Adjusting the Rovio to run on the hardwood floors with the different lights was a challenge -- I had to change the coefficients for distance to ball and goal and the threshold for detecting the ball. The floor made it particularly challenging because the reflection of the lights is about the same color as the tennis ball (to the robot) and so sometimes it thinks the ball is somewhere its not. Add in human interference, as a bunch of us were jammed into a 9'x9' area, and it was chaos. Also, I added a victory dance at the end, thanks to a request in the comments.

This is someone's 3π -- I have my code for this, but its not as fast as this one. Wow. The 3π uses 5 infrared sensors on the front end, along with some C++ and a PID controller to follow the line.

Also, the professor just sent out an email; looks like our class was picked up here:
http://www.slashgear.com/wowwee-rovio-taught-to-play-soccer-0642907/
and here:
http://www.robocommunity.com/blog/entry/15953/Rovio-Learns-Soccer-Bends-it-
Like-Beckham/

Rovios face off.

Blurry 3π racer

Rovio works!

The point of the whole project is to get the ball into the goal.

The algorithm goes:

1. take a picture
2. convert it from RGB to YUV
3. mask out the ball and the posts into 2 separate matrices
4. find the ball
5. turn to it
6. rotate around the ball until you find the goal
7. shoot!

And if it were only 7 lines of code my life would have been much easier for the last little while ;) Here's all the code. And here's the Rovio in action:

Woot!

The next step is to clean up and compile the code to get it ready to play soccer against the other Rovios!

Back to the 3pi

It follows a line... stops... turns around... and goes back to where it started! Finally...

The code is here.


That outside line is for its next trick ;)

(Lisp) is mind-numbing

Well, not entirely Lisp... its actually (lush). But the parentheses... Oy. Thank god for Emacs paren highlighting. Here's the whole thing: robotest.lsh, but here's just a little sample of the beauty of (lush) syntax:

(setq len (* h (/ (- (* k f) y) (+ (* k y) f))))

Just like http://xkcd.com/224/ and http://xkcd.com/297/!

The whole point of this was to take in an image (top), mask out the color (bottom) by first eroding, to eliminate noise, and then dilating, to get back the origninal big blob of color (the eraser):

Then that formula (above) tells the robot how far the object is from it, based on how many pixels down the screen the middle of it is, how high off the ground the robot's lens is, and its focal point (-371). That distance formula took a whole classroom a while to figure out....

This is for a Rovio robot (which is controlled over wifi), and that picture was taken from the robot.