By starting at the top of the triangle, move to adjacent numbers on the row below. On moving down to the below node, choose higher number. Produce the sum of the route.
e.g.
6
7 8
6 5 12
9 8 10 6
The route should be 6 -> 8 -> 12 -> 10. So the sum of the route is 40.
簡単な問題なので，たウォーミングアップ程度には丁度よいかと思われる．
ヒント
三角形を一次元のリストにマップして，インデックスをスライドさせていく．
三角形の格段の要素数は x(n)=n．
解答
import org.apache.commons.io.FileUtils;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class TrianglePuzzle {
private static final String SEPARATOR = " ";
private final File puzzleFile;
public TrianglePuzzle( final String fileName ) throws IOException {
this.puzzleFile = new File( TrianglePuzzle.class.getClassLoader().getResource( fileName ).getFile() );
if( !puzzleFile.exists() || !puzzleFile.isFile() || puzzleFile.length() == 0 )
throw new IOException( "File must be file with proper content" );
}
public long calc() throws IOException {
Stack<Long> trace = new Stack<Long>();
List<Long> vals = parse();
int step = 0;
int sel = 0;
int stepTotal = 0;
int val = 0;
long lval = 0;
long rval = 0;
// step 1 is automatically first item
trace.push( vals.get( 0 ) );
stepTotal += ++step;
// step 2 - N .. only adjacent numbers are checked
while( stepTotal != vals.size() ) {
lval = vals.get( stepTotal + sel );
rval = vals.get( stepTotal + sel + 1 );
System.out.println( lval + "," + rval );
sel = lval > rval ? sel : sel + 1;
System.out.println( vals.get( stepTotal + sel ) + " picked." );
trace.push( vals.get( stepTotal + sel ) );
System.out.println( "stepTotal=" + ( stepTotal ) );
stepTotal += ++step;
}
// With Java8 code should be like return trace.stream().sum()
Iterator<Long> iter = trace.iterator();
int total = 0;
while( iter.hasNext() ) {
total += iter.next();
}
return total;
}
final List<Long> parse() throws IOException {
List<Long> vals = new ArrayList<Long>();
BufferedReader br = new BufferedReader( new InputStreamReader( new FileInputStream( puzzleFile ) ) );
String line = null;
while( ( line = br.readLine() ) != null ) {
StringTokenizer st = new StringTokenizer( line, SEPARATOR );
while( st.hasMoreTokens() ) {
vals.add( Long.parseLong(st.nextToken()) );
}
}
return vals;
}
public static void main( String args[] ) throws IOException {
if( args.length != 1 ) {
System.out.println( "arg length must be 1" );
System.exit( 0 );
}
TrianglePuzzle tp = new TrianglePuzzle( args[ 0 ] );
}
}
