11
$\begingroup$

It's always amusing to watch two kids who don't trust each other swap baseball cards by exchanging them at exactly the same moment. Words can be equally mistrustful about trading their letters. Watch this:

    SOLVER        SLIDER
     |              |
     |              |
     ·              ·
       ·           ·
         ·       ·
           ·   ·
             ·
           ·   ·
         I       O
       ·           ·
      |            |
      |            |
    SLIVER        SOLDER
       |             |
       |             |
        ·           ·
          ·       ·
            ·   ·
              ·
            ·   ·
          D       V
        ·           ·
       |             |
       |             |
    SLIDER        SOLVER


Notice that with each step:
— One letter is extracted from each word, the two letters are swapped, and each letter is reinserted into the other word (but not necessarily in the same place where the other letter was extracted).
— Letters can be extracted from anywhere in the word, and can be inserted anywhere in the word. However, all the remaining letters must maintain their relative order.
— Both words must be valid English words at each step.


Now here is your challenge. Start with this pair:

    MISSING                LATTE     

and, through a series of simultaneous swaps, transform it into this pair:

    LASTING                ITEMS


Solving tips:

The example at the top shows how powerful simultaneous swapping can be. It switches SOLVER and SLIDER in just two steps! More often, however, progress is a bit more incremental.

It can sometimes take several steps to get each letter to where it needs to go. Observe:

    TRIED                SLACKER
      |                    |
      |                    |
        ·                  ·
           ·            ·
              ·      ·
                 ·
              ·     ·
          A            I
       ·                  ·
       |                   |
       |                   |
    TREAD                SLICKER
       |                   |
       |                   |
        ·                  ·
           ·            ·
              ·      ·
                 ·
             ·      ·
         I             A
      ·                   ·
     |                     |
     |                     |
    TIRED                SLACKER

This maneuver allows the word TRIED to be anagrammed to TIRED while keeping the other word (SLACKER) fixed. It is reminiscent of how some people solve the Rubik's cube, employing a sequence of manipulations which moves one square into a desired position while keeping all the other squares fixed. Sometimes it may take multiple steps to attain this isolated movement.

If the conditions are right, you can actually anagram one of the words in a single step. You do this by extracting the same letter from each word. Watch this:

    POACHED                PEAR
         |                  |
         |                  |
          ·                 ·
             ·           ·
                ·     ·
                   ·
                ·     ·
             E            E
          ·                  ·
         |                    |
         |                    |
    POACHED                PARE

It's an exchange of "E" for "E", changing PEAR to PARE, but effectively leaving POACHED unchanged.

And, of course, you can use this technique to anagram both words simultaneously:

    EMPATHIC          EARTHY
         |                |
         |                |
          ·               ·
            ·          ·
              ·     ·
                ·
             ·    ·
          H         H
       ·              ·
       |              |
       |              |
    EMPHATIC          HEARTY




Afterword:

Here is a more leisurely solution path using familiar words:

MISSING LATTE
MISTING SLATE
SMITING SLATE
SMILING STATE
SMITING STALE
SMITING TALES
SITTING MALES
SETTING MAILS
SITTING MEALS
SILTING MEATS
SMILING TEATS
SILTING TEAMS
SILTING STEAM
SMITING STEAL
MISTING STEAL
LISTING STEAM
LISTING TEAMS
LASTING ITEMS


@ace — Thanks for sharing your computer-generated solutions!

$\endgroup$
  • $\begingroup$ Solved it with computer assistance. I know this is tagged [no-computers], so I won't post it here so as to not spoil the fun. A hint for people solving this by hand: it takes 12 steps. $\endgroup$ – user12205 Sep 16 at 2:11
  • $\begingroup$ @ace — After the answer has been posted, I look forward to seeing your computer-generated solution! BTW, there are a number of variations in the solution, some of which range up to 17 steps. And they all succeed in getting to the end, so no one should feel bad if their solution takes a more leisurely path! $\endgroup$ – SlowMagic Sep 16 at 2:17
  • $\begingroup$ Optimized my code, now takes < 1 second to find all solutions. The word list I use gives 45 possible solutions, shortest takes 12 steps, longest takes 36. I think I'll maybe post some selected solutions and the code after a few days. $\endgroup$ – user12205 Sep 16 at 4:35
  • $\begingroup$ 12 steps? I only used 4... @ace $\endgroup$ – Omega Krypton Sep 16 at 8:11
  • $\begingroup$ @OmegaKrypton As I said, 12 according to the word list I used. And my word list didn't have "milting", "masting" and "lites". $\endgroup$ – user12205 Sep 16 at 10:48
5
$\begingroup$

4 intermediate steps (thanks @ace)

MISSING            LATTE
MISTING SLATE
MILTING SATES
MALTING SITES
MASTING LITES
LASTING ITEMS

6 intermediate steps

    MISSING                LATTE
MISTING SLATE
MILTING SATES
SILTING MATES
SALTING MITES
MALTING SITES
MASTING LITES
LASTING ITEMS

$\endgroup$
  • $\begingroup$ Nice. I didn't find this shorter one because my word list didn't have milting, masting and lites. But note that you can actually go from (milting, sates) to (malting, sites) directly without the intermediate steps. $\endgroup$ – user12205 Sep 16 at 3:28
  • $\begingroup$ thanks @ace, edited as appropiate! $\endgroup$ – Omega Krypton Sep 16 at 4:21
