#lang racket/base
(print "Hello, World!")
;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname problems) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #t)))
(require spd/tags)
(@htdd Status)
;; Status is one of:
;; - "buried"
;; - "sunken"
;; - "locked"
;; interp. the status of an unopened treasure box
;;<examples are redundant for enumeration>
(@htdd Treasure)
(define-struct treasure (label amount difficulty status routes))
;; Treasure is (make-treasure String Natural Natural Status (listof Route))
;; interp. a treasure box with a label name,
;; the number of gold coins contained in the treasure box,
;; a rating of difficulty to find and open the treasure box between 1
;; and 5, where 1 is very easy to find and open and 5 is very difficult,
;; the status of the treasure box before it was opened,
;; and a list of routes leading from this treasure box
;; to other treasure boxes
(@htdd Route)
(define-struct route (duration destination))
;; Route is (make-route Natural String)
;; interp. a route leading from one treasure box to another
;; duration is the time in hours it will take to travel to it and
;; destination is the name of the treasure box the route leads to
(define TREASURE-MAP
(list (make-treasure "E" 32 3 "buried" (list (make-route 3 "A")))
(make-treasure "F" 10 2 "locked" (list (make-route 7 "C")))
(make-treasure "B" 6 5 "locked" (list (make-route 9 "E")
(make-route 15 "F")))
(make-treasure "J" 1 1 "sunken" (list (make-route 6 "I")))
(make-treasure "H" 17 2 "sunken" (list (make-route 15 "J")
(make-route 4 "I")))
(make-treasure "G" 52 3 "buried" (list (make-route 2 "D")))
(make-treasure "I" 100 5 "locked" empty)
(make-treasure "D" 21 1 "sunken" (list (make-route 8 "G")
(make-route 13 "H")
(make-route 9 "I")
(make-route 11 "A")))
(make-treasure "C" 41 4 "buried" (list (make-route 6 "G")))
(make-treasure "A" 7 1 "locked" (list (make-route 12 "B")
(make-route 7 "C")
(make-route 27 "D")))))
;; Consider this to be a primitive function that comes with the data definitions
;; and that given a treasure name it produces the corresponding treasure.
;; Because this consumes a string and generates a treasure calling it will
;; amount to a generative step in a recursion through a graph of treasures and
;; routes. You must not edit this function, but you can experiment with it to
;; see how it works.
;;(@htdf lookup-treasure)
;;(@signature String -> Treasure)
(define (lookup-treasure name)
(local [(define (scan lst)
(cond [(empty? lst) (error "No treasure named " name)]
[else
(if (string=? (treasure-label (first lst)) name)
(first lst)
(scan (rest lst)))]))]
(scan TREASURE-MAP)))
(define TE (lookup-treasure "E"))
(define TF (lookup-treasure "F"))
(define TB (lookup-treasure "B"))
(define TJ (lookup-treasure "J"))
(define TH (lookup-treasure "H"))
(define TG (lookup-treasure "G"))
(define TI (lookup-treasure "I"))
(define TD (lookup-treasure "D"))
(define TC (lookup-treasure "C"))
(define TA (lookup-treasure "A"))
;; Template
(define (fn-for-treasure t)
(local [(define (fn-for-status s)
(cond [(string=? s "buried") (...)]
[(string=? s "sunken") (...)]
[(string=? s "locked") (...)]))
(define (fn-for-treasure t)
(... (treasure-label t)
(treasure-amount t)
(treasure-difficulty t)
(fn-for-status (treasure-status t))
(fn-for-lor (treasure-routes t))))
(define (fn-for-lor lor)
(cond [(empty? lor) (...)]
[else
(... (fn-for-route (first lor))
(fn-for-lor (rest lor)))]))
(define (fn-for-route r)
(... (route-duration r)
;; lookup-treasure is the generative step that makes the whole
;; MR generative
(fn-for-treasure (lookup-treasure (route-destination r)))))]
(fn-for-treasure t)))
;; problem 1
;;
;; Complete the function that lists the labels names of all reachable treasures
;; when following only routes with a duration less than n hours long.
;;
;; Your solution MUST be tail recursive.
;;
;(@htdf short-dur-reachable)
(@signature Treasure Number -> (listof String))
;; produce labels of all treasures reachable by following routes < n hr long
(check-expect (short-dur-reachable TI 12) (list "I"))
(check-expect (short-dur-reachable TH 4) (list "H"))
(check-expect (short-dur-reachable TH 5) (list "H" "I"))
(check-expect (short-dur-reachable TH 16) (list "H" "J" "I"))
(check-expect (short-dur-reachable TA 9) (list "A" "C" "G" "D"))
;(define (short-dur-reachable t n) empty) ;stub
(define (short-dur-reachable t0 n)
(local [(define-struct wle (n p))
;; wle is (make-wle Treasure Path)
;; Worklist entry with Treasure and path of the treasure
(define (short-dur-reachable t n t-wl path visited)
(if (not (empty? (treasure-routes t)))
(reachable-list
(append (map (lambda (d)
(make-wle d (cons t path)))
(treasure-routes t))
t-wl)
path
visited
n)
(reachable-list t-wl path visited n)))
(define (reachable-list t-wl path visited n)
(cond [(empty? t-wl) visited]
[else
(if (not (false? (route-func (wle-n (first t-wl))
n
(rest visited)
(wle-p (first t-wl))
visited)))
(route-func (wle-n (first t-wl))
n
(rest visited)
(wle-p (first t-wl))
visited)
(short-dur-reachable (wle-n (first t-wl))
n
(rest visited)
(wle-p (first t-wl))
visited))]))
(define (route-func r n t-wl path visited)
(cond [(< (route-duration r) n)
visited]
[else
(short-dur-reachable (lookup-treasure (route-destination r))
n
t-wl
path
visited)]))]
(short-dur-reachable t0 n empty empty empty)))
;; problem 2
;;
;; Complete the design of a function that consumes two treasures and counts
;; the number of routes reachable from TE that lead to TF.
;;
;; Note: This is counting the number of routes found in treasure boxes where TF
;; is the destination, NOT the total number of paths between the two treasure
;; boxes. It is asking how many routes have TF as their destination (how many
;; arrows are pointing to TF).
;;
;; Examples:
;;
;; (num-lead-to TA TI) produces 3. This is because there are three routes that
;; are reachable from TA that lead to TI. These routes are the route leading
;; from TH to TI, the route leading from TJ to TI, and the route leading from
;; TD to TI.
;;
;; (num-lead-to TI TA) produces 0. Even though two routes lead to TA (the
;; route from TD to TA and the route from TE to TA), neither route can be
;; reached from TI so the function produces 0.
;;
;; Note that you can use the built-in function equal? to compare if two
;; treasures are equal. For example:
;; - (equal? TE TF) produces false
;; - (equal? TB TB) produces true
;;
;; Your solution MUST be tail recursive.
;;
(@htdf num-lead-to)
(@signature Treasure Treasure -> Natural)
;; count the number of reachable routes that lead to TF
(check-expect (num-lead-to TI TA) 0)
(check-expect (num-lead-to TJ TI) 1)
(check-expect (num-lead-to TH TI) 2)
(check-expect (num-lead-to TA TI) 3)
(check-expect (num-lead-to TF TA) 2)
(check-expect (num-lead-to TD TC) 2)
;(define (num-lead-to TE TF) 0) ;stub
(define (num-lead-to TE0 TF)
(local [
(define (num-lead-to TE TF visited count)
(cond [(member? (treasure-label TE) visited) visited]
[else
(list-lead-to (treasure-routes TE)
TF
(cons (treasure-label TE) visited)
count)]))
(define (list-lead-to t-wl TF visited count)
(cond [(empty? t-wl) count]
[else
(if (not (false? (lead-to-func (first t-wl)
visited
count
TF)))
(lead-to-func (first t-wl) visited count)
(num-lead-to (rest t-wl)
TF
visited
count))]))
#;(define (lead-to-func r TF visited)
(cond [(member? (lookup-treasure (route-destination r)) visited)
visited]
[else
(num-lead-to (lookup-treasure (route-destination r))
visited)]))
(define (lead-to-func r visited count TF)
(if (not (false? (num-lead-to (lookup-treasure
(route-destination r))
visited
count
TF)))
(num-lead-to (lookup-treasure
(route-destination r))
visited
(add1 count)
TF)
(num-lead-to (lookup-treasure
(route-destination r))
visited
count
TF)))]
(num-lead-to TE0 TF empty 0)))
;; problem 3
;;
;; Complete the design of a function that consumes a treasure and the label
;; of another treasure, and produces the time in hours of route durations
;; it would take to travel from t to the treasure labeled s. This function
;; produces the total duration of the routes followed as soon as it finds a
;; treasure labeled s. The function produces false if there is no way of
;; reaching a treasure with the given label.
;;
(@htdf route-to)
(@signature Treasure String -> Natural or false)
;; produce the total duration traveled on route to s from t, false if not found
(check-expect (route-to TE "X") false)
(check-expect (route-to TE "E") 0)
(check-expect (route-to TE "A") 3)
(check-expect (route-to TH "I") 21)
(check-expect (route-to TA "G") 40)
(check-expect (route-to TA "J") 70)
(define (route-to t s) false) ;stub
;; problem 4
;;
;; Complete the design of a function that consumes a treasure and the label
;; of another treasure, and produces the MINIMUM time in hours of all of the
;; possible routes that could be taken to travel from t to the treasure
;; labeled s. The function produces false if there is no way of reaching the
;; a treasure with the given label.
;;
(@htdf min-route-to)
(@signature Treasure String -> Natural or false)
;; produce the min duration traveled on route to s from t, false if not found
(check-expect (min-route-to TE "X") false)
(check-expect (min-route-to TE "E") 0)
(check-expect (min-route-to TE "A") 3)
(check-expect (min-route-to TH "I") 4)
(check-expect (min-route-to TA "G") 13)
(check-expect (min-route-to TA "J") 43)
;(define (min-route-to t s) false) ;stub
(define (min-route-to t s)
(local [
(define (min-route-to t s visited)
(cond [(member t visited)
(reverse (cons t visited))]
[else
(label-list (append (treasure-routes s) visited)
(cons (treasure-routes t) visited))]))
(define (label-list t-wl visited)
(cond [(empty? t-wl) false]
[else
(choose-shorter
(route-func (first visited) (rest t-wl) visited)
(min-route-to (first t-wl) (rest t-wl) visited))]))
(define (route-func r s visited)
(cond [(member? (lookup-treasure (route-destination r)) visited)
visited]
[else
(min-route-to (lookup-treasure (route-destination r))
visited)]))
(define (choose-shorter t s)
(cond [(false? t) s]
[(false? s) t]
[else
(if (<= (length s) (length t))
s
t)]))
]
(min-route-to t s empty))) Write, Run & Share Racket code online using OneCompiler's Racket online compiler for free. It's one of the robust, feature-rich online compilers for Racket language, running on the latest version 6.8. Getting started with the OneCompiler's Racket compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as Racket and start coding.
OneCompiler's Racket online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample Racket program which takes name as input and print your name with hello.
#lang racket/base
(define name (read))
(printf "Hello ~a.\n" name)
Racket is a general-purpose programming language based on the Scheme dialect of Lisp. It is also used for scripting, computer science education, and research related applications.
| Item | Decsription |
|---|---|
; | To comment a single line |
;; | to mark important comments |
#; | to comment the following s-expression |
| Data-type | Decsription |
|---|---|
| Numbers | represents integers, float and complex numbers |
| Boolean | #t and #f are the two boolean literals |
| Strings | To represent sequence of characters and double quotes("") are used to represent strings |
let and define are used to declare variables
(let ([id value-expression] ...) body ...+)
(let proc-id ([id init-expression] ...) body ...+)
define id expression
> (let ([x 10]) x)
10
If, If-else are used when you want to perform a certain set of operations based on conditional expressions.
(if cond-expr then-expr)
(if cond-expr then-expr else-expr)
For loop is used to iterate a set of statements based on a condition.
(for (for-clause ...) body-or-break ... body)
where
for-clause = [id seq-expr] | [(id ...) seq-expr] | #:when guard-expr | #:unless guard-expr | break-clause
break-clause = #:break guard-expr | #:final guard-expr
body-or-break = body | break-clause
seq-expr : sequence?
A lambda expression is used to create a function.
(lambda (argument-id ...)
body ...+)