19
\$\begingroup\$

Yes, I know there is a similar question, but this one specifically concerns any possible words, even with letters left over, while the linked one restricts to a permutation of the input

Objective

Have you ever had those moments in a Scrabble game where you're staring at your letters, trying to find a good word, and your mind is just blank? Some of us feel cheaty and turn to word unscrambling software like this one to help us. This challenge is to build your own word unscrambler.

Given a list of possible words and a string of characters conforming to the regex ([A-Z]|[a-z])+, your program has to find all the words whose letters are all found in the scrambled string.

Sample inputs:

asto, [as, so, to, oats] -> [as, so, to, oats]
asto, [as, to] -> [as, to]
ast, [as, so, to] -> [as]
zzyzx, [as, to, so] -> []
trom, [as, to, too, or] -> [to, or]
roomt, [as, to, too, or] -> [to, too, or]

Scoring

This is , shortest answer wins.

\$\endgroup\$
0

19 Answers 19

8
\$\begingroup\$

Jelly, 4 bytes

œ&ƑƇ

Try it online!

How it works

œ&ƑƇ - Main link. Takes a list of words L on the left, a word W on the right
   Ƈ - Keep those words from L such that:
  Ƒ  -   They are unchanged after taking:
œ&   -     The multiset intersection with W
\$\endgroup\$
1
  • 1
    \$\begingroup\$ ChartZ Belatedly \$\endgroup\$
    – Fmbalbuena
    Nov 9 '21 at 2:19
7
\$\begingroup\$

Vyxal 2.6pre1, 5 3 bytes

Þ×↔

Don't Try it Online! (the site runs a few commits 2.4.1)

Haha builtin go brr.

-2 thanks to Lyxal.

  ↔ # The elements in common between
Þ×  # All combinations of the letters
    # And the input.
\$\endgroup\$
1
6
\$\begingroup\$

Python 2, 66 bytes

lambda s,l:[w for w in l if all(w.count(c)<=s.count(c)for c in w)]

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Python 3.10, 74 bytes

lambda w,l:[x for x in l if C(x)<=C(w)]
from collections import*
C=Counter

Attempt This Online!

In versions before 3.10 C(x)<=C(w) would have been not C(x)-C(w) instead.

\$\endgroup\$
1
  • \$\begingroup\$ Dammit, I tried <= (in Python 3.9) and I didn't realise you could do -, so I gave up on Counter! \$\endgroup\$
    – pxeger
    Nov 9 '21 at 11:37
4
\$\begingroup\$

JavaScript (Node.js), 61 bytes

s=>l=>l.filter(w=>w.map(g=c=>g|=w[c]=s.indexOf(c,w[c]+1))|~g)

Try it online!

Input / output words as list of characters.

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

Ruby, 46 bytes

->b,a{a.select{|w|d=b*1;w.all?{|c|d[c]&&=''}}}

Try it online!

Takes the list of tiles as a string; words are input and output as lists of characters. The inconsistent formats can be avoided at a cost of a few extra bytes: 47 bytes to use lists of characters exclusively and 52 bytes for strings.

All variants work the same way. For each letter of a word, remove the first occurrence of that letter from the list of tiles or return nil (falsy) if there is no such tile. The word can be formed if this procedure succeeds for all its letters.

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

Factor + math.combinatorics math.unicode, 53 bytes

