Exercise 169: Look up the documentation for explode and implode.

Exercise 169: Look up the documentation for explode and implode. 

Then formulate the function arrange-main, which consumes a String and produces all of its possible re-arrangements as a list of Strings.

This is a straight forward question. The method  implode will transform a (listof string) -> string) and explode will do the reverse. This will save us from needing to pass in a list of 1strings into the arrange method, and will present the rearranged letters as simple list of strings instead of a list of lists of strings.

Exploding the string being passed into arrange-main is a simple matter. However imploding the resulting list of strings is not - or at least it is not within the context of arrange-main. This is because by the time we get the list, it is already a list of lists of strings.

Imploding them within the arrange method when we have access to the individual lists of strings would be a simple matter, but that was not what was asked for.  Instead, we need to create a helper method that will then iterate over our list of lists of strings and implode them one by one.

; a simple test method. Most of the testing is done already 
; within the context of the arrange method.
(check-expect (arrange-main "cat")
              (list "tac" "tca" "cta" "atc" "act" "cat"))

; This method simply explodes the string passed in so that it can be 
; processed by arrange, and the passes the result into imploder-helper
; to implode the individual lists of strings.
;
; String -> List-of-Strings
(define (arrange-main string)
 (implode-helper (arrangements (explode string)) empty))


; This method takes in a complete list of lists of stings and an
; initially empty list-of-strings and implodes each list-of-strings
; and appends it to the end of the list-of-strings. 
;
; list-of-lists-of-strings, list-of-strings -> list-of-strings
(define (implode-helper list-of-lists list-of-strings)
  (cond ((empty? list-of-lists) list-of-strings)
        (else (implode-helper (rest list-of-lists) 
                              (cons (implode (first list-of-lists)) 
                                              list-of-strings)))))

Exercise 168

The code below is from exercise 168 and is only included as it is required to run the code above. The tests and documentation for the following code is detailed within the context of that exercise.

(define (arrangements w)
  (cond
    [(empty? w) (list empty)]
    [else (insert-everywhere/in-all-words (first w)
            (arrangements (rest w)))]))




(define (insert-everywhere/in-all-words letter words)
  (cond ((empty? words) empty)
        (else (append
               (insert letter (list empty (first words)) empty)
               (insert-everywhere/in-all-words letter (rest words))))))







(define (insert letter word-lists combinations)
  (cond ((empty? (second word-lists)) (append combinations  
                                              (ins-middle letter word-lists)))
        (else (insert letter
                      (progress-list word-lists)
                      (append combinations (ins-middle letter word-lists))))))




(define (progress-list word-lists)
  (list
   (append (first word-lists) (list (first (second word-lists))))
   (cond ((empty? (rest (second word-lists))) empty)
         (else   (rest (second word-lists))))))

(define (ins-middle letter word-lists)
  (cond ((empty? (first word-lists)) (list (cons letter (second word-lists))))
        (else (list (append (first word-lists) 
                            (list letter)  
                            (second word-lists) empty)))))

Exercise 168: Design insert-everywhere/in-all-words.

Exercise 168:  Design insert-everywhere/in-all-words.

It consumes a 1String and a list of words. The result is a list of words like its second argument, but with the first argument inserted at the beginning, between all letters, and at the end of all words of the given list.

Note: I've taken a slightly different approach to structuring this answer. As this is a reasonably complex question (at least compared to that which has been asked so far), there are a larger than normal number of functions. There are five supporting functions, which is not overly large number in itself, but as each function has a number of check-expect test functions to support, the signal-to-noise ratio became quite high. I have moved all of the check-expect functions to the end of the answer, and briefly described the point of each test there. This allows me to keep the main section of the answer uncluttered and a little easier to read

I'm not 100% happy with the approach I took to this solution. It seemed a clean solution in my head but when it came time to put it into code form it became a lot more complex. There is probably a solution out there that is a cleaner than this.

The problem we have is to take a list of letters, and return a new list of lists of letters with our new letter inserted into each place.  Helper functions aside, the main problem is to create a function that will take in a list and a letter, and return a new list with the letter inserted between each letter of the original list. I have called this function insert. In this function we need to recurse through the original word, letter by letter,  creating a new word by inserting the letter in the appropriate place and appending all these new words together.  The challenge here is as we recurse, we need to keep track of both the entire word that we are inserting the letter into, but also where in the word we should be inserting into.

