Missing lattes and mutually mistrustful words

Question

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!

Answer 1

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

Answer 2

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