8
\$\begingroup\$

Select any word from https://websites.umich.edu/~jlawler/wordlist with length greater than 1. For each letter on that word, remove it and check if any rearrangement of the remaining letters is present in the wordlist. If it is, this rearrangement is a child anagram of the original word.

For example, theism:

  • removing the t and rearranging heism gives nothing present in the wordlist
  • removing the h and rearranging teism gives times, items, metis and smite
  • removing the e and rearranging thism gives smith
  • removing the i and rearranging thesm gives nothing present in the wordlist
  • removing the s and rearranging theim gives nothing present in the wordlist
  • removing the m and rearranging theis gives heist

Therefore, the child anagrams of "theism" are "times", "items", "metis", "smite", "smith" and "heist".

Note that this needs to be done only once: you must not apply the algorithm again to "times", for example.

If the word contains any repeated letter, only a single instance of it must be considered. For example, the child anagrams of "lightning" are only "tingling" and "lighting" instead of "tingling", "lighting" (first n removed) and "lighting" (last n removed). In other words, remove child repeated anagrams.

Ignore words from the wordlist that contain additional characters apart from letters, such as "apparent(a)", "gelasma/gr" and "half-baked". They will not be passed as input and should not be handled as a child anagram of any other word.

Input

A string of length l containing the word to be searched, where 2 ≤ l ≤ 10. This string is guaranteed of being on the wordlist and it'll not contain any characters apart from letters (no hyphens, all lowercase).

You don't necessarily need to include the wordlist in your source code (compressed or not) nor fetch it every time from the network: you can assume it's provided by any standard method (e.g. as a function argument, as additional STDIN lines, as a predefined saved file, etc).

Output

All child anagrams of the input word.

You may output a list/array of strings or output them using any separator.

The output doesn't have to maintain the same order on each run, only the same elements.

Standard I/O applies.

Test cases

theism -> times,items,smite,metis,smith,heist
lightning -> tingling,lighting
learning -> leaning
today -> tody,toad,toda
response -> persons,spenser
tongue -> genou,tonue,tongu
code -> doe,deo,ode,cod
many -> any,nay,mya,may,yam,man,nam
interested -> 
something -> 
masculine -> 

Sandbox

\$\endgroup\$

8 Answers 8

7
\$\begingroup\$

JavaScript (ES6), 58 bytes

-22 (!) thanks to @Neil

Expects (dictionary)(word), where word is given as an array of characters.

d=>w=>d.filter(W=>w.sort().some(c=>w==[...W+c].sort()+''))

Try it online!

Commented

d =>             // d[] = dictionary (array of strings)
w =>             // w[] = word (array of characters)
d.filter(W =>    // for each word W in d[]:
  w.sort()       //   sort w[] in lexicographical order
  .some(c =>     //   for each character c in w[]:
    w ==         //     is w[] equal to ...
    [...W + c]   //     ...W + c turned into an array
    .sort() + '' //     and sorted in lexicographical order?
  )              //   end of some()
)                // end of filter()
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I ported my Charcoal answer and came up with d=>w=>d.filter(W=>w.sort().some(c=>w==[...W+c].sort()+'')). (Couldn't find an easy way to make w a string though.) \$\endgroup\$
    – Neil
    Jan 14 at 21:10
3
\$\begingroup\$

Charcoal, 20 bytes

WS¿⊙θ⬤⁺θι⁼№θμ№⁺ικμ⟦ι

Try it online! Link is to verbose version of code. Takes the original word as the first line of input followed by the newline-terminated wordlist to search. Explanation:

WS

Loop through all of the words. (On the first pass this will actually be the original word but that won't match the condition so it doesn't matter.)

¿⊙θ⬤⁺θι⁼№θμ№⁺ικμ

For each letter of the original word, check whether the current word plus that letter is an anagram of the original word.

⟦ι

Output the successful match on its own line.

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 63 bytes

Python3 port of the Javascript answer.

lambda w,d:[i for i in d if sorted(w)in[sorted(i+c)for c in w]]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Retina, 64 bytes

s`\w+(?<=^(\w+).*?)
$&,$&,$1,
/,\w+/_O`.
L$`,(.*)(.*),\1.\2,
$%`

Try it online! Link includes theism example compared against a selection from /usr/share/dict/words and therefore includes emits which isn't in the given wordlist for some reason. Takes the original word as the first line of input followed by the wordlist to search. Explanation:

s`\w+(?<=^(\w+).*?)
$&,$&,$1,

To each word append a copy of itself and a copy of the first line of input, all words being terminated by commas.

/,\w+/_O`.

For each copy, sort its characters.

L$`,(.*)(.*),\1.\2,
$%`

For each sorted word that's missing exactly one letter from the sorted first word, output its original word.

\$\endgroup\$
2
\$\begingroup\$

Perl 5 Algorithm::Permute, 88 bytes

sub{($_,$d,%r)=@_;s{.}{@s="$`$'"=~/./g;permute{$$d{$w=join'',@s}&&$r{$w}++}@s}ge;keys%r}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

Ṣe¥ƇṢ-Ƥ}

