Tracking Santa

December 24, 2010

We calculate the distance in kilometers between two points (a pair with latitude in the car and longitude in the cdr) using the haversine formula from the Wikipedia page; you might want to check your function at http://www.movable-type.co.uk/scripts/latlong.html. We round to the nearest mile because of potential numeric inaccuracy with the distance is small, and because the Earth is not a perfect sphere:

(define (dist pt1 pt2)
  (define (d->r d) (* d pi 1/180))
  (define (square x) (* x x))
  (let* ((lat1 (car pt1)) (lng1 (cdr pt1))
         (lat2 (car pt2)) (lng2 (cdr pt2))
         (r 6371) ; radius of "perfect" earth in kilometers
         (dlat (d->r (- lat2 lat1)))
         (dlng (d->r (- lng2 lng1)))
         (a (+ (* (sin (/ dlat 2)) (sin (/ dlat 2)))
               (* (cos (d->r lat1)) (cos (d->r lat2))
                  (square (sin (/ dlng 2))))))
         (c (* 2 (atan2 (sqrt a) (sqrt (- 1 a))))))
    (inexact->exact (round (* r c)))))

The other thing we need is a function to read the route from Norad’s file:

(define (read-route filename)
  (with-input-from-file filename (lambda ()
    (let loop ((line (read-line)) (ps '()))
      (cond ((eof-object? line) (reverse ps))
            ((string-find "\"lat\"" line)
              (let* ((lat (string->number
                            (substring line 12
                              (- (string-length line) 2))))
                     (line (read-line))
                     (lng (string->number
                            (substring line 12
                              (- (string-length line) 2)))))
                (loop (read-line) (cons (cons lat lng) ps))))
            (else (loop (read-line) ps)))))))

Then it’s easy to sum the distances between adjacent points to calculate the length of the route:

(define (route-length route)
  (let loop ((start (car route)) (rest (cdr route)) (len 0))
    (if (null? rest) (inexact->exact (round (* len .621371192)))
      (loop (car rest) (cdr rest)
            (+ (dist start (car rest)) len)))))

Santa covers an enormous number of miles in a day:

> (route-length (read-route "santa-track.txt"))
197423

The longest segment, from Rio de Janeiro to Greenland, is 9712 kilometers or 6035 miles. Santa covers that distance in 4 minutes, a speed of 90,500 miles per hour. I think those flying reindeer eat more than oats!

We used pi, atan2, string-find, and read-line from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/a9Uj7oPj.

About these ads

Pages: 1 2 3

8 Responses to “Tracking Santa”

  1. [...] today’s Programming Praxis, our task is to calculate the total distance traveled by Santa based on data [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/24/programming-praxis-tracking-santa/ for a version with comments):

    import Data.List.HT
    import Text.HJson
    import Text.HJson.Query
    
    dist :: RealFloat a => (a, a) -> (a, a) -> a
    dist (lat1, lng1) (lat2, lng2) =
      let toRad d = d * pi / 180
          haversin x = sin (toRad $ x / 2) ^ 2
          a = haversin (lat2 - lat1) +
              cos (toRad lat1) * cos (toRad lat2) * haversin (lng2 - lng1)
      in 2 * 6371 * atan2 (sqrt a) (sqrt (1 - a))
    
    coords :: Json -> [(Double, Double)]
    coords = map ((\[JString lat, JString lng] -> (read lat, read lng)) .
                  getFromKeys ["lat", "lng"]) . getFromArr
    
    totalMiles :: RealFloat a => [(a, a)] -> Int
    totalMiles = round . (* 0.621371192) . sum . mapAdjacent dist
    
    main :: IO ()
    main = either print (print . totalMiles . coords) . fromString .
           drop 16 =<< readFile "santa.txt"
    
  3. Hey guys,

    I’m new to Ruby so I did my best to throw this together in about 30 min…

    My solution

    Any help and comments are welcome!

  4. Jebb said

    With the file data.js saved in the same directory, having deleted the ‘var locations = ‘ bit at the beginning:

    #!/usr/bin/python2.7
    
    def read_locations(file_name):
    	import json
    	f = open(file_name, 'r')
    	locations = json.load(f)
    	f.close()
    	return locations
    
    def distance(pointA, pointB):
    	from math import radians, cos, acos
    	lat1 = radians(float(pointA['lat']))
    	lat2 = radians(float(pointB['lat']))
    	dlat = lat2 - lat1
    	dlong = radians(float(pointB['lng']) - float(pointA['lng']))
    	ang_dist = acos(cos(dlat) - cos(lat1) * cos(lat2) * (1 - cos(dlong)))
    	return 6371 * ang_dist
    
    def main():
    	locations = read_locations('data.js')
    	journey = 0
    	for i in range(len(locations) - 1):
    		journey += distance(locations[i], locations[i+1])
    	print 'Total distance traveled %.0f km' % journey
    
    if __name__ == '__main__':
    	main()
    

    that’s 320,627 km to the metric-inclined.

  5. Graham said

    A few days late, but here’s my Python
    version. I went with the arctangent formula given by Wikiepdia, which it calls
    “a more complicated formula that is accurate for all distances.” I also followed
    Jebb’s lead of saving “data.js” with the var locations = portion
    removed. This can be run (at least on my system) with ./santa.py data.js.

  6. Actually I screwed up my first solution, this is correct I believe: http://pastebin.com/6maXGn80

  7. Mike said

    Another Python version.

    Download the data.js and save to santaflightpath.py. Edit the first line to remove “var “, so it starts with “location =”.
    Remove the “;” from the last line. This creates a python compatible statement defining ‘locations’ to be a list of dictionaries. Importing ‘santaflightpath’ executes the code in the file, so there are clearly security implications.

    pairwise is from the recipies in the itertools documentation.

    Of interest, the flight plan is 28 hours long; stays within 600 miles of the north pole for the first 4 hours; doesn’t appear to visit Antarctica; and doesn’t return to the starting point.

    from santaflightplan import locations
    from math import asin, sin, cos, radians, sqrt
    from itertools import starmap
    from utils import pairwise

    earth_radius = 3958.76 #average

    def distance(p1, p2):
    lat1, lng1 = map(radians, p1)
    lat2, lng2 = map(radians, p2)
    dlat = lat1 – lat2
    dlng = lng1 – lng2
    ang = 2*asin(sqrt(sin(dlat/2)**2 + cos(lat1)*cos(lat2)*sin(dlng/2)**2))
    return ang * earth_radius

    locs = ((float(p['lat']),float(p['lng'])) for p in locations)
    print sum(starmap(distance, pairwise(locs)))
    [/sourcecode/

  8. With a little delay, my commented Python version (looks like the one above http://www.gleocadie.net/?p=572&lang=en)

    def get_coords():
        from json import load
        f = open("data.js", encoding='utf-8')
        l = load(f)
        f.close()
        return l
    
    def distance(o1, o2):
        from math import radians, cos, sin, acos
        lat1, lng1 = radians(float(o1['lat'])), float(o1['lng'])
        lat2, lng2 = radians(float(o2['lat'])), float(o2['lng'])
        sins = sin(lat1) * sin(lat2)
        coss = cos(lat1) * cos(lat2)
        da = acos(sins + coss * cos(radians(lng2 - lng1)))
        return 6372.8 * da * 0.621371192
    
    def track_santa():
        l = get_coords()
        res = 0
        for i in range(len(l) - 1):
            res = res + distance(l[i], l[i+1])
        return res
    
    if __name__ == "__main__":
        d = track_santa()
        print(d)
    

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

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: