Competition Programming

The art of know all the required tricks, and just “getting” the problem, and writing the solution. I have so much to learn.

I entered TopCoder SRM 258, and end with a zero score for the second time. But this time at least I submitted a problem that I thought worked. My score is was not too affect this time and I’m still in Division I. I plan to turn the slope of this graph around.

The first problem was calculating the interest rate given the start price, monthly payment and number of months. I’ve done a lot of self discovery in the finance area driving by our (Michaela and me) desire to purchasing a house. The problem reminded me of my book of formula’s so much I couldn’t get over it and just write a program to solve this problem. So after the event was over last night I worked on it. I almost had it solved correctly, but the way I was generating the correct interest rate was ugly (it just required a binary search due to the limit of 0% to 100% stated in the problem) and the exit conditions. The latter was a bigger issue. The problem stated 1e-9 precision, so I comparing the money owning at the end of the term to 1e-9 not the interest rate. So using the binary search also solves that problem.

The second problem was a compression problem. The problem that got my code rejected was a challenge of “ASD”. Although the problem stated the input was from 1 to 50, I had thought that the two compression keys needed to be unique, thus my inner loop would not use the same key as the outer loop. There was also a problem where my inner loop was from 0 to n-1 not n as it should have been. But looking at other peoples solutions I worked out that one correct way was to use Dynamic Programming, which I had been reading about that morning. So failing to spot the change to use it make me feel a little silly, but boy, from now on, DP is going to be on my check list.

The third problem was a really hard DP problem. Work out the probability of each play (1-4) winning a game of snakes and ladders (though they used a different name). That just messed with my head. But the people that did get it had very compressed but elegant solutions. Another learning opportunity.

Anyway the first two problems were opened, read, coded, tested in 5 minutes by the best people, so I’m just thinking they really grok there comp sci algorithm courses.

TopCoder - Single Round Match 257

Well, I just completed the TopCoder SRM 257, and I didn’t even get one problem solved.

The first problem was find the minimum error ( difference ) for a weighted average.
You used 5 weights, with a sum 1.0, that last bit (sum of 1.0) I forgot, so spent the whole time trying to workout why my result was different from the example. Also the run time was too long for the bigger dataset. Not till coding phase was over and I started reading other people solutions did I see my error. GRRRR. So I’m not sure how badly it will affect my ranking, but I’m think its going to hurt. Maybe I’ll get put into the second division, which will be easier, but not as much fun as playing with the big boys in Div I.

So tonight instead of doing game development, I’m going to solve the other two problems that I didn’t even start.

Programming Challenges

Was reading Marks July 15 post, and remembered about my Programming Challenges time. Back in November 2004 I found the site, and start solving the problems. I shared the site with the people at ATR and some internal competition started. The site also had a phpBB attached, where people would ask questions and nobody would answer. So I decided to be the person that at lest acknowledge the persons question even if I did not know the answer. Most questions could be answered by repeating the answer given the day before. I am not sure if it was the new user base that just didn’t understand the concept of search before ask. The more annoying thing was there were problems with the problems, like solutions that worked on the bigger UVA site. The sites phpBB was pulled done earlier this year due to it been hacked, and has not been replaced. The site admins never answered any questions, so it would appear to just be a pretty version of the UVA site, to help sell their book. I’ll admit the site gave you the error output when you code fails to compile which UVA does not. The small problem set also makes the site less intimidating.

While the phpBB was still active I was discussing the above problems another coder, who suggested TopCoder, describing it as having good feedback, and the chance to win money. So I promptly signed up there and never did anything about it.

So last week I entered my first algorithm competition, man it was fun. It was a session sponsored by the NSA, so they had a few people in the chat room for an hour before the competition. The competition it’s self was fun. The third problem was simpler than I first thought so I wasted a lot of time thinking I couldn’t do it. Then added extra code that wasn’t needed. So now I’m in Division I, and the problems look a lot hard. You start in Division II when you are unranked. I’m keen to compete in the next competition that happens in my time zone on the 8th. This one has cash prizes, but I’m not expecting to get any. Here the my TopCoder profile in case you feeling competitive ATR people.

Curse of the Azure Bonds Project

So I thought I’d write a little about my current development project. It is a port to the .Net platform of the SSI classic “Curse of the Azure Bonds” (which I refer to as coab, but I guess there really should be a t in there). This project started in February of this year when I decided to work on Coab instead of Pool of Radiance (the first in the SSI AD&D series).

