[plt-scheme] HtDP newbie question, 12.4.2

From: Marco Morazan (morazanm at gmail.com)
Date: Sat Mar 29 10:55:50 EDT 2008

On Sat, Mar 29, 2008 at 12:03 AM, Matthias Felleisen
<matthias at ccs.neu.edu> wrote:
>
>
> 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))
>

So, in other words:

>    (list (list 'X 'T)
>           (list 'T 'X))

are all the words you can create with letter = 'X and (rest a-word) =
(list 'T). As Matthias, points out this is done recursively....no need
to think about it. What do you with (first a-word) = 'A? Just add it
to the front of each of the words created from letter and (rest
a-word) to get all the words you can make with letter and a-word that
have (first a-word) as the first letter.

Are you worried about

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

not being the list of all possible words? Why are you worried about
it? The above, as I pointed out, is the list of words that have (first
a-word) = 'A as the first letter. The missing words (i.e. those for
which (first word) is not the first letter) are taken care of
elsewhere. Where? Take a look at (arrangements a-word)........

(define (arrangements a-word)
  (cond [(null? a-word) '(())]
        [else (insert-everywhere-in-all-words (first a-word)
                                              (arrangements (rest a-word)))]))

What is this saying?

(arrangements (rest a-word)) = all words that do not contain (first a-word)

(insert-everywhere-in-all-words (first a-word) (arrangements (rest a-word))) =
all words that can be formed with the letters in a-word.

Your problem is now reduced to inserting one letter (i.e. (first
a-word)) everywhere in every word in a list of words. You need to
process one word at a time, (insert-everywhere-in-word letter <word>),
which now reduces your problem to inserting a letter everywhere in a
single word.

(insert-everywhere-in-word letter a-word) = a list of all words that
can be formed with letter and a-word.

How do you do this?

1) One element is easy to see: (cons letter a-word)

2) Notice that all other words will have (first a-word) as the first
letter. That is easy to do using (add-letter-to-all  <letter>
<list-of-words>). What you need now is to create all the words
possible from letter and (rest a-word). What function consumes a
letter and a word and gives you a list of all the words you can create
from them?

Put 1 and 2 together and you are done!

> (10 keystrokes)
>

Yes, you are practically there!!!

I really hope I am not just confusing you and that I am actually
helping. Feel free to ignore my discourse if it is not clicking.

Marco


Posted on the users mailing list.