8
\$\begingroup\$

Given a word list, find all sets of five words of five letters each, such that the words of each set have 25 distinct letters in total.

This challenge was inspired by this video by Matt Parker.

Testcases

Use this file if you want to test your code against the English vocabulary. Sample output sets:

  • ["fjord", "vibex", "waltz", "nymph", "gucks"]
  • ["fjord", "vibex", "waltz", "gymps", "chunk"]

Here's a shorter version of the same file, with only words of five letters and no repeated letters. Here's an even shorter version with just 2000 words.

Rules

  • Standard I/O rules apply.
  • Words contain only lowercase (or alternatively, uppercase) alphabetic characters.
  • You can assume there are no empty words (i.e. words of length zero).
  • The input can contain words that cannot belong to any set that satisfies the property, such as words with less than five letters, words with more than five letters, and words with repeated letters.
  • You do not need to output every permutation of each valid set/list of five words.
  • This is so the shortest code in bytes wins

Sandbox

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Could you provide a smaller test case? \$\endgroup\$ Jan 4 at 23:40
  • \$\begingroup\$ @cairdcoinheringaahing hope the test cases I added are useful! \$\endgroup\$
    – matteo_c
    Jan 5 at 0:00
  • \$\begingroup\$ Do we have to output all permutations of valid 5 word lists, or just any single permutation of each group of valid 5 word lists? \$\endgroup\$ Jan 5 at 0:21
  • \$\begingroup\$ @cairdcoinheringaahing just one, since I consider them to be sets \$\endgroup\$
    – matteo_c
    Jan 5 at 10:01
  • 1
    \$\begingroup\$ Seeing as the length of each word in each set has to be 5 characters long, may we output each set without a delimiter between each word? Example \$\endgroup\$
    – Shaggy
    Jan 5 at 14:29

9 Answers 9

7
\$\begingroup\$

Vyxal, 11 bytes

'L5=;5ḋ'∑Þu

Try it Online!

Get all 5 letter words, and all 5 word combinations where all the letters are unique.

Explained

'L5=;5ḋ'∑Þu
'L5=;       # keep only words that are length 5
     5ḋ     # combinations without replacement of size 5
       '∑Þu # keep only those where the sum of all strings has all unique letters
\$\endgroup\$
2
  • \$\begingroup\$ Since we are supposed to return sets, I think you don't need the permutations. \$\endgroup\$
    – Arnauld
    Jan 5 at 0:14
  • \$\begingroup\$ @Arnauld good observation. Nice little 5 byte save. Thanks! \$\endgroup\$
    – lyxal
    Jan 5 at 0:31
4
\$\begingroup\$

05AB1E, 10 bytes

5ù5.ÆʒJDÙQ

Outputs as a list of lists.

Try it online.

Explanation:

5ù          # Keep all words of the (implicit) input-list of length 5
  5.Æ       # Get all 5-element combinations of the remaining words
     ʒ      # Filter this list of quintuplets by:
      J     #  Join the five words together to a single string
       DÙQ  #  Check that all characters are unique:
       D    #   Duplicate the string
        Ù   #   Uniquify its characters
         Q  #   Check if the two strings are still the same
            # (after which the filtered list of quintuplets are output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Japt v2.0a0, 14 13 bytes

12 bytes if the words in each set do not need to be delimited.

l5 à5 fȬ¶X¬â

Try it (Test case borrowed from Neil)

l5 à5 fȬ¶X¬â     :Implicit input of word array
l5                :Filter words of length 5
   à5             :Combinations of length 5
      f           :Filter by
       È          :Passing each X through the following function
        ¬         :  Join
         ¶        :  Is equal to
          X¬      :  Join X
            â     :  Deduplicate
\$\endgroup\$
3
  • \$\begingroup\$ Don't you need to count the l5 ? The challenge says "The input can contain words that cannot belong to any set that satisfies the property, such as words with less than five letters, words with more than five letters, and words with repeated letters." \$\endgroup\$ Jan 5 at 12:26
  • \$\begingroup\$ @cairdcoinheringaahing, no, because, if any word has less than 5 characters and even if all characters in the 5 words are unique, slicing to the 23rd index will always result in an empty string. \$\endgroup\$
    – Shaggy
    Jan 5 at 14:06
  • \$\begingroup\$ @cairdcoinheringaahing, wait, no, realised my error; you're right. Will update shortly. \$\endgroup\$
    – Shaggy
    Jan 5 at 14:14
