[racket] arrangements exercise

On Mon, Jul 2, 2012 at 1:51 AM, Dave Yrueta <dyrueta at gmail.com> wrote:
> I should have been more explicit:  "ensuring the function design conforms to its contract" means testing it in the manner demonstrated by Matthias. "Check-expect" is your friend :).
> On Jul 1, 2012, at 4:12 PM, Matthias Felleisen wrote:
>
>>
>> On Jul 1, 2012, at 4:17 PM, Sean Kemplay wrote:
>>
>>> Looking back, I am wondering if my solution is a bit of a cheat - specifically :
>>>
>>> (define (insert-everwhere/in-one-word s word)
>>> (make-words s word word))
>>
>>
>> It's not a cheat, it's wrong. I did you a favor and worked out a failing test case. See below.
>>
>>
>> On Jul 1, 2012, at 6:46 PM, Dave Yrueta wrote:
>>
>>> Try working through this exercise by systematically applying the design recipe.  That is, take the time to make your data definitions explicit, and begin the definition of each helper function with a contract, purpose statement, and template.  In my opinion, more than any other exercise in HtDP, the solution to this exercise relies on paying very close attention to how the data definitions, function contracts and function templates interact. If you allow the data definitions to shape the function templates, and are rigorous about ensuring the function designs conform to their contracts, the solution should fall into place.
>>
>>
>> The above is the best advice the list can give you. -- Matthias
>>
>>
>>
>>
>> ;; World  = [Listof Letter] ;; see chapter IV
>> ;; Letter = Symbol
>>
>> ;; Letter Word -> [Listof Word]
>> ;; the function says: insert _s_ in all positions in _word_
>>
>> (check-expect (insert-everwhere/in-one-word 'a '(w o))
>>              '((a w o) (w a o) (w o a)))
>> (check-expect (insert-everwhere/in-one-word 'a '(w w o))
>>              '((a w w o) (w a w o) (w w a o) (w w o a)))
>>
>> (define (insert-everwhere/in-one-word s word)
>> (make-words s word word))
>>
>> ;; Letter Word Word -> [Listof Word]
>> ;; insert _s_ in all positions in _word2_ using _word1_ as a list of insertion points
>> ;; intended usage: (make-words letter word word) i.e. word1 = word2 initially
>>
>> (check-expect (make-words 'a '(w o) '(w o)) '((a w o) (w a o) (w o a)))
>> (check-expect (make-words 'a '(w w o) '(w w o)) '((a w w o) (w a w o) (w w a o) (w w o a)))
>>
>> (define (make-words s word1 word2)
>> (cond
>>   [(empty? word1) (cons (append word2 (cons s empty)) empty)]
>>   [else (cons (insert-symbol s (first word1) word2) (make-words s (cdr word1) word2))]))
>>
>>
>> ;; Letter Letter Word -> Word
>> ;; add _new_ in front of each occurrence of _old_ in _word_
>>
>> (check-expect (insert-symbol 'a 'b '(c d e)) '(c d e)) ;; running in BSL with ..
>> (check-expect (insert-symbol 'a 'b '(b o b)) '(a b o a b))
>>
>> (define (insert-symbol new old word)
>> (cond
>>   [(empty? word) empty]
>>   [(symbol=? (first word) old) (cons new (cons old (insert-symbol new old (rest word))))]
>>   [else (cons (first word) (insert-symbol new old (rest word)))]))
>>
>>
>> ____________________
>>  Racket Users list:
>>  http://lists.racket-lang.org/users
>



Ok, I think I have it this time - only took five days!! After lots of
hear pulling, I started thinking about the actual steps required to
make the arrangements and created a wish list - then it started to
make sense. And yes the tests really do help.

; A split-word is a struct where left and right are list of words

(define-struct split-word (left right))

;; move-split split-word -> split-word
;; return a new split word with the list on the left having the first
of the right list appended to the end and the rest of the right
(define (move-split a-sw)
  (cond
    [(empty? (split-word-right a-sw)) a-sw]
    [else (make-split-word (append (split-word-left a-sw) (cons (first
(split-word-right a-sw)) empty)) (rest (split-word-right a-sw)))]))

(check-expect (move-split (make-split-word empty empty))
(make-split-word empty empty))
(check-expect (move-split (make-split-word '(a) empty))
(make-split-word '(a) empty))
(check-expect (move-split (make-split-word '(a) '(b)))
(make-split-word '(a b) empty))
(check-expect (move-split (make-split-word '(a) '(b c)))
(make-split-word '(a b) '(c)))
(check-expect (move-split (make-split-word '(a b) '(c d)))
(make-split-word '(a b c) '(d)))

;; insert-symbol symbol split-word -> word
;; Insert the sysmbo at the front of the left list and append the
right if left is empty
;; Append to end of left if right list is empty
;; Otherrwise insert between - returning one list
(define (insert-symbol s a-sw)
  (cond
    [(empty? (split-word-right a-sw)) (append (split-word-left a-sw)
(cons s empty))]
    [(empty? (split-word-left a-sw)) (cons s (split-word-right a-sw))]
    [else (append (split-word-left a-sw) (cons s (split-word-right a-sw)))]))

(check-expect (insert-symbol 'a (make-split-word empty empty)) '(a))
(check-expect (insert-symbol 'a (make-split-word '(b) empty)) '(b a))
(check-expect (insert-symbol 'a (make-split-word empty '(b))) '(a b))
(check-expect (insert-symbol 'a (make-split-word '(b) '(c))) '(b a c))


;;insert-everywhere/in-one-word symbol split-word -> low
;; take a symbol and a split word and insert the symbol before and
after each letter in the right hand side of the split
;;  creating a list of new words with the symbol progressing through.
(define (insert-everywhere/in-one-word s a-sw)
  (cond
    [(empty? (split-word-right a-sw)) (cons (insert-symbol s a-sw) empty)]
    [else (cons (insert-symbol s a-sw) (insert-everywhere/in-one-word
s (move-split a-sw)))]))


(check-expect (insert-everywhere/in-one-word 'a (make-split-word empty
empty)) (list (list 'a)))
(check-expect (insert-everywhere/in-one-word 'a (make-split-word '(b)
empty)) (list (list 'b 'a)))
(check-expect (insert-everywhere/in-one-word 'a (make-split-word empty
'(b))) (list '(a b) '(b a)))
(check-expect (insert-everywhere/in-one-word 'a (make-split-word empty
'(b c))) (list '(a b c) '(b a c) '(b c a)))

;; insert-everywhere/in-all-words symbol list-of-words -> list of words
;; insert the symbol in all possible positions in each word returning
an expanded list of words
(define (insert-everywhere/in-all-words s a-low)
  (cond
    [(empty? a-low) empty]
    [else (append (insert-everywhere/in-one-word s (make-split-word
empty (first a-low))) (insert-everywhere/in-all-words s (rest
a-low)))]))

(check-expect (insert-everywhere/in-all-words 'a (cons '(b) empty))
(list (list 'a 'b) (list 'b 'a)))

(check-expect (insert-everywhere/in-all-words 'd
  (cons (cons 'e (cons 'r empty))
    (cons (cons 'r (cons 'e empty))
      empty))) '((d e r) (e d r) (e r d) (d r e) (r d e) (r e d)))

(define (arrangements a-word)
  (cond
    [(empty? a-word) (cons empty empty)]
    [else (insert-everywhere/in-all-words (first a-word)
            (arrangements (rest a-word)))]))

(check-expect (arrangements '(a))  (list '(a)))
(check-expect (arrangements '(a b)) (list '(a b) '(b a)))

Any feedback welcome. Again, a big thank you for the advice above.

Sean