Solving this procedurally with something like Ruby or Python would be very straight forward, but we need to come up with a way of doing this in a functional manner.  I could think of two ways of doing this:

1. Passing in an insertion position/count as you recurse through the word
2. Splitting the list into two - a before and after split, and changing the position of the split as you recurse.

The second option seemed a better idea, though in hindsight, I think passing a position down would have been easier.

Choosing the second option introduced new problems - maintaining this new list. I chose to wrap these before and afters lists up in a new list so that I could pass around only one list, instead of continually passing both lists. To simplify the main function I also required a function dedicated to moving the split in these two lists along. None of these issues were particularly difficult, but I think they could have been avoided altogether by choosing the first option.

Solution

The arrangements function here is taken directly from the text. It recurses through a word building up a list of subwords using the insert-everywhere/in-all-words helper function.

; 1String -> List-of-words
(define (arrangements w)
  (cond
    [(empty? w) (list empty)]
    [else (insert-everywhere/in-all-words (first w)
            (arrangements (rest w)))]))



The insert-everywhere/in-all-words function is the main function that we are asked to create - but does very little of the actual work.
It consumes a letter and a list of words and creates a new expanded list of words with the supplied letter inserted at each point within each word.
The work is mostly farmed out to the helper function insert which for a specific letter and word combination, returns a new list of words with the letter correctly inserted in each place. These lists are then appended together to form a larger list containing the combinations for each word passed in in the original list.

; Letter List of Words -> List of Words
(define (insert-everywhere/in-all-words letter words)
  (cond ((empty? words) empty)
        (else (append
               (insert letter (list empty (first words)) empty)
               (insert-everywhere/in-all-words letter (rest words))))))



The insert function does the actual inserting of the letter into the word. This function takes in three arguments - the letter to insert, a list containing the two sections of the word it should be inserting this letter between, and the expanded list of words with the letter already inserted. This last argument will have the newly created arrangement appended to it and will be the value returned.
The idea here is that we are passing two lists - list1 and list2, each containing a section of the word. The boundaries of the word sections in this list will be adjusted each time. Eg, in pseudo-code, inserting the letter X in the word "dog":


X (list nil dog) ->  (list d og)    (list Xdog)
X (list d og)    ->  (list do g)    (list Xdog dXog)
X (list do g)    ->  (list dog nil) (list Xdog dXog doXg)
X (dog nil)      ->  (list dog nil) (list Xdog dXog doXg dogX)


;insert the letter between word1 and word2 (parts of the same word)
; Letter, List-of-1Strings,  
(define (insert letter word-lists combinations)
  (cond ((empty? (second word-lists)) (append combinations  
                                              (ins-middle letter word-lists))) 
        (else (insert letter 
                      (progress-list word-lists)
                      (append combinations (ins-middle letter word-lists)))))) 





To simplify the insert function I have another helper function progress-list that does nothing other than move the split in the two words one character further along. There is no reason we couldn't have done this within the insert function, but moving it out here makes the insert function a lot shorter and easier to read.

; takes in list of two words segments (eg, a word split in two) and
; moves the split further down the list
; (list "wor" "d") -> (list "wo" "rd")
; list-of-words -> list-of-words
(define (progress-list word-lists)
  (list
   ; when we pull the first letter of the second word-list it's no longer a list
   ; to append it correctly, we need to use cons, or turn it back into a list
   (append (first word-lists) (list (first (second word-lists))))
   ; if we're at the end of the second-word list return an empty list
   ; rather than a list containing an empty list
   (cond ((empty? (rest (second word-lists))) empty)
         (else   (rest (second word-lists))))
  ))


The second helper function created to support insert is the ins-middle function. This function takes in a letter and a list of two word sections, and returns a new word with the letter inserted in the middle of the two lists.
Eg:

X (list empty "dog") -> Xdog
X (list "d" "og")    -> dXog


The letter is passed in simply as a character, not as  part of a list, so to use append we need to make it a list. we could use cons here, but that is so . .. messy

