# Project Euler #18 - Max path in a triangle

I've been learning Java for the past 6 months online and haven't had anyone review my code before. I'm worried that I may be making lots of beginner mistakes and was wondering if anyone could point out any ideas on how to make the code more OO.

The class is instantiated from the main and all relevant code is here except for validation methods which are in super. My use of the constructor concerns me, but I don't see an obvious alternative, because my main will become a beast if I put the procedural stuff for 30 classes in there. Overall, the code feels pretty procedural, and a bit spaghetti. (moreso in this example than many, the interrelated triangles don't lend themselves to being black box)

Anyways, ideas, suggestions?

/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

package projecteuler;

/**
*
* @author Rar Rarr
*/
public class Problem18 extends Problems implements TalkNice{

private boolean useDefaultTriangle = false;
private int triangleSize;
private int [] triangle [];
private String [] pathingTriangle [];
private int[] printingTriangle[];
private String pathingInformation = new String();

Problem18(){
explainProblem();
useDefaultTriangle();
if(!useDefaultTriangle){
inputTriangleSize();
createPathingTriangle();
calculatePath(createTriangle());
}
else{
createPathingTriangle();
calculatePath(createDefaultTriangle());
}
printTriangle(triangle);
}

@Override
public final void explainProblem() {
System.out.println("By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.");
System.out.println("");
System.out.println("");
System.out.println("              3");
System.out.println("             7 4");
System.out.println("            2 4 6");
System.out.println("           8 5 9 3");
System.out.println("");
System.out.println("");
System.out.println("That is, 3 + 7 + 4 + 9 = 23.");
System.out.println("Find the maximum total from top to bottom of the triangle below:");
System.out.println("");
System.out.println("");
System.out.println("                                75");
System.out.println("                              95  64");
System.out.println("                            17  47  82");
System.out.println("                          18  35  87  10");
System.out.println("                        20  04  82  47  65");
System.out.println("                      19  01  23  75  03  34");
System.out.println("                    88  02  77  73  07  63  67");
System.out.println("                  99  65  04  28  06  16  70  92");
System.out.println("                41  41  26  56  83  40  80  70  33");
System.out.println("              41  48  72  33  47  32  37  16  94  29");
System.out.println("            53  71  44  65  25  43  91  52  97  51  14");
System.out.println("          70  11  33  28  77  73  17  78  39  68  17  57");
System.out.println("        91  71  52  38  17  14  91  43  58  50  27  29  48");
System.out.println("      63  66  04  68  89  53  67  30  73  16  69  87  40  31");
System.out.println("    04  62  98  27  23  09  70  98  73  93  38  53  60  04  23");
}

private void useDefaultTriangle() {
useDefaultTriangle = verifyBooleanChoice("use the default triangle?");
if (useDefaultTriangle){
triangleSize = 15;
}
}

private void inputTriangleSize() {
triangleSize = verifyPositiveInt("size of the triangle you would like to create.", 999);
}

private int[][] createTriangle() {
triangle = new int[triangleSize][];
printingTriangle = new int[triangleSize][];
for (int y = 0; y < triangle.length; y++){                              //creates y axis
int [] xAxis = new int[triangle.length - y];                        //inserts arrays of decreasing length.
int [] xAxis2= new int[triangle.length - y];
for (int x = 0; x < xAxis.length; x++){
xAxis[x] = (int) (Math.random() * 100);
}
System.arraycopy(xAxis, 0, xAxis2, 0, xAxis.length);
triangle[y] = xAxis;                                                //path found by summing paths from bottom to top, this triangle will be used to aggregate sums upwards
printingTriangle[y] = xAxis2;                                       //this is a copy of triangle which will be used for printing.  the other triangle is destroyed in the calculation process.
}
return triangle;
}

private void printTriangle (int[][] triangle){

int widthOfPrinting = triangle.length * 4 - 2;                          //width that all rows need to print out to keep a good triangle shape.

for (int y = triangle.length - 1; y >=0; y--) {                         //iterates from top to bottom.
int widthOfThisLine = (triangle.length - y) * 4 - 2;
int leadingSpaces = (widthOfPrinting - widthOfThisLine) / 2;        //number of space that need to be inserted to print it out in the middle.
for (int spaces = 0; spaces < leadingSpaces; spaces++){
System.out.print(" ");
}
for (int x = 0; x < triangle[y].length; x++) {
int pise = 3 * (triangle.length - (y + 1));                     //pise stands for Pathing Information Substring Extractor.
int pathed = Integer.parseInt(pathingInformation.substring(pise, pise + 3));//it extracts the 3-digit x-axis value of the path @ y from the String pathingInformation
if (x == pathed){
System.out.printf("*%02d*", printingTriangle[y][x]);
}
else{
System.out.printf(" %02d ", printingTriangle[y][x]);        //prints from left to right.
}
}
System.out.println("");
}
}

private int[][] createDefaultTriangle() {
triangle = new int[triangleSize][];
printingTriangle = new int[triangleSize][];

int[]yEquals0 = new int[]{4,62,98,27,23,9,70,98,73,93,38,53,60,4,23};
int[]yEquals0Print = new int[]{4,62,98,27,23,9,70,98,73,93,38,53,60,4,23};
int[]yEquals1 = new int[]{63,66,4,68,89,53,67,30,73,16,69,87,40,31};
int[]yEquals1Print = new int[]{63,66,4,68,89,53,67,30,73,16,69,87,40,31};
int[]yEquals2 = new int[]{91,71,52,38,17,14,91,43,58,50,27,29,48};
int[]yEquals2Print = new int[]{91,71,52,38,17,14,91,43,58,50,27,29,48};
int[]yEquals3 = new int[]{70,11,33,28,77,73,17,78,39,68,17,57};
int[]yEquals3Print = new int[]{70,11,33,28,77,73,17,78,39,68,17,57};
int[]yEquals4 = new int[]{53,71,44,65,25,43,91,52,97,51,14};
int[]yEquals4Print = new int[]{53,71,44,65,25,43,91,52,97,51,14};
int[]yEquals5 = new int[]{41,48,72,33,47,32,37,16,94,29};
int[]yEquals5Print = new int[]{41,48,72,33,47,32,37,16,94,29};
int[]yEquals6 = new int[]{41,41,26,56,83,40,80,70,33};
int[]yEquals6Print = new int[]{41,41,26,56,83,40,80,70,33};
int[]yEquals7 = new int[]{99,65,4,28,6,16,70,92};
int[]yEquals7Print = new int[]{99,65,4,28,6,16,70,92};
int[]yEquals8 = new int[]{88,2,77,73,7,63,67};
int[]yEquals8Print = new int[]{88,2,77,73,7,63,67};
int[]yEquals9 = new int[]{19,1,23,75,3,34};
int[]yEquals9Print = new int[]{19,1,23,75,3,34};
int[]yEquals10 = new int[]{20,4,82,47,65};
int[]yEquals10Print = new int[]{20,4,82,47,65};
int[]yEquals11 = new int[]{18,35,87,10};
int[]yEquals11Print = new int[]{18,35,87,10};
int[]yEquals12 = new int[]{17,47,82};
int[]yEquals12Print = new int[]{17,47,82};
int[]yEquals13 = new int[]{95,64};
int[]yEquals13Print = new int[]{95,64};
int[]yEquals14 = new int[]{75};
int[]yEquals14Print = new int[]{75};
for(int y =1; y <=triangle.length; y++){
switch (y){
case 1: triangle[y - 1] = yEquals0;
printingTriangle[y - 1] = yEquals0Print;
break;
case 2: triangle[y - 1] = yEquals1;
printingTriangle[y - 1] = yEquals1Print;
break;
case 3: triangle[y - 1] = yEquals2;
printingTriangle[y - 1] = yEquals2Print;
break;
case 4: triangle[y - 1] = yEquals3;
printingTriangle[y - 1] = yEquals3Print;
break;
case 5: triangle[y - 1] = yEquals4;
printingTriangle[y - 1] = yEquals4Print;
break;
case 6: triangle[y - 1] = yEquals5;
printingTriangle[y - 1] = yEquals5Print;
break;
case 7: triangle[y - 1] = yEquals6;
printingTriangle[y - 1] = yEquals6Print;
break;
case 8: triangle[y - 1] = yEquals7;
printingTriangle[y - 1] = yEquals7Print;
break;
case 9: triangle[y - 1] = yEquals8;
printingTriangle[y - 1] = yEquals8Print;
break;
case 10: triangle[y - 1] = yEquals9;
printingTriangle[y - 1] = yEquals9Print;
break;
case 11: triangle[y - 1] = yEquals10;
printingTriangle[y - 1] = yEquals10Print;
break;
case 12: triangle[y - 1] = yEquals11;
printingTriangle[y - 1] = yEquals11Print;
break;
case 13: triangle[y - 1] = yEquals12;
printingTriangle[y - 1] = yEquals12Print;
break;
case 14: triangle[y - 1] = yEquals13;
printingTriangle[y - 1] = yEquals13Print;
break;
case 15: triangle[y - 1] = yEquals14;
printingTriangle[y - 1] = yEquals14Print;
break;
}
}
return triangle;
}

private void createPathingTriangle() {
pathingTriangle = new String[triangleSize][];

for (int y = 0; y < pathingTriangle.length; y++){
String[] xAxis = new String[pathingTriangle.length - y];
for (int x = 0; x < pathingTriangle.length - y; x++){               //gives each x value the value of its  x axis array index.
if (x < 10){
xAxis[x] = "00" + String.valueOf(x);
}
else if (x < 100){
xAxis[x] = "0" + String.valueOf(x);
}
else{
xAxis[x] = String.valueOf(x);
}
pathingTriangle[y] = xAxis;
}
}
}

private void calculatePath(int[][] triangle) {

for (int y = 1; y < triangle.length; y++){

for (int x = 0; x < triangle.length - y; x++ ){
if (triangle[y - 1][x] > triangle [y - 1][x + 1]){
triangle [y][x] += triangle [y - 1][x];
pathingTriangle[y][x] = pathingTriangle[y][x].concat(pathingTriangle[y - 1][x]);
}
else {
triangle [y][x] += triangle [y - 1][x + 1];
pathingTriangle[y][x] = pathingTriangle[y][x].concat(pathingTriangle[y - 1][x + 1]);
}
}
}
pathingInformation = pathingTriangle[pathingTriangle.length - 1][0];
}

private String arrayIndexToString(int x){

if (x < 10){
String str = new String("00" + String.valueOf(x));
return str;
}
else if (x < 100){
String str = new String("0" + String.valueOf(x));
return str;
}
else{
String str = new String(String.valueOf(x));
return str;
}
}
}

