001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006import java.util.*;
007
008/**
009 * Solution for problem 18
010 * "<strong>Maximum path sum I</strong>"
011 * completed on Sat, 16 May 2015, 21:14.
012 * 
013 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
014 * @since 16.05.2015 06:18:58
015 * 
016 * @see <a href="https://projecteuler.net/problem=18" target="_blank">Problem @ Project Euler</a>
017 * @see <a href="http://n1da.net/specials/projekt-euler/problem-18-maximale-summe-eines-pfades-i/" target="_top">Solution @ Ni-Da-Net</a>
018 */
019public class PE0018 extends Problem {
020
021        /**
022         * The storage for the triangle data.
023         */
024        protected ArrayList< Integer[] > data;
025        
026        /**
027         * A simple base constructor to set the given {@link #number}
028         * and {@link #title}. In this special case it's needed for
029         * inheritance to {@link PE0067}.
030         * 
031         * @param num - the number of this problem
032         * @param tit - the title of this problem
033         */
034        protected PE0018( int num, String tit ) {
035                super( num, tit );
036        }
037        
038        /**
039         * A simple constructor to set {@link Problem#number number}
040         * and {@link Problem#title title}.
041         */
042        public PE0018() {
043                this( 18, "Maximum path sum I" );
044        }
045
046        /**
047         * Here the triangle data is initialized, e.g. by reading from a file.
048         * 
049         * @see IO#readTriangle(String)
050         */
051        @Override
052        public void prepare() {
053                super.prepare();
054                
055                /*** Test Data ***
056                 * 
057                data = new ArrayList< Integer[] >();
058                data.add( new Integer[]{ 3 } );
059                data.add( new Integer[]{ 7, 4 } );
060                data.add( new Integer[]{ 2, 4, 6 } );
061                data.add( new Integer[]{ 8, 5, 9, 3 } );
062                 */
063                
064                data = IO.readTriangle( "data-files/triangle-15rows.txt" );
065        }
066        
067        /**
068         * Finds the path with the biggest sum of all elements through the
069         * {@link #data} triangle. Therefore all rows are added to each one
070         * after another.
071         * 
072         * @return the "longest" path (maximum sum)
073         * @see #sumTriangleRows(Integer[], Integer[])
074         */
075        @Override
076        public String solve() {
077
078                Integer[] cur = sumTriangleRows( data.get( 0 ), data.get( 1 ) );
079                for( int i=2; i<data.size(); i++ ) 
080                        cur = sumTriangleRows( cur, data.get( i ) );
081                
082                Arrays.sort( cur );
083                
084                return IO.i2s( cur[ cur.length-1 ] );
085        }
086        
087        /**
088         * Sums the elements of two given triangle rows. Since there are two
089         * results for an element of the resulting row, it stores the maximum
090         * of both sums.
091         * 
092         * @param row1 the upper row of a triangle that is one element smaller
093         * than the row below 
094         * @param row2 the lower row that follows directly the first given row
095         * @return a row with the maximum sum of each pair of elements
096         */
097        protected Integer[] sumTriangleRows( Integer[] row1, Integer[] row2 ) {
098                int len = row2.length;
099                Integer[] result = new Integer[ len ];
100                
101                result[ 0 ] = row1[ 0 ] + row2[ 0 ];
102                
103                for( int i=1; i<len-1; i++ )
104                        result[ i ] = row2[ i ] + ( ( row1[ i-1 ] > row1[ i ] ) ? row1[ i-1 ] : row1[ i ] );
105                
106                result[ len-1 ] = row1[ len-2 ] + row2[ len-1 ];
107                
108                return result;
109        }
110}