Glue Shredded Pieces (CodeEval)

Question

I have solved problem 185 on CodeEval, Glue Shredded Pieces.

The solution got a 100% score on all tests (edit: see comments), within the allotted time and memory constraints. I'm looking mostly looking for tips to reduce memory usage (and improving speed) but all comments are welcome.

Description

Imagine that you are taking part in the investigation of a criminal organization. Having determined its location, you came there and found out that the criminals had recently left that place. But it is not a dead end, because there are lots of shredded documents in the room. On investigating these documents, you came to conclusion that the criminals had not been very careful. Firstly, the papers are shredded horizontally, and you can read some pieces of text. Secondly, there are many copies of the same documents, and the pieces of text overlap each other.

For example, you can put pieces together and get the original text:

evil pl
 vil pla
  il plan

The answer is ‘evil plan’.

Your task is to print out the original text. Due to repetitions in the text, you will sometimes get identical pieces.

INPUT SAMPLE:

Your program should accept a path to a file as its first argument. Each line in the file is one test case with the pieces of shredded text separated by a pipe. Each test case starts and finishes with symbol '|'.

For example:

|deEva|lan t|to ha|evil |ankin|il-ev|o hac| to h|vil p|an to|The e|CodeE| evil|plan |hack |Eval |ack C|l ran|king.|l-evi|evil-|-evil|l pla|il pl| hack|al ra|vil-e|odeEv|he ev|n to |ck Co|eEval|nking| rank| Code|e evi|ranki|k Cod| plan|val r|

OUTPUT SAMPLE:

Print to stdout the original text for each test case.

For example:

The evil-evil plan to hack CodeEval ranking.

CONSTRAINTS:

• For the text with the length t shredded into pieces with the length n, there are t - (n - 1) pieces of text in the input file. Each piece of text is shifted by one character. For example, the word ‘secret’ and n = 4: [secr, ecre, cret]
• There is only one correct answer for each test case.
• The minimum number of pieces is 125, the maximum number is 975.
• The minimum length of a piece of text is 8, the maximum length is 28.
• The number of test cases is 20.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class solves problem 185 at CodeEval:
 * https://www.codeeval.com/open_challenges/185/
 * 
 * By looking at the first and last (n-1) characters of each piece, we can
 * determine what pieces can possibly follow which other pieces. We arrange this
 * information in a directed graph where each vertex is a piece of text.
 * 
 * The graph can be constructed in forward or reverse direction, i.e. we can
 * start from the last piece and work our way backwards or start at the first
 * piece and work our way forwards. We choose forward direction.
 * 
 * The problem is now reduced to finding a start node and a path from this node
 * through the graph that visits every vertex exactly once.
 * 
 * Note that not all nodes are suitable starting nodes, we call a node that is a
 * plausible start point a "seed". Eliminating any nodes that are not suitable
 * before starting the search is vital to performance as there will be a lot of
 * them.
 * 
 * For each of the seeds, we use a depth first search, searching for the deepest
 * node. If we find a node with depth equal to the number of vertices, we have
 * found the solution.
 * 
 * @author Emily
 */
public class P185GlueShreddedPieces {
    public static class Graph {
        private final List<Vertex> vertecies = new ArrayList<>();
        private final List<Character> result = new ArrayList<>();
        private final Map<String, List<Vertex>> suffix2next = new HashMap<>();

        public void insert(Vertex aPiece) {
            vertecies.add(aPiece);

            // Add this piece to the list of pieces that can follow pieces that
            // end with the beginning of this piece. Yeah that's a mouthful...
            String lookup = aPiece.getPrefix();
            List<Vertex> successors = suffix2next.get(lookup);
            if (successors == null) {
                successors = new ArrayList<>();
                suffix2next.put(lookup, successors);
            }
            successors.add(aPiece);
        }

        public void solve(PrintStream aOutput) {
            createEdges();

            for (Vertex node : vertecies) {
                if (node.isPossibleSeed()) {
                    if (node.solve(1, vertecies.size(), result)) {
                        showResult(aOutput);
                        return;
                    }
                }
            }
        }

        private void createEdges() {
            for (Vertex node : vertecies) {
                List<Vertex> successors = suffix2next.get(node.getSuffix());
                if (successors != null) {
                    for (Vertex successor : successors) {
                        successor.addIncomming(successors.size() - 1);
                        node.addOutgoing(successor);
                    }
                }
            }
        }

        void reset() {
            result.clear();
            vertecies.clear();
            suffix2next.clear();
        }

        private void showResult(PrintStream aOutput) {
            for (int i = result.size() - 1; i >= 0; --i) {
                aOutput.append(result.get(i));
            }
            aOutput.println();
        }
    }

    public static class Vertex {
        private final List<Vertex> outgoingEdges = new ArrayList<>();
        private final String value;
        private short incommingEdgeCount;
        private short siblingCount;
        private boolean visited = false;

        public Vertex(String aText) {
            value = aText;
        }

        public void addIncomming(int aSiblings) {
            siblingCount += aSiblings;
            incommingEdgeCount++;
        }

        public void addOutgoing(Vertex aPiece) {
            outgoingEdges.add(aPiece);
        }

        public String getPrefix() {
            return value.substring(0, value.length() - 1);
        }

