; A Station is a (make-station String [List-of String] [List-of String])

(define-struct station [name lines neighbors])

; - where name is the name of the station

; - lines is the list of lines that this station is on

; - and neighbors is the list of stations you can get to immediately from this one

Sample Problem Create some example maps of the T.

(define DOWNTOWN

(list (make-station "North Station" '("orange" "green") '("Haymarket"))

(make-station "Bowdoin" '("blue") '("Govt Center"))

(make-station "Haymarket" '("orange" "green") '("North Station" "Govt Center" "State"))

(make-station "Govt Center" '("green" "blue") '("Bowdoin" "Haymarket" "Park St" "State"))

(make-station "Aquarium" '("blue") '("State"))

(make-station "Park St" '("red" "green") '("Govt Center" "Boylston" "Downtown Crossing"))

(make-station "State" '("orange" "blue")

'("Haymarket" "Govt Center" "Aquarium" "Downtown Crossing"))

(make-station "Boylston" '("green") '("Park St"))

(make-station "Downtown Crossing" '("red" "orange")

'("Park St" "State" "Chinatown" "South Station"))

(make-station "Chinatown" '("orange") '("Downtown Crossing"))

(make-station "South Station" '("red") '("Downtown Crossing"))))

(define GREENLINE-SPLIT

(list (make-station "Copley" '("green") '("Arlington" "Prudential" "Hynes Convention Ctr"))

(make-station "Hynes Convention Ctr" '("green") '("Copley" "Kenmore"))

(make-station "Kenmore" '("green")

'("Hynes Convention Ctr" "Blandford St" "St Marys St" "Fenway"))

(make-station "Prudential" '("green") '("Copley"))

(make-station "Blandford St" '("green") '("Kenmore"))

(make-station "St Marys St" '("green") '("Kenmore"))

(make-station "Fenway" '("green") '("Kenmore"))))

(define OUTBOUND-GREENLINE

(list (make-station "Copley" '("green") '("Prudential" "Hynes Convention Ctr"))

(make-station "Hynes Convention Ctr" '("green") '("Kenmore"))

(make-station "Kenmore" '("green")

'("Blandford St" "St Marys St" "Fenway"))

(make-station "Prudential" '("green") '())

(make-station "Blandford St" '("green") '())

(make-station "St Marys St" '("green") '())

(make-station "Fenway" '("green") '())))

Sample Problem Design a function can-ride-in-time? which consumes a Number (the amount of time you have), the names of two stations, and a map and returns a Boolean indicating whether you can make it in time. Assume that it takes 3 minutes to move from one station to the next even if you have to transfer to another line.

; can-ride-in-time? : String String Number [List-of Station] -> Boolean

; Can I get from a to b in time t?

; TERMINATION: This function always terminates since either we run out of

; time or we get to the station we were looking for

(define (can-ride-in-time? a b t the-map)

(local [(define the-station (get-station a the-map))]

(cond [(string=? a b) #true]

[else

(and (>= t 3)

(ormap (λ (neighbor) (can-ride-in-time? neighbor b (- t 3) the-map))

(station-neighbors the-station)))])))

(check-expect (can-ride-in-time? "Chinatown" "Aquarium" 10 DOWNTOWN) true)

(check-expect (can-ride-in-time? "Fenway" "Blandford St" 5 GREENLINE-SPLIT) false)

; get-station : String [List-of Station] -> Station

; Produces the first station with this name

(define (get-station the-name the-map)

(cond [(empty? the-map) (error (string-append "Could not find station "

station-name))]

[(cons? the-map)

(if (string=? (station-name (first the-map)) the-name)

(first the-map) (get-station the-name (rest the-map)))]))

Exercise 2 Riding the T is fun so you decide to find a way to ride it forever by going in circles. Design the function clique? which takes a list of station names and a map of the T and returns true if the stations are all interconnected. For example, Haymarket, State, and Govt Center are a clique in the map of downtown Boston.

Note: Park St, Govt Center, State, and Downtown Crossing are NOT a clique because Park St and State are not connected.

Exercise 3 Design the function biggest-clique which takes a map of the T and produces the largest set of stations that are all connected. You may break ties in any reasonable way.

Hint: The other functions you wrote may come in handy... so might argmax.