4
\$\begingroup\$

Python,  87  113 bytes

(+26 for word length filter)

i'm really interested in knowing if there's a way i could golf the 5-letter word length filter.

lambda x:[i for i in combinations([j for j in x if len(j)==5],5)if len({*''.join(i)})==25]
from itertools import*

Attempt This Online!

\$\endgroup\$
3
  • \$\begingroup\$ set( )->{* } \$\endgroup\$
    – att
    Jan 6 at 8:13
  • \$\begingroup\$ also can fail by including words of length ≠5 \$\endgroup\$
    – att
    Jan 6 at 8:14
  • \$\begingroup\$ You could move the len test into the {} comprehension [i for i in combinations(x,5)if len({c for w in i for c in w if len(w)<6})>24] \$\endgroup\$ Jan 6 at 22:30
3
\$\begingroup\$

Jelly, 12 bytes

Ẉẹ5ịœc5FQƑ$Ƈ

Try it online!

Outputs the sets of words. -1 byte to output all permutations.

How it works

Ẉẹ5ịœc5FQƑ$Ƈ - Main link. Takes a list of words W on the left
Ẉ            - Lengths of each word
 ẹ5          - Indexes of 5s
   ị         - Index into W
    œc5      - All combinations without replacement of 5 words
          $Ƈ - Filter by the following:
       F     -   when flattened...
         Ƒ   -   ...the list is unchanged after...
        Q    -   ...only keeping unique elements
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 35 bytes

⊞υωWSF⁼⁵Lι≔⁺υ⁺Φυ⬤ι¬№λνιυEΦυ⁼²⁵Lι⪪ι⁵

Try it online! Link is to verbose version of code. Too slow for TIO with 2000 words so link uses the 106 "words" in the question at time of writing. Takes input as a list of newline-terminated words. Explanation:

⊞υω

Start with the empty string.

WSF⁼⁵Lι

Loop over the input words of length 5.

≔⁺υ⁺Φυ⬤ι¬№λνιυ

Get all of the existing strings that have no overlap with this word, append the current word to all of those strings, and append the resulting strings to the list.

EΦυ⁼²⁵Lι⪪ι⁵

Find all of the strings of length 25 and split them back into words.

\$\endgroup\$
1
  • \$\begingroup\$ FYI it took six and a half hours to process the 2,000 words and find three answers on my machine. \$\endgroup\$
    – Neil
    Jan 5 at 16:49
3
\$\begingroup\$

JavaScript (V8), 88 bytes

Prints the sets as space-separated strings.

f=([w,...a],o='')=>o[29]?new Set(o).size-26||print(o):w&&f(a,o,w.length-5||f(a,o+w+' '))

Try it online!

Commented

f = (             // f is a recursive function taking:
  [w,             //   w   = next word from the input array
      ...a],      //   a[] = array of remaining words
  o = ''          //   o   = output set, as a string
) =>              //
o[29] ?           // if we have 5 x 6 characters in o:
  new Set(o)      //   turn o into a set
  .size - 26      //   if its size is 26 (space included),
  || print(o)     //   print the output set
:                 // else:
  w &&            //   if w is defined,
  f(              //   do a 1st recursive call:
    a,            //     pass a[] unchanged
    o,            //     pass o unchanged
    w.length - 5  //     if the word has 5 characters,
    || f(         //     do a 2nd recursive call:
      a,          //       pass a[] unchanged
      o + w + ' ' //       append w and a space to o
    )             //     end of recursive call
  )               //   end of recursive call
\$\endgroup\$
2
\$\begingroup\$

Pyth, 14 bytes

f{IsT.cfq5lTQ5

Try it online!

Explanation

                  # implicitly assign Q = eval(input())
       f    Q     # filter Q on lambda T
        q5lT      #   length(T) == 5
     .c      5    # all 5 element combinations of the filtered list
f                 # filter on lambda T
 {IsT             #   T, concatenated to a single string is invariant under deduplicaiton
\$\endgroup\$
2
\$\begingroup\$

Python, 104 bytes

lambda W:[w for w in combinations(W,5)if len({*chain(*w)})<<max(map(len,w))==800]
from itertools import*

Attempt This Online!

The direct port of the JS solution is shorter though :-(

def f(w=0,*R,g=""):len({*g})-26or print(g)if len(g)>29else w and(f(*R,g=g),len(w)-5or f(*R,g=g+w+" "))
\$\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.