-
You should try to have a more relevant title. Your title should be brief explanation of your code. You should a description of what the problem 18 is. (Sorry for the edit I conflicted with! ) –  Marc-Andre Sep 3 at 13:16

Just some points about the general structure, and a couple of smaller things that I noticed:

## OOP

Constructor and general OOP

My use of the constructor concerns me, but I don't see an obvious alternative

Yes, it does seem a little odd. The constructor should only construct an object. Yours already solves the problem.

I would at least pull out explainProblem and the problem solving code (createPathingTriangle, calculatePath, printTriangle) to a method called solveProblem defined in Problems. Printing the solution could also be extracted, as it is a different activity from solving the problem.

Does verifyPositiveInt get user input? If so, that should also be pulled out of the constructor. Ideally, you would create a new interface that retrieves user input, instead of having Problems handle it.

You might also create an Output interface, so your code doesn't hardcode System.out.println. That way, you could easily switch to eg writing to a file.

It doesn't really make your main too big. It would look like this:

    Problem18 problem18 = new Problem18();
problem18.explainProblem();
problem18.applyUserInput(new ConsoleInput());
problem18.solveProblem();
problem18.printSolution(new ConsoleOutput());


It has the advantage that you can easily only explain the problem or only solve the problem. And if you are worrying about a too big main method, extract that code into a function, so every problem becomes a one-liner.

