CPSC 110 Lecture Notes - Lecture 23: Backtracking
CPSC 110 verified notes
23/26View all
Document Summary
;; consider the following visualizations of a rail network. ;; has a name, number of platforms, and is wheelchair accessible or not. ;; - liv has 8 platforms and is wheelchair accessible, while. ;; - crw has 5 platforms and is not wheelchair accessible. ;; let"s start by thinking about how we can represent this information as data: (@htdd station) (define-struct station (name platforms accessible? dests)) ;; station is (make-station string natural boolean (listof station)) ;; interp. a station in a rail-network with name, ; encapsulated template from types: (define (fn-for-station s0) (local [(define (fn-for-station s) ( (station-name s) (station-platforms s) (station-accessible? s) (fn-for-los (station-dests s)))) (define (fn-for-los los) (cond [(empty? los) ] [else ( (fn-for-station (first los)) (fn-for-los (rest los)))]))] (fn-for-station s0))) ; tail recursive template from types with rsf and worklist accumululators: (define (fn-for-station s0) ;; todo is (listof station): worklist accumulator; stations to visit (local [(define (fn-for-station s todo rsf)