1
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Pavlo Nov 30 '17 at 14:51
  • \$\begingroup\$ @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). \$\endgroup\$ – cactus Nov 30 '17 at 22:27
  • \$\begingroup\$ This is equivalent to ∑((node depth) × (# children + 1)), though that isn't any faster to compute. \$\endgroup\$ – Veedrac Dec 1 '17 at 20:16
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot! Your suggestions along with some further modifications allowed me to achieve the performance needed. I had the nodes store their children in a list and used a hashmap to save the input and the nodes. The value was the calculated via DFS (like here). \$\endgroup\$ – cactus Dec 1 '17 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.