Triangle

You might also consider creating a Triangle class. Right now, the responsibility for maintaining a printable triangle is mixed in with the general code. Your code might be easier to read if this functionality was extracted.

## Other

createDefaultTriangle

Your for - switch seems entirely unneeded here. Just assign the values directly:

triangle[0] = new int[]{4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23};


Also, if you were using the switch, start with y = 0, that way you don't need to subtract 1 from y everywhere.

Using String constructor

Don't use the String constructor. Instead of

String str = new String("00" + String.valueOf(x));


write

String str = "00" + String.valueOf(x);


unnecessary temporary variables

You don't need to save values to a variable if you return them directly afterwards. Instead of

String str = "00" + String.valueOf(x);
return str;


write

return "00" + String.valueOf(x);


Spaces when using an Array

This:

triangle [y][x] += triangle [y - 1][x];


Looks odd to me. The standard would be to not use spaces:

triangle[y][x] += triangle[y - 1][x];


Magic Numbers

Don't hardcode special numbers. Instead, define them in a field with a proper name. For example, what is the significance of 4 - 2? The code doesn't tell me, but a properly named field might.

Define variables where they are used

For example, you are defining xAxis2 before a for loop, but it isn't used until after that loop. Move the definition to where it is actually used.

While some methods such as explainProblem don't necessarily need a comment, the entire class should have one (stating what the problem is), and most other methods should have one as well.