3
$\begingroup$

Computer-assisted solutions based on /usr/share/dict/words as provided by the Ubuntu wamerican package, version 7.1-1. There are 45 solutions I found, posted below are the shortest and longest ones. For the full list click here or run the code yourself.

Least steps (12 swaps):

Solution 1:

 ('missing', 'latte'),
 ('misting', 'slate'),
 ('smiting', 'slate'),
 ('smiling', 'state'),
 ('smiting', 'stale'),
 ('smiting', 'tales'),
 ('sitting', 'males'),
 ('setting', 'mails'),
 ('sitting', 'meals'),
 ('smiting', 'teals'),
 ('misting', 'teals'),
 ('listing', 'teams'),
 ('lasting', 'items')

Solution 2:

 ('missing', 'latte')
 ('misting', 'slate')
 ('smiting', 'slate')
 ('smiling', 'state')
 ('smiting', 'stale')
 ('smiting', 'tales')
 ('sitting', 'males')
 ('setting', 'mails')
 ('sitting', 'meals')
 ('smiting', 'teals')
 ('silting', 'teams')
 ('slating', 'items')
 ('lasting', 'items')

Most steps (36 swaps):

 ('missing', 'latte')
 ('misting', 'slate')
 ('smiting', 'slate')
 ('smiling', 'state')
 ('smiting', 'stale')
 ('smiting', 'tales')
 ('misting', 'stale')
 ('misting', 'tales')
 ('listing', 'tames')
 ('lasting', 'times')
 ('tasting', 'limes')
 ('stating', 'slime')
 ('stating', 'limes')
 ('slating', 'times')
 ('silting', 'tames')
 ('salting', 'times')
 ('malting', 'sties')
 ('malting', 'sites')
 ('salting', 'mites')
 ('salting', 'smite')
 ('stating', 'smile')
 ('stating', 'miles')
 ('tasting', 'smile')
 ('lasting', 'smite')
 ('slating', 'smite')
 ('slating', 'mites')
 ('silting', 'mates')
 ('sitting', 'males')
 ('setting', 'mails')
 ('sitting', 'meals')
 ('smiting', 'teals')
 ('smiting', 'steal')
 ('silting', 'steam')
 ('tilting', 'seams')
 ('silting', 'teams')
 ('slating', 'items')
 ('lasting', 'items')

Python code (apologies in advance for the 4-level nested loops)

Brief explanation: breadth-first search, inserting nodes to tree if swapping creates a valid distinct pair of words. Nodes that reach the goal can be traversed backwards to reconstruct the steps.

The code prints a very long list at the end, so you may want to play with it using python -i to pick out some solutions or format them.

class Tree:
  def __init__(self, data, parent=None):
    self.data = data
    self.parent = parent

  def __eq__(self, other):
    return self.data == other.data

  def __repr__(self):
    return str(self.data)

  def not_same_as_ancestors(self):
    ancestor = self.parent
    while ancestor is not None:
      if ancestor == self:
        return False
      ancestor = ancestor.parent
    return True

  def to_list(self):
    ans = [self.data]
    ancestor = self.parent
    while ancestor is not None:
      ans = [ancestor.data] + ans
      ancestor = ancestor.parent
    return ans


with open("/usr/share/dict/words") as f:
  wordlist = f.read().splitlines()


def remove(word, pos):
    """Returns word with letter at pos position removed.

    >>> remove('python', 2)
    'pyhon'

    """
    return word[:pos] + word[pos+1:]


def insert(word, pos, ch):
  """Returns word with ch inserted at pos position.

  >>> insert('pyhon', 2, 't')
  'python'

  """
  return word[:pos] + ch + word[pos:]


def solve(start1, start2, end1, end2):
  """Performs a breadth-first search, returns list of all solutions."""

  possible_answers = []

  root = Tree((start1, start2))
  current = [root]

  wordlist1 = set([x.lower() for x in wordlist if len(x) == len(start1)])
  wordlist2 = set([x.lower() for x in wordlist if len(x) == len(start2)])

  while len(current) > 0:
    newlist = []

    for node in current:
      w1, w2 = node.data
      # The following has 4 levels of loop (sorry):
      # 1st level: remove ith letter (c2) from w1
      # 2nd level: remove jth letter (c1) from w2
      # 3rd level: choose kth position in w1 to insert c1
      # 4th level: choose mth position in w2 to insert c2
      for i in range(len(w1)):
        w1cut = remove(w1, i)
        c2 = w1[i]
        for j in range(len(w2)):
          w2cut = remove(w2, j)
          c1 = w2[j]
          for k in range(len(w1)):
            w1new = insert(w1cut, k, c1)

            if w1new in wordlist1:
              for m in range(len(w2)):
                w2new = insert(w2cut, m, c2)
                if w2new in wordlist2:
                  newnode = Tree((w1new, w2new), node)
                  if w1new == end1 and w2new == end2:
                    possible_answers.append(newnode.to_list())
                    break

                  elif newnode not in newlist and newnode.not_same_as_ancestors():
                    newlist.append(newnode)

    current = newlist
  return possible_answers


answers = solve("missing", "latte", "lasting", "items")
for i in range(len(answers)):
    a = answers[i]
    print("Solution {}: {} swaps".format(i, len(a) - 1))
    for step in a:
        print(step)
    print()
$\endgroup$

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.