The Accountant

The Accountant Official Trailer #1 (2016) - Ben Affleck Movie HD
I've been working on a programming problem / puzzle over at Codingame the last couple of weeks. The puzzle is called The Accountant, and it looks like they've managed a marketing tie-in with the movie. I mean, I hadn't heard of the movie until I started working on the puzzle.

The puzzle involves developing a search & destroy algorithm for Ben, excuse me, Wolff, to use to eliminate all enemy combatants without getting killed himself. As with many puzzles at Codingame there are several test cases. They start out relatively simple and easy to solve, but they get progressively more complex and correspondingly more difficult to survive.

I'm guesstimating that I only spent about eight hours actually working on my program, that is, actually sitting down at the keyboard and typing, but I spent untold hours thinking about it, and who knows how many CPU cycles my subconscious spent ruminating on it.

My first pass at the problem involved simple locating the closest bad guy and issuing a SHOOT command. That worked for about the first third of the tests, but now we have more bad guys and sometimes you need to run away for a bit to get some breathing room. Fortunately, actor (my name for the variable representing actor Ben Affleck's position on the field) can run twice as fast as the bad guys. Not surprising since he is a strong, physically fit American who is totally focused on his mission. These qualities are missing from the typical bad guy, at least in Hollywood, and likewise in this computer simulation of Hollywood.

But where do you run to? How do you figure out which area is safest? Well, you could use brute force, and simply calculate the distance from every point on the map to every enemy agent. But that could get expensive in terms of time and CPU cycles. There are roughly 150 million locations on our field and there could be a zillion enemy agents. You run a calculation like that and you could get shot while waiting for the computation to finish. Actually, the master computer would simply cancel you and your program because you exceeded your allocated time.

Computers have gotten much faster than when I first ran into that time limit thing. It could be that the master computer could actually make all those calculations in the allotted time, especially since there never any more than 100 bad guys on the field at any one time.

My early training in Computer Science instilled in me a desire to minimize CPU cycles, so I spent some time thinking about ways to reduce this HUGE problem into something manageable, trying to come up with strategies for mapping concentrations of bad guys and open, safe areas, and then trying to come up with a way to represent these ideas. I never came up with one I liked, which means that they all looked like a great deal of work. And there is no way of telling whether they would work or not without actually writing the code and trying them.

In the end I decided on a simplified brute force solution. I used the eight cardinal compass directions to locate eight points 1000 feet away (which is how far Ben can run in one turn, which I figure is about two minutes in real time), and then computed the distance from each of these points to each of the enemy agents. That brings the problem down from 15 billion computations to 800. And that was enough to pass all the tests.

Sark and the Master Control Program from Tron

I'm sure there are whiz kids out there who have developed very elaborate strategies for optimizing their total scores, but I'm lazy. I got the job done with simplest means I could find. Maybe I'll get a T-shirt, though if the master computer over at Codingame gets wind of this post, that will probably get canceled as well.