Problem #15

Code Wars II
Danger Level: Black


}Matrix Amazement~

Point Value: 13

Problem Statement

Political prisoner Bobby "Byte" Bouchet has been captured in a hostile military zone and confined to a cell four feet on each side.  You work for a foreign intelligence service assigned to free Bouchet.  The operative needs to override the access rights of the security doors, and your task is to write the decoder.

Each door has a local security controller with a 4x4 matrix of byte control codes that are changed on a daily basis.  The matrix override sequence is a "path" of values through the matrix which conforms to the following rules:

  1. the sequence begins at position 0,0
  2. the sequence ends at position 3,3
  3. as the sequence progresses, each number in the sequence is directly adjacent (up, left, down, or right) to the previous number (no diagonal connections)
  4. the path cannot contain loops, and
  5. the value at position 3,3 is the sum of all the previous numbers in the sequence.
Program Input

Each security door is described in the input file PROB15.IN by a series of five lines.  The first line in each descriptor is an identifier, and the next four lines are each a sequence of four numbers, with each line representing a matrix row and each number in column sequence.  There may be several doors in the file.  For example:

DOOR NUMBER 1
 12  26   7  31
101   8  61  44
 18  82  13 119
 83   3  47 251

Program Output

For each security door the program should print, on one line, the identifier and the command override sequence.  For example:

DOOR NUMBER 1: 12 26 7 61 13 82 3 47 251