Building a thermonuclear bomb to kill a moderately annoying fly (Or: How I went a leeettle overboard with problem eleven on Project Euler)

I recently had an interview and was given a coding test in Java and Eclipse. It was a simplified text-based battleship game, with eleven failing unit tests. My job was to get those tests to pass in exactly thirty minutes. I got lost in what I was doing (which, if this weren’t an interview test, could be a good thing), and lost track of time. When time was up, it was in a completely unstable state. So, despite the talking part of the interview going well, I didn’t get the job. Had I the chance to do it over again, I would do just fine.

It got me thinking about how I would implement the ideal text-based battleship game, which reminded me of a old blog post I wrote on navigating a grid, which I came up with after answering this Stack Overflow question.

Then I found problem eleven on Project Euler:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

So I decided to use my final not-having-a-job time to go nuts and create a generic package for navigating a matrix–moving from one element to another in a rectangular array, in one of the eight main directions: up, down, left, right, up-left, up-right, down-left, down-right.

Although the package I’ve created doesn’t go quite as far as handling Battleship, it does provides a good foundation for it (and there’s some untested code at the bottom of this post, which is the beginning of doing just that), it is something that could be used as the basis for board games such as mazes or checkers. A major feature missing in relation to mazes is “path” or “wall” detection.

A basic use of this package:

   import  com.github.xbn.util.matrix.BoundedMatrix;
   import  com.github.xbn.util.matrix.EdgeExceeded;
   import  com.github.xbn.util.matrix.MatrixDirection;
   import  com.github.xbn.util.matrix.MatrixElement;
   /*
      java  BoundedMatrixXmpl
    */
public class BoundedMatrixXmpl  {
   public static final void main(String[] cmd_lineParams)  {
      BoundedMatrix matrix = new BoundedMatrix(20); //20x20 square
      MatrixElement element = matrix.get(3,5);
      MatrixElement element2 = matrix.getNeighbor(element,
         MatrixDirection.DOWN_RIGHT, 3, EdgeExceeded.CRASH);
      MatrixElement element3 = matrix.moveDown(element2, EdgeExceeded.CRASH);

      System.out.println("First:  " + element);
      System.out.println("Second: " + element2);
      System.out.println("Third:  " + element3);

      System.out.println("The third element has the following neighbor counts:");
      System.out.println("   up=        " +
         matrix.getNeighborCount(element3, MatrixDirection.UP));
      System.out.println("   up-right=  " +
         matrix.getNeighborCount(element3, MatrixDirection.UP_RIGHT));
      System.out.println("   right=     " +
         matrix.getNeighborCount(element3, MatrixDirection.RIGHT));
      System.out.println("   down-right=" +
         matrix.getNeighborCount(element3, MatrixDirection.DOWN_RIGHT));
      System.out.println("   down=      " +
         matrix.getNeighborCount(element3, MatrixDirection.DOWN));
      System.out.println("   down-left= " +
         matrix.getNeighborCount(element3, MatrixDirection.DOWN_LEFT));
      System.out.println("   left=      " +
         matrix.getNeighborCount(element3, MatrixDirection.LEFT));
      System.out.println("   up-left=   " +
         matrix.getNeighborCount(element3, MatrixDirection.UP_LEFT));
   }
}

Output

First:  [row=3,col=5]
Second: [row=6,col=8]
Third:  [row=7,col=8]
The third element has the following neighbor counts:
   up=        7
   up-right=  7
   right=     11
   down-right=11
   down=      12
   down-left= 8
   left=      8
   up-left=   7

I used this matrix package to solve the Project Euler problem in two ways: First, with as simple-as-possible code, and then again more efficiently.

The simple way

To not give away the answer and to shorten the output, I’m using a different input matrix.

   import  com.github.xbn.number.IndexInRange;
   import  com.github.xbn.util.matrix.BoundedMatrix;
   import  com.github.xbn.util.matrix.EdgeExceeded;
   import  com.github.xbn.util.matrix.MatrixDirection;
   import  com.github.xbn.util.matrix.MatrixElement;
   /*
      java  Largest4InARowProductInMatrix
    */
public class Largest4InARowProductInMatrix  {
   //The number of cells *next* to the first one. The element chain is one
   //greater than this
   public static final int NEIGHBOR_COUNT = 3;

