[plt-scheme] HtDP newbie question, 12.4.2

Hallelujah......I've pretty much got it!  
   
  I don't exactly get the correct answer (see below), but it pretty much works:
   
  ;MAIN FUNCTION: arrangements: word --> list of words
  (define (arrangements a-word)
  (cond [(empty? a-word) (cons empty empty)]
        [else (insert-everywhere/in-all-words (first a-word) (arrangements (rest
 a-word)))]))
   
  ;HELPER #1: insert-everywhere/in-all-words : letter, list of words --> list of words
  (define (insert-everywhere/in-all-words s low)
  (cond
    [(empty? (rest low)) (insert-everywhere/one-word s (first low))]
    [else (append (insert-everywhere/one-word s (first low)) (insert-everywhere/in-all-words s (rest low)))]))
   
  ;HELPER #2: insert-everywhere/one-word : letter, word --> list of words
  ;NOTE: this function just adds the last word to Helper #3
  (define (insert-everywhere/one-word letter a-word)
  (append (list (append a-word (list letter))) (insert-everywhere-except-last-letter letter a-word)))
   
  ;HELPER #3: insert-everywhere-except-last-letter : letter, word --> list of words
  (define (insert-everywhere-except-last-letter letter a-word)
  (cond
    [(empty? a-word) (cons empty empty)]
    [(empty? (rest a-word)) (cons (list letter (first a-word)) empty)]
    [else (cons (cons letter a-word) (add-first-letter (first a-word) (insert-everywhere-except-last-letter letter (rest a-word))))]))
  ; NOTE: THERE IT IS!  the expression I couldn't figure out: "(cons (cons letter a-word) (add-first-letter (first a-word) (insert... letter (rest a-word))))"
   
  ;HELPER #4 : add-first-letter : letter, list of words --> list of words
  (define (add-first-letter letter low)
  (cond 
    [(empty? (rest low)) (cons (append (list letter) (first low)) empty)]
    [else (cons (append (list letter) (first low)) (add-first-letter letter (rest low)))]))
  
