Complete this challenge to apply for a Digital Reasoning Software Engineering Internship. Submission instructions are found at the bottom of this page. A full job description can be found here: http://www.digitalreasoning.com/job-search
Flow is a game in which the player is given a grid with a number of pairs of colored tiles. The player must fill the entire board by drawing paths between tiles of the same color. Paths may only connect vertically or horizontally, never diagonally. Only one path may exist on a given tile, and paths may never cross each other.
For a playable example, see: http://play.famobi.com/flow-free
Write a program that, given a series of flow grids, will output their solution. You may use any technique and programming language you prefer to find the solution. Input will be passed via stdin
, and output should be written to stdout
. Programs must run in a reasonable amount of time.
A space
delimited grid. _
represent empty tiles, and A-Za-z
represent colored tiles. The max grid size is 100x100.
A series of lines representing the path taken for each color, one color per line. The format of each line should be {color_letter} - ({row1},{col1}) ({row2},{col2}) {...}
. The top left coordinate is (0,0)
.
Output lines should be sorted ascending by the character used to represent the color.
If a given grid is unsolvable, output unsolvable
.
Input:
_ _
A A
Output:
A - (1,0) (0,0) (0,1) (1,1)
Input:
A _ _ _
_ B C _
_ B _ _
C _ _ A
Output:
A - (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3)
B - (1,1) (1,0) (2,0) (2,1)
C - (1,2) (2,2) (3,2) (3,1) (3,0)
Input:
A _ _ B
B _ _ A
Output:
unsolvable
Submit responses to talentacquisition@digitalreasoning.com along with a resume. Solutions should be zipped with the original source code and a README file with explicit instructions on how to build and run your solution. Should your solution require any technologies outside of Java 8, Python 2.7, C++, or require a specific version of your chosen language, include instructions for finding and installing these technologies in your README. Your solution should build and run without the use of an IDE on a *nix (Ubuntu, Mac OSX, Cygwin on Windows, etc.) system. All submissions are due by 11:59pm CST, November 4th, 2015.