[ <permutations> '[ _ [ subseq? ] with ∃ ] filter ]

Try it online!

In plain English, select all words from the dictionary that appear in any permutation of the scrabble letters.

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

Charcoal, 12 bytes

Φη⬤鬛№ιλ№θλ

Try it online! Link is to verbose version of code. Explanation:

 η              Word list
Φ               Filtered where
   ι            Current word
  ⬤             All letters satisfy
      №ιλ       Count of letter
    ¬›          Does not exceed
         №θλ    Count available
                Implicitly print
\$\endgroup\$
3
\$\begingroup\$

J, 24 bytes

(1 e.[E.e.~#])&(/:~@>)#[

Try it online!

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

05AB1E, 7 5 bytes

怜˜Ã

-2 bytes thanks to @ovs.

Inputs in the order letters, words-list.

Try it online or verify all test cases.

Explanation:

æ      # Get the powerset of the (implicit) first input-string of letters
 €œ    # Get the permutations of each string in this list
   ˜   # Flatten this nested list to a single list of strings
    Ã  # Keep the words from the second (implicit) input-list that are also in this list
       # (after which the result is output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why sort when you can list all permutations ;) 怜˜Ã works for 5 \$\endgroup\$
    – ovs
    Nov 9 '21 at 15:28
  • \$\begingroup\$ @ovs Ah nice. Didn't realize it was this short. My initial thought was to use Ã, but by keeping letters instead of keeping potential words. :/ Thanks for -2! :) \$\endgroup\$ Nov 9 '21 at 16:25
3
\$\begingroup\$

Retina, 49 bytes

A`^|(.)(.*\1)*(?<!^.*(?(2)^)(?<-2>.*\1)*\1(.|¶)+)

Try it online! Takes newline-separated input but link is to test suite that splits on commas for convenience. Explanation:

A`^|

Delete the first line, plus...

(.)(.*\1)*

... any lines that have more of a particular letter...

(?<!^.*(?(2)^)(?<-2>.*\1)*\1(.|¶)+)

... than the first line does.

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

ayr, 10 9 bytes

[#*/&,:/:

Takes the words on the left and the letters on the right

Explained

       /:  Each left
     ,:    Membership
  */&      And then reduce with multiplication
[#         Filter words with this mask

*/ 1 0 0 1 0 is the same as ^./ 1 0 0 1 0 but shorter.

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

Python, 88 bytes

lambda a,w:filter(" ".join(map("".join,permutations(a))).count,w)
from itertools import*

Attempt This Online!

Assumes the words don't contain spaces, but the " " can be changed to any other character that the words won't contain.

Unusually for Python, this declarative approach (map+filter) is shorter than a list comprehension.

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

Perl 5 + -F -M5.10.0, 38 bytes

say grep{$t=$_;$t=~s/$_// for@F;!$t}<>

Try it online!

Explanation

The letters (first line of input) are implicitly stored in @F via the -F flag.

We grep through the word list (<>), temporarily storing the word ($_) in $t, then for each letter in @F, s///ubstitute it ($_) for the empty string, returning a truthy value (which includes the word in the set to be printed by say) if $t is now empty (all letters of the word were removed because they exist in the input letters).

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

Perl 5, 52 47 bytes

sub{$c=pop;grep{$C=$c;!grep{$C!~s/$_//}/./g}@_}

Try it online!

(shaved 5 extra bytes from Dom Hastings' suggestions)

\$\endgroup\$
3
  • \$\begingroup\$ Nice! I came up with a very similar answer (and missed that you'd posted this in the time I was writing it up, sorry!) \$\endgroup\$ Nov 9 '21 at 14:21
  • 1
    \$\begingroup\$ You can replace split// with /./g for a little saving and (I didn't realise 'til I tried, but) you can also replace grep{1-$C=~...} with grep$C!~...,: Try it online! \$\endgroup\$ Nov 9 '21 at 14:21
  • \$\begingroup\$ @DomHastings – Thx, nice. I knew about /./g but thought that !~ was just for //, not s///. Apparently not :-) \$\endgroup\$
    – Kjetil S.
    Nov 9 '21 at 14:30
2
\$\begingroup\$

K4, 28 bytes

Solution:

{y@&x{&/1>(#:'=y)-#:'=x}/:y}

Examples:

Count letter occurrences, subtract and spit out words that match...

q)k){y@&x{&/1>(#:'=y)-#:'=x}/:y}["trom";("as";"to";"too";"or")]
"to"
"or"
q)k){y@&x{&/1>(#:'=y)-#:'=x}/:y}["asto";("as";"so";"to";"oats")]
"as"
"so"
"to"
"oats"
q)k)()~{y@&x{&/1>(#:'=y)-#:'=x}/:y}["zzyzx";("as";"to";"so")]
1b

Explanation:

{y@&x{&/1>(#:'=y)-#:'=x}/:y} / the solution
{                          } / lambda taking implicit x and y args
    x{                 }/:y  / apply inner lambda to x and each y
                     =x      / group x
                  #:'        / count length of each group
                 -           / subtract from
          (     )            / do this together
              =y             / group y
           #:'               / count length of each group
        1>                   / 1 greater than subtraction result?
      &/                     / all
   &                         / indices where true
 y@                          / index into y with these indices

Alternatives:

  • {y@&&/'1>(#:''=:'y)-\:#:'=x}, also 28 bytes
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 5 bytes

ṖvKf↔

Try it Online!

This has to be the first time I've found a use for K on strings lol

Explained

ṖvKf↔
Ṗ      # All permutations of the input word
 vK    # and get the divisors (substrings that split the string into more than once piece - idk how this actually makes this work)
   f   # flatten that
    ↔  # remove words from the input list that aren't in ^
\$\endgroup\$
1
\$\begingroup\$

Pyth, 9 bytes

@E{.nyM.p

Try it online!

@E{.nyM.p
     yM.P   // Collect all subsets of all permutations of the input
  {.n       //     -> Flatten and de-duplicate the list
 E          // Read the word list
@           // Get the intersections of the two lists.
\$\endgroup\$
0
1
\$\begingroup\$

Japt -f, 6 5 bytes

øVáUl

Try it

-f flag to output the elements of first input
   that return a truthy value when passed through

ø       - true if word contains any of:
  Vá    - permutations of alphabet 
   Ul   - of same length of word hence equal 

Or try that

\$\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.