#lang scheme ;loc : string, string, number, number, number, (list-of string), (list-of number) (define-struct loc (name desc latitude longitude radius neighbors distances)) ;Stores the name, description, and geographic information of a location, including its visitation radius in meters, neighbors, and the distances in meters to those neighbors. Every location will have a unique, unambiguous name. ;loc-list-no-dist : (list-of loc) ;missing distances (define loc-list-no-dist (list (make-loc "The John Hay Library" "" 41.826372 -71.404703 15 (list "The Rock" "(x)Waterman/Prospect" "Van Wickle Gates") empty) (make-loc "The Rock" "" 41.825721 -71.404776 10 (list "The John Hay Library" "Van Wickle Gates" "(x)George/Prospect") empty) (make-loc "The SciLi" "" 41.826800 -71.400094 10 (list "1 1/2" "America One" "Soldier's Arch" "(x)Manning/Brook" "(x)Waterman/Thayer") empty) (make-loc "The John Carter Brown Library" "" 41.825536 -71.402681 10 (list "University Hall North" "University Hall South" "Sayles South" "(x)George/Brown") empty) (make-loc "Andrews" "" 41.830352 -71.402459 20 (list "Pembroke Green" "The Gate" "(x)Cushing/Brown") empty) (make-loc "New Pembroke" "" 41.830194 -71.401500 15 (list "The Gate" "(x)E Cushing/Thayer") empty) (make-loc "Hope" "" 41.826629 -71.403693 15 (list "Van Wickle Gates" "University Hall North" "Sayles North" "Sayles South" "The Brown Bear" "Bridge Prop") empty) (make-loc "Littlefield" "" 41.825631 -71.402075 15 (list "Marcus Aurelius/Lincoln Field" "(x)George/Brown" "The Ratty" "(x)George/Thayer") empty) (make-loc "Wayland" "" 41.825018 -71.402202 10 (list "Caesar/Wriston" "The Ratty" "(x)George/Brown" "(x)Benevolent/Brown") empty) (make-loc "Patriot's Court" "" 41.824369 -71.400639 15 (list "Caesar/Wriston" "The Ratty" "(x)Charlesfield/Thayer") empty) (make-loc "Keeney" "" 41.824492 -71.403075 10 (list "(x)Benevolent/Magee" "(x)Benevolent/Brown") empty) (make-loc "Grad Center" "" 41.823375 -71.400261 15 (list "Josiah's" "(x)Charlesfield/Thayer") empty) (make-loc "The Ratty" "" 41.825227 -71.401168 10 (list "Wayland" "Caesar/Wriston" "Patriot's Court" "Littlefield" "(x)George/Brown" "(x)George/Thayer") empty) (make-loc "The V-Dub" "" 41.829272 -71.401675 10 (list "Pembroke Steps" "Walkway(Meeting)" "(x)Meeting/Brown" "(x)Meeting/Thayer") empty) (make-loc "The Gate" "" 41.829914 -71.402086 10 (list "Andrews" "Pembroke Steps" "New Pembroke" "Pembroke Green" "(x)E Cushing/Thayer") empty) (make-loc "Josiah's" "" 41.823419 -71.399422 15 (list "Grad Center" "(x)Charlesfield/Thayer") empty) (make-loc "Marcus Aurelius/Lincoln Field" "" 41.826236 -71.401986 25 (list "Soldier's Arch" "Sayles North" "Sayles South" "Littlefield") empty) (make-loc "Caesar/Wriston" "" 41.825038 -71.401375 20 (list "Wayland" "The Ratty" "Patriot's Court") empty) (make-loc "The Brown Bear" "" 41.826653 -71.402789 15 (list "Hope" "University Hall North" "University Hall South" "Sayles North" "Bridge Prop" "Blue Room/Shearer Memorial Fountain" "(x)Waterman/Brown") empty) (make-loc "Bridge Prop" "" 41.826528 -71.403264 15 (list "University Hall North" "University Hall South" "Sayles North" "Sayles South" "Hope" "The Brown Bear" "(x)Waterman/Brown") empty) (make-loc "1 1/2" "" 41.826514 -71.400028 10 (list "The SciLi" "America One" "Soldier's Arch" "(x)Manning/Brook") empty) (make-loc "America One" "" 41.826776 -71.399713 10 (list "The SciLi" "1 1/2" "(x)Manning/Brook") empty) (make-loc "Blue Room/Shearer Memorial Fountain" "" 41.826708 -71.402597 15 (list "The Brown Bear") empty) (make-loc "List Art" "" 41.826150 -71.405392 15 (list "Van Wickle Gates") empty) (make-loc "Pembroke Green" "" 41.829761 -71.402417 20 (list "Pembroke Steps" "Andrews" "The Gate" "(x)Cushing/Brown" "(x)E Cushing/Thayer") empty) (make-loc "Pembroke Steps" "" 41.829289 -71.402392 10 (list "Pembroke Green" "The V-Dub" "Walkway(Meeting)" "(x)Meeting/Brown" "(x)Meeting/Thayer" "The Gate") empty) (make-loc "University Hall North" "" 41.826353 -71.403528 10 (list "University Hall South" "Sayles North" "Sayles South" "Van Wickle Gates" "The John Carter Brown Library" "Bridge Prop" "Hope" "The Brown Bear" "(x)George/Brown" "(x)Waterman/Brown") empty) (make-loc "University Hall South" "" 41.825903 -71.403597 10 (list "University Hall North" "Sayles North" "Sayles South" "Van Wickle Gates" "The John Carter Brown Library" "Bridge Prop" "The Brown Bear" "(x)George/Brown" "(x)Waterman/Brown") empty) (make-loc "Sayles North" "" 41.826328 -71.402892 10 (list "University Hall North" "University Hall South" "Sayles South" "Marcus Aurelius/Lincoln Field" "Soldier's Arch" "Bridge Prop" "Hope" "The Brown Bear" "(x)Waterman/Brown") empty) (make-loc "Sayles South" "" 41.826006 -71.402836 10 (list "Hope" "University Hall North" "University Hall South" "Sayles North" "Marcus Aurelius/Lincoln Field" "Soldier's Arch" "The John Carter Brown Library" "Bridge Prop" "(x)George/Brown") empty) (make-loc "Soldier's Arch" "" 41.826361 -71.400503 20 (list "1 1/2" "The SciLi" "Marcus Aurelius/Lincoln Field" "Sayles North" "Sayles South" "(x)Manning/Brook" "(x)Waterman/Thayer" "(x)George/Thayer") empty) (make-loc "(x)Manning/Brook" "" 41.826503 -71.399194 15 (list "1 1/2" "America One" "The SciLi" "Soldier's Arch" "(x)Waterman/Brook" "(x)George/Brook") empty) (make-loc "Walkway(Waterman)" "" 41.827164 -71.401753 15 (list "Walkway(Angel)" "(x)Waterman/Brown" "(x)Waterman/Thayer") empty) (make-loc "Walkway(Angel)" "" 41.827967 -71.401819 15 (list "Walkway(Waterman)" "Walkway(Olive)" "(x)Angel/Brown" "(x)Angel/Thayer") empty) (make-loc "Walkway(Olive)" "" 41.828447 -71.401881 15 (list "Walkway(Angel)" "Walkway(Meeting)" "(x)Olive/Brown" "(x)Olive/Thayer") empty) (make-loc "Walkway(Meeting)" "" 41.829064 -71.401903 15 (list "The V-Dub" "Walkway(Olive)" "Pembroke Steps" "(x)Meeting/Brown" "(x)Meeting/Thayer") empty) (make-loc "(x)Cushing/Brown" "" 41.829678 -71.403464 15 (list "Andrews" "Pembroke Green" "(x)Meeting/Brown") empty) (make-loc "(x)E Cushing/Thayer" "" 41.830017 -71.400886 15 (list "The Gate" "Pembroke Green" "New Pembroke" "(x)Meeting/Thayer") empty) (make-loc "(x)Meeting/Brown" "" 41.828983 -71.403375 15 (list "The V-Dub" "Pembroke Steps" "Walkway(Meeting)" "(x)Meeting/Thayer" "(x)Cushing/Brown" "(x)Olive/Brown") empty) (make-loc "(x)Meeting/Thayer" "" 41.829156 -71.400753 15 (list "The V-Dub" "Pembroke Steps" "Walkway(Meeting)" "(x)Meeting/Brown" "(x)E Cushing/Thayer" "(x)Olive/Thayer") empty) (make-loc "(x)Olive/Brown" "" 41.828289 -71.403233 15 (list "Walkway(Olive)" "(x)Olive/Thayer" "(x)Meeting/Brown" "(x)Angel/Brown") empty) (make-loc "(x)Olive/Thayer" "" 41.828556 -71.400697 15 (list "Walkway(Olive)" "(x)Olive/Brown" "(x)Meeting/Thayer" "(x)Angel/Thayer") empty) (make-loc "(x)Angel/Prospect" "" 41.827719 -71.404789 15 (list "(x)Angel/Brown" "(x)Waterman/Prospect") empty) (make-loc "(x)Angel/Brown" "" 41.827858 -71.403158 15 (list "Walkway(Angel)" "(x)Angel/Prospect" "(x)Angel/Thayer" "(x)Olive/Brown" "(x)Waterman/Brown") empty) (make-loc "(x)Angel/Thayer" "" 41.828097 -71.400636 15 (list "Walkway(Angel)" "(x)Angel/Brown" "(x)Angel/Brook" "(x)Olive/Thayer" "(x)Waterman/Thayer") empty) (make-loc "(x)Angel/Brook" "" 41.828211 -71.399431 15 (list "(x)Angel/Thayer" "(x)Waterman/Brook") empty) (make-loc "Van Wickle Gates" "" 41.826111 -71.404508 15 (list "Hope" "The Rock" "The John Hay Library" "List Art" "University Hall North" "University Hall South" "(x)Waterman/Prospect" "(x)George/Prospect") empty) (make-loc "(x)Waterman/Prospect" "" 41.826903 -71.404689 15 (list "The John Hay Library" "Van Wickle Gates" "(x)Angel/Prospect" "(x)Waterman/Brown") empty) (make-loc "(x)Waterman/Brown" "" 41.827036 -71.402994 15 (list "Bridge Prop" "Walkway(Waterman)" "University Hall North" "University Hall South" "Sayles North" "The Brown Bear" "(x)Waterman/Prospect" "(x)Waterman/Thayer" "(x)Angel/Brown") empty) (make-loc "(x)Waterman/Thayer" "" 41.827272 -71.400542 15 (list "The SciLi" "Walkway(Waterman)" "(x)Waterman/Brown" "(x)Waterman/Brook" "(x)Angel/Thayer" "Soldier's Arch") empty) (make-loc "(x)Waterman/Brook" "" 41.827361 -71.399317 15 (list "(x)Waterman/Thayer" "(x)Angel/Brook" "(x)Manning/Brook") empty) (make-loc "(x)George/Prospect" "" 41.825267 -71.404514 15 (list "The Rock" "Van Wickle Gates" "(x)George/Brown" "(x)Benevolent/Magee") empty) (make-loc "(x)George/Brown" "" 41.825342 -71.402667 15 (list "Wayland" "The John Carter Brown Library" "Littlefield" "The Ratty" "University Hall North" "University Hall South" "Sayles South" "(x)George/Prospect" "(x)George/Thayer" "(x)Benevolent/Brown") empty) (make-loc "(x)George/Thayer" "" 41.825528 -71.400347 15 (list "The Ratty" "Littlefield" "(x)George/Brown" "(x)George/Brook" "Soldier's Arch" "(x)Benevolent/Thayer") empty) (make-loc "(x)George/Brook" "" 41.825628 -71.399017 15 (list "(x)George/Thayer" "(x)Manning/Brook" "(x)Benevolent/Brook") empty) (make-loc "(x)Benevolent/Magee" "" 41.824569 -71.404028 15 (list "Keeney" "(x)Benevolent/Brown" "(x)George/Prospect") empty) (make-loc "(x)Benevolent/Brown" "" 41.824597 -71.402708 15 (list "Keeney" "Wayland" "(x)Benevolent/Magee" "(x)George/Brown" "(x)Charlesfield/Brown") empty) (make-loc "(x)Benevolent/Thayer" "" 41.824783 -71.400250 15 (list "(x)Benevolent/Brook" "(x)George/Thayer" "(x)Charlesfield/Thayer") empty) (make-loc "(x)Benevolent/Brook" "" 41.824886 -71.398981 15 (list "(x)Benevolent/Thayer" "(x)George/Brook" "(x)Charlesfield/Brook") empty) (make-loc "(x)Charlesfield/Brown" "" 41.823747 -71.402614 15 (list "(x)Charlesfield/Thayer" "(x)Benevolent/Brown") empty) (make-loc "(x)Charlesfield/Thayer" "" 41.823903 -71.400144 15 (list "Josiah's" "Grad Center" "Patriot's Court" "(x)Charlesfield/Brown" "(x)Charlesfield/Brook" "(x)Benevolent/Thayer") empty) (make-loc "(x)Charlesfield/Brook" "" 41.823981 -71.398836 15 (list "(x)Charlesfield/Thayer" "(x)Benevolent/Brook") empty))) ;; loc-list->ht: (listof loc) -> (hashof string loc) ;; Given a list of locs, produces a hashtable keyed by loc-name (define (loc-list->ht a-loc-list) (foldl (lambda (a-loc a-ht) (begin (hash-set! a-ht (loc-name a-loc) a-loc) a-ht)) (make-hash) a-loc-list)) ;; loc-list-no-dist-ht: (hashtableof string loc) (define loc-list-no-dist-ht (loc-list->ht loc-list-no-dist)) ;tour-dist : number, number, number, number -> number ;Given the latitude and longitude of two locations, returns the approximate distance in meters between them. Note that the argument order is latitude1, longitude1, latitude2, longitude2. ;You won't need to use this for determining the distance between two nodes, as we have precomputed them for you, but you may find it useful in situations in which the user has deviated from the proscribed path. (define (tour-dist latA lonA latB lonB) (* 6378000 (* 2 (asin (min 1 (sqrt (+ (expt (sin (/ (- (deg->rad latA) (deg->rad latB)) 2)) 2) (* (cos (deg->rad latA)) (cos (deg->rad latB)) (expt (sin (/ (- (deg->rad lonA) (deg->rad lonB)) 2)) 2))))))))) (define (deg->rad angle) (* angle (/ pi 180))) ;tour-head : number, number, number, number -> string ;Given the latitude and longitude of two locations as above, returns the approximate heading of the path from the first location to the second asa string such as "North" or "Southwest." (define (get-dir-string latA lonA latB lonB) (local [(define angle (direction latA lonA latB lonB))] (cond [(or (> (/ pi 8) angle) (< (* 1.875 pi) angle)) "North"] [(> (* 3 (/ pi 8)) angle) "North-East"] [(> (* 5 (/ pi 8)) angle) "East"] [(> (* 7 (/ pi 8)) angle) "South-East"] [(> (* 9 (/ pi 8)) angle ) "South"] [(> (* 11 (/ pi 8)) angle ) "South-West"] [(> (* 13 (/ pi 8)) angle ) "West"] [(> (* 15 (/ pi 8)) angle ) "North-West"]))) (define (ext-modulo num1 num2) (- num1 (* num2 (floor (/ num1 num2))))) (define (direction latA lonA latB lonB) (cond [(= (cos (deg->rad latA)) 0) (if (latA > 0) pi (* 2 pi))] [(and (= latA latB) (= lonA lonB)) -1] [else (ext-modulo (+ pi (atan (* (sin (- (deg->rad lonB) (deg->rad lonA))) (cos (deg->rad latB))) (- (* (cos (deg->rad latA)) (sin (deg->rad latB))) (* (sin (deg->rad latA)) (cos (deg->rad latB)) (cos (- (deg->rad lonB) (deg->rad lonA))))))) (* 2 pi))])) ;; find-loc-in-ht: (hashtableof string loc) string -> loc (define (find-loc-in-ht ht name) (hash-ref ht name (lambda () (error 'find-loc-in-loc-list (format "No such location: ~s" name))))) ;calc-dist : loc -> loc ;adds list of distances for neighbors using loc-list-no-dist for locations and tour-dist for calculation (define (calc-dist l) (make-loc (loc-name l) (loc-desc l) (loc-latitude l) (loc-longitude l) (loc-radius l) (loc-neighbors l) (map (lambda (n) (local ((define n-loc (find-loc-in-ht loc-list-no-dist-ht n))) (tour-dist (loc-latitude l) (loc-longitude l) (loc-latitude n-loc) (loc-longitude n-loc)))) (loc-neighbors l)))) ;loc-list : (list-of loc) ;loc-list provides a complete list of all the locations your program will use to find paths. (define loc-list (map calc-dist loc-list-no-dist)) (define loc-list-ht (loc-list->ht loc-list)) ;tour : string, (list-of loc) (define-struct tour (name stops)) ;Stores the name of a tour (which your program will need to display) and its stops. ;create-tour : name, (list-of string) -> tour ;takes a name and a list of loc-names and returns a tour with that name and those locations (define (create-tour name loc-names) (make-tour name (map (lambda (n) (find-loc-in-ht loc-list-ht n)) loc-names))) ;tours : (list-of tour) (define tours (list (create-tour "Library Tour" (list "The John Hay Library" "The Rock" "The SciLi" "The John Carter Brown Library")) (create-tour "Housing Tour" (list "Andrews" "New Pembroke" "Hope" "Littlefield" "Wayland" "Caesar/Wriston" "Patriot's Court" "Keeney" "Grad Center")) (create-tour "Dining Tour" (list "The Ratty" "The V-Dub" "The Gate" "Josiah's" "Blue Room/Shearer Memorial Fountain")) (create-tour "Campus Art Tour" (list "Marcus Aurelius/Lincoln Field" "Caesar/Wriston" "The Brown Bear" "Bridge Prop" "1 1/2" "America One" "Blue Room/Shearer Memorial Fountain" "List Art"))))