programming contest: success

[nibot]

Date: Sun, 25 Sep 2005 16:52:33 -0700
From: Paul Hilfinger
To: tobin at csua dot berkeley dot edu
Subject: Congratulations!

Congratulations on your fine performance in Saturday's programming contest. Alas, you have both indicated to me that you do not meet the eligibility requirements for the ACM contests, so I can't put you on our teams this year, much as I'd like to. Still, I hope you enjoyed yourselves and have a pleasant semester.

Paul Hilfinger

Comments

[nibot.livejournal.com]

I answered the following problems (linked to my solutions):

3. permutation puzzle (http://splorg.org:8080/people/tobin/projects/ctest/contest/Berkeley/2005/3.cc)
6. lisp expressions to bruijn form (http://splorg.org:8080/people/tobin/projects/ctest/contest/Berkeley/2005/6.cc)
8. how many steps on the diagonal ladder thing (http://splorg.org:8080/people/tobin/projects/ctest/contest/Berkeley/2005/8.cc) (trivial)

Nothing too fancy. I would have liked to have solved number two, the binary xor inversion problem.

I think I spent about three hours on it.

[nibot.livejournal.com]

The permutation puzzle was solved with a backtracking search.
The lisp expressions thing involved a little parser and then simple recursive tree printing.
The diagonal ladder thing just required a little math.

I first solved the diagonal one by implementing the function to get the linear coordinate recursively; that failed because a test case in the contest uses a high-numbered coordinate which caused stack overflow. A few minutes tinkering yielded the closed form expression for the coordinate.

[nibot.livejournal.com]

Do you have any ideas how to solve numbers 2 or 7?

[nibot.livejournal.com]

actually, a better url is:

http://splorg.org:8080/people/tobin/projects/contest/Berkeley/

i am not sure what I did with 2003-2004.