Hex Game
Tag(s):

## Hard

Problem
Editorial
Analytics
Hex is a strategy board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Other popular dimensions are 13×13 and 19×19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14×14 as the optimal size.

Each player has an allocated color, Gray or Black being conventional. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal is to form a connected path of your stones linking the opposing sides of the board marked by your colors, before your opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corners each belong to both adjacent sides.

We will play it on an 8x8 grid simulated as rhombus. The top left of the grid is [0, 0] and the bottom right is [7, 7]. The rule is that a cell[i, j] is connected to any of top, left, right, or bottom cell. It is also connected to two of the diagonal cells - cell[i+1, j+1] and cell [i-1, j-1], but not connected with the other two diagonal cells. View example image.

Input
The input will be a 8x8 matrix consisting only of 0, 1 or 2. Then another line will follow which will contain a number - 1 or 2 which is your player id.

In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn't contain any stones. The cell marked 1 means it contains player 1 stone which is gray in color. The cell marked 2 means it contains player 2 stone which is black in color. The player 1 has to connect from top to bottom (or vice-versa) and player 2 has to connect from left to right (or vice-versa) while following the rules.

Output
Print the coordinates of the cell separated by space, where you want to play your move. You must take care that you don't print invalid coordinates. For example, [1 1] might be a valid coordinate in the game play, but [9 10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

First Input
This is the input give to the first player at the start of the game.

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1

Scoring
The scores will be calculated by running a tournament of all submissions at the end of the contest. Your last submission will be used while running the tournament. Score will be assigned according to Elo rating system.

Examples
A bot which plays the game randomly, while avoiding invalid move: http://code.hackerearth.com/f03cb7L
A bot which fills the rows assuming that it's the seconds player, while avoiding invalid move: http://code.hackerearth.com/4ffa55Q
SAMPLE INPUT
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
2
SAMPLE OUTPUT
0 1
Explanation

This is player 2's turn, and the player moves at cell[1, 1].

The next state of the board after the move is following:

1 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

You don't need to worry about the next state. This is handled automatically by the code-checker servers. You just need to take a 8x8 matrix followed by player id as input and then print one valid move. The player id helps you determine which player you are and the matrix helps you determine what's the current state of the board. You have to perform all the logic then and print one valid move.

Time Limit: 2.0 sec(s) for all input files combined.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

India Hacks 2013

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays
• Algorithms > Sorting