33
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Great puzzle! River crossing tag though? $\endgroup$ – Duck Aug 12 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 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 at 23:23
  • 1
    $\begingroup$ Another great puzzle! $\endgroup$ – TwoBitOperation Aug 13 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$ – Michael Karas Aug 13 at 15:04
31
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I was close, but you were closer! Nice work! $\endgroup$ – Cloudy7 Aug 13 at 1:24
  • 1
    $\begingroup$ I got to rend and catering, and then gave up :) +1 $\endgroup$ – Duck Aug 13 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 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$ – John Clifford Aug 13 at 8:19
  • 2
    $\begingroup$ @JohnClifford Good point! $\endgroup$ – Bass Aug 13 at 11:46
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Single-letter chunk moves are prohibited. $\endgroup$ – user2357112 supports Monica Aug 14 at 6:35
  • $\begingroup$ @user2357112 Ah, is that what it is? $\endgroup$ – Kaz Aug 14 at 6:47
  • $\begingroup$ Nice algorithmic approach! And how cool that you used Lisp! $\endgroup$ – SlowMagic Aug 14 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$ – TwoBitOperation Aug 14 at 15:32
  • 1
    $\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 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.