Maximize a traveling employee's vacation over k weeks

Question

I have following problem statement

A lazy employee works at a multi-national corporation with N offices spread across the globe.

They want to work as few days over k weeks as possible.

Their company will pay for them to fly up to once per week (on weekends) to a remote office with a direct flight from their current office. Once in an office, they must stay there until the end of the week.

If an office observes a holiday while the employee is working there, they get that day off.

Find the path that maximizes the employee's vacation over k weeks.

Assume they start at a home office H on a weekend (so in the first week, they can be in any office connected to the home office).

For example:

H<--->A (It means there is a flight path from H to A and vice versa)

H<--->B

Here is my solution in Python.

vacation = [
{"H": 1, "A": 0, "B": 2},  # week 1
{"H": 0, "A": 2, "B": 0}
]


flights = [("H", "A"), ("H", "B")]


def get_optimal_path():
    all_possible_paths = []

    for offices in list(itertools.product(*vacation)):
        total_cost = 0
        week_level = 0
        for office in offices:
            vac_level = vacation[week_level]
            total_cost += vac_level[office]
            week_level += 1
        if checkIfValidPath(offices[0], offices[1]):
            all_possible_paths.append((offices, total_cost))

    print(max(all_possible_paths, key=lambda x: x[1]))


def checkIfValidPath(source, destination):
    return any(i for i in flights if i[0] == source and i[1] == destination 
or i[0] == destination and i[1] == source)


get_optimal_path()

In this example best answer is for the employee to stay at office H in the first week and then move to office A in the second week so the total vacation days will be (1+2)=3. B and A cannot be the answer here because there is no path between them.

How can I optimize this code to increase its efficiency? Right now its complexity is n^k (since we have k weeks).

Answer 1

With this kind of problems it is important to build good mathematical model. After that, the best algorithm known to science can be easily found.

The problem in question seems to be Longest path problem, which if we build a graph properly has linear time solution.

Lets consider a graph (V, E), where V are week-offices (for example, H1, A1, B1, H2, A2, B2, ... - where H1 means home office at first week, B2 - office B at week two, and so on).

Edges are possible flights. For the example in the question we have the following edges:

H1 -> H2, H1 -> A2, H1 -> B2, H2 -> H3, A2 -> H3, B2 -> H3, H2 -> A3, H2 -> B3 (note, that there is never An -> Bn direct flights).

Here is the flights graph, which is an input, (on the left) and corresponding unrolled space-time one, for which a linear time algorithm can be found. Each node has a given weight.

Then a somewhat lengthy quotation from wikipedia:

"For instance, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps:

1. Find a topological ordering of the given DAG.
2. For each vertex v of the DAG, in the topological ordering, compute the length of the longest path ending at v by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If v has no incoming neighbors, set the length of the longest path ending at v to zero. In either case, record this number so that later steps of the algorithm can access it.

Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex v with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way."

Please, note, that our graph has been already topologically sorted - we know where it starts and where it ends.

A recursive algorithm can be elegant, but it's not really needed here.

This is maybe a bit unusual answer for a code review, but I strongly believe it is appropriate to point out at the possibility of a better algorithm while doing code review. I hope this is useful not only as a specific answer, but also as a good approach to apply math where it's due.

Please also note it is not necessary to memorize all possible graph and theory algorithms: At first I only had a vague idea, which became clear after some thinking and finding right terms.

Answer 2

Here is the solution I proposed, thought more as a DP problem: We update the best distance with each passing week, so at all times we know the highest vacations we can get after x weeks have passed. Here best[officeA] stores the highest vacations we can get after the week ending up at officeA.

The complexity is the same as the one @Roman Susi proposed.

vacation = [
{"H": 1, "A": 0, "B": 2},  # week 1
{"H": 0, "A": 2, "B": 0}
]


flights = [("H", "A"), ("H", "B")]

def get_optimal_path():
    best = {}
    neighbors = {}

    for officeA, officeB in flights:
       best[officeA] = 0
       best[officeB] = 0

       if officeA not in neighbors:
           neighbors[officeA] = [] 

       if officeB not in neighbors:
           neighbors[officeB] = []   

       neighbors[officeA].append(officeB)
       neighbors[officeB].append(officeA)      

    reached = set("H")

    for week in range(0, len(vacation)):
       oldBest = {}
       for office in best.keys():
           oldBest[office] = best[office]

       for currentOffice in set(reached): #for each office we have already reached
           for officeB in neighbors[currentOffice]:
               best[officeB] = max(oldBest[currentOffice] + vacation[week][officeB], best[officeB]) # keep max between taking the flight and what we had
               reached.add(officeB)
           best[currentOffice] = max(oldBest[currentOffice] + vacation[week][currentOffice], best[currentOffice]) #keep max between staying at current office and what we had

    print(max(best.values()))

get_optimal_path()