December 18th, 2007
I've been doing very little on LJ these days -- apologies. It's not even work, really. It's other stuff killing my time.
Some personal junk -- mostly drama-inducing things I find myself not caring to post on LJ. I barely want to deal with them in real life.
I started playing Tokyo Extreme Racer Drift 2. It's forced me to write two scripts. One to sort car stats (power to weight ratio, mostly) and another one to run a variant of the traveling salesman problem
As you play the game, you can gather sponsors. When you win an organized race, you get money from your sponsors (in addition to prize money) for the stickers on your car. Each sticker is worth a different amount based on where it is on your car.
At the moment, I have 8 sponsors. There are 16 points on the car where a sticker can be applied. This can be treated as a 16 digit number in base 9 (until I get more sponsors anyway). More generally, an m bit number in base-n where m is the number of points on the car and n is the number of sponsors + 1. No digit can appear two or more times (except for 0). It seems like there should be a better algorithm than iterating through all the possibilities. The best optimization (assuming that all possible stickers will be in use) I've made cut down the range from 0-(9^17)-1 to around 6*10^6 to 1*10^15 for my current case.
I don't have an obvious, non-computationally-intensive way of detecting when two stickers from the same sponsor are used or detecting when all possible sponsors are used, so that removes that as a reasonable limit.
Last, but not least -- The Altair 8880 (the first personal computer) went on sale today in 1976. We've come quite a ways since then.
I just had a minor correction -- it's a 16 digit base-9 number. There are 16 points on the car to put a sticker and there are 8 sponsors. Sponsors have preferences for their sticker to be placed on certain parts of the car, so they'll pay differently.
On point 16, for example, the sponsor payouts go: 2000, 2000, 10000, 10000, 10000, 15000, 7000, 65000. These values change for each point on the car. Additionally, the prices don't vary the same way for given points. Some sponsors really like the rear window. Some really like the driver's door. The difference functions aren't similar at all.
It's tempting to go through point by point and select the largest payout, but it's pretty clear that doesn't find the optimum solution which is really what I'm after.
I hadn't considered a genetic algorithm, but I had considered the Monte Carlo approach which amounts to more or less the same thing. This is really just a point of intellectual curiousity -- I have a decent approximation that my brute force iteration hasn't beaten yet, but how could one find the best solution?
The criteria I have in mind are:
1) If there are more sponsors than points on the car, then each point must have a sticker.
2) If there are more points on the car than sponsors, then each sponsor must have a sticker on the car.
3) No two stickers can be from the same sponsor -- that's a precondition.
If I had a quick way of determining if:
1) there were any zeroes in the m digit, base-n representation of a number.
2) the same nonzero digit appeared twice in the m digit, base-n representation of a number.
...then I could speed this up significantly, but solving one of those takes long enough that I'm reasonably sure that I'm better off with stupidly calculating each one.
Because of the values I'm using, I really need to do this as a bignum implementation, so I've rolled my own simplistic one using a perl array and implementing my own carries. Because I have to look at each digit in the number, I've rolled the check for point 2 in using a lookup table which I reset for each iteration. It saves me some time, but the cost of the partial calculation isn't trivial.