Building tree from edges puzzle with performance requirement

Question

I'm working on a puzzle and have solved it, but my code is not fast enough to get the maximum score (if the code is faster than a certain achievable threshold, one gets awarded the maximum score). I have tried multiple approaches but it seems I can't figure it out. My Java code is appended at the end.

The puzzle is as follows: Input is a number >= 1 of lines of two integers separated by a space which represent edges in a graph. This graph is a tree with 0 as root. We have to calculate the "value" of the graph defined as:
Each node initially has value 1. If a node has children, they each increase its value by their value +1. The final value of a node it its new value + values of all it's children. So:

node value =  1 + (# of children) + (sum of children's values). 

The value of the graph is the sum of values of its nodes.
Then print the value modulo 1234567.

Examples:

0 1  
2 1  
2 3  

has value 16.

1 0  
2 0  
1 3  
1 4  

has value 17.

Here's my code, if someone has any idea where I'm being inefficient, thanks for the help!

public static void main (String[] args) {

    Scanner stdin = new Scanner(System.in);
    Stack<Tuple> allNodes = new Stack<>();
    List<Integer> input = new ArrayList<>();

    //add all input to input list
    while (stdin.hasNext()) {
        input.add(stdin.nextInt());
    }

    allNodes.push(new Tuple(0, -1));
    int index, childIndex, child, parent, iterator = 0;

    //search input for known nodes from parents and add them to allNodes
    while (input.size() > 0) {
        parent = allNodes.get(iterator++).id;
        while ((index = input.indexOf(parent)) >= 0) {
            //check whether index is even or odd
            childIndex = (index%2 == 0) ? index+1 : index-1;
            child = input.get(childIndex);

            allNodes.push(new Tuple(child, parent));

            input.remove(index);
            if (index > childIndex) { input.remove(childIndex); }
            else { input.remove(index); }
        }
    }

    int[] values = new int[allNodes.size()];
    Tuple currentNode;

    //compute values
    while (allNodes.size() > 1) {
        currentNode = allNodes.pop();
        values[currentNode.parent] += ++values[currentNode.id]+1;
    }
    values[0]++;

    int sum = 0;
    for (int i=0; i<values.length; i++) {
        sum += values[i];
    }

    System.out.println(sum%1234567);
    stdin.close();
}

public static class Tuple {

    int id;
    int parent;

    public Tuple (int id, int parent) {
        this.id = id;
        this.parent = parent;
    }
}

Answer 1

Would rather make this a comment, but I need 50 reputation for that, so: It became quite an answer apparently.

I find given code quite confusing. From what I am picking up, it does excessive searching/iteration where it is not necessary. I'd propose to make a refactoring, creating a class representing your tree. Then you can cleanely implement your requirements. E.g.:

public class Node {

    private final int id;
    private final List<Node> children;

    public Node(final int id) {
        this.id = id;
        this.children = new ArrayList<>();
    }

    public void addChild(final Node child) {
        children.add(child);
    }
}

Now you can add some methods directly expressing your requirements:

    public int graphValue() {
        return nodeValue() + children.stream().collect(summingInt(Node::graphValue));
    }

    public int nodeValue() {
        return 1 + children.size() + children.stream().collect(summingInt(Node::nodeValue));
    }

When creating your tree, you could use something like a HashMap so you can retrieve an already existing node by id in constant time. Perhaps you might need more optimizations.

Some other comments:

• Try to avoid using the Stack class: see Stack JavaDoc

• Close the scanner as soon as possible; it is also AutoCloseable, so you can use try-with-resources: see try-with-resources documentation

• Prefer !list.isEmpty() over list.size() > 0, it is more idiomatic and potentially more efficient. Some implementations might traverse all elements to calculate the size, but as soon as there is an element it is of course not empty.

• You created a Tuple class, which is a generic thing. But the implementation is not generic. I'd give it a more specific and telling name. (or possibly make it truly generic)

• The amount of +'s in values[currentNode.parent] += ++values[currentNode.id] + 1 is too damn high :D