How to find Sophie… Facebook Puzzle

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:

Find Sophie

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).

Sophie... well not quite

Sophie... well not quite

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.

Advertisements
Tagged , , , , , ,

30 thoughts on “How to find Sophie… Facebook Puzzle

  1. HX says:

    0 hỉu j về mấy cái algorithm hay chương trình chi hết, nhưng không phải Sophie là một con mèo và nghe tên chắc 95% là lữ giới. Còn cái hình 0 phải là 1 con chó và trông cũng 0 có vẻ j là pêđê lắm =))

  2. sheep says:

    I tried any test case I can find on the internet and my program solved them. But it still cannot pass the Facebook robot. Do you have any idea? My algorithm is the same as you mentioned, nothing special and fairly fast.

    Thanks!
    sheep

  3. sheep says:

    My program’s answer:
    $ ./sophie.exe ../sophie-examples/input1.txt
    6.00
    $ ./sophie.exe ../sophie-examples/input2.txt
    38.20
    $ ./sophie.exe ../sophie-examples/input3.txt
    115.86
    $ ./sophie.exe ../sophie-examples/input4.txt
    76.18
    $ ./sophie.exe ../sophie-examples/input5.txt
    -1.00
    $ ./sophie.exe ../sophie-examples/input6.txt
    183.04
    $ ./sophie.exe ../sophie-examples/input7.txt
    9.95
    $ ./sophie.exe ../sophie-examples/input8.txt
    5.42
    $ ./sophie.exe ../sophie-examples/input9.txt
    -1.00
    $ ./sophie.exe ../sophie-examples/input10.txt
    10.42
    $ ./sophie.exe ../sophie-examples/input11.txt
    1.40
    $ ./sophie.exe ../sophie-examples/input12.txt
    11.20
    $ ./sophie.exe ../sophie-examples/input13.txt
    -1.00
    $ ./sophie.exe ../sophie-examples/input14.txt
    1.00
    $ ./sophie.exe ../sophie-examples/input15.txt
    3.00

    The Java one I found from internet and submit it and it passed but it failed 4 cases!!!
    10, 13, 15 exception and 14 should 1.00 not -1.00
    Do you have any idea?

    input1.txt
    6.00
    input2.txt
    38.20
    input3.txt
    115.86
    input4.txt
    76.18
    input5.txt
    -1.00
    input6.txt
    183.04
    input7.txt
    9.95
    input8.txt
    5.42
    input9.txt
    -1.00
    input10.txt
    Exception in thread “main” java.lang.NumberFormatException: For input string: “5
    00000000000000000000”
    input11.txt
    1.40
    input12.txt
    11.20
    input13.txt
    Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 0
    input14.txt
    -1.00
    input15.txt
    Exception in thread “main” java.lang.NumberFormatException: For input string: “2.5”

    Thanks for any help~~~ I cannot figure out this for 2 weeks.

    sheep

    • Long Ho says:

      – input5 should return the same as input4 since the unconnected node has probability 0
      – input14 should be 0.00 cause u found Sophie at the starting location
      – input10 uses number longer than double so the actual answer is 10.42 (using DecimalNumber) but using double would be 5.42, mine uses double and still passed so 5.42 is fine
      – input15 uses non-integer distance so probably that’s why it fails

      Those are all the test cases I used. I’m kinda out of ideas. Try making those changes and see if it helps. Oh BTW you should change the executable filename to sophie instead of sophie.exe cause the grader bot only runs ./sophie [test case]
      If you’re using Java, try including the build file from here (I think you might know it already).

  4. sheep says:

    It still failed…
    My Makefile
    sophie: sophie.cpp Makefile
    $(CXX) -o $@ $<
    The output has ".exe" because I run it on cygwin?
    I have submitted other cases and they were passed with the same Makefile format.

    The only thing left is parsing input and printing output.
    Do you just
    printf("%.2f\n", exp);
    or do rounding first? like this:
    exp=(double)((int)(exp * 100 + 0.5))/100;

    Thanks,
    sheep

    • Long Ho says:

      I didn’t do any rounding, just printed out 2 decimal figures. Sorry man I’m out of ideas.

      • sheep says:

        Is it possible I email you my code or you email me your code so we can do side by side comparison? I have tried many many ways…still no luck….

        Thanks,
        sheep

  5. Naveed says:

    Since we are not dealing with negative edge weights, wouldn’t it have been easier and faster to use Dijkstra’s algorithm to generate the all pairs shortest paths, instead of Floyd Warshall?

  6. Naveed says:

    Facebook accepted my solution, and I ended up finding all pairs shortest paths using Floyd Warshall. I had forgotten how simple and elegant Floyd Warshall was. Good call.

  7. Teodor says:

    “- input5 should return the same as input4 since the unconnected node has probability 0”
    Does not look like that for me: there can be a path in input4 through that node 3, which is not the path for input5. Thus the number of paths in input4 is more, and the time should be less.

  8. pappu says:

    First doubt: are you deleting the nodes of the tree while you are going up.
    Second: Are you constructing the tree completely or creating a part of the tree for evaluating the expected cost and then deleting it. I think I may run out of memory if I construct the complete tree.

  9. Long Ho says:

    I constructed the entire tree, that’s why I believe the maximum # of location is limited before you run out of memory (20 nodes or sth). But reconstructing the tree is not a good idea I think since you’ll have to find shortest paths for that portion of tree again and it’s not efficient

  10. Jose says:

    May I ask how you do the backtracking, I mean, I am trying an example that has 17 nodes, and still takes literally days to compute.

    The reason is that if the shortestPaths between nodes are within the same order of magnitude, the best you can do is to filter out some nodes from the bottom of the tree, but you’d still have to go down 15 levels (17 – 1 – root node), which is still too heavy.

  11. Long Ho says:

    As I’ve mentioned I used Greedy backtracking so everytime there’s a dead end, it pops a recursion stack, backtracks and looks for the next best path, as ranked in a PriorityQueue. The preprocessing part is pretty fast so it’s likely not a problem. Greedy turns out to work pretty well actually, I would say keep the re-computations to the minimum cause the decision tree is huge for like 15 nodes

  12. Mikesh says:

    My solution is not able to calculate for inputs ‘Input2.txt’ and ‘Input3.txt’. Everything else is fine. Any idea why this happens?
    Also, did you use any algorithm to initialise your first path?
    Thanks

    • Long Ho says:

      I think input2 and 3 either has 0-weight path or circular. Those are the special cases but I dont think fb bot checks for that. I used Floyd-Warshall to initialize all the shortest paths, the greedy backtrack to find the best ones based on path length

      • Mikesh says:

        I did some optimizations and input2 is being calculated in 5 minutes. But, the output for input4 is 76.18 while that for input5 is 76.17. Is that new?
        I had another one which took about 8 minutes for input2 and calculated 76.18 from both input4 and input5.
        Both were rejected by the bot. Any ideas why?
        Its really getting disheartening!

      • Kosmo says:

        Mikesh,
        So was the problem with input2 a circular list?

  13. AvM says:

    Hey!
    When you are saying greedy backtracking, which one have you used??
    Are you going to a location which is the closest?
    Are you going to a location with the highest probability?
    or anything else??
    Could you please tell us the time which your program takes on input 2 and 3??
    Thanks for your help!

    • Long Ho says:

      By greedy backtracking, I actually mean greedy. Once u’ve run Floyd Warshall u’ll get a list of shortest paths that visit all the locations, throw them into a sorted set/priority queue. Start trying 1 by 1 until u find the shortest one. Sorry it’s been so long I don’t keep the code and time metrics anymore.

  14. ts says:

    Hi,
    I have been stuck on this for some time and am now getting frustrated.
    I am using Python and use Dijkstra’s algorithm to find shortest paths.
    Next, I use backtracking recursion to find shortest path. My solution isn’t too fast but its correct for all test cases I could find. Do you think it isnt getting accepted because it isnt fast enough or am i missing some input/output bug?
    How fast does the puzzlebot require my code to be?
    Thanks!

    • Long Ho says:

      I know that they improved their grading bot to be harsher so I’m not sure whether it’s the corner case that failed u. I knew that some people’s algorithms didn’t pass the corner cases like 0-weight locations or loops or unconnected location with weight 0 (which is still legit) and still passed the grading bot. I used Floyd-Warshall cause it’s fast, simple and efficient (3 tight loops which maximize instructions and caching) so u can definitely try that. After getting all the shortest paths, I did recursive backtracking using path weight as heuristic so that’s similar to urs. It took me a few tries also.
      If ur still stuck, try looking at the fb forum discussion on this problem. They might just change the bot again somehow. When mine was accepted, it said the longest case took my code 242.888 ms and that was since like April last year.

      Good luck,

      Long Ho

  15. Kosmo says:

    Hi Long,
    When you calculate the shortest path, do you go directly to that node or do you visit the itermittent nodes and calculate their EV too? e.g. if A to B has a shortest path through C and D, do you just go to B and calculate EV based on B or since you are going through C and D, do you add the EV of C and D if they are not already visited?
    Thanks

    • Mikesh says:

      Kosmo,
      My code had some errors in checking boundary conditions. Although, I made some improvements in pruning which improves my results in terms of time. There was no problem with input2 eventually.

  16. Triti says:

    Hey, for input 12, can you please tell me the path that yielded 11.2. I have run my algorithm, and it gives 11.6 . Please help me

    Triti

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: