UVA - 10854 - Number of Paths 

This article will explain my thought process to solve a problem called Number of Paths (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Tree, Recursive, Combinatorics

Objective 

Given:

  1. Lines of code.

We want to:

  1. Find the number of paths to cover every lines.

Glossary 

  1. Tree — A hierarchical data structure used to represent data in a parent-child relationship.

  2. Recursion — The process in which a function calls itself directly or indirectly.

  3. Combinatorics — A branch of mathematics concerned with counting, arranging, and structuring finite sets of objects.

  4. Fundamental Counting Principle — A rule used to count the total number of possible outcomes in a situation.

Observation 

The branching mechanism (IF, ELSE, and END_IF) on the code have a hierarchical structure. It is also possible to have a nested branch (IF inside an IF). We can model the branching mechanism as a tree, where the lines of code are the vertices and the branches are the edges.

Next, we want to calculate the total paths from the tree. We can divide this into 2 problems: (1) calculate the total paths for 1 branch; (2) calculate the total paths for multiple branches.

For the first problem, the structure of the branch looks like this. 

# Branch 1
IF { ... }
# Branch 2
ELSE { ... }
ENDIF

Lets say that B(i) is the total paths for every branch. The total paths in this case, can be calculated by calculating the sum of B(i).

For the second problem, the structure of the branches looks like this.

# Group 1 - Branch 1
IF { ... }
# Group 1 - Branch 2
ELSE { ... }
ENDIF

# Group 2 - Branch 1
IF { ... }
# Group 2 - Branch 2
ELSE { ... }
ENDIF

Lets say G(i) is the sum of B(i) or the total paths for every group. This is a combinatorics problem, as we want to explore every combination of group branches to get the total paths. Using the fundamental counting principle, we can calculate the total paths by multiplying the G(i).

Algorithm 

For simplicity, the tree can be stored in a hashmap + list. To reconstruct the hierarchical structure, we can use stack to store the nested branches. After that, we can implement the B(i) and G(i) as a recursion.

The time complexity of this solution is O({total lines of code}).

Implementation 

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

/**
 * 10854 - Number of Paths
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1795
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalCases = in.nextInt();
        for (int i = 0; i < totalCases; i++) {
            final LinkedList<String> keywords = new LinkedList<>();
            do {
                keywords.addLast(in.next());
            } while (!"ENDPROGRAM".equals(keywords.getLast()));

            final Input input = new Input();
            input.keywords = keywords.toArray(new String[0]);

            final Output output = process.process(input);
            out.println(output.totalPaths);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public String[] keywords;
}

class Output {
    public long totalPaths;
}

class Process {
    public Output process(final Input input) {
        final Stack<String> stack = new Stack<>();
        final Map<String, List<String>> tree = new HashMap<>();
        tree.put(null, new LinkedList<>());

        for (int idx = 0; idx < input.keywords.length; idx++) {
            final String keyword = input.keywords[idx];
            final String line = String.format("%s:%d", keyword, idx);

            if (line.startsWith("IF")) {
                final String parentLine = stack.isEmpty() ? null : stack.peek();
                tree.get(parentLine).add(line);
                tree.putIfAbsent(line, new LinkedList<>());

                stack.push(line);
            } else if (line.startsWith("ELSE")) {
                stack.pop();

                final String parentLine = stack.isEmpty() ? null : stack.peek();
                tree.get(parentLine).add(line);
                tree.putIfAbsent(line, new LinkedList<>());

                stack.push(line);
            } else if (line.startsWith("END_IF")) {
                stack.pop();
            }
        }

        final Output output = new Output();
        output.totalPaths = getTotalPaths(tree, null);
        return output;
    }

    private long getTotalPaths(final Map<String, List<String>> tree, final String parent) {
        final List<String> children = tree.get(parent);
        final LinkedList<List<String>> groups = new LinkedList<>();
        for (final String child : children) {
            if (child.startsWith("IF")) {
                groups.addLast(new LinkedList<>());
            }
            groups.getLast().add(child);
        }

        long totalPaths = 1;
        for (final List<String> group : groups) {
            long groupTotalPaths = 0;
            for (final String child : group) {
                groupTotalPaths += getTotalPaths(tree, child);
            }
            totalPaths *= groupTotalPaths;
        }

        return totalPaths;
    }
}


Powered by Docmost