   public static final int[][] intMatrixFromProjectEuler = {
      new int[] { 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
      new int[] {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
      new int[] {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
      new int[] {52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91},
      new int[] {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
      new int[] {24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
      new int[] {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
      new int[] {67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
      new int[] {24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
      new int[] {21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
      new int[] {78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
      new int[] {16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
      new int[] {86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
      new int[] {19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
      new int[] { 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
      new int[] {88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
      new int[] { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
      new int[] {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
      new int[] {20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
      new int[] { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48}
   };

   //So I don't give the answer away, and for less output
   public static final int[][] intMatrixAnother = {
      new int[]  {31, 48, 50, 20, 57, 51, 48, 78},
      new int[]  {19,  7,  3,  2, 23, 76, 58, 51},
      new int[]  {99, 78, 12, 64,  9, 15, 72,  0},
      new int[]  {92,  5, 86, 68, 13, 55,  2, 98},
      new int[]  {43, 79,  4, 62,  0, 70, 57, 89},
      new int[]  {69, 65, 84, 27, 12, 14, 83, 16},
      new int[]  { 5, 97, 96, 65, 77, 77, 62, 67},
      new int[]  {94,  2,  5, 99,  3, 60, 49, 54}
   };
   public static final int[][] intMatrix = intMatrixAnother;

   //For moving from one element to another, in any direction, and
   //detecting which cells should be analyzed.
   public static final BoundedMatrix matrix = new BoundedMatrix(
                                                       intMatrix[0].length,
                                                       intMatrix.length);
   public static final void main(String[] cmd_lineParams)  {

      //A trivial object to hold the highest product and its starting
      //element, and with a convenient debugging function.
      ProductElementDirection highestProductElem = new ProductElementDirection();

      //Initialize it to the lowest-possible value, so the first product
      //overrides it.
      highestProductElem.product = Integer.MIN_VALUE;

      //For every element in the matrix, analyze the four-element chains
      //that starts with it.
      for(int rowIdx = 0; rowIdx < matrix.getRowCount(); rowIdx++)  {
         for(int elemInRowIdx = 0; elemInRowIdx < matrix.getElementsInRowCount();
                  elemInRowIdx++)  {

            MatrixElement element = matrix.get(rowIdx, elemInRowIdx);

            //Analyze the cell in all four directions.
            //
            //If a higher product is found, highestProductElem is updated.
            //
            //No need to do the opposites (LEFT, UP_LEFT, UP, UP_RIGHT),
            //because multiplication is commutative.
            getHigherProduct(element, MatrixDirection.RIGHT, highestProductElem);
            getHigherProduct(element, MatrixDirection.DOWN_RIGHT, highestProductElem);
            getHigherProduct(element, MatrixDirection.DOWN, highestProductElem);
            getHigherProduct(element, MatrixDirection.DOWN_LEFT, highestProductElem);
         }
      }
      System.out.println("Highest product of " + (NEIGHBOR_COUNT + 1) +
         " contiguous elements: " + highestProductElem);
   }
   public static final void getHigherProduct(MatrixElement first_element,
            MatrixDirection direction,
            ProductElementDirection current_highest)  {

      System.out.print(first_element + " " + direction + ": ");

      if(matrix.getNeighborCount(first_element, direction) < NEIGHBOR_COUNT)  {
         System.out.println("Not enough neighbors");
         return;
      }

      //There are enough neighbors

      //The product of the first number IS the first number.
      int product = intMatrix[first_element.getRowIndex()][first_element.getColumnIndex()];
      System.out.print(product + " * ");

      //Go to the next element, and multiply the product by it.
      MatrixElement nextElement = first_element;

      for(int i = 1; i <= NEIGHBOR_COUNT; i++)  {
         nextElement = matrix.moveNextDoor(nextElement, direction,
            EdgeExceeded.CRASH);

         int num = intMatrix[nextElement.getRowIndex()][nextElement.getColumnIndex()];
         product *= num;

         System.out.print(num);
         if(i < NEIGHBOR_COUNT)  {
            System.out.print(" * ");
         }
      }
      System.out.print(" = " + product);

      if(product > current_highest.product)  {
         current_highest.firstElement = first_element;
         current_highest.direction = direction;
         current_highest.product = product;

         System.out.print(" --NEW HIGH--");
      }

      System.out.println();
   }
}
class ProductElementDirection  {
   public int product;
   public MatrixElement firstElement;
   public MatrixDirection direction;
   public String toString()  {
      return  "Starting at " + firstElement + ", going " + direction +
         ": Product=" + product;
   }
}

Output

[row=0,col=0] RIGHT: 31 * 48 * 50 * 20 = 1488000 --NEW HIGH--
[row=0,col=0] DOWN_RIGHT: 31 * 7 * 12 * 68 = 177072
[row=0,col=0] DOWN: 31 * 19 * 99 * 92 = 5364612 --NEW HIGH--
[row=0,col=0] DOWN_LEFT: Not enough neighbors
[row=0,col=1] RIGHT: 48 * 50 * 20 * 57 = 2736000
[row=0,col=1] DOWN_RIGHT: 48 * 3 * 64 * 13 = 119808
[row=0,col=1] DOWN: 48 * 7 * 78 * 5 = 131040
[row=0,col=1] DOWN_LEFT: Not enough neighbors
[row=0,col=2] RIGHT: 50 * 20 * 57 * 51 = 2907000
[row=0,col=2] DOWN_RIGHT: 50 * 2 * 9 * 55 = 49500
[row=0,col=2] DOWN: 50 * 3 * 12 * 86 = 154800
[row=0,col=2] DOWN_LEFT: Not enough neighbors
[row=0,col=3] RIGHT: 20 * 57 * 51 * 48 = 2790720
[row=0,col=3] DOWN_RIGHT: 20 * 23 * 15 * 2 = 13800
[row=0,col=3] DOWN: 20 * 2 * 64 * 68 = 174080
[row=0,col=3] DOWN_LEFT: 20 * 3 * 78 * 92 = 430560
[row=0,col=4] RIGHT: 57 * 51 * 48 * 78 = 10883808 --NEW HIGH--
[row=0,col=4] DOWN_RIGHT: 57 * 76 * 72 * 98 = 30566592 --NEW HIGH--
[row=0,col=4] DOWN: 57 * 23 * 9 * 13 = 153387
[row=0,col=4] DOWN_LEFT: 57 * 2 * 12 * 5 = 6840
[row=0,col=5] RIGHT: Not enough neighbors
[row=0,col=5] DOWN_RIGHT: Not enough neighbors
[row=0,col=5] DOWN: 51 * 76 * 15 * 55 = 3197700
[row=0,col=5] DOWN_LEFT: 51 * 23 * 64 * 86 = 6456192
[row=0,col=6] RIGHT: Not enough neighbors
[row=0,col=6] DOWN_RIGHT: Not enough neighbors
[row=0,col=6] DOWN: 48 * 58 * 72 * 2 = 400896
[row=0,col=6] DOWN_LEFT: 48 * 76 * 9 * 68 = 2232576
[row=0,col=7] RIGHT: Not enough neighbors
[row=0,col=7] DOWN_RIGHT: Not enough neighbors
[row=0,col=7] DOWN: 78 * 51 * 0 * 98 = 0
[row=0,col=7] DOWN_LEFT: 78 * 58 * 15 * 13 = 882180
[row=1,col=0] RIGHT: 19 * 7 * 3 * 2 = 798
[row=1,col=0] DOWN_RIGHT: 19 * 78 * 86 * 62 = 7902024
[row=1,col=0] DOWN: 19 * 99 * 92 * 43 = 7441236
[row=1,col=0] DOWN_LEFT: Not enough neighbors
[row=1,col=1] RIGHT: 7 * 3 * 2 * 23 = 966
[row=1,col=1] DOWN_RIGHT: 7 * 12 * 68 * 0 = 0
[row=1,col=1] DOWN: 7 * 78 * 5 * 79 = 215670
[row=1,col=1] DOWN_LEFT: Not enough neighbors
[row=1,col=2] RIGHT: 3 * 2 * 23 * 76 = 10488
[row=1,col=2] DOWN_RIGHT: 3 * 64 * 13 * 70 = 174720
[row=1,col=2] DOWN: 3 * 12 * 86 * 4 = 12384
[row=1,col=2] DOWN_LEFT: Not enough neighbors
[row=1,col=3] RIGHT: 2 * 23 * 76 * 58 = 202768
[row=1,col=3] DOWN_RIGHT: 2 * 9 * 55 * 57 = 56430
[row=1,col=3] DOWN: 2 * 64 * 68 * 62 = 539648
[row=1,col=3] DOWN_LEFT: 2 * 12 * 5 * 43 = 5160
[row=1,col=4] RIGHT: 23 * 76 * 58 * 51 = 5170584
[row=1,col=4] DOWN_RIGHT: 23 * 15 * 2 * 89 = 61410
[row=1,col=4] DOWN: 23 * 9 * 13 * 0 = 0
[row=1,col=4] DOWN_LEFT: 23 * 64 * 86 * 79 = 10000768
[row=1,col=5] RIGHT: Not enough neighbors
[row=1,col=5] DOWN_RIGHT: Not enough neighbors
[row=1,col=5] DOWN: 76 * 15 * 55 * 70 = 4389000
[row=1,col=5] DOWN_LEFT: 76 * 9 * 68 * 4 = 186048
[row=1,col=6] RIGHT: Not enough neighbors
[row=1,col=6] DOWN_RIGHT: Not enough neighbors
[row=1,col=6] DOWN: 58 * 72 * 2 * 57 = 476064
[row=1,col=6] DOWN_LEFT: 58 * 15 * 13 * 62 = 701220
[row=1,col=7] RIGHT: Not enough neighbors
[row=1,col=7] DOWN_RIGHT: Not enough neighbors
[row=1,col=7] DOWN: 51 * 0 * 98 * 89 = 0
[row=1,col=7] DOWN_LEFT: 51 * 72 * 55 * 0 = 0
[row=2,col=0] RIGHT: 99 * 78 * 12 * 64 = 5930496
[row=2,col=0] DOWN_RIGHT: 99 * 5 * 4 * 27 = 53460
[row=2,col=0] DOWN: 99 * 92 * 43 * 69 = 27023436
[row=2,col=0] DOWN_LEFT: Not enough neighbors
[row=2,col=1] RIGHT: 78 * 12 * 64 * 9 = 539136
[row=2,col=1] DOWN_RIGHT: 78 * 86 * 62 * 12 = 4990752
[row=2,col=1] DOWN: 78 * 5 * 79 * 65 = 2002650
[row=2,col=1] DOWN_LEFT: Not enough neighbors
[row=2,col=2] RIGHT: 12 * 64 * 9 * 15 = 103680
[row=2,col=2] DOWN_RIGHT: 12 * 68 * 0 * 14 = 0
[row=2,col=2] DOWN: 12 * 86 * 4 * 84 = 346752
[row=2,col=2] DOWN_LEFT: Not enough neighbors
[row=2,col=3] RIGHT: 64 * 9 * 15 * 72 = 622080
[row=2,col=3] DOWN_RIGHT: 64 * 13 * 70 * 83 = 4833920
[row=2,col=3] DOWN: 64 * 68 * 62 * 27 = 7285248
[row=2,col=3] DOWN_LEFT: 64 * 86 * 79 * 69 = 30002304
[row=2,col=4] RIGHT: 9 * 15 * 72 * 0 = 0
[row=2,col=4] DOWN_RIGHT: 9 * 55 * 57 * 16 = 451440
[row=2,col=4] DOWN: 9 * 13 * 0 * 12 = 0
[row=2,col=4] DOWN_LEFT: 9 * 68 * 4 * 65 = 159120
[row=2,col=5] RIGHT: Not enough neighbors
[row=2,col=5] DOWN_RIGHT: Not enough neighbors
[row=2,col=5] DOWN: 15 * 55 * 70 * 14 = 808500
[row=2,col=5] DOWN_LEFT: 15 * 13 * 62 * 84 = 1015560
[row=2,col=6] RIGHT: Not enough neighbors
[row=2,col=6] DOWN_RIGHT: Not enough neighbors
[row=2,col=6] DOWN: 72 * 2 * 57 * 83 = 681264
[row=2,col=6] DOWN_LEFT: 72 * 55 * 0 * 27 = 0
[row=2,col=7] RIGHT: Not enough neighbors
[row=2,col=7] DOWN_RIGHT: Not enough neighbors
[row=2,col=7] DOWN: 0 * 98 * 89 * 16 = 0
[row=2,col=7] DOWN_LEFT: 0 * 2 * 70 * 12 = 0
[row=3,col=0] RIGHT: 92 * 5 * 86 * 68 = 2690080
[row=3,col=0] DOWN_RIGHT: 92 * 79 * 84 * 65 = 39683280 --NEW HIGH--
[row=3,col=0] DOWN: 92 * 43 * 69 * 5 = 1364820
[row=3,col=0] DOWN_LEFT: Not enough neighbors
[row=3,col=1] RIGHT: 5 * 86 * 68 * 13 = 380120
[row=3,col=1] DOWN_RIGHT: 5 * 4 * 27 * 77 = 41580
[row=3,col=1] DOWN: 5 * 79 * 65 * 97 = 2490475
[row=3,col=1] DOWN_LEFT: Not enough neighbors
[row=3,col=2] RIGHT: 86 * 68 * 13 * 55 = 4181320
[row=3,col=2] DOWN_RIGHT: 86 * 62 * 12 * 77 = 4926768
[row=3,col=2] DOWN: 86 * 4 * 84 * 96 = 2774016
[row=3,col=2] DOWN_LEFT: Not enough neighbors
[row=3,col=3] RIGHT: 68 * 13 * 55 * 2 = 97240
[row=3,col=3] DOWN_RIGHT: 68 * 0 * 14 * 62 = 0
[row=3,col=3] DOWN: 68 * 62 * 27 * 65 = 7399080
[row=3,col=3] DOWN_LEFT: 68 * 4 * 65 * 5 = 88400
[row=3,col=4] RIGHT: 13 * 55 * 2 * 98 = 140140
[row=3,col=4] DOWN_RIGHT: 13 * 70 * 83 * 67 = 5060510
[row=3,col=4] DOWN: 13 * 0 * 12 * 77 = 0
[row=3,col=4] DOWN_LEFT: 13 * 62 * 84 * 97 = 6567288
[row=3,col=5] RIGHT: Not enough neighbors
[row=3,col=5] DOWN_RIGHT: Not enough neighbors
[row=3,col=5] DOWN: 55 * 70 * 14 * 77 = 4150300
[row=3,col=5] DOWN_LEFT: 55 * 0 * 27 * 96 = 0
[row=3,col=6] RIGHT: Not enough neighbors
[row=3,col=6] DOWN_RIGHT: Not enough neighbors
[row=3,col=6] DOWN: 2 * 57 * 83 * 62 = 586644
[row=3,col=6] DOWN_LEFT: 2 * 70 * 12 * 65 = 109200
[row=3,col=7] RIGHT: Not enough neighbors
[row=3,col=7] DOWN_RIGHT: Not enough neighbors
[row=3,col=7] DOWN: 98 * 89 * 16 * 67 = 9349984
[row=3,col=7] DOWN_LEFT: 98 * 57 * 14 * 77 = 6021708
[row=4,col=0] RIGHT: 43 * 79 * 4 * 62 = 842456
[row=4,col=0] DOWN_RIGHT: 43 * 65 * 96 * 99 = 26563680
[row=4,col=0] DOWN: 43 * 69 * 5 * 94 = 1394490
[row=4,col=0] DOWN_LEFT: Not enough neighbors
[row=4,col=1] RIGHT: 79 * 4 * 62 * 0 = 0
[row=4,col=1] DOWN_RIGHT: 79 * 84 * 65 * 3 = 1294020
[row=4,col=1] DOWN: 79 * 65 * 97 * 2 = 996190
[row=4,col=1] DOWN_LEFT: Not enough neighbors
[row=4,col=2] RIGHT: 4 * 62 * 0 * 70 = 0
[row=4,col=2] DOWN_RIGHT: 4 * 27 * 77 * 60 = 498960
[row=4,col=2] DOWN: 4 * 84 * 96 * 5 = 161280
[row=4,col=2] DOWN_LEFT: Not enough neighbors
[row=4,col=3] RIGHT: 62 * 0 * 70 * 57 = 0
[row=4,col=3] DOWN_RIGHT: 62 * 12 * 77 * 49 = 2807112
[row=4,col=3] DOWN: 62 * 27 * 65 * 99 = 10772190
[row=4,col=3] DOWN_LEFT: 62 * 84 * 97 * 94 = 47486544 --NEW HIGH--
[row=4,col=4] RIGHT: 0 * 70 * 57 * 89 = 0
[row=4,col=4] DOWN_RIGHT: 0 * 14 * 62 * 54 = 0
[row=4,col=4] DOWN: 0 * 12 * 77 * 3 = 0
[row=4,col=4] DOWN_LEFT: 0 * 27 * 96 * 2 = 0
[row=4,col=5] RIGHT: Not enough neighbors
[row=4,col=5] DOWN_RIGHT: Not enough neighbors
[row=4,col=5] DOWN: 70 * 14 * 77 * 60 = 4527600
[row=4,col=5] DOWN_LEFT: 70 * 12 * 65 * 5 = 273000
[row=4,col=6] RIGHT: Not enough neighbors
[row=4,col=6] DOWN_RIGHT: Not enough neighbors
[row=4,col=6] DOWN: 57 * 83 * 62 * 49 = 14372778
[row=4,col=6] DOWN_LEFT: 57 * 14 * 77 * 99 = 6083154
[row=4,col=7] RIGHT: Not enough neighbors
[row=4,col=7] DOWN_RIGHT: Not enough neighbors
[row=4,col=7] DOWN: 89 * 16 * 67 * 54 = 5152032
[row=4,col=7] DOWN_LEFT: 89 * 83 * 77 * 3 = 1706397
[row=5,col=0] RIGHT: 69 * 65 * 84 * 27 = 10171980
[row=5,col=0] DOWN_RIGHT: Not enough neighbors
[row=5,col=0] DOWN: Not enough neighbors
[row=5,col=0] DOWN_LEFT: Not enough neighbors
[row=5,col=1] RIGHT: 65 * 84 * 27 * 12 = 1769040
[row=5,col=1] DOWN_RIGHT: Not enough neighbors
[row=5,col=1] DOWN: Not enough neighbors
[row=5,col=1] DOWN_LEFT: Not enough neighbors
[row=5,col=2] RIGHT: 84 * 27 * 12 * 14 = 381024
[row=5,col=2] DOWN_RIGHT: Not enough neighbors
[row=5,col=2] DOWN: Not enough neighbors
[row=5,col=2] DOWN_LEFT: Not enough neighbors
[row=5,col=3] RIGHT: 27 * 12 * 14 * 83 = 376488
[row=5,col=3] DOWN_RIGHT: Not enough neighbors
[row=5,col=3] DOWN: Not enough neighbors
[row=5,col=3] DOWN_LEFT: Not enough neighbors
[row=5,col=4] RIGHT: 12 * 14 * 83 * 16 = 223104
[row=5,col=4] DOWN_RIGHT: Not enough neighbors
[row=5,col=4] DOWN: Not enough neighbors
[row=5,col=4] DOWN_LEFT: Not enough neighbors
[row=5,col=5] RIGHT: Not enough neighbors
[row=5,col=5] DOWN_RIGHT: Not enough neighbors
[row=5,col=5] DOWN: Not enough neighbors
[row=5,col=5] DOWN_LEFT: Not enough neighbors
[row=5,col=6] RIGHT: Not enough neighbors
[row=5,col=6] DOWN_RIGHT: Not enough neighbors
[row=5,col=6] DOWN: Not enough neighbors
[row=5,col=6] DOWN_LEFT: Not enough neighbors
[row=5,col=7] RIGHT: Not enough neighbors
[row=5,col=7] DOWN_RIGHT: Not enough neighbors
[row=5,col=7] DOWN: Not enough neighbors
[row=5,col=7] DOWN_LEFT: Not enough neighbors
[row=6,col=0] RIGHT: 5 * 97 * 96 * 65 = 3026400
[row=6,col=0] DOWN_RIGHT: Not enough neighbors
[row=6,col=0] DOWN: Not enough neighbors
[row=6,col=0] DOWN_LEFT: Not enough neighbors
[row=6,col=1] RIGHT: 97 * 96 * 65 * 77 = 46606560
[row=6,col=1] DOWN_RIGHT: Not enough neighbors
[row=6,col=1] DOWN: Not enough neighbors
[row=6,col=1] DOWN_LEFT: Not enough neighbors
[row=6,col=2] RIGHT: 96 * 65 * 77 * 77 = 36996960
[row=6,col=2] DOWN_RIGHT: Not enough neighbors
[row=6,col=2] DOWN: Not enough neighbors
[row=6,col=2] DOWN_LEFT: Not enough neighbors
[row=6,col=3] RIGHT: 65 * 77 * 77 * 62 = 23893870
[row=6,col=3] DOWN_RIGHT: Not enough neighbors
[row=6,col=3] DOWN: Not enough neighbors
[row=6,col=3] DOWN_LEFT: Not enough neighbors
[row=6,col=4] RIGHT: 77 * 77 * 62 * 67 = 24629066
[row=6,col=4] DOWN_RIGHT: Not enough neighbors
[row=6,col=4] DOWN: Not enough neighbors
[row=6,col=4] DOWN_LEFT: Not enough neighbors
[row=6,col=5] RIGHT: Not enough neighbors
[row=6,col=5] DOWN_RIGHT: Not enough neighbors
[row=6,col=5] DOWN: Not enough neighbors
[row=6,col=5] DOWN_LEFT: Not enough neighbors
[row=6,col=6] RIGHT: Not enough neighbors
[row=6,col=6] DOWN_RIGHT: Not enough neighbors
[row=6,col=6] DOWN: Not enough neighbors
[row=6,col=6] DOWN_LEFT: Not enough neighbors
[row=6,col=7] RIGHT: Not enough neighbors
[row=6,col=7] DOWN_RIGHT: Not enough neighbors
[row=6,col=7] DOWN: Not enough neighbors
[row=6,col=7] DOWN_LEFT: Not enough neighbors
[row=7,col=0] RIGHT: 94 * 2 * 5 * 99 = 93060
[row=7,col=0] DOWN_RIGHT: Not enough neighbors
[row=7,col=0] DOWN: Not enough neighbors
[row=7,col=0] DOWN_LEFT: Not enough neighbors
[row=7,col=1] RIGHT: 2 * 5 * 99 * 3 = 2970
[row=7,col=1] DOWN_RIGHT: Not enough neighbors
[row=7,col=1] DOWN: Not enough neighbors
[row=7,col=1] DOWN_LEFT: Not enough neighbors
[row=7,col=2] RIGHT: 5 * 99 * 3 * 60 = 89100
[row=7,col=2] DOWN_RIGHT: Not enough neighbors
[row=7,col=2] DOWN: Not enough neighbors
[row=7,col=2] DOWN_LEFT: Not enough neighbors
[row=7,col=3] RIGHT: 99 * 3 * 60 * 49 = 873180
[row=7,col=3] DOWN_RIGHT: Not enough neighbors
[row=7,col=3] DOWN: Not enough neighbors
[row=7,col=3] DOWN_LEFT: Not enough neighbors
[row=7,col=4] RIGHT: 3 * 60 * 49 * 54 = 476280
[row=7,col=4] DOWN_RIGHT: Not enough neighbors
[row=7,col=4] DOWN: Not enough neighbors
[row=7,col=4] DOWN_LEFT: Not enough neighbors
[row=7,col=5] RIGHT: Not enough neighbors
[row=7,col=5] DOWN_RIGHT: Not enough neighbors
[row=7,col=5] DOWN: Not enough neighbors
[row=7,col=5] DOWN_LEFT: Not enough neighbors
[row=7,col=6] RIGHT: Not enough neighbors
[row=7,col=6] DOWN_RIGHT: Not enough neighbors
[row=7,col=6] DOWN: Not enough neighbors
[row=7,col=6] DOWN_LEFT: Not enough neighbors
[row=7,col=7] RIGHT: Not enough neighbors
[row=7,col=7] DOWN_RIGHT: Not enough neighbors
[row=7,col=7] DOWN: Not enough neighbors
[row=7,col=7] DOWN_LEFT: Not enough neighbors
Highest product of 4 contiguous elements: Starting at [row=4,col=3], going DOWN_LEFT: Product=47486544

Each element is analyzed four times, once per direction, for a total of

8 height * 8 width * 4 directions = 256 chains

(in the 20×20 Project Euler matrix, it’s

20^2 * 4 = 1600).

One obvious improvement would be to short-circuit when any element in the chain is zero.

In addition, there’s no reason to even approach elements that are known to have too few neighbors, given the directions being analyzed. For example, there’s no point in looking at the bottom three rows at all, when you’re analyzing a four-element chain going down. The same goes for the three left-most elements in any row, for a four-element chain going left. To solve this, I’m using a function that detects the range of indexes in a single row (or column) that have at least the required number of neighbors in the needed direction.

An example use of that function:

   import  com.github.xbn.util.matrix.BoundedMatrix;
   import  com.github.xbn.util.matrix.MatrixDirection;
   import  com.github.xbn.number.IndexInRange;
public class GetRowItemIdxRangeForNeighborCountXmpl {
   public static final void main(String[] cmd_lineParams)  {
      BoundedMatrix matrix = new BoundedMatrix(20);  //20x20 square
      printRowItemIdxRangeForNeighborCount(matrix, 0,
         MatrixDirection.DOWN, 5);
      printRowItemIdxRangeForNeighborCount(matrix, 0,
         MatrixDirection.UP, 5);
      printRowItemIdxRangeForNeighborCount(matrix, 0,
         MatrixDirection.UP, 0);
      printRowItemIdxRangeForNeighborCount(matrix, 0,
         MatrixDirection.DOWN_RIGHT, 3);
   }
   public static final void printRowItemIdxRangeForNeighborCount(
            BoundedMatrix matrix, int row_idx, MatrixDirection direction,
            int neighbor_count)  {
      IndexInRange range = matrix.getRowItemIdxRangeForNeighborCount(
            row_idx, direction, neighbor_count);
      System.out.println(range);
   }
}

Output

[0,20)
null
[0,20)
[0,17)

Here is the more efficient version of the Project Euler solver. A version with no diagnostic output is below.

   import  com.github.xbn.number.IndexInRange;
   import  com.github.xbn.util.matrix.BoundedMatrix;
   import  com.github.xbn.util.matrix.EdgeExceeded;
   import  com.github.xbn.util.matrix.MatrixDirection;
   import  com.github.xbn.util.matrix.MatrixElement;
   import java.text.DecimalFormat;
/*
   java  Largest4InARowProductInMatrixEfficient
 */
public class Largest4InARowProductInMatrixEfficient  {
   //The number of cells *next* to the first one. The element chain is one
   //greater than this
   public static final int NEIGHBOR_COUNT = 3;

   public static final int[][] intMatrixFromProjectEuler = {
      new int[] { 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
      new int[] {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
      new int[] {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
      new int[] {52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91},
      new int[] {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
      new int[] {24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
      new int[] {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
      new int[] {67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
      new int[] {24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
      new int[] {21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
      new int[] {78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
      new int[] {16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
      new int[] {86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
      new int[] {19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
      new int[] { 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
      new int[] {88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
      new int[] { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
      new int[] {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
      new int[] {20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
      new int[] { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48}
   };

   //So I don't give the answer away, and for less output
   public static final int[][] intMatrixAnother = {
      new int[]  {31, 48, 50, 20, 57, 51, 48, 78},
      new int[]  {19,  7,  3,  2, 23, 76, 58, 51},
      new int[]  {99, 78, 12, 64,  9, 15, 72,  0},
      new int[]  {92,  5, 86, 68, 13, 55,  2, 98},
      new int[]  {43, 79,  4, 62,  0, 70, 57, 89},
      new int[]  {69, 65, 84, 27, 12, 14, 83, 16},
      new int[]  { 5, 97, 96, 65, 77, 77, 62, 67},
      new int[]  {94,  2,  5, 99,  3, 60, 49, 54}
   };
   public static final int[][] intMatrix = intMatrixAnother;

   //For moving from one element to another, in any direction, and
   //detecting which cells should be analyzed.
   public static final BoundedMatrix matrix = new BoundedMatrix(
                                                       intMatrix[0].length,
                                                       intMatrix.length);
   public static final void main(String[] cmd_lineParams)  {

      //A trivial object to hold the highest product and its starting
      //element, and with a convenient debugging function. ("2" because
      //you can't declare a private class having the same name as a private
      //class in *another* file.)
      ProductElementDirection2 pedHighest = new ProductElementDirection2();

      //Initialize it to the lowest-possible value, so the first product
      //overrides it.
      pedHighest.product = Integer.MIN_VALUE;

      //The number of element-chains fully analyzed. If any elements in the
      //chain are zero, it isn't counted (even if the first three elements
      //are non-zero).
      int chainsFullyAnalyzed = 0;
      for(int rowIdx = 0; rowIdx < matrix.getRowCount(); rowIdx++)  {

         //Analyze each row in all four directions. Only those cells known
         //to have the proper number of neighbors are analyzed.
         //
         //If a higher product is found, highestProductElem is updated.
         //
         //No need to do the opposites (LEFT, UP_LEFT, UP, UP_RIGHT),
         //because multiplication is commutative.
         chainsFullyAnalyzed += processRowElementsForOneDirection(rowIdx,
            MatrixDirection.RIGHT, pedHighest);
         chainsFullyAnalyzed += processRowElementsForOneDirection(rowIdx,
            MatrixDirection.DOWN, pedHighest);
         chainsFullyAnalyzed += processRowElementsForOneDirection(rowIdx,
            MatrixDirection.DOWN_RIGHT, pedHighest);
         chainsFullyAnalyzed += processRowElementsForOneDirection(rowIdx,
            MatrixDirection.DOWN_LEFT, pedHighest);
      }

      //Print stats
      float avgPerRow = (float)chainsFullyAnalyzed / matrix.getRowCount();
      System.out.println("Rows in matrix=" + matrix.getRowCount() +
         ", cells per row=" + matrix.getElementsInRowCount() +
         ", total cells=" +  matrix.getElementCount());
      System.out.println("Element-chains fully analyzed: " + chainsFullyAnalyzed +
         " Average per row=" + new DecimalFormat("#.##").format(avgPerRow));

      //Final result
      System.out.println("Highest product of " + (NEIGHBOR_COUNT + 1) +
         " contiguous elements is " + pedHighest);
   }
      private static final int processRowElementsForOneDirection(
               int row_idx, MatrixDirection direction,
               ProductElementDirection2 ped_highest)  {

         //Get the *range* of indexes in this row representing the elements
         //in it that have at least the required number of neighbors.
         IndexInRange indexRange = matrix.getRowItemIdxRangeForNeighborCount(
            row_idx, direction, NEIGHBOR_COUNT);

         System.out.print("Row index " + row_idx);
         if(indexRange == null)  {
            System.out.println(" contains no elements with " + NEIGHBOR_COUNT +
               " neighbors " + direction + "");
            return  0;
         }

         //At least one element needs to be analyzed

         //The number of element-chains fully analyzed (the number of
         //elements that have enough neighbors AND in which no elements are zero).
         int chainsAnalyzed = 0;

         System.out.println(": Analyzing element indexes " + indexRange +
            ", going " + direction + ". NEIGHBOR_COUNT=" + NEIGHBOR_COUNT);

         int product = 0;
         if(indexRange != null)  {

            //For each element in the index range, get the product of its
            //chain
            MatrixElement firstElement = null;
            for(int colIdx = indexRange.getMin(); colIdx < indexRange.getMax();
                  colIdx++)  {

               //Initialize
               int firstNum = intMatrix[row_idx][colIdx];
               firstElement = matrix.get(row_idx, colIdx);
               MatrixElement element = firstElement;

               System.out.print(" -" + firstElement + " going " + direction +
                  ": [" + firstNum);


               if(firstNum == 0)  {
                  //If any of the numbers are zero, the product is
                  //definitely zero. No need to continue.
                  System.out.println(" ZERO!], product=0");
                  continue;
               }
               System.out.print(", ");

               //The product of a single number (the first number in the
               //chain) is the number itself.
               product = firstNum;

               for(int counter = 0; counter < NEIGHBOR_COUNT; counter++)  {

                  //Get the value of its next-door neighbor
                  element = matrix.moveNextDoor(element, direction,
                     EdgeExceeded.CRASH);
                  int elemRowIdx = element.getRowIndex();
                  int elemColIdx = element.getColumnIndex();
                  int nextNum = intMatrix[elemRowIdx][elemColIdx];

                  System.out.print(nextNum);
                  if(nextNum == 0)  {
                     System.out.print(" ZERO!");
                     product = 0;
                     break;
                  }

                  if(counter < (NEIGHBOR_COUNT - 1))  {
                     //At least one more element in the chain
                     System.out.print(", ");
                  }

                  //Multiply this number to the product
                  product *= nextNum;
               }

               System.out.print("]: product=" + product);

               if(product != 0)  {
                  chainsAnalyzed++;
               }

               if(product > ped_highest.product)  {
                  ped_highest.product = product;
                  ped_highest.firstElement = firstElement;
                  ped_highest.direction = direction;
                  System.out.println("   -- NEW HIGH --");
               }  else  {
                  System.out.println();
               }
            }
         }

         //The number of elements analyzed
         return  chainsAnalyzed;
      }
}
class ProductElementDirection2  {
   public int product;
   public MatrixElement firstElement;
   public MatrixDirection direction;
   public String toString()  {
      return  "Starting at " + firstElement + ", going " + direction + ": Product=" + product;
   }
}

Output

Row index 0: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=0,col=0] going RIGHT: [31, 48, 50, 20]: product=1488000   -- NEW HIGH --
 -[row=0,col=1] going RIGHT: [48, 50, 20, 57]: product=2736000   -- NEW HIGH --
 -[row=0,col=2] going RIGHT: [50, 20, 57, 51]: product=2907000   -- NEW HIGH --
 -[row=0,col=3] going RIGHT: [20, 57, 51, 48]: product=2790720
 -[row=0,col=4] going RIGHT: [57, 51, 48, 78]: product=10883808   -- NEW HIGH --
Row index 0: Analyzing element indexes [0,8), going DOWN. NEIGHBOR_COUNT=3
 -[row=0,col=0] going DOWN: [31, 19, 99, 92]: product=5364612
 -[row=0,col=1] going DOWN: [48, 7, 78, 5]: product=131040
 -[row=0,col=2] going DOWN: [50, 3, 12, 86]: product=154800
 -[row=0,col=3] going DOWN: [20, 2, 64, 68]: product=174080
 -[row=0,col=4] going DOWN: [57, 23, 9, 13]: product=153387
 -[row=0,col=5] going DOWN: [51, 76, 15, 55]: product=3197700
 -[row=0,col=6] going DOWN: [48, 58, 72, 2]: product=400896
 -[row=0,col=7] going DOWN: [78, 51, 0 ZERO!]: product=0
Row index 0: Analyzing element indexes [0,5), going DOWN_RIGHT. NEIGHBOR_COUNT=3
 -[row=0,col=0] going DOWN_RIGHT: [31, 7, 12, 68]: product=177072
 -[row=0,col=1] going DOWN_RIGHT: [48, 3, 64, 13]: product=119808
 -[row=0,col=2] going DOWN_RIGHT: [50, 2, 9, 55]: product=49500
 -[row=0,col=3] going DOWN_RIGHT: [20, 23, 15, 2]: product=13800
 -[row=0,col=4] going DOWN_RIGHT: [57, 76, 72, 98]: product=30566592   -- NEW HIGH --
Row index 0: Analyzing element indexes [3,8), going DOWN_LEFT. NEIGHBOR_COUNT=3
 -[row=0,col=3] going DOWN_LEFT: [20, 3, 78, 92]: product=430560
 -[row=0,col=4] going DOWN_LEFT: [57, 2, 12, 5]: product=6840
 -[row=0,col=5] going DOWN_LEFT: [51, 23, 64, 86]: product=6456192
 -[row=0,col=6] going DOWN_LEFT: [48, 76, 9, 68]: product=2232576
 -[row=0,col=7] going DOWN_LEFT: [78, 58, 15, 13]: product=882180
Row index 1: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=1,col=0] going RIGHT: [19, 7, 3, 2]: product=798
 -[row=1,col=1] going RIGHT: [7, 3, 2, 23]: product=966
 -[row=1,col=2] going RIGHT: [3, 2, 23, 76]: product=10488
 -[row=1,col=3] going RIGHT: [2, 23, 76, 58]: product=202768
 -[row=1,col=4] going RIGHT: [23, 76, 58, 51]: product=5170584
Row index 1: Analyzing element indexes [0,8), going DOWN. NEIGHBOR_COUNT=3
 -[row=1,col=0] going DOWN: [19, 99, 92, 43]: product=7441236
 -[row=1,col=1] going DOWN: [7, 78, 5, 79]: product=215670
 -[row=1,col=2] going DOWN: [3, 12, 86, 4]: product=12384
 -[row=1,col=3] going DOWN: [2, 64, 68, 62]: product=539648
 -[row=1,col=4] going DOWN: [23, 9, 13, 0 ZERO!]: product=0
 -[row=1,col=5] going DOWN: [76, 15, 55, 70]: product=4389000
 -[row=1,col=6] going DOWN: [58, 72, 2, 57]: product=476064
 -[row=1,col=7] going DOWN: [51, 0 ZERO!]: product=0
Row index 1: Analyzing element indexes [0,5), going DOWN_RIGHT. NEIGHBOR_COUNT=3
 -[row=1,col=0] going DOWN_RIGHT: [19, 78, 86, 62]: product=7902024
 -[row=1,col=1] going DOWN_RIGHT: [7, 12, 68, 0 ZERO!]: product=0
 -[row=1,col=2] going DOWN_RIGHT: [3, 64, 13, 70]: product=174720
 -[row=1,col=3] going DOWN_RIGHT: [2, 9, 55, 57]: product=56430
 -[row=1,col=4] going DOWN_RIGHT: [23, 15, 2, 89]: product=61410
Row index 1: Analyzing element indexes [3,8), going DOWN_LEFT. NEIGHBOR_COUNT=3
 -[row=1,col=3] going DOWN_LEFT: [2, 12, 5, 43]: product=5160
 -[row=1,col=4] going DOWN_LEFT: [23, 64, 86, 79]: product=10000768
 -[row=1,col=5] going DOWN_LEFT: [76, 9, 68, 4]: product=186048
 -[row=1,col=6] going DOWN_LEFT: [58, 15, 13, 62]: product=701220
 -[row=1,col=7] going DOWN_LEFT: [51, 72, 55, 0 ZERO!]: product=0
Row index 2: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=2,col=0] going RIGHT: [99, 78, 12, 64]: product=5930496
 -[row=2,col=1] going RIGHT: [78, 12, 64, 9]: product=539136
 -[row=2,col=2] going RIGHT: [12, 64, 9, 15]: product=103680
 -[row=2,col=3] going RIGHT: [64, 9, 15, 72]: product=622080
 -[row=2,col=4] going RIGHT: [9, 15, 72, 0 ZERO!]: product=0
Row index 2: Analyzing element indexes [0,8), going DOWN. NEIGHBOR_COUNT=3
 -[row=2,col=0] going DOWN: [99, 92, 43, 69]: product=27023436
 -[row=2,col=1] going DOWN: [78, 5, 79, 65]: product=2002650
 -[row=2,col=2] going DOWN: [12, 86, 4, 84]: product=346752
 -[row=2,col=3] going DOWN: [64, 68, 62, 27]: product=7285248
 -[row=2,col=4] going DOWN: [9, 13, 0 ZERO!]: product=0
 -[row=2,col=5] going DOWN: [15, 55, 70, 14]: product=808500
 -[row=2,col=6] going DOWN: [72, 2, 57, 83]: product=681264
 -[row=2,col=7] going DOWN: [0 ZERO!], product=0
Row index 2: Analyzing element indexes [0,5), going DOWN_RIGHT. NEIGHBOR_COUNT=3
 -[row=2,col=0] going DOWN_RIGHT: [99, 5, 4, 27]: product=53460
 -[row=2,col=1] going DOWN_RIGHT: [78, 86, 62, 12]: product=4990752
 -[row=2,col=2] going DOWN_RIGHT: [12, 68, 0 ZERO!]: product=0
 -[row=2,col=3] going DOWN_RIGHT: [64, 13, 70, 83]: product=4833920
 -[row=2,col=4] going DOWN_RIGHT: [9, 55, 57, 16]: product=451440
Row index 2: Analyzing element indexes [3,8), going DOWN_LEFT. NEIGHBOR_COUNT=3
 -[row=2,col=3] going DOWN_LEFT: [64, 86, 79, 69]: product=30002304
 -[row=2,col=4] going DOWN_LEFT: [9, 68, 4, 65]: product=159120
 -[row=2,col=5] going DOWN_LEFT: [15, 13, 62, 84]: product=1015560
 -[row=2,col=6] going DOWN_LEFT: [72, 55, 0 ZERO!]: product=0
 -[row=2,col=7] going DOWN_LEFT: [0 ZERO!], product=0
Row index 3: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=3,col=0] going RIGHT: [92, 5, 86, 68]: product=2690080
 -[row=3,col=1] going RIGHT: [5, 86, 68, 13]: product=380120
 -[row=3,col=2] going RIGHT: [86, 68, 13, 55]: product=4181320
 -[row=3,col=3] going RIGHT: [68, 13, 55, 2]: product=97240
 -[row=3,col=4] going RIGHT: [13, 55, 2, 98]: product=140140
Row index 3: Analyzing element indexes [0,8), going DOWN. NEIGHBOR_COUNT=3
 -[row=3,col=0] going DOWN: [92, 43, 69, 5]: product=1364820
 -[row=3,col=1] going DOWN: [5, 79, 65, 97]: product=2490475
 -[row=3,col=2] going DOWN: [86, 4, 84, 96]: product=2774016
 -[row=3,col=3] going DOWN: [68, 62, 27, 65]: product=7399080
 -[row=3,col=4] going DOWN: [13, 0 ZERO!]: product=0
 -[row=3,col=5] going DOWN: [55, 70, 14, 77]: product=4150300
 -[row=3,col=6] going DOWN: [2, 57, 83, 62]: product=586644
 -[row=3,col=7] going DOWN: [98, 89, 16, 67]: product=9349984
Row index 3: Analyzing element indexes [0,5), going DOWN_RIGHT. NEIGHBOR_COUNT=3
 -[row=3,col=0] going DOWN_RIGHT: [92, 79, 84, 65]: product=39683280   -- NEW HIGH --
 -[row=3,col=1] going DOWN_RIGHT: [5, 4, 27, 77]: product=41580
 -[row=3,col=2] going DOWN_RIGHT: [86, 62, 12, 77]: product=4926768
 -[row=3,col=3] going DOWN_RIGHT: [68, 0 ZERO!]: product=0
 -[row=3,col=4] going DOWN_RIGHT: [13, 70, 83, 67]: product=5060510
Row index 3: Analyzing element indexes [3,8), going DOWN_LEFT. NEIGHBOR_COUNT=3
 -[row=3,col=3] going DOWN_LEFT: [68, 4, 65, 5]: product=88400
 -[row=3,col=4] going DOWN_LEFT: [13, 62, 84, 97]: product=6567288
 -[row=3,col=5] going DOWN_LEFT: [55, 0 ZERO!]: product=0
 -[row=3,col=6] going DOWN_LEFT: [2, 70, 12, 65]: product=109200
 -[row=3,col=7] going DOWN_LEFT: [98, 57, 14, 77]: product=6021708
Row index 4: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=4,col=0] going RIGHT: [43, 79, 4, 62]: product=842456
 -[row=4,col=1] going RIGHT: [79, 4, 62, 0 ZERO!]: product=0
 -[row=4,col=2] going RIGHT: [4, 62, 0 ZERO!]: product=0
 -[row=4,col=3] going RIGHT: [62, 0 ZERO!]: product=0
 -[row=4,col=4] going RIGHT: [0 ZERO!], product=0
Row index 4: Analyzing element indexes [0,8), going DOWN. NEIGHBOR_COUNT=3
 -[row=4,col=0] going DOWN: [43, 69, 5, 94]: product=1394490
 -[row=4,col=1] going DOWN: [79, 65, 97, 2]: product=996190
 -[row=4,col=2] going DOWN: [4, 84, 96, 5]: product=161280
 -[row=4,col=3] going DOWN: [62, 27, 65, 99]: product=10772190
 -[row=4,col=4] going DOWN: [0 ZERO!], product=0
 -[row=4,col=5] going DOWN: [70, 14, 77, 60]: product=4527600
 -[row=4,col=6] going DOWN: [57, 83, 62, 49]: product=14372778
 -[row=4,col=7] going DOWN: [89, 16, 67, 54]: product=5152032
Row index 4: Analyzing element indexes [0,5), going DOWN_RIGHT. NEIGHBOR_COUNT=3
 -[row=4,col=0] going DOWN_RIGHT: [43, 65, 96, 99]: product=26563680
 -[row=4,col=1] going DOWN_RIGHT: [79, 84, 65, 3]: product=1294020
 -[row=4,col=2] going DOWN_RIGHT: [4, 27, 77, 60]: product=498960
 -[row=4,col=3] going DOWN_RIGHT: [62, 12, 77, 49]: product=2807112
 -[row=4,col=4] going DOWN_RIGHT: [0 ZERO!], product=0
Row index 4: Analyzing element indexes [3,8), going DOWN_LEFT. NEIGHBOR_COUNT=3
 -[row=4,col=3] going DOWN_LEFT: [62, 84, 97, 94]: product=47486544   -- NEW HIGH --
 -[row=4,col=4] going DOWN_LEFT: [0 ZERO!], product=0
 -[row=4,col=5] going DOWN_LEFT: [70, 12, 65, 5]: product=273000
 -[row=4,col=6] going DOWN_LEFT: [57, 14, 77, 99]: product=6083154
 -[row=4,col=7] going DOWN_LEFT: [89, 83, 77, 3]: product=1706397
Row index 5: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=5,col=0] going RIGHT: [69, 65, 84, 27]: product=10171980
 -[row=5,col=1] going RIGHT: [65, 84, 27, 12]: product=1769040
 -[row=5,col=2] going RIGHT: [84, 27, 12, 14]: product=381024
 -[row=5,col=3] going RIGHT: [27, 12, 14, 83]: product=376488
 -[row=5,col=4] going RIGHT: [12, 14, 83, 16]: product=223104
Row index 5 contains no elements with 3 neighbors DOWN
Row index 5 contains no elements with 3 neighbors DOWN_RIGHT
Row index 5 contains no elements with 3 neighbors DOWN_LEFT
Row index 6: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=6,col=0] going RIGHT: [5, 97, 96, 65]: product=3026400
 -[row=6,col=1] going RIGHT: [97, 96, 65, 77]: product=46606560
 -[row=6,col=2] going RIGHT: [96, 65, 77, 77]: product=36996960
 -[row=6,col=3] going RIGHT: [65, 77, 77, 62]: product=23893870
 -[row=6,col=4] going RIGHT: [77, 77, 62, 67]: product=24629066
Row index 6 contains no elements with 3 neighbors DOWN
Row index 6 contains no elements with 3 neighbors DOWN_RIGHT
Row index 6 contains no elements with 3 neighbors DOWN_LEFT
Row index 7: Analyzing element indexes [0,5), going RIGHT. NEIGHBOR_COUNT=3
 -[row=7,col=0] going RIGHT: [94, 2, 5, 99]: product=93060
 -[row=7,col=1] going RIGHT: [2, 5, 99, 3]: product=2970
 -[row=7,col=2] going RIGHT: [5, 99, 3, 60]: product=89100
 -[row=7,col=3] going RIGHT: [99, 3, 60, 49]: product=873180
 -[row=7,col=4] going RIGHT: [3, 60, 49, 54]: product=476280
Row index 7 contains no elements with 3 neighbors DOWN
Row index 7 contains no elements with 3 neighbors DOWN_RIGHT
Row index 7 contains no elements with 3 neighbors DOWN_LEFT
Rows in matrix=8, cells per row=8, total cells=64
Element-chains fully analyzed: 109 Average per row=13.62
Highest product of 4 contiguous elements is Starting at [row=4,col=3], going DOWN_LEFT: Product=47486544

A fifty-seven percent improvement. 109 chains analyzed versus 256. Running this with the Project Euler matrix analyzes 1,184 chains, versus 1,600 in the non-efficient version (a 26-percent improvement).

The same code with no diagnostics

   import  com.github.xbn.number.IndexInRange;
   import  com.github.xbn.util.matrix.BoundedMatrix;
   import  com.github.xbn.util.matrix.EdgeExceeded;
   import  com.github.xbn.util.matrix.MatrixDirection;
   import  com.github.xbn.util.matrix.MatrixElement;
   import java.text.DecimalFormat;
/*
   java  Largest4InARowProductInMatrixEfficientNoDiag
 */
public class Largest4InARowProductInMatrixEfficientNoDiag  {
   //The number of cells *next* to the first one. The element chain is one
   //greater than this
   public static final int NEIGHBOR_COUNT = 3;

   public static final int[][] intMatrixFromProjectEuler = {
      new int[] { 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
      new int[] {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
      new int[] {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
      new int[] {52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91},
      new int[] {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
      new int[] {24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
      new int[] {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
      new int[] {67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
      new int[] {24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
      new int[] {21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
      new int[] {78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
      new int[] {16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
      new int[] {86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
      new int[] {19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
      new int[] { 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
      new int[] {88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
      new int[] { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
      new int[] {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
      new int[] {20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
      new int[] { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48}
   };

   //So I don't give the answer away, and for less output
   public static final int[][] intMatrixAnother = {
      new int[]  {31, 48, 50, 20, 57, 51, 48, 78},
      new int[]  {19,  7,  3,  2, 23, 76, 58, 51},
      new int[]  {99, 78, 12, 64,  9, 15, 72,  0},
      new int[]  {92,  5, 86, 68, 13, 55,  2, 98},
      new int[]  {43, 79,  4, 62,  0, 70, 57, 89},
      new int[]  {69, 65, 84, 27, 12, 14, 83, 16},
      new int[]  { 5, 97, 96, 65, 77, 77, 62, 67},
      new int[]  {94,  2,  5, 99,  3, 60, 49, 54}
   };
   public static final int[][] intMatrix = intMatrixAnother;

   //For moving from one element to another, in any direction, and
   //detecting which cells should be analyzed.
   public static final BoundedMatrix matrix = new BoundedMatrix(
                                                       intMatrix[0].length,
                                                       intMatrix.length);
   public static final void main(String[] cmd_lineParams)  {

      //A trivial object to hold the highest product and its starting
      //element, and with a convenient debugging function. ("3" because
      //you can't declare a private class having the same name as a private
      //class in *another* file.)
      ProductElementDirection3 pedHighest = new ProductElementDirection3();

      //Initialize it to the lowest-possible value, so the first product
      //overrides it.
      pedHighest.product = Integer.MIN_VALUE;

      for(int rowIdx = 0; rowIdx < matrix.getRowCount(); rowIdx++)  {

         //Analyze each row in all four directions. Only those cells known
         //to have the proper number of neighbors are analyzed.
         //
         //If a higher product is found, highestProductElem is updated.
         //
         //No need to do the opposites (LEFT, UP_LEFT, UP, UP_RIGHT),
         //because multiplication is commutative.
         processRowElementsForOneDirection(rowIdx, MatrixDirection.RIGHT, pedHighest);
         processRowElementsForOneDirection(rowIdx,MatrixDirection.DOWN, pedHighest);
         processRowElementsForOneDirection(rowIdx, MatrixDirection.DOWN_RIGHT, pedHighest);
         processRowElementsForOneDirection(rowIdx, MatrixDirection.DOWN_LEFT, pedHighest);
      }

      System.out.println("Highest product of " + (NEIGHBOR_COUNT + 1) +
         " contiguous elements is " + pedHighest);
   }
      private static final void processRowElementsForOneDirection(
               int row_idx, MatrixDirection direction,
               ProductElementDirection3 ped_highest)  {

         //Get the *range* of indexes in this row representing the elements
         //in it that have at least the required number of neighbors.
         IndexInRange indexRange = matrix.getRowItemIdxRangeForNeighborCount(
            row_idx, direction, NEIGHBOR_COUNT);

         if(indexRange == null)  {
            return;
         }

         //At least one element needs to be analyzed

         int product = 0;
         if(indexRange != null)  {

            //For each element in the index range, get the product of its
            //chain
            MatrixElement firstElement = null;
            for(int colIdx = indexRange.getMin(); colIdx < indexRange.getMax();
                  colIdx++)  {

               //Initialize
               int firstNum = intMatrix[row_idx][colIdx];
               firstElement = matrix.get(row_idx, colIdx);
               MatrixElement element = firstElement;

               if(firstNum == 0)  {
                  //If any of the numbers are zero, the product is
                  //definitely zero. No need to continue.
                  continue;
               }

               //The product of a single number (the first number in the
               //chain) is the number itself.
               product = firstNum;

               for(int counter = 0; counter < NEIGHBOR_COUNT; counter++)  {

                  //Get the value of its next-door neighbor
                  element = matrix.moveNextDoor(element, direction,
                     EdgeExceeded.CRASH);
                  int elemRowIdx = element.getRowIndex();
                  int elemColIdx = element.getColumnIndex();
                  int nextNum = intMatrix[elemRowIdx][elemColIdx];

                  if(nextNum == 0)  {
                     product = 0;
                     break;
                  }

                  //Multiply this number to the product
                  product *= nextNum;
               }

               if(product > ped_highest.product)  {
                  ped_highest.product = product;
                  ped_highest.firstElement = firstElement;
                  ped_highest.direction = direction;
               }
            }
         }
      }
}
class ProductElementDirection3  {
   public int product;
   public MatrixElement firstElement;
   public MatrixDirection direction;
   public String toString()  {
      return  "Starting at " + firstElement + ", going " + direction + ": Product=" + product;
   }
}

Output

Highest product of 4 contiguous elements is Starting at [row=4,col=3], going DOWN_LEFT: Product=47486544

Extending the matrix package to work for Battleship

My goal was to use this matrix package to make a text based Battleship game. Since I wish to stay married (and therefore need to get a job), I don’t have time to see this through. Below you will find three classes, which is some of the (untested) code that is at least the beginning of what’s needed.

  • FillableElement: An extension of MatrixElement with the addition of a boolean “is occupied” flag.
  • FillableMatrix: An extension of BoundedMatrix that uses FillableElements.
  • ElementLine: A series of contiguous elements in a matrix, going in one of the eight directions (vertical, horizontal, or 45-degree diagonal). In Battleship, this is a ship

The missing piece is how to lay those ships down onto the board, and to properly handle each turn. Is the coordinate for a turn (say [row=3, column=4]) on a ship, or in the water? And was that space already hit? For this, I envision an additional double-array that is the same size as the matrix, containing either null (for water) or a private LineWithIndex object:

class LineWithIndex  {
   public final ElementLine line;
   public final int index;
   public LineWithIndex(ElementLine line, int index)  {
      this.line = line;
      this.index = index;
   }
   public ElementLine getElement()  {
      return  line.get(index);
   }
}

So, on each turn, the element in this “lookup” array is retrieved. If it’s

  • null: It’s water, and the element must be retrieved from the FillableMatrix, and then, if it’s not already filled, fill it with

        matrix.get(x, y).fill())
  • A LineWithIndex object (non-null): It’s on a ship. If the element isn’t already filled, fill it with

        [the ElementLine].getElement().fill()

FillableElement.java

/*license*\
   XBN-Java: http://xbnjava.aliteralmind.com

   Copyright (C) 2014, Jeff Epstein (aliteralmind __DASH__ github __AT__ yahoo __DOT__ com)

   This software is dual-licensed under the:
   - Lesser General Public License (LGPL) version 3.0 or, at your option, any later version;
   - Apache Software License (ASL) version 2.0.

   Either license may be applied at your discretion. More information may be found at
   - http://en.wikipedia.org/wiki/Multi-licensing.

   The text of both licenses is available in the root directory of this project, under the names "LICENSE_lgpl-3.0.txt" and "LICENSE_asl-2.0.txt". The latest copies may be downloaded at:
   - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt
   - ASL 2.0: http://www.apache.org/licenses/LICENSE-2.0.txt
\*license*/
package  com.github.xbn.util.matrix;
   import  com.github.xbn.lang.ObjectOrCrashIfNull;
/**
 * <p>A element that may or may not be occupied.</p>
 * @since  0.1.5
 * @author  Copyright (C) 2014, Jeff Epstein ({@code aliteralmind __DASH__ github __AT__ yahoo __DOT__ com}), dual-licensed under the LGPL (version 3.0 or later) or the ASL (version 2.0). See source code for details. <A HREF="http://xbnjava.aliteralmind.com">{@code http://xbnjava.aliteralmind.com}</A>, <A HREF="https://github.com/aliteralmind/xbnjava">{@code https://github.com/aliteralmind/xbnjava}</A>
 */
public class FillableElement extends MatrixElement  {
   private boolean isFilled;
   /**
    * <p>Create a new instance.</p>
    *
    * <p>This calls<ol>
    *    <li><code>{@link MatrixElement#MatrixElement(int, int) super}(row_idx, col_idx)</code></li>
    *    <li>{@link #unfill()}{@code ()}</li>
    * </ol></p>
    * @@see  #FillableElement(FillableElement)
    */
   public FillableElement(int row_idx, int col_idx)  {
      super(row_idx, col_idx);
      unfill();
   }
   /**
    * <p>Create a new instance as a duplicate of another.</p>
    *
    * <p>This calls
    * <br/>     <code>super(to_copy.{@link MatrixElement#getColumnIndex() getColumnIndex}(), to_copy.{@link MatrixElement#getRowIndex() getRowIndex}())</code></p>
    * @param   to_copy  May not be <code>null</code>.
    * @see #getObjectCopy()
    * @see #FillableElement()
    */
   public FillableElement(FillableElement to_copy)  {
      super(ObjectOrCrashIfNull.get(to_copy, "to_copy").getColumnIndex(),
         to_copy.getRowIndex());
   }
   /**
    * <p>Occupy the element.</p>
    *
    * <p>Equal to <code>{@link #fill(boolean) fill}{@code (true)}</code></p>
    * @return  <i>{@code this}</i>
    */
   public FillableElement fill()  {
      fill(true);
      return  this;
   }
   /**
    * <p>Unoccupy the element.</p>
    *
    * <p>Equal to <code>{@link #fill(boolean) fill}{@code (true)}</code></p>
    * @return  <i>{@code this}</i>
    */
   public FillableElement unfill()  {
      fill(false);
      return  this;
   }
   /**
    * Declare the element as occupied or not.
    * @param  is_filled  If {@code true}, the element is filled. Get with
    * {@link #isFilled()}{@code ()}.
    * @@see  #fill()
    * @@see  #unfill()
    */
   public void fill(boolean is_filled)  {
      isFilled = is_filled;
   }
   /**
    * Is the element occupied?
    * @return  {@code is_filled} As provided to
    * {@link #fill(boolean) fill}{@code (b)}.
    */
   public boolean isFilled()  {
      return  isFilled;
   }
   /**
    * @return  <code>{@link #appendToString(java.lang.StringBuilder)(new {@link java.lang.StringBuilder#StringBuilder() StringBuilder}()).toString()</code>
    */
   public String toString()  {
      return  appendToString(new StringBuilder()).toString();
   }
   /**
    * @param  bldr  May not be <code>null</code>.
    * @see  #toString()
    */
   public StringBuilder appendToString(StringBuilder bldr)  {
      super.appendToString(bldr).append(": ");
      if(!isFilled())  {
         bldr.append("un");
      }
      return  bldr.append("filled");
   }
   /**
    * @return  <CODE>(new {@link #FillableElement(FillableElement) FillableElement}(this))</CODE>
    */
   public FillableElement getObjectCopy()  {
     return  (new FillableElement(this));
   }
}

FillableMatrix.java

/*license*\
   XBN-Java: http://xbnjava.aliteralmind.com

   Copyright (C) 2014, Jeff Epstein (aliteralmind __DASH__ github __AT__ yahoo __DOT__ com)

   This software is dual-licensed under the:
   - Lesser General Public License (LGPL) version 3.0 or, at your option, any later version;
   - Apache Software License (ASL) version 2.0.

   Either license may be applied at your discretion. More information may be found at
   - http://en.wikipedia.org/wiki/Multi-licensing.

   The text of both licenses is available in the root directory of this project, under the names "LICENSE_lgpl-3.0.txt" and "LICENSE_asl-2.0.txt". The latest copies may be downloaded at:
   - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt
   - ASL 2.0: http://www.apache.org/licenses/LICENSE-2.0.txt
\*license*/
package  com.github.xbn.util.matrix;
/**
 * <p>A bounded grid whose elements may be occupied or unoccupied.</p>
 * @since  0.1.5
 * @author  Copyright (C) 2014, Jeff Epstein ({@code aliteralmind __DASH__ github __AT__ yahoo __DOT__ com}), dual-licensed under the LGPL (version 3.0 or later) or the ASL (version 2.0). See source code for details. <A HREF="http://xbnjava.aliteralmind.com">{@code http://xbnjava.aliteralmind.com}</A>, <A HREF="https://github.com/aliteralmind/xbnjava">{@code https://github.com/aliteralmind/xbnjava}</A>
 */
public class FillableMatrix extends BoundedMatrix  {
   /**
    * <p>Create a new grid with a particular height and width.</p>
    */
   public FillableMatrix(int height, int width)  {
      super(height, width);
   }
   /**
    * Create a new instance as a duplicate of another.
    */
   public FillableMatrix(FillableMatrix to_copy)  {
      super(to_copy);
   }
   /*
    * <p>Create a new instance from a provided element double-array.</p>
   protected FillableMatrix(FillableElement[][] coords)  {
      super(coords);
   }
    */
   public FillableElement get(int row_idx, int col_idx)  {
      return  (FillableElement)super.get(row_idx, col_idx);
   }
   public FillableElement get(int row_idx, int col_idx, String ri_name,
            String ci_name)  {
      return  (FillableElement)super.get(row_idx, col_idx, ri_name, ci_name);
   }
   public void unfillAll()  {
      fillAll(false);
   }
   public void fillAll()  {
      fillAll(true);
   }
   public void fillAll(boolean is_filled)  {
      for(int i = 0; i < getRowCount(); i++)  {
         for(int j = 0; j < getElementsInRowCount(); j++)  {
            get(i, j).fill(is_filled);
         }
      }
   }
   public boolean areAllFilled()  {
      return  (getFillCount() == getElementCount());
   }
   public boolean areAllUnfilled()  {
      return  (getFillCount() == 0);
   }
   public int getFillCount()  {
      int filled = 0;
      for(int i = 0; i < getRowCount(); i++)  {
         for(int j = 0; j < getElementsInRowCount(); j++)  {
            if(get(i, j).isFilled())  {
               filled++;
            }
         }
      }
      return  filled;
   }
   public FillableMatrix unfill(int row_idx, int col_idx)  {
      return  fill(false, row_idx, col_idx);
   }
   public FillableMatrix fill(int row_idx, int col_idx)  {
      return  fill(true, row_idx, col_idx);
   }
   public FillableMatrix fill(boolean is_filled, int row_idx, int col_idx)  {
      get(row_idx, col_idx, "col_idx", "row_idx").fill(is_filled);
      return  this;
   }
   public boolean isFilled(int row_idx, int col_idx)  {
      return  get(row_idx, col_idx, "col_idx", "row_idx").isFilled();
   }
   /**
    * Get a new double array of elements with a specific width and
    * height.
    * @param  width  May not be less than zero.
    * @param  height  May not be less than zero.
    * @return A
    * <br/>     <code>new FillableElement[width][height]</code>
    * Where each }, is an
    * {@linkplain FillableElement#isFilled() unfilled}
    * <code>FillableElement</code>, having
    * {@linkplain FillableElement#getColumnIndex() horizontal} and
    * {@linkplain FillableElement#getRowIndex() vertical} indexes
    * equivalent to its location in the array (vertical is the sub-array,
    * horizontal is the }, within that array).
    */
   public MatrixElement[][] getArrayFromWidthHeight(int height, int width)  {
      FillableElement[][] coords = null;
      try  {
         coords = new FillableElement[width][height];
      }  catch(ArrayIndexOutOfBoundsException ibx)  {
         throw  new ArrayIndexOutOfBoundsException("width=" + width + ", height=" +
            height);
      }

      for(int i = 0; i < coords.length; i++)  {
         for(int j = 0; j < coords[0].length; j++)  {
            coords[i][j] = new FillableElement(i, j);
         }
      }
      return  coords;
   }
   /**
    * @return  <CODE>(new {@link #FillableMatrix(FillableMatrix) FillableMatrix}(this))</CODE>
    */
   public FillableMatrix getObjectCopy()  {
      return  (new FillableMatrix(this));
   }
}

ElementLine.java

/*license*\
   XBN-Java: http://xbnjava.aliteralmind.com

   Copyright (C) 2014, Jeff Epstein (aliteralmind __DASH__ github __AT__ yahoo __DOT__ com)

   This software is dual-licensed under the:
   - Lesser General Public License (LGPL) version 3.0 or, at your option, any later version;
   - Apache Software License (ASL) version 2.0.

   Either license may be applied at your discretion. More information may be found at
   - http://en.wikipedia.org/wiki/Multi-licensing.

   The text of both licenses is available in the root directory of this project, under the names "LICENSE_lgpl-3.0.txt" and "LICENSE_asl-2.0.txt". The latest copies may be downloaded at:
   - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt
   - ASL 2.0: http://www.apache.org/licenses/LICENSE-2.0.txt
\*license*/
package  com.github.xbn.util.matrix;
   import  com.github.xbn.lang.IllegalArgumentStateException;
/**
 * <p>A set of contiguous elements in a matrix, going directly horizontal,
 * vertical, or forty-five degrees diagonal.</p>
 *
 * <p><i>TODO: Add function <code>doDiagonalsIntersectNotOverlap(ElementLine)</code></i></p>
 * @see MatrixDirection
 * @since  0.1.5
 * @author  Copyright (C) 2014, Jeff Epstein ({@code aliteralmind __DASH__ github __AT__ yahoo __DOT__ com}), dual-licensed under the LGPL (version 3.0 or later) or the ASL (version 2.0). See source code for details. <A HREF="http://xbnjava.aliteralmind.com">{@code http://xbnjava.aliteralmind.com}</A>, <A HREF="https://github.com/aliteralmind/xbnjava">{@code https://github.com/aliteralmind/xbnjava}</A>
 */
public class ElementLine  {
   private final DistanceDirection distDir;
   private final MatrixElement[] coords;
   private final BoundedMatrix matrix;
   /**
    * Create a new instance.
    * @param   matrix  May not be <code>null</code>. Get with
    * {@link #getMatrix()}{@code ()}.
    * @param   start_colIdx  The vertical index of the start-element.
    * Must be valid for <code>matrix.{@link BoundedMatrix#getRowCount() getHeight}()</code>
    * @param   start_rowIdx  The horizontal index of the start-element.
    * Must be valid for <code>matrix.{@link BoundedMatrix#getElementsInRowCount() getWidth}()</code>
    * @param   direction  The direction from the start-element the line
    * goes in. May not be <code>null</code>.
    * @param   length  The number of elements in the line.
    */
   public ElementLine(BoundedMatrix matrix, int start_colIdx, int start_rowIdx,
            MatrixDirection direction, int length)  {
      try  {
         coords = new MatrixElement[length];
      }  catch(ArrayIndexOutOfBoundsException abx)  {
         throw  new ArrayIndexOutOfBoundsException("length=" + length);
      }
      MatrixElement start = null;
      try  {
         start = matrix.get(start_colIdx, start_rowIdx,
            "start_colIdx", "start_rowIdx");
      }  catch(NullPointerException npx)  {
         throw  new NullPointerException("matrix");
      }
      coords[0] = start;
      MatrixElement current = start;
      for(int i = 1; i < length; i++)  {
         MatrixElement next = null;
         try  {
            next = matrix.moveNextDoor(current, direction, EdgeExceeded.CRASH);
         }  catch(IllegalArgumentException iax)  {
            throw  new IllegalArgumentStateException("matrix=" + matrix +
               ", start_colIdx=" + start_colIdx + ", start_rowIdx=" +
               start_rowIdx + ", direction=" + direction + ", length=" +
               length, iax);
         }
         coords[i] = next;
         current = next;
      }
      this.matrix = matrix;
      distDir = DistanceDirection.newForStartEnd(start, current);

      assert  (direction == distDir.getDirection()) : "direction (" + direction +
         ") does not equal DistanceDirection.newForStartEnd(" + start + ", " +
         current + ").getDirection() (" + distDir.getDirection() + ")";
   }
   /**
    * The number of elements in the line.
    * @return  {@code length} As provided to the {@linkplain #ElementLine(com.github.xbn.util.matrix.BoundedMatrix, int, int, com.github.xbn.util.matrix.MatrixDirection, int) constructor}.
    */
   public int getLength()  {
      return  coords.length;
   }
   /**
    * The matrix in which this line exists.
    * @return  {@code matrix} As provided to the {@linkplain #ElementLine(com.github.xbn.util.matrix.BoundedMatrix, int, int, com.github.xbn.util.matrix.MatrixDirection, int) constructor}.
    */
   protected BoundedMatrix getMatrix()  {
      return  matrix;
   }
   /**
    * The direction in which the line goes, starting from the initial
    * element.
    * @return  As created in the constructor {@linkplain #ElementLine(com.github.xbn.util.matrix.BoundedMatrix, int, int, com.github.xbn.util.matrix.MatrixDirection, int) constructor}.
    */
   public DistanceDirection getDistDir()  {
      return  distDir;
   }
   /**
    * Get the n-th element in this line.
    * @param   index  Must be valid given {@link #getLength()}{@code ()}.
    * @return  The {@code index}-th element in this line, starting with the
    * initial element, and going in
    * <code>{@link #getDistDir()}.{@link DistanceDirection#getDirection() getDirection}()</code>
    */
   public MatrixElement get(int index)  {
      try  {
         return  coords[index];
      }  catch(ArrayIndexOutOfBoundsException ibx)  {
         throw  new ArrayIndexOutOfBoundsException("index=" + index +
            ", getLength()=" + getLength());
      }
   }
   /**
    * <p>Get the first index in <i>{@code this}</i> line whose element has the
    * same coordinates as an element in another line.</p>
    *
    * <p>Note this does not detect two diagonal lines that <i>intersect but do not overlap</i>. See the TODO at the top of this class.</p>
    * @param   line  May not be <code>null</code>
    * @return  {@code -1} if no elements overlap. Otherwise the first index
    * that overlaps one element in {@code line}.
    */
   public int getFirstOverlappingIndex(ElementLine line)  {
      for(int i = 0; i < line.getLength(); i++)  {
         for(int j = 0; j < getLength(); j++)  {
            MatrixElement gcFromParam = line.get(i);
            if(gcFromParam.equals(get(j)))  {
               return  j;
            }
         }
      }
      return  -1;
   }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s