Problem 569. Encoding Google Maps Polylines

This problem is based on the Google Polyline Encoder algorithm. This is how Google Maps encodes a line for display on a map. You will be given a single latitude-longitude pair for which you must generate the encoded string used by the Google Maps API.

Example:

Given

 lat = 42.3 
 lon = -71.35

then

 str = '_vdaGnpnrL'

Here is the complete algorithm description. You can use this interactive tool to play around with it (I used it to generate the test points).