tungwaiyip.info

home

about me

links

my software

Media

Yucatán Photos

St Lucia Photos

Photo Album

Videos

Blog

< July 2010 >
SuMoTuWeThFrSa
     1 2 3
4 5 6 7 8 910
11121314151617
18192021222324
25262728293031

past articles »

Click for San Francisco, California Forecast

San Francisco, USA

 

Find Sophie Solution (Facebook Programming Puzzle)

This is the fourth and probably my last post about solving Facebook programming puzzle. The Find Sophie problem is a buffet (hardest) level puzzle. It is basically a variation of the traveling salesman problem. Traveling salesman is of course, a NP-complete problem. But before you throw up your hand, consider the puzzle refers to locations in your home where you may find a cat. Just how many locations are there. Let's say living room, dining room, bedroom, on the bed, under the desk, behind the curtain, ... etc. If Facebook is not very wicked, this puzzle should be bounded to a low hundreds of locations. This mean it is still possible to solve using some relatively simple search algorithm.

Here is the outline of my solution:

  1. Prepare to enumerate all paths.
  2. Prefer the local optimal during the search. Remember the best solution encountered so far.
  3. Prune the search tree. For example if the current best solution has a score of 50. When you are considering another path, as soon as its score exceed 50, you should abandon it.
  4. Improve the pruning by taking the additional score to complete the path into account. For example, if the current score of a partial path is S, the minimum score to complete the remaining walk is Rmin. Then if S+Rmin > best score, prune it.

Actually I have submitted the solution a few months ago. Only today do I find out I have not posted my solution in my blog. So I'm really speaking from my memory. I hope my plan is still accurate. Again my un-tidied code is available.

The other 3 facebook puzzles I have solved was posted below:

2010.07.22 [] - comments

 

 

blog comments powered by Disqus

past articles »

 

BBC News

 

Israel and Hamas agree new truce (01 Aug 2014)

 

Multiple Taiwan gas blasts kill 24 (01 Aug 2014)

 

Sudan 'apostasy' woman arrives in US (01 Aug 2014)

 

Memo reveals response to CIA 'abuse' (31 Jul 2014)

 

Ebola victim heads to US hospital (01 Aug 2014)

 

US ex-governor's wife 'sought gifts' (31 Jul 2014)

 

China manufacturing growth speeds up (01 Aug 2014)

 

Forensic scientists reach MH17 site (31 Jul 2014)

 

Argentina blames US for debt default (31 Jul 2014)

 

Make-up 'godfather' Dick Smith dies (31 Jul 2014)

more »

 

Slashdot News for nerds, stuff that matters

 

French Provider Free Could Buy US Branch of T-Mobile (2014-08-01T00:08:00Z)

 

New Display Technology Corrects For Vision Defects (2014-07-31T23:31:00Z)

 

Passport Database Outage Leaves Thousands Stranded (2014-07-31T22:54:00Z)

 

Why TiVo's Founders Crashed and Burned With Qplay (2014-07-31T22:12:00Z)

 

HP Gives OpenVMS New Life and Path To X86 Port (2014-07-31T21:32:00Z)

 

Peter Hoddie Talks About His Internet of Things Construction Kit (Video) (2014-07-31T20:49:00Z)

 

Ask Slashdot: When Is It Better To Modify the ERP vs. Interfacing It? (2014-07-31T20:08:00Z)

 

UK Government Report Recommends Ending Online Anonymity (2014-07-31T19:29:00Z)

more »

 

TechPsychic Tech Rumors and Invented News

more »

 

SF Gate

 

Bay Area News (7 Jan 2012)

 

City Insider (11 Feb 2012)

 

Crime Scene (13 Feb 2012)

 

C.W Newius Column (10 Jan 2012)

 

C.W. Nevius Blog (11 Feb 2012)

 

Education News (10 Jan 2012)

 

KALW (11 Feb 2012)

 

Matier and Ross Blog (11 Feb 2012)

 

EBay workforce more diverse than Silicon Valley peers (31 Jul 2014)

 

Whole Foods profit rises (30 Jul 2014)

 

'Valley Girl' Jesse Draper on tech's gender problem (30 Jul 2014)

 

Time to update health exchange data to avoid tax surprises (30 Jul 2014)

 

Snapchat valued at billion in talks with Alibaba (30 Jul 2014)

 

Outsourcing scientific tests aids biotech startups (30 Jul 2014)

more »

 

Asia Times Online

 

Putin edges toward a personal Waterloo (Thu 31 Jul 2014 11:00:00 GMT)

 

THE ROVING EYE Crime (Israel) and punishment (Russia) (Thu 31 Jul 2014 11:00:00 GMT)

 

Leading Chinese iman murdered in Xinjiang (Thu 31 Jul 2014 11:00:00 GMT)

 

Is Obama really adrift in the world? (Thu 31 Jul 2014 11:00:00 GMT)

 

Vietnam buckles under Chinese pressure (Thu 31 Jul 2014 11:00:00 GMT)

 

The al-Sisi his allies can't see (Thu 31 Jul 2014 11:00:00 GMT)

 

Arab countries in land-grab strategy to secure food (Thu 31 Jul 2014 11:00:00 GMT)

 

THE BEAR'S LAIR Business and free markets (Thu 31 Jul 2014 11:00:00 GMT)

more »

 


Site feed Updated: 2014-Jul-31 21:00