[plt-scheme] HtDP newbie question, 12.4.2

From: Cooke Kelsey (cookekelsey at yahoo.com)
Date: Fri Mar 28 21:03:20 EDT 2008

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?"
  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)
    [(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)))]))
  (add-letter-to-recursive-list 'x (list 'w 'a 't 'e 'r))
 (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)
    [(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)))
  (add-letter-plus-prefix 'x (list 'w 'a 't 'e 'r))
 (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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080328/477d4764/attachment.html>

Posted on the users mailing list.