README.md

Requirements

• Java 8

Generate track

wget https://gist.githubusercontent.com/trautonen/9595293/raw/TrackGenerator.java
javac TrackGenerator.java
java TrackGenerator /tmp/track.txt 10000

Solve track

wget https://gist.githubusercontent.com/trautonen/9595293/raw/OutRunStream.java
javac OutRunStream.java
java OutRunStream /tmp/track.txt

OutRunStream.java

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class OutRunStream {

    public static Integer solve(BufferedReader reader) throws IOException {
        Pattern separator = Pattern.compile("\\s+");
        String seed = reader.readLine();
        List<Integer> reduced = reader.lines()
                .map(String::trim)
                .filter(line -> !line.isEmpty())
                .map(line -> separator.splitAsStream(line))
                .map(tokens -> tokens.map(Integer::parseInt).collect(Collectors.toList()))
                .reduce(Collections.emptyList(), OutRunStream::reduce);
        Integer result = Collections.max(reduced);
        System.out.println(seed);
        System.out.println("# result: " + result);
        return result;
    }
    
    private static List<Integer> reduce(List<Integer> accumulator, List<Integer> row) {
        List<Integer> reduced = Arrays.asList(new Integer[row.size()]);
        for (int i = 0; i < row.size(); i++) {
            int left = 0;
            int right = 0;
            if (i != accumulator.size()) {
                left = accumulator.get(i);
            }
            if (i != 0) {
                right = accumulator.get(i - 1);
            }
            reduced.set(i, row.get(i) + Math.max(left, right));
        }
        return reduced;
    }
    
    public static void main(String[] args) {
        try (BufferedReader reader = Files.newBufferedReader(Paths.get(args[0]))) {        
            long start = System.currentTimeMillis();
            solve(reader);
            long end = System.currentTimeMillis();
            System.out.println("# execution duration: " + (end - start) + "ms");
        } catch (final IOException ex) {
            throw new RuntimeException(ex);
        }
    }
}

TrackGenerator.java

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Writer;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Optional;
import java.util.Random;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.IntStream;

public class TrackGenerator {

    private static final int DEFAULT_SIZE = 1000;
    private static final int RANDOM_BOUND = 100;
    private static final Charset FILE_CHARSET = Charset.forName("UTF-8");
    private static final OpenOption[] FILE_OPTIONS = new OpenOption[] {
            StandardOpenOption.CREATE,
            StandardOpenOption.TRUNCATE_EXISTING,
            StandardOpenOption.WRITE
    };
    
    public void generate(String path, Optional<Integer> size, Optional<Long> seed) {
        int limit = size.orElse(DEFAULT_SIZE);
        long s = seed.orElse(System.currentTimeMillis());
        Random random = new Random(s);
        create(path, writer -> {
            write(writer, "# seed: " + s + "\n");
            IntStream.rangeClosed(1, limit)
                    .forEach(i -> {
                        IntStream.rangeClosed(1, i)
                                .forEach(j -> {
                                    if (j > 1) write(writer, " ");
                                    write(writer, segment(random));
                                });
                        write(writer, "\n");
                    });
        });
    }
    
    private void create(String path, Consumer<Writer> consumer) {
        try (BufferedWriter writer = Files.newBufferedWriter(
                Paths.get(path), FILE_CHARSET, FILE_OPTIONS)) {
            consumer.accept(writer);
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    }
    
    private String segment(Random random) {
        return Integer.toString(random.nextInt(RANDOM_BOUND));
    }
    
    private void write(Writer writer, String value) {
        try {
            writer.write(value);
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    }
    
    public static void main(String[] args) {
        if (args.length == 0) {
            System.out.println("Usage: java " + TrackGenerator.class.getSimpleName() +
                               " <track file> [<track size>] [<random seed>]");
            return;
        }
        
        Iterator<String> argumentIterator = Arrays.asList(args).iterator();
        String path = argumentIterator.next();
        Optional<Integer> size = argument(argumentIterator, Integer::parseInt);
        Optional<Long> seed = argument(argumentIterator, Long::parseLong);
        new TrackGenerator().generate(path, size, seed);
    }
    
    private static <T> Optional<T> argument(Iterator<String> argumentIterator, Function<String, T> f) {
        return (!argumentIterator.hasNext() ?
                Optional.empty() : Optional.of(f.apply(argumentIterator.next())));
    }
}