Package net.n1da.dev.euler

Class PE0018

java.lang.Object

net.n1da.dev.euler.core.Problem

net.n1da.dev.euler.PE0018

All Implemented Interfaces:

Solvable

Direct Known Subclasses:

PE0067

public class PE0018
extends Problem

Solution for problem 18 "Maximum path sum I" completed on Sat, 16 May 2015, 21:14.

Since:

16.05.2015 06:18:58

Author:

Nico Danneberg

See Also:

Problem @ Project Euler, Solution @ Ni-Da-Net

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.ArrayList<java.lang.Integer[]>	data	The storage for the triangle data.

Fields inherited from class net.n1da.dev.euler.core.Problem

number, title

Constructor Summary

Constructors

Modifier	Constructor	Description
	PE0018()	A simple constructor to set number and title.
protected	PE0018(int num, java.lang.String tit)	A simple base constructor to set the given Problem.number and Problem.title.

Method Summary

Modifier and Type	Method	Description
void	prepare()	Here the triangle data is initialized, e.g. by reading from a file.
java.lang.String	solve()	Finds the path with the biggest sum of all elements through the data triangle.
protected java.lang.Integer[]	sumTriangleRows(java.lang.Integer[] row1, java.lang.Integer[] row2)	Sums the elements of two given triangle rows.

Methods inherited from class net.n1da.dev.euler.core.Problem

finish, getResult, getRuntime, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

data

protected java.util.ArrayList<java.lang.Integer[]> data

The storage for the triangle data.

Constructor Detail

PE0018

protected PE0018(int num,
                 java.lang.String tit)

A simple base constructor to set the given Problem.number and Problem.title. In this special case it's needed for inheritance to PE0067.

Parameters:

num - - the number of this problem

tit - - the title of this problem

PE0018

public PE0018()

A simple constructor to set number and title.

Method Detail

prepare

public void prepare()

Here the triangle data is initialized, e.g. by reading from a file.

Specified by:

prepare in interface Solvable

Overrides:

prepare in class Problem

See Also:

IO.readTriangle(String)

solve

public java.lang.String solve()

Finds the path with the biggest sum of all elements through the data triangle. Therefore all rows are added to each one after another.

Returns:

the "longest" path (maximum sum)

See Also:

sumTriangleRows(Integer[], Integer[])

sumTriangleRows

protected java.lang.Integer[] sumTriangleRows(java.lang.Integer[] row1,
                                              java.lang.Integer[] row2)

Sums the elements of two given triangle rows. Since there are two results for an element of the resulting row, it stores the maximum of both sums.

Parameters:

row1 - the upper row of a triangle that is one element smaller than the row below

row2 - the lower row that follows directly the first given row

Returns:

a row with the maximum sum of each pair of elements