NOTE: all source code, including the driver, can be found here

What We're Going to Solve

You are on a subway. At each platform along the way you either:

  • receive an amount of cash
  • pay an amount of cash

When you arrive at your destination you are able to keep your winnings ONLY IF you have collected the greatest amount of money that was possible.

RULES:

  1. The amount of money you receive or pay at each platform is a function of what platform you came from. For example, if you stop at the 3rd platform on your journey, the amount of money you receive or pay depends on whether you came from the 1st or 2nd platform. The amount of money you receive or pay for any source/destination combination is known to you in advance.

  2. You cannot go more than 3 platforms without stopping. In other words, if you have just gotten on the subway or if you have just received or paid at a platform, you must stop at one of the next 3 platforms.

Formally, this challenge can we worded as follows:

Find the maximum number of dollars that can be received by traveling to an nth vertex. Only the $h_{i+1}$, $h_{i+2}$, or $h_{i+3}$ vertex can be visited from any given source vertex. For a path $h_{i,j}$, the dollars received is denoted by $d_{i,j}$. All $d_{i,j}$ are given.

Modeling the Problem

We will model this problem as a graph and represent the graph by an adjacency matrix with the following form:

Adjacency Matrix

Each $d_{i,j}$ represents the cost or reward for traveling a certain path. Also, note that every vertex only has directed edges to each of its three following vertices.

Solving the Problem

An efficient way to solve this challenge is to use dynamic programming. I'm going to show the solution in Java and then explain what is going on. Here's the algorithm:

public static void bestRoute(int[][] cost){  
    int[] hops = new int[cost.length];
    int[] reward = new int[cost.length];

    for(int i=1; i<cost.length; ++i) {
        reward[i] = Integer.MIN_VALUE;
        for(int j=i-3; j<i; ++j) {
            if(j < 0) continue;
            if(cost[j][i] + reward[j] > reward[i]) {
                reward[i] = cost[j][i] + reward[j];
                hops[i] = i-j;
            }
        }
    }

    System.out.println("The best reward possible is $" + reward[reward.length-1]);
    System.out.println(Playground.print(hops, hops.length-1, hops.length));
}

private static String print(int[] arr, int index, int curr) {  
    if(index == 0) return "vertex 1";
    return print(arr, index - arr[index], curr-arr[index]) + " -> vertex " + curr;
}

The input holds all the $d_{i,j}$ costs. We'll grab our adjacency matrix from a .txt file:

2

00 34 12 01 00 00  
00 00 45 12 98 00  
00 00 00 12 04 02  
00 00 00 00 96 74  
00 00 00 00 00 11  
00 00 00 00 00 00

00 12 53 65 00 00  
00 00 45 92 93 00  
00 00 00 19 44 02  
00 00 00 00 26 74  
00 00 00 00 00 95  
00 00 00 00 00 00  

Here's the output:

Specify an input file: input.txt

Case #1: 

The best reward possible is $198  
vertex 1 -> vertex 2 -> vertex 3 -> vertex 4 -> vertex 5 -> vertex 6

Case #2: 

The best reward possible is $187  
vertex 1 -> vertex 4 -> vertex 6

Total Time: 0ms  

To find the maximum reward for n vertices, max(n), we choose the subpath to vertex n that produces the maximum reward.

Adjacency Matrix

Note that in order to do this we must have an optimal substructure. For example, max(n-1) must produce the maximum reward to vertex n-1. Also, note that in order to choose this maximum, max(n-1), max(n-2), max(n-3) must already be computed and available for us. To accomplish this, we use dynamic programming's bottom-up approach.

In the first test case above, the below values are computed bottom-up from max(1) to max(6).

Runtime Analysis

This algorithm runs in Θ(n) time. We are able to accomplish this because we only have to find the max of 3 costs and so the computing time for each vertex is constant.

source code