The cat exchanges places with a drawing of the cat

Question

Given

CAT               RENDERING

see if you can get them to exchange places, resulting in

RENDERING               CAT

by transferring one "chunk" of letters at a time.

A "chunk" is a consecutive string of letters taken from anywhere within the word. It can also be inserted anywhere into the other word. It must consist of at least two letters (no single-letter chunks), but there is no length limit. The transferred chunk does not need to be a valid word.

Each side, however, must remain a valid English word after extraction and insertion of the chunk.

Demonstration of the movement:

 PLANS            PAINTER
   |            .   |
   |          .     |
   |        ER      |
   |      .         |
   v    .           v
PLANERS           PAINT
   |    .           |
   |      .         |
   |       ERS      |
   |          .     |
   v            .   v
 PLAN             PAINTERS
   |            .   |
   |          .     |
   |       TER      |
   |      .         |
   v    .           v
PLANTER           PAINS
   |    .           |
   |      .         |
   |       LANT     |
   |          .     |
   v            .   v
  PER             PLANTAINS
   |            .   |
   |          .     |
   |       TAIN     |
   |      .         |
   v    .           v
PERTAIN           PLANS

While this example happens to show the movement of the transfers alternating between right to left and left to right, this is not a requirement. At each step, you may transfer the chunk in either direction as you choose.

Answer 1

I think this fits the criteria:

CAT-----------------RENDERING
CATERING-------REND
CARING-----------RENTED
CANTERING-----RED
RING---------------CANTERED
RINGED-----------CANTER
RED----------------CANTERING
RENTED----------CARING
REND--------------CATERING
RENDERING----CAT

Answer 2

This is solvable in seven nine^* moves, using the dictionary file /usr/share/dict/words that coms with Ubuntu 18.04.

1> (solve "cat" "rendering") cat rendering catering rend (ering) cantering red (n) canter ringed (ing) cantered ring (ed) red cantering (cante) rend catering (n) rendering cat (ering)

Code below, in TXR Lisp. To find the shortest path, we perform a depth-first search.

The nodes in the search graph are represented by items which consist of a left word, right word, a path link (giving a reverse path from the found node back to the start), and a key for determining whether two nodes are equal.

At each node, we generate all the possible next items by moving all possible chunks from either word, inserting it in all places in the other word, pruning away items that aren't dictionary words, and then in the traversal, pruning away anything we have already visited.

Function find-path is basically this algorithm.

(defparm dict (hash-list (file-get-lines "/usr/share/dict/words")))

;; some non-word junk in the above file; add as necessary
(each ((junk '#"s t q"))
  (del [dict junk]))

(defstruct item nil
  left right chunk
  key link
  (:postinit (me) (set me.key (cons me.left me.right)))
  (:method equal (me) me.key)
  (:method recover-path (me)
    (build (while me (add* me) (set me me.link)))))

(defun next-word-pairs (cull-word grow-word reversed)
  (build
    (for ((cl 2)) ((< cl (len cull-word))) ((inc cl)) ;; chunk length
      (for ((sp 0)) ((<= sp (- (len cull-word) cl))) ((inc sp)) ;; start pos
        (let* ((next-cull (copy cull-word))
               (chunk (del [next-cull sp..(+ sp cl)])))
          (when [dict next-cull]
            (for ((ip 0)) ((<= ip (len grow-word))) ((inc ip))
              (let ((next-grow (copy grow-word)))
                (set [next-grow ip..ip] chunk)
                (when [dict next-grow]
                  (add (if reversed
                         (new item left next-grow
                                   right next-cull chunk chunk)
                         (new item left next-cull
                                   right next-grow chunk chunk))))))))))))

(defun find-path (start goal visited)
  (buildn
    (set [visited start] t)
    (add start)
    (while (get)
      (let ((item (del)))
        (if (equal item goal)
          (return item)
          (let ((nwp (append (next-word-pairs item.left item.right nil)
                             (next-word-pairs item.right item.left t))))
            (each ((p nwp))
              (unless [visited p]
                (set [visited p] t
                     p.link item)
                (add p)))))))))

(defun solve (left-word right-word)
  (let ((start (new item left left-word right right-word))
        (goal (new item left right-word right left-word))
        (visited (hash)))
    (whenlet ((found (find-path start goal visited)))
      (each ((p found.(recover-path)))
        (put-line `@{p.left} @{p.right}@(if p.chunk ` (@{p.chunk})`)`)))))

P.S. A different sequence is found for the example given in the question:

1> (modified-solve "plans" "painter" "pertain")
plans painter
planters pain (ter)
plan painters (ters)
planter pains (ter)
per plantains (lant)
pertain plans (tain)

Why? Because the dictionary lacks an entry for planers! If that is manually added to the dict hash, then the example sequence is found.

---

* I fixed the initial value of cl from 1 to 2 to conform to the rule that single letter moves are disallowed.