Havannah is an abstract strategy board game created by Christian Freeling. Havannah is a game played on a hexagonal board with S hexagons to each side. Each hexagon has two horizontal and four slanted edges. The hexagons are identified by pairs of integer values. The hexagon in the bottom corner of the board is (1, 1). The hexagon adjacent to (x, y) in the direction of a two-o'clock hand is (x, y+1). The hexagon adjacent to (x, y) in the direction of a ten-o'clock hand is (x + 1, y). Here is an example board with S = 5:
In the game of Havannah, each hexagon can be occupied by at most one stone. Stones once put on the board are never removed or moved. The goal of the game is to build from stones a connected set of stones of one of three kinds. The winning structures are:
This picture shows examples of winning structures:
Your program should determine whether a sequence of moves of a single player
builds a winning structure. If so, it should output the name of the
structure and the number of the move that completed it. If a move
completes multiple rings, connects more than two corners, or connects
more than three edges, the structure is still considered a ring, a
bridge, or a fork, respectively. But if a move completes structures of
different kinds at once, your program should output the names of all of
them. We are only interested in the first winning move: ignore all
moves following the winning one.
If there is no winning structure on the board after playing all the
moves from the sequence,
your program should output
The first line of input gives the number of test cases, T. T test cases follow. The first line of each test case contains two integers S and M, the number of hexagons on each side of the board and the number of moves in the sequence, respectively. The next M lines provide the sequence of moves, in order, where each line contains a space-separated pair (x, y) of hexagon identifiers. All the moves in the sequence lie on the board of size S. In each test case, the board is initially empty and the moves do not repeat.
For each test case, output one line containing "Case #n: " followed by one of:
bridge in movek
fork in movek
ring in movek
bridge-fork in movek
bridge-ring in movek
fork-ring in movek
bridge-fork-ring in movek
The cases are numbered starting from 1. The moves are numbered starting from 1.
1 ≤ T ≤ 200
2 ≤ S ≤ 50
0 ≤ M ≤ 100
1 ≤ T ≤ 20
2 ≤ S ≤ 3000
0 ≤ M ≤ 10000
Havannah was created by Christian Freeling and MindSports. MindSports and Christian Freeling do not endorse and have no involvement with Google Code Jam.