# Building tree from edges puzzle with performance requirement

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()) {
}

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;
}
}

• Can you please describe it better. If you get the sum of the nodes, then example 1 should return 9. I ran your program and got 16, so i think that the behavior you need is different from the one you describe – Pavlo Nov 30 '17 at 14:51
• @Pavlo Example 1: 3 has default value 1 and no children. Its parent 2 has default value 1 plus the value of its child 3 (1) plus 1, so 2 has value 3. 1 has value 5 and 0 has value 7. Total value is 1+3+5+7=16. Basically every node has value: 1 + (# of children) + (sum of children's values). – cactus Nov 30 '17 at 22:27
• This is equivalent to ∑((node depth) × (# children + 1)), though that isn't any faster to compute. – Veedrac Dec 1 '17 at 20:16

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) {
}
}


    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.

• 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