Friday, April 4, 2002

Problem Summary

These were easy problems, by semifinal standards. The easy problem, a Reverse-Polish-Notation calculator, is really just a measure of typing speed. The medium, a sort of Tic-Tac-Toe "AI", was relatively easy for a medium problem as well. The hard problem was nice and hard, however, with a brief and elegant solution that is only apparent after some thinking.

Value	200
Submission Rate	4/4 (100%)
Success Rate	4/4 (100%)
High Score	niteneb for 183.76 points

This is a very easy problem for a semifinal round. All one needs is a working implementation of a stack, which any language would come with. Or one could go without an explicit stack altogether, solving the problem recursively.

The process of evaluating an expression is fairly well described in the problem statement. We read the next token (separated conveniently by spaces). If it is a digit, we push that value onto the stack. Otherwise, it is an operation that we must apply to the top one or two elements of the stack.

Application of an operator is a simple switch statement (or something similar). Not all of the operators are commutative (order is important for the - operator), so it is important to make sure that operator is applied to the operands in the proper order. When subtracting, the top of the stack is subtracted from the value just below it.

All that is left at this point is error checking. It is easy enough to ensure that the stack is empty at the end of evaluation. It is marginally more difficult to make sure that the stack is non-empty every time a value is popped. The whole evaluation process could simply be surrounded by an exception handler, or one can just be careful about performing error checking at each point in the code where values from the stack are popped.

Value	500
Submission Rate	4/4 (100%)
Success Rate	4/4 (100%)
High Score	dmwright for 364.04 points

This simplest form of Tic-Tac-Toe is generally liked by programmers, because it is such a small game. There are only 3⁹ = 19683 possible ways to draw a Tic-Tac-Toe board, and only a subset of those possibilities represent valid game states. Because of this, it is easy to generate every possible outcome from a given starting state.

The first piece of code we need is a function that determines whether a particular player has won. The crudest method is hard-coding expressions that determine if every position in each winning triple of locations is occupied by the same player. There are only eight of these triples. Once we have this function, we can work on board validity, as well as generating possible outcomes.

There are two ways to determine board validity. The first consists of simply generating all possible states from the initial, empty board, by following the rules of the game. If the input configuration isn't in this set of possible states, then it must be invalid.

The other method is more analytical and easier to make a mistake with. First, count the number of Xs and the number of Os. Since in this problem O goes first, the difference between the number of Os and the number of Xs must be either 0 or 1. Any other difference indicates an invalid board. There are also a few other invalid conditions that involve a player having already won. If the number of Os exceeds the number of Xs, but X has won the game, we have an invalid state. If the number of Os equals the number of Xs, but O has won the game, we have an invalid state. If both players have won, we also have an invalid state.

We are now ready to generate all the possible outcomes. These will be generated within a directed acyclic graph (DAG) structure. Each particular state branches off into a number of possible new states, except for wins or draws which form the vertices with no outgoing edges. For each state, we will need to know whose turn is next and whether or not they have won.

Once we have this DAG (or the means of generating it as we go along), we can implement a recursive function that determines which player can force a win (if any) by walking the DAG. The base case is when the next player can win on the next move or when all the locations are filled. This corresponds to a vertex in the DAG with no outgoing edges. Otherwise we look at every possible move for the current player. Our recursive function will tell us for each move whether a win is forced or not. If there exists a move that forces a win for the current player, then we know that the current state also means a forced win for the current player. Otherwise, the current player has to hope for a way to force a draw. If a move exists that forces a draw, then the current state also forces a draw. Otherwise, the other player can force a win from this particular state.

The DAG generation and the walk of the DAG can be implemented either separately and explicitly, or together and implicitly. Implemented implicitly, the solution looks like standard memoization. It helps to be able to generate a unique identifier for each state (e.g., a 9-digit number in base-3), so that one can look up the result for a particular state in the memoization table. The return value for our public method can then just involve a lookup of the input state in that table, after a check for validity first.

Value	1050
Submission Rate	2/4 (50%)
Success Rate	0/2 (0%)

This is the sort of problem where the solution is difficult to derive, but once it is discovered, it is very easy to implement. What makes this problem tractable is the fact that a circle of irremovable connections is given. We know right off that a connection will have to be routed either within this circle or without.

For each pair of removable connections, we first determine whether they can exist on the same side of the circle without crossing. Given two points along a circle, any third point on that circle will be between those two points. If we arbitrarily pick one of the two given points, the third point will be located in an interval that is either the clockwise or counterclockwise relative to the chosen point. This gives us a simple means of labelling the two intervals.

To apply this model to this problem, let the two given points be the endpoints of one connection. Then take a second connection. If and only if both endpoints of the second connection are located in the same interval, then the connections do not cross.

For each pair of connections that cross, we know they must be routed on opposite sides of the circle. Suppose we build a graph, where each vertex represents a connection, and an edge between two connections indicates that the two connections cannot exist on the same side of the circle. Then it becomes evident that what we want to find the largest subset of edges that make this a bipartite graph, meaning that the vertices can be grouped into two sets consisting of vertices that have no edges to each other.

So all we have to do is build this graph, iterate through all subsets of edges in this graph, and choose the subset with the most edges that gives a bipartite graph. To iterate through subsets of a set of n elements, just count from 0 to 2ⁿ - 1. The binary representation of our counter will describe each subset.

For each subset, we have to determine whether it describes a bipartite graph. An alternate definition of a bipartite graph is that it contains no cycles of odd length. Or, put another way, it means that we can color all the edges using only two colors without having any two adjacent edges be the same color. Whichever definition you choose to work with, it is fairly easy to implement a function that walks the graph consisting of any given subset of edges and finds all the minimum-length cycles. If none exist that are of odd length, we have a bipartite graph.