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
   |    .           |
   |      .         |
   |       ERS      |
   |          .     |
   v            .   v
 PLAN             PAINTERS
   |            .   |
   |          .     |
   |       TER      |
   |      .         |
   v    .           v
   |    .           |
   |      .         |
   |       LANT     |
   |          .     |
   v            .   v
  PER             PLANTAINS
   |            .   |
   |          .     |
   |       TAIN     |
   |      .         |
   v    .           v

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.

  • 3
    $\begingroup$ Great puzzle! River crossing tag though? $\endgroup$
    – Duck
    Aug 12 '19 at 22:33
  • 2
    $\begingroup$ @Duck — I feel that in its structure, it is a river-crossing problem. You have to get something from one side to the other (or, in this case, two things to opposite sides simultaneously) under certain constraints. $\endgroup$
    – SlowMagic
    Aug 12 '19 at 22:39
  • 1
    $\begingroup$ @Duck — At each step, there should always be a single, valid English word on each side of the river, as in the demonstration. So while your proposal is intriguing for another puzzle, the solution I have for this puzzle never allows for anything other than a single word on each side of the river. $\endgroup$
    – SlowMagic
    Aug 12 '19 at 23:23
  • 1
    $\begingroup$ Another great puzzle! $\endgroup$ Aug 13 '19 at 1:24
  • 1
    $\begingroup$ You should edit your puzzle question to specify that each side should remain a valid word after each extraction and insertion. $\endgroup$ Aug 13 '19 at 15:04

I think this fits the criteria:


  • 1
    $\begingroup$ I was close, but you were closer! Nice work! $\endgroup$
    – Cloudy7
    Aug 13 '19 at 1:24
  • 1
    $\begingroup$ I got to rend and catering, and then gave up :) +1 $\endgroup$
    – Duck
    Aug 13 '19 at 2:27
  • $\begingroup$ Since it's not required to zig-zag all the way, you can skip the third line (from both ends) altogether. $\endgroup$
    – Bass
    Aug 13 '19 at 6:41
  • 2
    $\begingroup$ @Bass Skipping the third line would mean a step with a single letter and it's stated in the OP that a chunk needs to be at least two. $\endgroup$ Aug 13 '19 at 8:19
  • 2
    $\begingroup$ @JohnClifford Good point! $\endgroup$
    – Bass
    Aug 13 '19 at 11:46

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)
    (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)
    (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.

  • 3
    $\begingroup$ Single-letter chunk moves are prohibited. $\endgroup$ Aug 14 '19 at 6:35
  • $\begingroup$ @user2357112 Ah, is that what it is? $\endgroup$
    – Kaz
    Aug 14 '19 at 6:47
  • $\begingroup$ Nice algorithmic approach! And how cool that you used Lisp! $\endgroup$
    – SlowMagic
    Aug 14 '19 at 13:10
  • $\begingroup$ Does this mean my solution was accidentally optimal?! Because I got to it by frantically scribbling and erasing words for an hour or so with no plan... $\endgroup$ Aug 14 '19 at 15:32
  • 2
    $\begingroup$ @TwoBitOperation It's optimal WRT the 90,000+ entry dictionary file. It's probably hard not to be optimal because the paths are so sparse; there just aren't that many choices. For most word pairs, there is no solution at all. $\endgroup$
    – Kaz
    Aug 14 '19 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.