4
$\begingroup$

Let's define a radiation-hardened word (a homage to radiation-hardened quines in programming) to be a word that, with any one letter removed, is still a valid English word. For example, "seat" is such a word:

  • sea
  • sat
  • set
  • eat

are all valid words, but "seats" isn't, since "sats" isn't a valid word (we will ignore the plural proper noun "SATs" for the purposes of this example).

What is the longest possible such word that's valid in Scrabble (so we have a qualifyable definition of "valid word")?

$\endgroup$
2
  • $\begingroup$ Which iteration of Scrabble? The official dictionary changes every so often. Also, is it necessary that the word be playable in Scrabble (limited by the number of tiles) or just that it is legal in the dictionary? $\endgroup$
    – bobble
    Oct 12, 2021 at 2:48
  • 1
    $\begingroup$ YAWL is also recommended for defining what makes a word valid, since it's not going to change any time soon. $\endgroup$ Oct 12, 2021 at 3:19

1 Answer 1

4
$\begingroup$

Since the tag wasn't added, I wrote an algorithm utilizing YAWL to prove that;

the longest possible words are $6$ letters long, and there are only $5$ of them.

They are;

dearns, heards, shoots, spared, and yeard.

Of these, only:

shoots is considered "valid" because hoots, soots, shots (can be formed twice), shoos, and shoot are all valid words too.

I verified it as a valid "Scrabble" word using this website.


Even though it didn't count, the one I found the most interesting was:

spared because it's variants are; pared, sared, spred, spaed, spard, and spare. Most of these I would have never thought of as valid words.

Fun fact;

there are $201$ words that, with exactly one letter removed from any position in the word, still forms another word in YAWL. There are fewer still that would be considered valid in a Scrabble dictionary (not significantly fewer, but I don't want to look up 201 words by hand).

The algorithm I created worked by:

starting with all words with $15$ letters (the longest possible word length in Scrabble) and removing $1$ letter from each index in the word. It then checked the entire $14$ letter word list to see if all of these candidates were contained within it. This process repeated all the way down through the $4$ letter word list, which you proved on your own could easily provide a word.

For those interested, here's the C# code that powered my answer: [1]

using System;
using System.Collections.Generic;
using System.Linq;
using BruteForceDictionary;
static void Main(string[] args) {
    Console.WriteLine("Starting");
    var lists = new List<List<string>>();
    for (int i = 15; i > 3; i--) {
        foreach (var word in WordLists.AllWords.Where(w => w.Length == i)) {
            var words = ChaseWords(word);
            if (words?.Count > 0) {
                lists.Add(words);
                Console.WriteLine(string.Join(";", words));
            }
            else
                Console.WriteLine($"No results found for '{word}'.");
        }
    }

    Console.WriteLine("Writing maximums.");
    int max = lists.Max(m => m.Count);
    foreach (var list in lists.Where(w => w.Count == max))
        Console.WriteLine(string.Join(";", list));

    Console.WriteLine("Done");
    Console.ReadKey();
}
public static List<string> ChaseWords(string candidate) {
    var strippedWords = GetVariants(candidate);
    var nextSet = WordLists.AllWords.Where(w => w.Length == candidate.Length - 1);
    if (strippedWords.All(a => nextSet.Any(n => n.Equals(a)))) {
        strippedWords.Insert(0, candidate);
        return strippedWords;
    }

    return null;
}
public static List<string> GetVariants(string word) {
    var result = new List<string>();
    for (int i = 0; i < word.Length; i++)
        result.Add(word.Remove(i, 1));

    return result;
}

Fun puzzle!

1: The using directive for BruteForceDictionary is provided by my personal "hard coded" version of YAWL, available on my GitHub if you need it for reproduction purposes.

$\endgroup$
2
  • $\begingroup$ @SteveV originally, I did! Great catch! I decided to brute force it the second go around. $\endgroup$ Oct 12, 2021 at 4:21
  • $\begingroup$ Wow, very cool, thanks for doing that! Python might be able to do this with shorter code though :p $\endgroup$
    – Raymo111
    Oct 13, 2021 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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