Fields should also have a comment. For example, what is the difference between triangle, pathingTriangle, printingTriangle, and pathingInformation? Ideally, anyone reading your code has at least a good idea what these variables will be used for without first understanding all your code.

Inside methods, I would put more comments (but I sometimes like to write too many comments, so take it with a grain of salt). For example, why does y start at 1 instead of 0 in calculatePath? What does the y switch do in createDefaultTriangle, etc?

Also, the comments you do have start very far to the right. I would place them above the code they are commenting (otherwise, some people might have to scroll to read them).

-
Thanks, bro. Read this like 5 times, will consider how to incorporate 1. a private Triangle class (reuse for all three triangles?) 2. a use default option as an interface which chooses between 2 constructors, one with default Euler settings, and one with user supplied settings. 3. taking the solving/printing of the problem out of the constructor and into a solve function called from main just so it's not so odd =P –  stravinsky7 Sep 3 at 16:37
Also, both of you mentioned using a more general output to be handled by an output interface. I will look into that. –  stravinsky7 Sep 3 at 16:50
String.valueOf() is unnecessary. return "00" + x will do. –  200_success Sep 3 at 17:47
• I see some good things in your code that I'm really happy to see. You've made a Problem class every specific challenge can use.
• Without much information, I really wonder what a TalkNice interface is suppose to do.
• private int [] triangle []; using [] at two different place to indicate a two dimensional array is misleading. Use the more conventional private int [][] triangle for multidimensional array.
• int[]yEquals0 = new int[]{...}; you don't need the new int [] here, since your array is already declared. Just used int[]yEquals0 = {...}.

Now let's take explainProblem. It's a good idea to separate concern like this. But your explanation of the problem is now dependant of System.out. What if you need to use something else like a GUI or write to a file ? You will need to change all the implementation of explainProblem. That's exactly what we don't want to happen. What are you're option ? I would suggest that explainProblem would change to something in the line of getProblemDescription where you return a String or a format fitting for presentation.

-
I didn't like the int[] triangle[] code either (will rewrite with int[][]triangle), but as far as i could find, the double brackets are required to declare it as a two dimensional array? (otherwise it's an array that just holds ints, not arrays of them?) –  stravinsky7 Sep 3 at 16:58
@stravinsky7 This is my bad, I will fix my answer. Indeed , if it's a two dimensional array you need [][]. I was certain it was a double indication that triangle was an array, which I was finding odd and non obvious. One important lesson here is, when you're following "standard", the code is easier to read easily. –  Marc-Andre Sep 3 at 17:07
What is a flexible solution then? I can make the explanation consist of Strings, and println them, but I'm wondering if there's a convention for doing it. The same for the output.. Is there a more advanced technique you would recommend, such as putting them all in a file and reading lines from it or somesuch? Really to make the code flexible, I need to know more i/o because otherwise I don't know what I'm leaving flexibility for :| (where or how to leave it). Makes me want to learn some swing or javafx. –  stravinsky7 Sep 5 at 4:09
It's not that important if you a String or a file that you read, since it's an implementation details. If you have a GUI, is it important if the text is in a class or a file? No since you will have a String and both a GUI and a console know how to format that. A GUI don't know how to take what System.out is outputting to show it itself, that is what you need to achieve. For your particular case , I would say keep it simple. What would be the most useful, having a file with all the description or each class to have it in a String directly (it's an open question there is no wrong answer) –  Marc-Andre Sep 5 at 12:51