So I said I was gonna write about how to solve this puzzle since it took me quite a while to figure out. In case you guys don’t know, the puzzle is:
After a long day of coding, you love to head home and relax with a loved one. Since that whole relationship thing hasn’t been working out for you recently, that loved one will have to be your cat, Sophie. Unfortunately you find yourself spending considerable time after you arrive home just trying to find her. Being a perfectionist and unable to let anything suboptimal be a part of your daily life, you decide to devise the most efficient possible method for finding Sophie.
Luckily for you, Sophie is a creature of habit. You know where all of her hiding places are, as well as the probability of her hiding in each one. You also know how long it takes you to walk from hiding place to hiding place. Write a program to determine the minimum expected time it will take to find Sophie in your apartment. It is sufficient to simply visit a location to check if Sophie is hiding there; no time must be spent looking for her at a location. Sophie is hiding when you enter your apartment, and then will not leave that hiding place until you find her. Your program must take the name of an input file as an argument on the command line.
So basically to sum up, you have list of places to find Sophie and each place has a probability of finding her. The probability of course sum up to 1 so you have to visit all the places to guarantee that you’ll find her.
This problem is very similar to Traveling Salesman (TSP Problem). In fact it’s called PTSP (Probabilistic Traveling Salesman Problem) and a simple Google on it will yield a whole bunch of results (mainly using Ant Colony Optimization and stuff). The problem takes O(n!) time to solve so brute force doesn’t work (it used to work for the Facebook Grader Bot but they recently made it harder).
I myself use something much simpler: Floyd-Warshall and Greedy backtracking algorithm. The general idea is to calculate all-pair shortest path so that you know what’s the shortest path going from 1 place to another. Then you just go down the tree, keep track of the minimum expected time. Once another branch produces an expected time that’s longer than the min expected time, backtrack immediately as going down further only increases the expected time.
You can find out about Floyd-Warshall here and Backtracking here. I’m not gonna put the source code here but if you need help just comment in this post and I’ll help you out! Aight have fun and keep on rolling guys!!
P.S: The source code is here for your reference.