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.

Improve this question
\$\endgroup\$
0

19 Answers 19

Reset to default
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
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ ChartZ Belatedly \$\endgroup\$
    – Fmbalbuena
    Commented Nov 9, 2021 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.
Improve this answer
\$\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!

Improve this answer
\$\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.

Improve this answer
\$\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
    Commented Nov 9, 2021 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.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

J, 24 bytes

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

Try it online!

Improve this answer
\$\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)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why sort when you can list all permutations ;) 怜˜Ã works for 5 \$\endgroup\$
    – ovs
    Commented Nov 9, 2021 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\$
    – Kevin Cruijssen
    Commented Nov 9, 2021 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.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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).

Improve this answer
\$\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)

Improve this answer
\$\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\$
    – Dom Hastings
    Commented Nov 9, 2021 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\$
    – Dom Hastings
    Commented Nov 9, 2021 at 14:21
  • \$\begingroup\$ @DomHastings – Thx, nice. I knew about /./g but thought that !~ was just for //, not s///. Apparently not :-) \$\endgroup\$
    – Kjetil S
    Commented Nov 9, 2021 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
Improve this answer
\$\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 ^
Improve this answer
\$\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.
Improve this answer
\$\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

Improve this answer
\$\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.