;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                                                                     ;;;
;;; CS3 FALL 2001 MIDTERM #2 (RECURSION) ANSWERS, Instructor Dan Garcia ;;;
;;;                                                                     ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;
;; QUESTION 1 : numbers
;;;;;;;;;;;;;;;;;;;;;;;

(define (numbers n ans)
  (if (= n 0)
      ans
      (numbers
        (- n 2)
        (se (- n 1) ans n)))) 

;; PART a

numbers is TAIL recursive, because the recursive call is not embedded
within another waiting expression, like:

(word (numbers (- n 2) ...
(+    (numbers (- n 2) ...
etc.

;; GRADING: All-or-nothing (2 pts)

;; PART b

(numbers 2 '())
;; ==> (if (= 2 0) '() (numbers (- 2 2) (se (- 2 1) '() 2)))
;; ==> (if   #f    '() (numbers (- 2 2) (se (- 2 1) '() 2)))
;; ==> (numbers 0 (se 1 '() 2))
;; ==> (numbers 0 '(1 2))
;; ==> (if (= 0 0) '(1 2) (numbers (- 0 2) (se ...
;; ==> (if   #t    '(1 2) (numbers (- 0 2) (se ...
;; ==> (1 2)

;; GRADING: All-or-nothing (2 pts).
;;          -1 for returning '(1 2), but in future exams extra/missing quotes
;;             will probably render an otherwise perfect answer incorrect.

;; PART c

(numbers 3 '())
;; ==> base case test false, so...
;; ==> (numbers  1 (se 2 '() 3))
;; ==> (numbers  1 '(2 3))
;; ==> base case test false, so...
;; ==> (numbers -1 (se 0 '(2 3) 1))
;; ==> (numbers -1 '(0 2 3 1))
;; ==> base case test false, so...
;; ==> (numbers -3 (se -2 '(0 2 3 1) -1))
;; ==> (numbers -3 '(-2 0 2 3 1 -1))
;; ==> ...etc... (infinite-loop)
;;
;; ==> Answer: "it never returns"

;; GRADING: All-or-nothing (2 pts)

(define (my-numbers n ans)
  (if (<= n 0)
      ans
      (my-numbers
        (- n 2)
        (se (- n 1) ans n))))

;; PART d

(count (my-numbers 100 '()))

On every recursive call, the sentence gets bigger by 2 
and n is decreased by 2. 

Another way to look at this is to look at the pattern on the length
for small values of n. That is,

(count (my-numbers 2 '())) ==> (1 2) [count = 2]
(count (my-numbers 4 '())) ==> (1 3 4 2) [count = 4]
(count (my-numbers 6 '())) ==> (1 3 5 6 4 2) [count = 6]
(count (my-numbers 8 '())) ==> (1 3 5 7 8 6 4 2) [count = 8]
...etc.
Therefore, the return value is exactly n for even n.
;; 
;; ==> 100    

;; GRADING: 2 points for 100
;;          1 point  for 98, 99, 100, 101 [probably off-by-1 error]

;; PART e

(mystery 100 '())

Again, looking at the pattern gives a good idea how the function works.

(count (my-numbers 2 '())) ==> (1 2) [count = 2]
(count (my-numbers 4 '())) ==> (1 3 4 2) [count = 4]
(count (my-numbers 6 '())) ==> (1 3 5 6 4 2) [count = 6]
(count (my-numbers 8 '())) ==> (1 3 5 7 8 6 4 2) [count = 8]
...etc.

Taking a look at the return values above, it appears
the return values for higher and higher n only change internally.
I.e., n >= 2, the outside values are always 1 and 2, 
      n >= 4, the ones inside that are always 3 and 4, etc.
      n >= 6, the ones inside that are always 5 and 6, etc.
;;
;; ==> (1 3 5 ... 6 4 2)

;; GRADING: 2 points for the first 3, 2 points for the last 3.
;;          If you swapped the first three and last three, only 2 points total.

;;;;;;;;;;;;;;;;;;;;;
;; QUESTION 2 : Betty 
;;;;;;;;;;;;;;;;;;;;;

(define (not-betty-word? w)
  (cond 
    ((empty?     w ) #f)
    ((empty? (bf w)) #f)
    ((before? (first w) (second w))
     (not-betty-word? (bf (bf w))))
    (else
     (word (first w) (second w)))))

;; PART a

The suggestion is that betty-word? does the following

(define (betty-word? w)
  (if ;; a betty word
      ;; then return #t
      ;; otherwise, return first pair of letters violating betty-word property
  ))

Is this fundamentally wrong?

YES! (for two reasons discussed below)

1. "The function name ends in '?' which seems to imply that it should be
   a predicate, but it doesn't return #t/#f -- fundamental range error"

2. "The function, which seems to want to be a semipredicate, doesn't ever
   return #f so will always be considered 'true' by if & cond -- fundamental
   logic error"

   Said another way, if we read between the lines and assume the person really 
   wanted to write a semi-predicate (which don't end in "?"), then it
   isn't restricted to returning #t always. However, it MUST return #f
   in some cases, otherwise it will always return a non-#f answer, and
   will always be treated as 'true' by if/cond statements. That is,

(define (foo w)
  (if (betty-word? w) 'yay 'nay))

   will ALWAYS return yay.

;; GRADING: All-or-nothing (2 pts)

;; PART b

not-betty-word? is a FINDING pattern, since it _finds_ the first set of
letters that matches some criterion. 

;; GRADING: 2 pts FINDING pattern
;;          1 pt  TESTING pattern (thrown off by the trailing '?', but close)

;; PART c

(define (not-betty-word? w)
  (cond 
1    ((empty?     w ) #f)
2    ((empty? (bf w)) #f)
3    ((before? (first w) (second w))
4     (not-betty-word? (bf (bf w))))
5    (else
6     (word (first w) (second w)))))

(not-betty-word? 'abcedf) 
;; third case (the before? test) is true, so
;; ==> (not-betty-word? 'cedf) 
;; third case (the before? test) is true, so
;; ==> (not-betty-word? 'df) 
;; third case (the before? test) is true, so
;; ==> (not-betty-word? "") 
;; first base case #t, so return #f

But it should have returned 'ed'. Looking at the recursive calls, it is clear
that it's skipping TWO letters instead of just ONE with every recursive call.
I.e., it's doing (bf (bf w)) instead of simply (bf w). Therefore, we replace 
line 4 with (not-betty-word? (bf w))

;; GRADING: All-or-nothing (5 pts)

;; PART c

Hmmm. What's the bug? This takes some detective work. After trying it on,
say, the sentence Betty says at the top of the page as input, it returns:

(not-betty-word?    'lo) ==> #f, correct response
(not-betty-word?     'i) ==> #f, correct response
(not-betty-word?    'am) ==> #f, correct response
(not-betty-word?  'lost) ==> #f, correct response
(not-betty-word?  'bill) ==> ll, INCORRECT RESPONSE

What was wrong? It appears that the code tests for the word to be strictly
increasing, whereas betty-words are words that are non-decreasing. That is,
any words with adjacent duplicate letters (like 'bill) get flagged when they
really shouldn't. If we make the connection with numbers, we want to test
whether first <= second, but the code tests whether first < second.

How can we fix it? The easiest fix would be to write (or use, if one already
exists) another function called 'before-or-same?' and just replace
'before' with 'before-or-same?'. (Math analogy: replace '<' with '<=')

But before-or-same? doesn't exist (and we can't write a helper), so what
do we do? There's the easy-and-clever way and the hard way.

The easy-and-clever way is to realize that, logically, a <= b is the same
as saying b is NOT < a. Or in scheme: (<= a b) is the same as (not (< b a))
Thus, we just swap the arguments to before? and put a 'not' in front:

"Replacing line #3 with (not (before? (second w) (first w)))" ...

The harder way is to try to write (<= a b) by writing (or (< a b) (= a b)),
BUT the exam said we can't use 'equal?', which would be the equivalent test
for equality with letters. How can we write equal? some other way? Students
thought of many:

(member? (first w) (second w))
(member? (first w) (se (second w)))
(= 1 (appearances (first w) (second w)))
(= 2 (appearances (first w) (word (first w) (second w))))

So the answer, as written, using the harder way (and the first example) is:

"Replacing line #3 with (or (before? (first w) (second w))
                            (member? (first w) (second w)))" ...

;; Thus, the final edited version of the original code becomes:

(define (not-betty-word? w)
  (cond ((empty?     w ) #f)
        ((empty? (bf w)) #f)
        ((not (before? (second w) (first w)))
         (not-betty-word? (bf w)))
        (else
         (word (first w) (second w)))))

...but what is the shortest English that has adjacent duplicate
letters, ALL in non-decreasing order? It's useful to have the alphabet around:

abcdefghijklmnopqrstuvwxyz

Are there any two-letter words with an adjacent duplicate letter? Well,
consonants won't work, so are aa, ee, ii, oo and uu words? No. Therefore
the word has to be at least three characters long. Fortunately, there are
tons of these (sl=slang, which were accepted):

add, all, ass (as in 'donkey'), aww (sl), egg, err (sl), eww (sl)
ill, inn, oww (sl), bee, boo, doo (sl), foo (cs sl), goo (sl), moo (sl)

using one of these the last answer becomes:

"...would cause (not-betty-word? add) to correctly return #f instead of dd.

;; GRADING: 4 "replacement" line (-1 for redundant [a<b AND a<=b] case)
;;          2 "would cause" line (-1 for not being a word and 3 letters)

;;;;;;;;;;;;;
;; QUESTION 3
;;;;;;;;;;;;;

;; PART a

We need to define play-round so that...

(play-round '(morocco france argentina usa iran germany england brazil))
;; ==> (france argentina germany brazil)

and the only constraints are that the count is even. Hmmm -- zero is
even, so this must be able to handle the case when teams is empty. In
that case, we should return the empty sentence.

Otherwise, we should play the first two teams against one another and
recursively call ourselves with the rest of the teams with the first
two removed. Translating this to scheme, this becomes:

(define (play-round teams)
  (if (empty? teams)                          ;; first line
      '()                                     ;; second line
      (se                                     ;; third line
        (winner (first teams) (second teams))
        (play-round (bf (bf teams))))))

Some people had the following as their base case:

(if (= (count teams) 2) ;; or (empty? (bf (bf teams)))
    (se (winner (first teams) (second teams)))

...but that would give an error if given empty input, which was in the
domain, so these folks lost a point for that. Some people did the above
but simply returned (winner (first teams) (second teams)). The range is
supposed to be teams (a sentence), but winner returns a team (a word).
These folks lost all 3 of their base case points for that.

;; GRADING: 3 base case test and answer (-3 not returning a sentence)
;;          6 recursive case (-3 first error)

;; PART b

Hmmm. We've got to write world-cup such that

(play-round '(morocco france argentina usa iran germany england brazil))
;; ==> france

But we know we have play-round which will reduce the field by half with
every call. Our base case is when there is one champion, i.e., teams is
of size 1. In this case we return that team, or (first teams)

Otherwise we recursively call ourselves with the problem one smaller. But
the procedure we use to simplify the input is not (- n 1) or (bf s) but
play-round! So the procedure is simply:

(define (world-cup teams)
  (if (empty? (bf teams)) ;; also (= (count teams) 1)
      (first teams)
      (world-cup (play-round teams))))

;; GRADING: 4 base case test and answer (-3 for returning teams)
;;          5 recursive case

;; PART c

Since there is no embedding procedure to the left of the recursive call,
we're using TAIL recursion.

;; GRADING: 2 (all-or-nothing)