https://community.topcoder.com/stat?c=problem_statement&pm=203&rd=53
This is quite straightforward - you have to scan every row, column and diagonal range on the board and detect if you can surround a contiguous line of your opponent's pieces on both sides by placing your next piece and capture them. Each set of captured pieces becomes your piece and they can cause further cascading captures until there are no more capture situations on the board
You have to find the move that captures the maximum number of pieces.
The obvious way to do it (as many solutions do) is to scan the board using for() loops - To me this seemed a terribly ugly way of doing this.
We're trying to find a pattern like RBBBBBBR along any straight line of the board. If it were only in the horizontal direction we can do this cleanly with just two calls to adjacent_find().
However we need to handle eight different directions not just the horizontal ones.
So I decided that a 2d iterator would be interesting to write.
2D iterator
Usually, iterators are a subtype of a container, but here we're not going to do that, since we can't extend vector and so on.
Instead we create a class that holds a reference/pointer to its container - in our case a vector<vector<T>>
STL iterators have a lot of properties and are written in a consistent way, since they all work on linear one dimensional sequences. They move in two directions at most.
Our requirements are different:
- We want the iterator to be able to move in any of the eight directions
- We want to have the bare minimum of operations implemented and a couple of extras
The basic operations we need:
- Ability to set a direction
- Copy constructible
- *, >, ==, != and pre-increment operators (post increment is not useful enough)
Extras:
- bool operator to check if an iterator is not at the end.
- A function to get a successor to an iterator without mutating it.
- a distance() function - I could not get std::distance() to work right with my iterator. Needs some studying
Full implementation
The code is not brilliant and some corners are cut, but it does the job.
Some points to note:
- Coordinates and increments are simple pair<int, int>
- We predefine the eight directions
- We have to store a pointer to the container we refer to, so we can refer to its contents.
- The increment operator clamps to the first out of bounds co-ordinate
- Whatever extra boilerplate the STL needs is borrowed from std::vector
- Our end iterator is created from another iterator, not from the container as is usually done, since our iterator has a direction
The way its used is - you construct an iterator passing in a vector of vectors, a coordinate, and a direction. You construct an end of range iterator in turn from that. Now you can treat the two iterators like any other ones you have seen.
Once we have this 2d iterator class, the original problem becomes almost trivial to solve
Full implementation
The algorithm is as follows:
- We place a piece tentatively on the board on an empty position
- We look for any captures - on every column, on every row, every primary and secondary diagonal
- If anything was captured, repeat the above step because we may have cascading captures
- If we had no captures, count how many total pieces we have after
- Repeat this entire process for every empty position on the board and see what is the maximum count we can get.
apply() calls applyOne() eight times, each time passing a co-ordinate and two directions - The two directions are the primary and secondary axis to scan - For example we'd scan each column by starting at each point on the first row and going downwards.
applyOne() is extremely simple since we can use the STL
- We need to find a pattern like 100000001 on the board along the secondary axis starting at each point on the primary axis (our representation uses 1 for our piece and 0 for the opponents)
- Call adjacent_find to see if there is a 1,0
- Call adjacent_find on that result to find an 0,1 - the fun part is that if the previous call had not succeeded, it would have returned the end() iterator, so this call will do nothing. We don't have to do any messy and error prone special casing.
- Now we have two iterators one that points to an 1,0 and another to a 0,1
- If both are valid, we count how many 0s exist between the two surrounding 1s
- If that count is equal to the distance between the two iterators, everything between the 1s was a 0 and thus we have a capture
- If we have a capture, just fill that captured range with 1
It looks like a lot of work to write an iterator just for this problem, but we made our code simple and error free - just imagine the nightmare of writing several loops, each which has multiple conditions. Maybe some people are so smart they can juggle all that in their head. Personally, I'd let the compiler handle it.
Some of the solutions in the practice room are horrendously verbose. A typo would be fatal for such code.
It turns out that the 1000 point problem in this room is a similar problem involving a 2d game board. Having this iterator code made that problem trivial to solve - in fact it turned out even simpler than this one!
Use the abstraction Luke!
No comments:
Post a Comment