# Missing lattes and mutually mistrustful words

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.

    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
·                  ·
|                   |
|                   |
|                   |
|                   |
·                  ·
·            ·
·      ·
·
·      ·
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!

• 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. Commented Sep 16, 2019 at 2:11
• @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! Commented Sep 16, 2019 at 2:17
• 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. Commented Sep 16, 2019 at 4:35
• 12 steps? I only used 4... @ace Commented Sep 16, 2019 at 8:11
• @OmegaKrypton As I said, 12 according to the word list I used. And my word list didn't have "milting", "masting" and "lites". Commented Sep 16, 2019 at 10:48

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

• 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. Commented Sep 16, 2019 at 3:28

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:

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."""

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:
break

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

current = newlist