Exercise 161: Design a program that sorts lists of game players by score:
(define-struct gp (name score)) ; A GamePlayer is a structure: ; – (make-gp String Number) ; interp. (make-gp p s) represents player p who scored ; a maximum of s points
This question (and solution) is again fairly similar to exercises 160 and 159. It's almost as though they wanted to drive home how similar these sorts of problems are.
Accordingly my answer is similar to the last, but we will still play along and create the solution from scratch...
; this struct is supplied by the question.
(define-struct gp (name score))
; start by creating a number of structs for easy testing etc
(define FIRST (make-gp "dave" 0 ))
(define SECOND (make-gp "bob" 10))
(define THIRD (make-gp "frank" 20))
(define FOURTH (make-gp "tom" 30))
; some tests to make sure we are doing things right.
(check-expect (sort-> empty) empty)
(check-expect (sort-> (list THIRD FOURTH FIRST))
(list FOURTH THIRD FIRST))
(check-expect (sort-> (list THIRD SECOND FIRST))
(list THIRD SECOND FIRST))
(check-expect (sort-> (list FIRST SECOND THIRD))
(list THIRD SECOND FIRST))
This is the basic sort function - as you can see it is more or less identical to the last solution.
; List-of-gps -> List-of-gps
; produces a version of a gps (game player score), sorted by score in
; descending order
(define (sort-> gps)
(cond
[(empty? gps) empty]
[else (insert (first gps) (sort-> (rest gps)))]))
; Gps, List-of-Gps -> List-of-Gps
; a helper function to do the actual insert
; insert n into the sorted list of gps's
(define (insert n alogps)
(cond [(empty? alogps) (cons n empty)]
[else (cond [(higher-score? n (first alogps)) (cons n alogps)]
[else (cons (first alogps)
(insert n (rest alogps)))])]))
; utility function to determine which of two games had the higher score
; we could do this inline, but this lends itself to more clarity i think
(define (higher-score? game-1 game-2)
(>= (gp-score game-1) (gp-score game-2)))
No comments:
Post a Comment