A dyadic Link that accepts the word list on the left and the word on the right and yields a list of the child anagrams.

Try it online! (using a reduced word list with some made-up edge cases for the "theism" example).

How?

Ṣe¥ƇṢ-Ƥ} - Link: list of lists of characters, WordList; list of characters, Word
       } - using the right argument, Word:
     -Ƥ  -   for overlapping outfixes of length Length(Word)-1
    Ṣ    -   sort
            -> e.g. Word="order" -> ["derr", "deor", "eorr", "dorr", "deor"]
   Ƈ     - {Wordlist} filter keep those for which:
  ¥      -   last two links as a dyad - f(CandidateWord, Outfixes):
Ṣ        -     sort {CandidateWord}
 e       -     exists in {Outfixes}?
\$\endgroup\$
3
  • \$\begingroup\$ Your example of "hello" isn't ideal since the word is sorted by that point, so maybe another word such as "adder", "allow", "annoy", ... "mossy"? \$\endgroup\$
    – Neil
    Jan 14 at 20:48
  • \$\begingroup\$ Replaced with "order" as it's clearer what's going on. \$\endgroup\$ Jan 15 at 18:39
  • \$\begingroup\$ The implementation changed a little since too, so each outfix of the original word is sorted now (should've spotted that golf earlier!). \$\endgroup\$ Jan 15 at 19:04
1
\$\begingroup\$

Google Sheets, 161 bytes

=let(_,lambda(w,join(,sort(mid(w,sequence(len(w)),1)))),l,len(B1),j,sequence(l),ifna(filter(A1:A,match(map(A1:A,_),map(sort(left(B1,j-1)&mid(B1,j+1,l-j)),_),))))

Paste the dictionary in cells A1:A, or add enough blank rows and put this formula in cell A1:

=importdata("https://websites.umich.edu/~jlawler/wordlist")

Put the search string in cell B1 and the formula in cell C1.

Commented

// function that sorts letters into alphabetical order; _("code") → cdeo
_, lambda(w, join(, sort(mid(w,sequence(len(w)),1)))), 

// generate sequence 1,2,3..l
l, len(B1), 
j, sequence(l), 

// "code" → ode, cde, coe, cod → deo, cde, ceo, cdo
n, map(sort(left(B1, j - 1) & mid(B1, j + 1, l - j)), _), 

// show words where _(word) appears in n
ifna(filter(A1:A, match(map(A1:A, _), n, ))) 

Results

A1 B1 C1
a theism heist
a-horizon items
a-ok metis
aardvark smite
aardwolf smith
ab times
aba
abaca
abacist
aback
...
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 9 bytes

æ¤g<ù€œ˜Ã

Takes the dictionary-list as additional input.

Try it online. (It's too slow for a test suite of multiple test cases. The example dictionary-list is taken from @Arnauld's answer.)

Explanation:

æ         # Get the powerset of the first (implicit) input-string
 ¤        # Push its last item (without popping), which is the first input itself 
  g       # Pop and push its length
   <      # Decrease it by 1
    ù     # Keep all powerset strings of that length (inputLength-1)
     €    # Map over each remaining string:
      œ   #  Get all permutations
       ˜  # Flatten it
        Ã # Only keep those values from the second (implicit) input-list of words
          # (after which the resulting list is output implicitly)
\$\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.