;test
  (arrangements (list 'd 'a 'r 'e))
  ;expected result:
  ;(list
; (list 'e 'r 'a 'd)
; (list 'd 'e 'r 'a)
; (list 'e 'd 'r 'a)
; (list 'e 'r 'd 'a)
; (list 'a 'e 'r 'd)
; (list 'd 'a 'e 'r)
; (list 'a 'd 'e 'r)
; (list 'a 'e 'd 'r)
; (list 'e 'a 'r 'd)
; (list 'd 'e 'a 'r)
; (list 'e 'd 'a 'r)
; (list 'e 'a 'd 'r)
; (list 'r 'e 'a 'd)
; (list 'd 'r 'e 'a)
; (list 'r 'd 'e 'a)
; (list 'r 'e 'd 'a)
; (list 'a 'r 'e 'd)
; (list 'd 'a 'r 'e)
; (list 'a 'd 'r 'e)
; (list 'a 'r 'd 'e)
; (list 'r 'a 'e 'd)
; (list 'd 'r 'a 'e)
; (list 'r 'd 'a 'e)
; (list 'r 'a 'd 'e))
   
  ; actual result:
  ;(list
; (list 'e 'r 'a 'd)
; (list 'd 'e 'r 'a)
; (list 'e 'd 'r 'a)
; (list 'e 'r 'd 'a)
; (list 'a 'e 'r 'd)
; (list 'd 'a 'e 'r)
; (list 'a 'd 'e 'r)
; (list 'a 'e 'd 'r)
; (list 'e 'a 'r 'd)
; (list 'd 'e 'a 'r)
; (list 'e 'd 'a 'r)
; (list 'e 'a 'd 'r)
; (list 'r 'e 'a 'd)
; (list 'd 'r 'e 'a)
; (list 'r 'd 'e 'a)
; (list 'r 'e 'd 'a)
; (list 'a 'r 'e 'd)
; (list 'd 'a 'r 'e)
; (list 'a 'd 'r 'e)
; (list 'a 'r 'd 'e)
; (list 'r 'a 'e 'd)
; (list 'd 'r 'a 'e)
; (list 'r 'd 'a 'e)
; (list 'r 'a 'd 'e)
; (list 'r 'a 'd)
; (list 'd 'r 'a)
; (list 'r 'd 'a)
; (list 'a 'r 'd)
; (list 'd 'a 'r)
; (list 'a 'd 'r)
; (list 'a 'd)
; (list 'd 'a)
; (list 'd)
; empty)

Matthias Felleisen <matthias at ccs.neu.edu> wrote:
  
  On Mar 28, 2008, at 9:03 PM, Cooke Kelsey wrote:
    Here's an answer to your question:
   
  Q: "Can you design a function that adds a letter (no matter what it is) to the front of all these words you have gotten back?...DONE? After that: what is missing?"
  

  NO! NO! 
  

  Look at the table for a call to insert-everywhere/one-word with 'X and (list 'A 'T). <<--- original call 
  

   If you now recursively call 
  

   * (insert-everywhere/one-word s (rest word)) and get 
     (list (list 'X 'T) 
            (list 'T 'X)) 
  

  and then you call 
  

   *  (add-letter-to-all (first word) ... the above ..) you get 
       (list (list 'A 'X 'T) 
              (list 'A 'T 'X))
  

  What do you want for the result of the original call? 
  How can you add this to what you have so far? 
  (10 keystrokes)
  

  That's the question I raise. -- Matthias
  

  

  

  

  

  

  

  

  


     
  A: What's missing is the second letter, the third, etc.   
   
  That is, I can add "W" to a list:
   
   (list 'w 'x 'a 't 'e 'r)
 (list 'w 'x 't 'e 'r)
 (list 'w 'x 'e 'r)
 (list 'w 'x 'r))
   
  But I also need "A" "T" E" "R" to be added, incrementally:
   
   (list 'w 'x 'a 't 'e 'r)
 (list 'w 'a 'x 't 'e 'r)
 (list 'w 'a 't 'x 'e 'r)
 (list 'w 'a 't 'e 'x 'r)
   
  Mark suggested that I look carefully at the table and see how I can "rearrange" the items in the columns to produce the result.  Everyone seems to suggest that the answer is found in that table, so I have been copying it and drawing arrows between the letters.  
   
  At this point the solution seems to be to create a second shrinking list of (rest words), flip it around backwards and then merge it into the original list.  I've written some functions to attempt this, but nothing near the expected result.  
   
  Marco has suggested that my entire approach is wrong, that I should build words correctly from the beginning instead of adding missing letters.  
   
  I'm going to begin again from scratch and pay closer attention to the template and contracts.
   
  
Matthias Felleisen <matthias at ccs.neu.edu> wrote:
    

  Why did you throw away your progress (add-first-letter)? 
  

  Why did you not answer my second question? 
  

  (I'll give you that much: with the two you are about 10 keystrokes from the answer.) 
  

  I am getting the feeling your jumping again. 
  

  ;; --- 
  

  Let's step back a bit. The purpose of this extended exercise is to practice the two ideas that the book has introduced at that point: 
  

  1. that the design recipe works on a per function basis -- BUT YOU NEED TO STICK TO IT; 
  2. that the 'wish list' works -- BUT YOU NEED TO STICK TO IT.  (If you are systematic about this, you just never forget where in the problem you are.) 
  

  ;; --- 
  

  Another step back: 
  

  1. In case you're wondering:  most people would consider this exercise way beyond a first-semester exercise. (It was on my MS exam in 1981.) 
  

  2. HtDP/2e will use a simpler exercise than that and push back Arrangements until students have more practice. A lot of people have problems with it though in 1-1 meetings, it's much easier to tease out the answers to these questions because the speed is higher and less frustrating. 
  

  

  

  -- Matthias
  

  

  

  


  On Mar 28, 2008, at 5:35 PM, Cooke Kelsey wrote:
    Dear Matthias / Marco,
   
  I read Marco's suggestions.  It was very helpful to read through the whole problem again in clear English and remember how I got to the function "insert-in-single-word."  I think I am near to the answer.
   
  You both ask me a similar question:

  (1) Matthias:  Can you design a function that adds a letter (no matter what it is) to the front of all these words you have gotten back?...DONE? After that: what is missing? 
   
     given:          the recursion                           in the final result I want                     
    'X   "ATE"     "X" "TE" --> "XTE" "TXE" "TEX"     "AXTE" "ATXE" "ATXE" "ATEX"           

  (2) Marco: "Here is where I believe you are really stuck. It is easy to see one member of the result: (letter a-word). This puts letter before the first letter of a-word. Is that the only place it can go? No, it can go before any of the letters in a word and at the end of a-word. How do you insert a letter everywhere in (rest a-word)? Once you have this list (call it R) all you need is to do something with (first a-word).  Where does it have to go in each of R?"

   
  OK, here is a function which I think answers these questions:
   
  (define (add-letter-to-recursive-list letter a-word)
  (cond
    [(empty? (rest a-word)) (cons (list letter (first a-word)) empty)]
    [else (cons (cons letter a-word) (add-letter-to-recursive-list letter (rest a-word)))]))
   
  ;example:
  (add-letter-to-recursive-list 'x (list 'w 'a 't 'e 'r))
  ;answer
  (list
 (list 'x 'w 'a 't 'e 'r)
 (list 'x 'a 't 'e 'r)
 (list 'x 't 'e 'r)
 (list 'x 'e 'r)
 (list 'x 'r))
  
Then next question is, how can I put the missing letters back on the front of these words?  
   
  For this, I can use the "add-first-letter" function which I sent earlier to Matthias:
   
  (define (add-first-letter first-letter low)
  (cond 
    [(empty? (rest low)) (cons (append (list first-letter) (first low)) empty)]
    [else (cons (append (list first-letter) (first low)) (add-first-letter first-letter (rest low)))]))
   
  Now, I can combine the two functions into a main function, "add-letter-plus-prefix":
   
  (define (add-letter-plus-prefix x a-word)
  (add-first-letter (first a-word) (Rest x a-word)))
   
  ;example:
  (add-letter-plus-prefix 'x (list 'w 'a 't 'e 'r))
  ;answer:
  (list
 (list 'w 'x 'w 'a 't 'e 'r)
 (list 'w 'x 'a 't 'e 'r)
 (list 'w 'x 't 'e 'r)
 (list 'w 'x 'e 'r)
 (list 'w 'x 'r))
   
  It looks nice, but the word is still shrinking away.  I have simply added the first letter to the beginning of all the words.  My problem is still, how can I increment the prefix in order: 'w, 'a, 't, 'e, 'r?  
   
  At this point, I think my problem is too many levels of abstraction.  I think that you all can see the answer very clearly, but I can't visualize multiple recursive functions.  The tables, etc have been extremely helpful for me to develop the individual functions.  As far as the final solution, perhaps I don't have the ability to "see" it on that level of abstraction?

  

  
---------------------------------
  You rock. That's why Blockbuster's offering you one month of Blockbuster Total Access, No Cost.



       
---------------------------------
Be a better friend, newshound, and know-it-all with Yahoo! Mobile.  Try it now.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080329/3a4e417d/attachment.html>