8
\$\begingroup\$

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 nk (since we have k weeks).

\$\endgroup\$
20
  • \$\begingroup\$ Do you have any idea which combinatorial optimization problem this is (or can be reduced to)? This will let you to easily find the best algorithm known today. This seems like a problem from graph theory, with a small twist. \$\endgroup\$ – Roman Susi Jul 24 '18 at 18:47
  • \$\begingroup\$ @RomanSusi apologies I have no idea . I know i am missing something but I cant figure out what. Can you please explain it to me \$\endgroup\$ – Rohit Jul 24 '18 at 19:02
  • \$\begingroup\$ To solve these kinds of problems best, it is good to know some theory (math). Mathematics (combinatorial optimization / optimization theory) knows how to solve some common problems like your. So I've asked whether you tried to find matching problem before reinventing the wheel? \$\endgroup\$ – Roman Susi Jul 24 '18 at 19:07
  • \$\begingroup\$ Usually maximizing stuff on graphs is NP hard. You could avoid repeating some paths by storing the best value (max vacations) reached at each place of length j. If there are 2 paths of length j to reach an office, you only want the path that got the most vacations \$\endgroup\$ – juvian Jul 24 '18 at 19:11
  • \$\begingroup\$ @RomanSusi thank you so much for invoking my thought process. But I am still not able to figure out or find a matching problem. I can think of a way to solve this using backtracking is that what you are looking for ? \$\endgroup\$ – Rohit Jul 24 '18 at 19:13
5
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
0
\$\begingroup\$

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()
\$\endgroup\$
4
  • \$\begingroup\$ the answer seems to be wrong or am I missing something? \$\endgroup\$ – Rohit Jul 25 '18 at 14:18
  • \$\begingroup\$ @Rohit I don´t know why you said the best answer is stay at H and then go to A, going to B and then staying at B yields 6 vacation days \$\endgroup\$ – juvian Jul 25 '18 at 16:17
  • \$\begingroup\$ I have modified the input. Can you check the answer \$\endgroup\$ – Rohit Jul 25 '18 at 16:39
  • \$\begingroup\$ @Rohit indeed it was wrong, should be fixed now \$\endgroup\$ – juvian Jul 25 '18 at 16:46

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.