        public String getSuffix() {
            return value.substring(1, value.length());
        }

        public boolean isPossibleSeed() {
            return incommingEdgeCount == 0 || (incommingEdgeCount == 1 && siblingCount > 0) || incommingEdgeCount > 1;
        }

        @Override
        public String toString() {
            return value;
        }

        boolean solve(int aDepth, int aExpectedDepth, List<Character> aOutput) {
            visited = true;
            if (aDepth == aExpectedDepth) {
                for (int i = value.length() - 1; i >= 0; --i) {
                    aOutput.add(value.charAt(i));
                }
                return true;
            } else {
                for (Vertex child : outgoingEdges) {
                    if (!child.visited && child.solve(aDepth + 1, aExpectedDepth, aOutput)) {
                        aOutput.add(value.charAt(0));
                        return true;
                    }
                }
            }
            visited = false;
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        try (FileReader fr = new FileReader(args[0]); BufferedReader reader = new BufferedReader(fr)) {
            Graph graph = new Graph();

            String line;
            while ((line = reader.readLine()) != null) {
                graph.reset();

                int pieceStart = 1; // Skip first "|"
                final int pieceSize = line.indexOf("|", pieceStart);
                while (pieceStart < line.length()) {
                    String piece = line.substring(pieceStart, pieceStart + pieceSize - 1);
                    pieceStart += pieceSize;
                    graph.insert(new Vertex(piece));
                }
                graph.solve(System.out);
            }
        }
    }
}

Answer 1

Focusing on memory usage: forget all "one-of" stuff - that leaves vertices (use new ArrayList<>(ExpectedOutgoingEdges)) and suffix2next (use new ArrayList<>(ExpectedPrefixSuccessors)):

static final int
    ExpectedVertices = 123,
    ExpectedOutgoingEdges = 2,
    ExpectedPrefixSuccessors = ExpectedOutgoingEdges, //2,
    ExpectedCharacters = 28;
public static class Graph {
    private final List<Vertex>
        vertices = new ArrayList<>(ExpectedVertices);
    private final StringBuilder
        result = new StringBuilder(ExpectedVertices+ExpectedCharacters);
    private final Map<String, List<Vertex>> suffix2next;

/** alternative population of {@code suffix2next} */
    Graph(Stream<? extends CharSequence> pieces) {
        suffix2next = pieces
            .map(p -> new Vertex(p))
            .peek(v -> vertices.add(v))
            .collect(Collectors.groupingBy(v -> v.getPrefix(),
                () -> new HashMap<CharSequence,
                                  List<Vertex>>(Expectedvertices)
                , Collectors.toCollection(
                    () -> new ArrayList<>(ExpectedPrefixSuccessors))
                ));
    }
    Graph() {
        suffix2next = new java.util.HashMap<>(ExpectedVertices);
    }
    public void insert(Vertex aPiece) {
        vertices.add(aPiece);
    // Add this piece to the list of pieces that can follow pieces that
    // end with the beginning of this piece. Yeah that's a mouthful...
        suffix2next.computeIfAbsent(aPiece.getPrefix(),
            k -> new ArrayList<Vertex>(ExpectedPrefixSuccessors)).add(aPiece);
    }

    void showResult(PrintStream aOutput) {
        aOutput.println(result.reverse());
        aOutput.append(suffix2next.entrySet().stream()
            //.collect(Collectors.summarizingInt(e -> e.getValue().size()))
            .collect(Collectors.groupingBy(e -> e.getValue().size(), Collectors.counting()))
            .toString());
    }
    …
}
public static void main(String[] args) throws Exception {
    try (BufferedReader reader =
         new BufferedReader(new java.io.FileReader(args[0]))) {
        final Pattern bar = Pattern.compile("|", Pattern.LITERAL);
        for (String line ; null != (line = reader.readLine()) ; ) {
//            line = "|deEva|lan t|to ha|evil |ankin|il-ev|o hac| to h|vil p|an to|The e|CodeE| evil|plan |hack |Eval |ack C|l ran|king.|l-evi|evil-|-evil|l pla|il pl| hack|al ra|vil-e|odeEv|he ev|n to |ck Co|eEval|nking| rank| Code|e evi|ranki|k Cod| plan|val r|";
//            piece.splitAsStream(line.substring(line.indexOf('|')+1))
//              .forEach(p -> graph.insert(new Vertex(p)));
            Graph graph = new Graph(bar.splitAsStream(line.substring(line.indexOf('|')+1)));
            graph.solve(System.out);
        }
    }
}

(Using Map.computeIfAbsent, MultiMap doesn't hurt as much as it used to, even less with Collectors.groupingBy().)
Using outgoingEdges.trimToSize() probably doesn't reduce max. memory usage, trimming the elements of suffix2next.values() might help a bit.
You could use pieceSize and (line.lastIndexOf('|') - line.indexOf('|')) / pieceSize to improve upon the static ExpectedVertices and ExpectedCharacters.
Then, you can roll your own List<E> extends AbstractList<E> (drop ArrayList's size, have the element in a NonArrayList or an Object refer to the array, …) - if (List)Iterators don't kill you, subList() returning a view might.
Or use 3rd party collections - Goldman Sachs FixedSizeLists (&of(element)/with(element) look good, MutableMultimaps not bad.