We also wrap what we are returning in a list. This isn't necessary, but this is a helper function for the main insert function which is more complex. The insert function requires the returned word to be part of a list already, (or it needs to convert the word to a list there). If we do not do this  all the words will get munged into one long word. By double wrapping the list here, we can make the main insert function shorter and a little clearer.


; letter list-of-1strings -> list-of-lists-of-1strings
(define (ins-middle letter word-lists)
  (cond ((empty? (first word-lists)) (list (cons letter (second word-lists))))
        (else (list (append (first word-lists)
                            (list letter) 
                            (second word-lists) empty)))))

Example Output

Finally, here is an example output of our arrangement function:


> (arrangements (list "w" "o" "r" "d"))
(list
 (list "w" "o" "r" "d")
 (list "o" "w" "r" "d")
 (list "o" "r" "w" "d")
 (list "o" "r" "d" "w")
 (list "w" "r" "o" "d")
 (list "r" "w" "o" "d")
 (list "r" "o" "w" "d")
 (list "r" "o" "d" "w")
 (list "w" "r" "d" "o")
 (list "r" "w" "d" "o")
 (list "r" "d" "w" "o")
 (list "r" "d" "o" "w")
 (list "w" "o" "d" "r")
 (list "o" "w" "d" "r")
 (list "o" "d" "w" "r")
 (list "o" "d" "r" "w")
 (list "w" "d" "o" "r")
 (list "d" "w" "o" "r")
 (list "d" "o" "w" "r")
 (list "d" "o" "r" "w")
 (list "w" "d" "r" "o")
 (list "d" "w" "r" "o")
 (list "d" "r" "w" "o")
 (list "d" "r" "o" "w"))

Tests for arrangements function

; a simple test of the functions behavior overall using a 3 letter list
(check-expect (arrangements (list "c" "a" "t"))
              (list
               (list "c" "a" "t")
               (list "a" "c" "t")
               (list "a" "t" "c")
               (list "c" "t" "a")
               (list "t" "c" "a")
               (list "t" "a" "c")))


; an arranged empty list should be an empty list
(check-expect (arrangements empty)
              (list empty))


; an arranged list of 1 char, should be a list of 1 list containing 1 char
(check-expect (arrangements (list "c"))
              (list (list "c")))

Tests for insert-everywhere/in-all-words function

; this is a subset of the arrangements test. A single list should
; rearrange as expected.
(check-expect (insert-everywhere/in-all-words "X" (list (list "d" "e")))
              (list (list "X" "d" "e")
                    (list "d" "X" "e")
                    (list "d" "e" "X")))


; test for an empty list - just returns an empty list
(check-expect (insert-everywhere/in-all-words "X" empty)
              empty)




; one word list
(check-expect (insert-everywhere/in-all-words "X" (list (list "e")))
                  (list (list "X" "e")
                        (list "e" "X")))

Tests for insert function

; this is a subset of the arrangements test. A single list should
; rearrange as expected.
(check-expect (insert "x" (list empty (list "c" "a" "t")) empty)
              (list (list "x" "c" "a" "t")
                    (list "c" "x" "a" "t")
                    (list "c" "a" "x" "t")
                    (list "c" "a" "t" "x")))

Tests for progress-list function

; "" "cat" -> "c" "at"
(check-expect (progress-list (list empty (list "c" "a" "t") ))
              (list (list "c") (list "a" "t")))


; "ca" "t" -> "cat" ""
(check-expect (progress-list (list (list "c" "a") (list "t" )))
              (list (list "c" "a" "t") empty))


No point testing this function with a empty second list as you can't progress this list any further - you would expect this to fail.

Tests for ins-middle function

; "x" "ca" "t"  -> "caxt"
(check-expect (ins-middle "x" (list (list "c" "a") (list "t")))
              (list (list "c" "a" "x" "t")))


; "x "" "cat" -> "xcat"
(check-expect (ins-middle "x" (list empty (list "c" "a" "t")))
              (list (list "x" "c" "a" "t" )))




; "x" "cat" "" -> "cat"
(check-expect (ins-middle "x"  (list (list "c" "a" "t") empty))
              (list (list  "c" "a" "t" "x")))