Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

I’m ornery; I finished two programming challenges last night, I think, but the UVa judge has been offline for a while with database issues, and the banner keeps getting updated to say “it’ll be fixed sometime after tomorrow.” Free beer tomorrow!

This isn’t particularly surprising, since the UVa website is junk (longstanding cookie bug that the site maintainers fail to acknowledge, slow, disorganized, disconnected, LAMP, Joomla). LAMP sucks, especially if you’re trying to use some massive off the shelf CMS system, and do anything useful with it. Especially if it’s open sores and written by a bunch of ass clowns. Sometimes it’s better just to roll your own.

For the astute, yes, I am a hypocrite. You win! This website is on LAMP, implemented using an off the shelf CMS system (sort of, though it’s not “massive”), and also sucks. On the other hand, I’m not trying to coerce Textpattern into doing anything other than what it was designed to do, and as such it mostly works. It will crumble if I ever get significant traffic.

Anyhow, since UVa is probably gone forever at this rate (they’re recommending using their old website), I had to attempt to use the book judge instead, which is of course slow and limited to begin with. With the increased traffic due to the UVa judge being dead, it’s … not judging anything. Maybe I’m wrong about the roll your own thing too. As such, while I think my last two submissions are complete, and they pass all of the test cases in the forum, they have not yet been judged correct by an official judge. I’ll try to remember to come back and do this at some point.

10247 – Complete Tree Labeling

This problem won the game, and I decided to give up. I can’t get a workable recurrence or solution that looks even close, and have decided that I should embrace failure. I’ll return to it once I finish the rest of the book. Once I gave up, I got some better ideas about how to approach it, so I don’t think it will be too bad the second time around.

10264 – The Priest Mathematician

Needed the ego boost after the last one. Looked into the discussion of the hanoi puzzle at Wolfram’s Math World (I’ve seen and solved the problem/recurrence before, but wanted to see what the clever kids say about it). They point out that the four-rod minimal solution is defined by Reve’s puzzle (Sloane’s A007664). In my mind, it made sense that the optimal solution using a fourth peg is to … solve optimally the four peg puzzle. So, I implemented the recurrence listed by the cool math kids, submitted it, and waited; the UVa judge queue was backed up for some reason, so I didn’t get to find out if I’d succeeded. As I was thinking about it, I realized I didn’t, due to some flawed assumptions about the size of the result space. So, I recoded things, and figured I had a good solution, and then returned to waiting to see if I won the game. While waiting, I reflected that I really hate Java, but it does have mature BigInteger support, and that’s handy, versus C++ (at least in the context of the UVa judge not including BigInteger support of any sort, and I not being competent enough to code a super-duper-fast version). My solution is in Java, as mentioned, so it’s ugly. It computes the entire solution space in about .7 seconds without doing any “hard math” or recursion, so it’s relatively quick.

10049 – Self-Describing Sequence

Yay, back to c++. Sloane’s integer sequences made this one easy in theory, though the approximate solution was too approximate, and the recursive solution was too recursive. Using an interval array though, it was easy to bootstrap and binary search the solution space; my solution (-warning: not judged yet- AC) is fast enough, but not particularly elegant. There might be a better way. Yay, wasting memory!

846 – Steps

This one wasn’t too bad, once I understood the problem, which was slightly difficult, since “One steps through the integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous” meant nothing to me. I sketched out the first dozen steps, implemented (-warning: not judged yet- AC) the formula from Sloane’s, and all was well.

And that’s chapter six, beyond that I skipped a problem and haven’t tested the other two. On to number theory!

Update: Judge is now fixed, last two solutions are AC.