Optimal “if-else” tree algorithm to minimize duplicate code

algorithmsgraphtrees

I'm having trouble formulating this problem as an algorithm:

I have a set of conditionals (combined with &&) and operations, for example:

if (A && B)
    execute C
else if (D && A)
    execute E

I want an algorithm to find the optimal "if-else" tree that minimizes the amount of duplicate code. The optimal branching for the example above would be:

if (A){
    if (B)
        execute C
    else if (D)
        execute E
}

The cost of duplicate conditionals will be different for each conditional, but it is at least 1. The cost for duplicate operations (e.g. execute C) is 3.

This smells like a minimum spanning tree problem, to me. Or maybe some other known graph theory problem. But I can't figure out how to represent the problem as a graph to begin with.

Here is a comparison of the two "if-else" trees from the example:

example graph

Best Answer

Avoid nesting logic into inner blocks as much as possible. It makes code harder to read.

if (!A)
   return

if (B)
   execute C

if (D)
   execute E

Exit if not A. Otherwise B or D, but if you know D is already true when B is false. You could drop the if (D) and just execute E.

In cases like this it's preferred to use a switch.

if (!A)
   return

switch R
    case B:
       execute C
       break
    case D:
       execute E
       breal

Related Solutions

Algorithmic Paradigms – Understanding Key Concepts

Algorithmic paradigms are:

General approaches to the construction of efficient solutions to problems

Any basic, commonly used approach in designing algorithms could be considered an algorithmic paradigm:

Divide and Conquer

Idea: Divide problem instance into smaller sub-instances of the same problem, solve these recursively, and then put solutions together to a solution of the given instance.

Examples: Mergesort, Quicksort, Strassen’s algorithm, FFT.

Greedy Algorithms

Idea: Find solution by always making the choice that looks optimal at the moment — don’t look ahead, never go back.

Examples: Prim’s algorithm, Kruskal’s algorithm.

Dynamic Programming

Idea: Turn recursion upside down.

Example: Floyd-Warshall algorithm for the all pairs shortest path problem.

The word paradigm does translate to example, but that's not how it's used in a scientific context. Your examples are all examples of algorithms (except the travelling salesman problem, which is a NP-hard problem), none of which is trivial enough to be considered an algorithmic paradigm.

Visiting points on a number line while minimizing a cost not related to distance

I think you can improve this by looking at the problem as a directed graph of pairs of positions.

For this example I will use the line with values -9, -6, -1, 3, and 5.

Because it's too hard to draw a graph with just text, I'm going to represent the pairs as a table. We can think of the cells as representing the state where all containers between those two positions have been collected. Each cell has two values, one representing the cost to go left, the other representing the cost to go right (to the next container).

The values can simply be calculated as the distance between the two points multiplied by the number of barrels outside of those two points + 1. Cells where both numbers have the same sign represent cases when all barrels of the opposite sign have been collected. These are calculated using only the number of barrels in the direction away from zero.

In the table values of X mean that you can't go in that direction (all the barrels in that direction have been taken). The rows represent the current position of the collector and the columns represent the location of the next opposite barrel.

    +------+------+------+------+------+
    |  -9  |  -6  |  -1  |   3  |   5  |
+---+------+------+------+------+------+
|-9 |      |      |      | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X |      |      | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 |      |10, X |      |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 |      | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X |      |      |
+---+------+------+------+------+------+

The rules for moving between squares can be somewhat confusing.

For negative numbered columns, the rules are as follows:

Going right moves down one cell.
Going left moves down one cell and then mirrors across the diagonal.
If the right value is X, going left moves up to the diagonal (where the column and row are equal) and left by one.

For positive numbered columns, the rules are as follows:

Going left moves up one cell.
Going right moves up one cell and then mirrors across the diagonal.
If the left value is X, going right moves down to the diagonal and right by one.

Now we can run Dijkstra's algorithm to calculate the best path, using these movement rules to traverse the graph. Our starting positions are (-1, 3) and (3, -1) with initial costs of 5 and 15, respectively. Once we've calculated values for the two end positions (left of (-9, -9) and right of (5, 5)) the smaller of the two is our answer.

The running time for each of the steps are:

O(N log N) for initially sorting the input values along the line
O(N^2) for calculating the table/graph
O(N^2 log N) for running Dijkstra's on the graph (Note: there are at most two edges for any given vertex).

The first two steps are dominated by the last, so your overall runtime is O(N^2 log N) which should be a good enough runtime for the challenge.

Best Answer

Related Solutions

Algorithmic Paradigms – Understanding Key Concepts

Visiting points on a number line while minimizing a cost not related to distance

Related Topic