So I used the ever trusty IDA Pro from Hex Rays to open the game up, but like a lot of games from this period, the game was compress/encrypted. I got bored of trying to manual decode it, so I used the very helpful debug.exe to decode the game for me. After single stepping through the decompression code a few times, I wanted to dump the ram image of the game. I could not workout the syntax for the write to file command, so I dumped memory to screen. Dump to screen would only do 64K sections, so I needed to change the DI register. This ended up been done by altering the code about to be executed to alter the DI register as required. I wrote all the required commands into a text file so I could redirect this into debugger, and redirect the output to a file. This then gave me an ASCII file of the memory dump. I wrote a C++ program to parse the file and write a bin file. I then loaded this into IDA using the same offset as the original program was loaded at by debug.exe.

One of the things I’d noticed in all this was the way debug.exe loaded the game (16 bit DOS) was different to how IDA loads it. IDA loaded it verbatim and debug.exe removed one byte and altered the next.

Anyway with the uncompressed image now in IDA, I spent a week rebuilding the segment table that the game used. I then found my IDA scripts I had written back in 2000 while working on Pool of Radiance and used them to load the overlay file, and correctly re-write the jump tables etc. The first problem I found was that the scripts that I had were not the last version I had developed when working on PoR due to back-up issues, so I spent a week rewriting the scripts. I also fine tuned how they did there work. Once I did that I started to decode the functions, but soon noticed the library functions were all unmarked due to the flirt engine not have been run. So I load the original decoded bin file again and found out how to force the flirt engine to run. I saved off the changes. Somewhere in there I either applied the changes to the work in progress, or just started again with the flirt version, ether way, I started making progress on decoding the game.

This carried on for about a month in total, when I noticed that even though I’d dump 192K of the decoded game memory, I only had ~70K of it in IDA, I then double check the dump procedure, and the ASCII to bin program. In the end the problem lay in ASCII to bin program as I’d put a limit in there for testing (~4000 lines) that was stopping parsing before the end of file was reached. So I re-parsed the ASCII file. Then I wrote a IDA script to import the missing file at the correct point, and extend the segments to deal with it. The original problem was that the data segment was half missing. With this resolved more of data look-ups in the code made sense.

Another month passed, and I now had a pretty good understanding of the game structures used by the game. The biggest problems were the verbosity of the assembly code. So around May I start writing a C# program to translate the assembly code into C#. The first thing I did was create files from the segments. There were about 50 memory segments in the game due to the overlay memory management system. Then I got function blocks parsed and correct C# replacements. I then worked on parsing the parameters, and local variables. All the rest of the assembly was written in as comments.

At this time there was\ ~110K lines of assembly to translate. I started from scratch a few times due to errors in the translator, but I ended up getting good at writing Visual Studio regex to match the asm. In reality the fact the original game was un-optimised Pascal was quite nice. Structure access and assignments are done the same each and every time. The one thing that is very annoying about it been Pascal based is the base 1 arrays. Because the global data segment would have a single address used as a byte, and as a word array, and you need to sort the two usage’s out. This is one place IDA is (or I should say was as I’m using a older version) not to great at.

It is now August and there are only 24,485 lines of assembly left in the code. There are ~2.5K errors to deal with, mainly steaming from parameter mismatch, and C#’s overly picky maths rules. But it’s a work in progress. I’m really enjoying working on it.

IMGUI Design

I’ve been reading Book of Hook for a while now, and a few weeks ago on the Game Development forum he posted a link to his friends site Molly Rocket where Casey had a cool video of his immediate mode graphical user interface. Having been spending the last few weeks bashing me head against gotcha’s in RMGUI’s (.Net Winforms) I could see the value in building UI’s this way. Not for apps like we have here at work, but for real-time stuff it makes a lot of sense. So anyway, it helped me by putting some names to idea’s that were in my head, and describe different ways of doing stuff. It also allowed to see area’s where our current code could have issues, due to the nature of the UI model.

All-in-all very much the classic way stuff was done in the old days before windows, but cool to pull it back off the self to see where it’s still applicable to modem development.

New Blog - Yeah!

Created this blog to write and share thoughts and ideas, the plan is to write up the stuff I’ve been doing on MD5 but not completed, and track progress on my “Curse of the Azure Bond” port. And just track things that I’ve been reading and find interesting.