Problem
I have come up with a Java 8 solution for the following problem:
In the 20×20 grid below, four numbers along a diagonal line have been marked in red (bold here).
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 48The 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?
I would comments on everything:
public class Problem11 extends Problem<Integer> {
/** The n of the n x n grid. */
private final int n;
/** The grid. */
private final Grid grid;
/**
* Constructs this class.
*
* @param n The n of the n x n grid
* @param gridString The String representation of the grid
*/
public Problem11(final int n, final String gridString) {
this.n = n;
this.grid = new Grid(n, gridString);
}
@Override
public void run() {
List<Integer> list = new ArrayList<>(n * n * 8);
grid.forEach(cell -> processCell(list, cell));
result = list.stream().mapToInt(x -> x).max().getAsInt();
}
/**
* Processes a cell and adds the result to a list.
*
* @param list The list of results
* @param cell The cell to consider
*/
private void processCell(final List<Integer> list, final Cell cell) {
IntBinaryOperator sumOperator = (x, y) -> x * y;
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y, sumOperator)); //right
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y, sumOperator)); //left
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x, y -> y + 1, sumOperator)); //top
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x, y -> y - 1, sumOperator)); //down
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y + 1, sumOperator)); //topright
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y - 1, sumOperator)); //downleft
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y - 1, sumOperator)); //downright
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y + 1, sumOperator)); //topleft
}
/**
* Adds an integer to the list if the OptionalInt is not empty.
*
* @param list The list to be added to
* @param optionalInt The OptionalInt
* @return The input list, with possibly the element appended
*/
private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
if (!optionalInt.isPresent()) {
return list;
}
list.add(optionalInt.getAsInt());
return list;
}
/**
* Returns a calculation on the cell.
*
* @param cell The starting cell
* @param steps The number of steps to take to other cells
* @param steppingXOperator The operator to apply to go to the next cell on x
* @param steppingYOperator The operator to apply to go to the next cell on y
* @param calculationOperator The operator to apply to get the result
* @return An OptionalInt instance that is empty if and only if the calculation did not work
*/
private OptionalInt calculationOnCell(final Cell cell, final int steps, final IntUnaryOperator steppingXOperator, final IntUnaryOperator steppingYOperator, final IntBinaryOperator calculationOperator) {
int x = cell.x;
int y = cell.y;
int calculationResult = cell.value;
for (int i = 0; i < steps; i++) {
x = steppingXOperator.applyAsInt(x);
y = steppingYOperator.applyAsInt(y);
if (!grid.inBounds(x, y)) {
return OptionalInt.empty();
}
calculationResult = calculationOperator.applyAsInt(calculationResult, grid.getCell(x, y).value);
}
return OptionalInt.of(calculationResult);
}
@Override
public String getName() {
return "Problem 11";
}
/**
* Structure holding the cells.
*/
private static class Grid implements Iterable<Cell> {
/** The n of the n x n grid. **/
private final int n;
/** A double array holding the cells. **/
private final Cell[][] cells;
/**
* Constructs the Grid.
*
* @param n The n of the n x n grid
* @param input The String input for the grid
*/
public Grid(final int n, final String input) {
this.n = n;
this.cells = createCellsFromString(input);
}
/**
* Creates the Cell double array from the String input.
*
* @param input The string nput
* @return The cell double array
*/
private Cell[][] createCellsFromString(final String input) {
Cell[][] returnCells = new Cell[n][n];
String[] lines = input.split("\n");
for (int i = 0; i < lines.length; i++) {
String[] words = lines[i].split(" ");
for (int j = 0; j < words.length; j++) {
String word = words[j];
returnCells[i][j] = new Cell(i, j, Integer.parseInt(word));
}
}
return returnCells;
}
/**
* Checks if the x and y are in bounds.
*
* @param x The x to be tested
* @param y The y to be tested
* @return Whether x and y are in bounds
*/
public boolean inBounds(final int x, final int y) {
return (0 <= x && x < n && 0 <= y && y < n);
}
/**
* Returns a cell based on the coordinates.
*
* Throws an IllegalArgumentException if the x and y coordinates are not in bounds
*
* @param x The x coordinate
* @param y The y coordinate
* @return The cell corresponding to the coordinate
*/
public Cell getCell(final int x, final int y) {
if (!inBounds(x, y)) {
throw new IllegalArgumentException("problems.Problem11.Grid.getCell: !inBounds(x, y): x = " + x + " / y = " + y);
}
return cells[x][y];
}
@Override
public Iterator<Cell> iterator() {
return new Iterator<Cell>() {
/** The current x of the iterator. **/
private int x = 0;
/** The current y of the iterator. **/
private int y = 0;
@Override
public boolean hasNext() {
return !(x == n && y == 0);
}
@Override
public Cell next() {
Cell cell = cells[x][y];
advance();
return cell;
}
/**
* Advanced to the next element in the cell double array.
*/
private void advance() {
y++;
if (y == n) {
y = 0;
x++;
}
}
};
}
}
/**
* Structure holding the cell data.
*/
private static class Cell {
/** The x coordinate of the cell. **/
public final int x;
/** The y coordinate of the cell. **/
public final int y;
/** The value of the cell. **/
public final int value;
/**
* Constructs the Cell.
*
* @param x The x coordinate of the cell
* @param y The y coordinate of the cell
* @param value The value of the cell
*/
public Cell(final int x, final int y, final int value) {
this.x = x;
this.y = y;
this.value = value;
}
}
}
public abstract class Problem<T> implements Runnable {
protected T result;
public String getResult() {
return String.valueOf(result);
}
abstract public String getName();
}
The code gets called by something along the lines of:
Problem<?> problem11 = new Problem(20,
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08n" +
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00n" +
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65n" +
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91n" +
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80n" +
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50n" +
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70n" +
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21n" +
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72n" +
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95n" +
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92n" +
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57n" +
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58n" +
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40n" +
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66n" +
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69n" +
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36n" +
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16n" +
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54n" +
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48");
problem11.run();
System.out.println(problem11.getResult());
One additional question I have about the code:
- Is it possible to write the code for the maximum-evaluation such that it does not use storage (ie. the
list), nor uses handwritten code for calculating the sum? I don’t know whether such thing would be possible with anIntStreamfor example.
Solution
Your code looks great and I can see that you have put some thought and time into it. Also, you’ve used pretty fancy concepts that I didn’t know (which is not so hard as my Java is pretty rusty). However, it looks slightly over-engineered to me so I’ll try to make things more simple.
- Don’t mess with anyone’s brain
IntBinaryOperator sumOperator = (x, y) -> x * y; : calling sum a product is one of the most confusing thing you could possibly do :-).
In many places, things could have been done in a more straightforward way.
- First example :
addIfNotEmpty
You don’t need to have two return doing the same thing in :
private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
if (!optionalInt.isPresent()) {
return list;
}
list.add(optionalInt.getAsInt());
return list;
}
It could easily be written :
private List<Integer> addIfNotEmpty(final List<Integer> list, final OptionalInt optionalInt) {
if (optionalInt.isPresent()) {
list.add(optionalInt.getAsInt());
}
return list;
}
- Second example :
n
Your Problem11 class has a private final int n and a Grid.
Your Grid has a private final int n; and an Array.
An Array has a length attribute.
Do you see the pattern here ? Good news is that you are considering squares because if we were to have 2 dimensions here, it would probably be a mess.
This shows some kind of problem with your design. Maybe you should rely on the length attribute whenever you need to, maybe you shouldn’t even need to (cf Leaky Abstraction).
- Third example :
Cell
Your Cell is a structure containing a value and its coordinates in an array of Cells. This reminds me of one of the examples in the “Stop Writing Classes ” presentation and I have the feeling that we don’t really need it.
I have no time to go on right now. I’ll try to edit my answers and provide a working piece of code. In the meantime, as you have solved the Project Euler already, I suggest you have a look at the solutions posted on the boards. They are a great way to learn about algorithms, math and programming style as well.
You are doing twice as much work as you need to…. you fell in to ‘the trap’ of making the code follow the instructions, without thinking about the implications of the instructions.
In the grid:
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16
The right-to-left product is going to be the same as the left-to-right product, top to bottom will be the same as the bottom to top, etc. There is no need to calculate all the values in both directions. All you need is to track the maximum… Comment out the lines:
private void processCell(final List<Integer> list, final Cell cell) {
IntBinaryOperator sumOperator = (x, y) -> x * y;
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y, sumOperator)); //right
//addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y, sumOperator)); //left
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x, y -> y + 1, sumOperator)); //top
//addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x, y -> y - 1, sumOperator)); //down
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y + 1, sumOperator)); //topright
//addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y - 1, sumOperator)); //downleft
//addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x + 1, y -> y - 1, sumOperator)); //downright
addIfNotEmpty(list, calculationOnCell(cell, 3, x -> x - 1, y -> y + 1, sumOperator)); //topleft
}
I agree with other comments, your naming for the product methods as add and sum is very confusing….