5
$\begingroup$

I'd like to take the premise of my previous (and insofar, only other) post and extend it. Are there any wordsets that cover all 26 letters across...

Three 11-letter words, Three 10-letter words, or Three 9-letter words?

My current wordsets include:
11s: Downrightly Lumberjacks (20 letters, missing QZXFVP)
10s: never attempted
9s: Depraving Schmaltzy Jukeboxes (23, missing QWF; all suggested 24-letter-spanning wordsets on my previous post contained at least 1 unaccepted word)

EDIT: The bounty for +100 reputation will be issued to the poster who, within the 7-day time frame:

  1. Generates 3-word wordlists for all 3 lengths (11-letter, 10-letter, 9-letter).
  2. Gets the closest to covering 26 letters with each list, especially 9-letter.
  3. I keep forgetting: please use the dictionary provided by YAWL by Mendel Leo Cooper - download here.

Good luck! Fun Fact (I'm full of these): the Japanese colloquialism for 'good luck' is 頑張って「 ください」 / Ganbatte [Kudasai] / (Please) Do Your Best. I take solace in the idea that good luck isn't a matter of fate, but the intersection of growth mindset and hard work.

$\endgroup$
13
  • 2
    $\begingroup$ Three 9-letter words is a tall order. I don't know of any pangram with only 1 letter duplicated, let alone in just three words. $\endgroup$ Dec 2, 2023 at 20:12
  • 1
    $\begingroup$ I believe that it is impossible to find three 9-letter words in the English language that contain every single letter of the alphabet. I would be happy for someone to prove me wrong (or right) but I believe it is possible to contain 25-24 $\endgroup$ Dec 3, 2023 at 3:53
  • 1
    $\begingroup$ @WeatherVane Waltz Vibex Fjord Chunk Gymps Qi. $\endgroup$
    – user87072
    Dec 3, 2023 at 4:46
  • $\begingroup$ buckjumps wildgrave zanthoxyl -fq $\endgroup$ Dec 3, 2023 at 5:20
  • $\begingroup$ @user87072 can you please give a source that words must be in, because this trickle of nonce words might turn into flood. $\endgroup$ Dec 3, 2023 at 10:20

2 Answers 2

8
+100
$\begingroup$

From @computer_goblin's list of 46659 nine-letter words, the maximum number of letters covered by three words is

24: bockwurst exemplify Ghaznevid

If you instead consider only the subset of 43098 words that do not contain a capital letter, the maximum is

23: bedworthy magnaflux quickstep

I found both sets by solving a maximum coverage problem via integer linear programming, with a binary decision variable $x_w$ to indicate whether word $w$ is selected and a binary decision variable $y_\ell$ to indicate whether letter $\ell$ is covered. Let $W_\ell$ be the set of words that contain letter $\ell$. The problem is to maximize $\sum_\ell y_\ell$ subject to \begin{align} \sum_w x_w &= 3 \tag1\label1 \\ y_\ell &\le \sum_{w\in W_\ell} x_w &&\text{for all $\ell$} \tag2\label2 \end{align} Constraint \eqref{1} selects exactly three words. Constraint \eqref{2} enforces the logical implication $y_\ell \implies \bigvee_{w\in W_\ell} x_w$. That is, if letter $\ell$ is covered, then some word $w$ that contains $\ell$ must be selected.


By request, here is more detail about the solution process.

Here's the SAS code I used, with more descriptive variable names SelectWord and CoverLetter instead of $x$ and $y$, respectively:

data words;
   infile 'Nine Letter Words.txt';
   input word $9.;
run;

proc optmodel;
   /* declare parameters and read data */
   set <str> WORDS;
   read data words into WORDS=[word];
   WORDS = setof {w in WORDS} lowcase(w);
   set LETTERS = setof {k in 97..97+26-1} byte(k);
   set <str> WORDS_l {LETTERS} init {};
   str letterThis;
   for {w in WORDS} do;
      for {k in 1..length(w)} do;
         letterThis = char(w,k);
         WORDS_l[letterThis] = WORDS_l[letterThis] union {w};
      end;
   end;

   /* SelectWord[w] = 1 if word w is selected; 0 otherwise */
   var SelectWord {WORDS} binary;

   /* CoverLetter[l] = 1 if letter l is covered; 0 otherwise */
   var CoverLetter {LETTERS} binary;

   /* maximize the number of letters covered */
   max NumLettersCovered = sum {l in LETTERS} CoverLetter[l];

   /* select exactly three words */
   con Cardinality:
      sum {w in WORDS} SelectWord[w] = 3;

   /* if CoverLetter[l] = 1 then SelectWord[w] = 1 for some word w that contains letter l */ 
   con LetterImpliesWord {l in LETTERS}:
      CoverLetter[l] <= sum {w in WORDS_l[l]} SelectWord[w];

   /* call MILP solver */
   solve;

   /* display selected words */
   put ({w in WORDS: SelectWord[w].sol > 0.5});
quit;

And here is the resulting log:

NOTE: There were 46659 observations read from the data set WORK.WORDS.
NOTE: Problem generation will use 4 threads.
NOTE: The problem has 46683 variables (0 free, 0 fixed).
NOTE: The problem has 46683 binary and 0 integer variables.
NOTE: The problem has 27 linear constraints (26 LE, 1 EQ, 0 GE, 0 range).
NOTE: The problem has 390770 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The OPTMODEL presolver is disabled for linear problems.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 0 variables and 0 constraints.
NOTE: The MILP presolver removed 50163 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 46683 variables, 27 constraints, and 340607 constraint
      coefficients.
NOTE: The MILP solver is called.
NOTE: The parallel Branch and Cut algorithm is used.
NOTE: The Branch and Cut algorithm is using up to 4 threads.
          Node   Active   Sols    BestInteger      BestBound      Gap    Time
             0        1      3     17.0000000     24.4187817   30.38%       0
NOTE: The MILP solver's symmetry detection found 31186 orbits. The largest orbit contains 28
      variables.
             0        1      4     20.0000000     24.4187817   18.10%       0
             0        1      4     20.0000000     24.3769559   17.96%       0
             0        1      4     20.0000000     24.3474535   17.86%       1
             0        1      4     20.0000000     24.3403990   17.83%       1
             0        1      4     20.0000000     24.3230216   17.77%       1
             0        1      4     20.0000000     24.3018657   17.70%       1
             0        1      5     21.0000000     24.3018657   13.59%       1
             0        1      5     21.0000000     24.2928681   13.55%       1
             0        1      5     21.0000000     24.2719184   13.48%       2
             0        1      5     21.0000000     24.2474321   13.39%       2
             0        1      5     21.0000000     24.2403600   13.37%       2
             0        1      5     21.0000000     24.2295855   13.33%       3
             0        1      5     21.0000000     24.2221405   13.30%       3
             0        1      5     21.0000000     24.2185102   13.29%       3
             0        1      5     21.0000000     24.2137198   13.27%       4
             0        1      5     21.0000000     24.2114068   13.26%       4
             0        1      5     21.0000000     24.2095593   13.26%       5
             0        1      5     21.0000000     24.2045244   13.24%       6
             0        1      5     21.0000000     24.2010946   13.23%       6
NOTE: The MILP solver added 13 cuts with 601893 cut coefficients at the root.
             1        2      5     21.0000000     24.2010946   13.23%       7
             9        8      6     23.0000000     24.1990119    4.95%       8
            13        2      6     23.0000000     24.1519567    4.77%       8
            58        0      7     24.0000000     24.0000000    0.00%       8
NOTE: Optimal.
NOTE: Objective = 24.
  • The Node column reports the number of (non-root) branch-and-bound nodes in the search tree. Node 0 is the root.
  • The Active column reports the number of active nodes in the tree.
  • The Sols column reports the number of integer feasible solutions found so far.
  • The BestInteger column reports the objective value of the best integer feasible solution found so far and is a lower bound on the global maximum.
  • The BestBound column reports the best upper bound found so far; in particular, the first value 24.4187817 is the optimal objective value of the linear programming relaxation.
  • The Gap column reports the optimality gap, that is, relative difference between these lower and upper bounds.
  • The Time column reports the number of seconds that have elapsed.

In case it helps your understanding, here are the nonzero parts of an optimal LP solution that yields objective value 24.4187817 and satisfies all variable bounds and linear constraints but violates integrality:

w         SelectWord[w] 
backswamp 0.129019 
backvelds 0.117597 
blitzweed 0.033418 
byproduct 0.096447 
dezinkify 0.096024 
egyptized 0.040609 
fauxhawks 0.358714 
fevertwig 0.055415 
flapjacks 0.091794 
flaxbirds 0.129442 
ghaznavid 0.217851 
jarovized 0.236464 
jumpingly 0.435279 
objectify 0.236464 
pibloktoq 0.069797 
prongbuck 0.046531 
sixtyfold 0.032149 
verklempt 0.090525 
vetchworm 0.282149 
whizbangs 0.141286 
zygantrum 0.063029 

l CoverLetter[l] 
a 1.000000 
b 1.000000 
c 1.000000 
d 1.000000 
e 1.000000 
f 1.000000 
g 1.000000 
h 1.000000 
i 1.000000 
j 1.000000 
k 1.000000 
l 1.000000 
m 1.000000 
n 1.000000 
o 1.000000 
p 1.000000 
q 0.069797 
r 1.000000 
s 1.000000 
t 1.000000 
u 1.000000 
v 1.000000 
w 1.000000 
x 0.520305 
y 1.000000 
z 0.828680 

The branch-and-bound algorithm would choose some fractional variable, say SelectWord[backswamp] = 0.129019, and "branch" on that variable, that is, create two child nodes, one with SelectWord[backswamp] = 0 and one with SelectWord[backswamp] = 1. It would then choose one of those nodes, solve the LP, and repeat the process. Branch-and-bound is a recursive "divide and conquer" tree search, where the tree is dynamically constructed as needed.


Here are optimal results obtained with word.list as the dictionary.

The maximum coverage from the 26649 eleven-letter words is

24: buckjumping reflexivity schwarzlots

The maximum coverage from the 33679 ten-letter words is

24: buckjumped flyweights overtaxing

The maximum coverage from the 38318 nine-letter words is

24: buckjumps wildgrave zanthoxyl

The maximum coverage from all 264097 words is

25: exemplificative jawbreakingly soliloquized

which you can also achieve by restricting to words that have at most eleven letters:

25: buckjumped overflowing zanthoxyls


Here are optimal results obtained with word.list as the dictionary, excluding buckjump* and zanthoxyl*.

The maximum coverage from the eleven-letter words is

24: frankpledge objectivize sympathique

The maximum coverage from the ten-letter words is

24: jackknifed playwright squeezebox

The maximum coverage from the nine-letter words is

23: foxgloves whipjacks zygantrum

The maximum coverage from all words is

25: exemplificative hydrogenizes kabeljouw

which you can also achieve by restricting to words that have at most eleven letters:

25: jumboizing paddywhacks reflexivity

$\endgroup$
11
  • $\begingroup$ fascinating. What do I need in order to run ILP? MatLAB? $\endgroup$
    – JLee
    Dec 4, 2023 at 16:11
  • 1
    $\begingroup$ @JLee There are many commercial and open-source ILP solvers. I use SAS. $\endgroup$
    – RobPratt
    Dec 4, 2023 at 16:15
  • 1
    $\begingroup$ Hard for me to understand how the answer can be found without considering every possibility. I looked into ILP today, but it all seems like theory and summaries. How do you feed it that massive wordlist? Could you elaborate on the solving process, both yours and the stuff under the hood? $\endgroup$
    – JLee
    Dec 4, 2023 at 23:58
  • 1
    $\begingroup$ @JLee I added more details to my answer. $\endgroup$
    – RobPratt
    Dec 5, 2023 at 0:28
  • 1
    $\begingroup$ Glad to help. I added even more detail just now, explicitly displaying the (fractional) LP solution. $\endgroup$
    – RobPratt
    Dec 5, 2023 at 1:22
1
$\begingroup$

My answer uses words with distinct letters in each (a condition of the previous puzzle) so as not to repeat the findings of another answer, which allows duplicated letters. Obviously there must be duplicated letters shared by words. Using the YAWL dictionary as asked.

I can only find 24 letters using 3 words.

9-letter words, only one solution:
buckjumps wildgrave zanthoxyl

10-letter words, only one solution:
buckwheats complexify jargonized

11-letter words: no solutions.

9, 10 and 11-letter words, some of the 117 solutions are:
backfired showjumping vexatiously
downmarket flexography subvocalize
subjectify vulgarized workmanship

I can get 25 letters by using 4 words of length 7 (total 28).

Some of the 119 solutions are:
blocked jewfish quartzy vamping
cowflap dryings jukebox mitzvah
jukebox swiftly vamping zorched

I can get all 26 letters by going to 4 words of length 8 (total 32).

The 28 solutions are:
backflow hexapody jerquing mitzvahs
backflow jerquing mythized poxvirus
backflow jodhpurs mezquits vexingly
biforked mezquits vexingly whipjack
biformed mezquits vexingly whipjack
biformed quartzes vexingly whipjack
biformed quetzals vexingly whipjack
bodysurf mezquits vexingly whipjack
clangbox fervidly mezquits whipjack
convexly jumboize prefight squawked
defuzing movables quixotry whipjack
detoxify jerquing mitzvahs plowback
detoxify overjump quackles whizbang
dewaxing jackfish mezquits provably
emboxing fervidly mezquits whipjack
emboxing fervidly quartzes whipjack
emboxing fervidly quetzals whipjack
emboxing flypitch jarovize squawked
fibrosed mezquits vexingly whipjack
flowback hexapody jerquing mitzvahs
flowback jerquing mythized poxvirus
flowback jodhpurs mezquits vexingly
forbidal mezquits vexingly whipjack
fordable mezquits vexingly whipjack
jovialty quadplex wharfing zambucks
joystick quadplex vasiform whizbang
joystick quadplex waveform whizbang
mezquits unforbid vexingly whipjack

I can also get all 26 letters from 5 words of length 6 (total 30).

Some of the many solutions are:
abject fluxed moving squawk zephyr
abrupt faxing qualmy vozhds wejack
aching folksy jawbox quartz vamped

Method: exhaustive recursion with the search space reduced by
a) using unique letters in each word reduces the dictionary size
b) not proceeding when there can't be enough letters remaining

$\endgroup$

Your Answer

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

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