Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tree: b36fe569ca
Fetching contributors…

Cannot retrieve contributors at this time

212 lines (193 sloc) 5.685 kB
#! /usr/bin/env racket
#lang racket
(require rackunit)
(define (quiz-name)
"2-problem-solving")
(define (corresponding-videos)
(list
"https://www.ai-class.com/course/video/videolecture/27"
"https://www.ai-class.com/course/video/videolecture/28"
"and more!"))
(define (1-introduction)
(printf
(string-append
"can the agent come up with a solution from arod to bucarest\n"
"given knowledge on map which excludes the location of bucarest?\n"))
(printf "no.\n"))
(define (example-problem)
(printf "find path from arad to bucharest"))
(define action-costs
'((arad zerind 75)
(arad sibiu 140)
(arad timisoara 118)
(zerind oradea 71)
(sibiu oradea 151)
(sibiu fagaras 99)
(sibiu rimnicu-vilcea 80)
(timisoara lugoj 111)
(fagaras bucharest 211)
(rimnicu-vilcea pitesti 101)
(rimnicu-vilcea craiova 146)
(lugoj mehadia 70)
(bucharest pitesti 101)
(bucharest urziceni 85)
(bucharest giurgiu 90)
(pitesti craiova 138)
(mehadia drobeta 75)
(urziceni vaslui 142)
(urziceni hirsova 98)
(drobeta craiova 120)
(vaslui iasi 92)
(hirsova eforie 86)
(iasi neamt 87)))
(define cities
(remove-duplicates (append (map first action-costs)
(map second action-costs))))
(struct
state (city)
#:transparent
#:guard
(lambda (city type-name)
(if (member city cities)
city
(error type-name "bad city: ~e" city))))
(struct
action (state-from state-to)
#:transparent
#:guard
(lambda (state-from state-to type-name)
(unless (member state-from state-space)
(error type-name "bad state-from: ~e" state-from))
(unless (member state-to state-space)
(error type-name "bad state-to: ~e" state-to))
(values state-from state-to)))
(define state-space
(for/list ([city cities])
(state city)))
(define initial-state
(state 'arad))
(define (actions current-state)
(define current-city (state-city current-state))
(define (go-to destination)
(action (state current-city) (state destination)))
(define (is-current-city? city)
(equal? city (state-city current-state)))
(cond
[(is-current-city? 'arad)
(list
(go-to 'zerind)
(go-to 'sibiu)
(go-to 'timisoara))]
[(is-current-city? 'zerind)
(list
(go-to 'arad)
(go-to 'oradea))]
[(is-current-city? 'sibiu)
(list
(go-to 'arad)
(go-to 'oradea)
(go-to 'fagaras)
(go-to 'rimnicu-vilcea))]
[(is-current-city? 'timisoara)
(list
(go-to 'arad)
(go-to 'lugoj))]
[(is-current-city? 'oradea)
(list
(go-to 'zerind)
(go-to 'sibiu))]
[(is-current-city? 'fagaras)
(list
(go-to 'sibiu)
(go-to 'bucharest))]
[(is-current-city? 'rimnicu-vilcea)
(list
(go-to 'sibiu)
(go-to 'pitesti)
(go-to 'craiova))]
[(is-current-city? 'lugoj)
(list
(go-to 'timisoara)
(go-to 'mehadia))]
[(is-current-city? 'bucharest)
(list
(go-to 'pitesti)
(go-to 'fagaras)
(go-to 'urziceni)
(go-to 'giurgiu))]
[(is-current-city? 'pitesti)
(list
(go-to 'rimnicu-vilcea)
(go-to 'bucharest)
(go-to 'craiova))]
[(is-current-city? 'craiova)
(list
(go-to 'drobeta)
(go-to 'rimnicu-vilcea)
(go-to 'pitesti))]
[(is-current-city? 'mehadia)
(list
(go-to 'lugoj)
(go-to 'drobeta))]
[(is-current-city? 'urziceni)
(list
(go-to 'vaslui)
(go-to 'hirsova)
(go-to 'bucharest))]
[(is-current-city? 'giurgiu)
(list
(go-to 'bucharest))]
[(is-current-city? 'drobeta)
(list
(go-to 'mehadia)
(go-to 'craiova))]
[(is-current-city? 'vaslui)
(list
(go-to 'iasi)
(go-to 'urziceni))]
[(is-current-city? 'hirsova)
(list
(go-to 'urziceni)
(go-to 'eforie))]
[(is-current-city? 'iasi)
(list
(go-to 'neamt)
(go-to 'vaslui))]
[(is-current-city? 'eforie)
(list
(go-to 'hirsova))]
[(is-current-city? 'neamt)
(list
(go-to 'iasi))]
[else (error "invalid state: " state)]))
(define (result state action)
(action-state-to action))
(define (step-cost current-state current-action)
(define city-a (state-city (action-state-from current-action)))
(define city-b (state-city (action-state-to current-action)))
(if (member current-action (actions current-state))
(third (findf (lambda (action-cost)
(or (and (equal? city-a (first action-cost))
(equal? city-b (second action-cost)))
(and (equal? city-a (second action-cost))
(equal? city-b (first action-cost)))))
action-costs))
(error "invalid state action pair: " current-state current-action)))
(define (goal-test check-state)
(equal? check-state (state 'bucharest)))
(define (path-valid? path)
(define (_path-valid? path expected-start)
(or (empty? path)
(match path [(list (list start action end) rest-of-path ...)
(and (equal? start expected-start)
(member action (actions start))
(equal? (action-state-to action) end)
(_path-valid? rest-of-path end))])))
(_path-valid? path initial-state))
(define (path-cost path)
#;"path should be list of (state action result) triplets"
(foldl (lambda (step-triplet total-cost)
(let ([current-state (first step-triplet)]
[current-action (second step-triplet)])
(+ total-cost (step-cost current-state current-action)))) 0 path))
(provide (all-defined-out))
Jump to Line
Something went wrong with that request. Please try again.