Words with Easy Letters in a Word Search

Question

Introduction:

Apparently I keep coming up with word search related challenges lately. :)
When I do the word search in the Dutch news paper, some words are very easy to find because they contain letters that aren't too common in Dutch words, like x or q. So although I usually look for the first letter or prefix of a word I'm searching, in some cases looking for these letters in the grid is faster to find the words.

Brief explanation of what a word search is^†:

^{† Although it's not too relevant for the actual challenge this time.}
In a word search you'll be given a grid of letters and a list of words. The idea is to cross off the words from the list in the grid. The words can be in eight different directions: horizontally from left-to-right or right-to-left; vertically from top-to-bottom or bottom-to-top; diagonally from the topleft-to-bottomright or bottomright-to-topleft; or anti-diagonally from the topright-to-bottomleft or bottomleft-to-topright.

Challenge:

Given a grid of letters and a list of words, output for each word the lowest count of the letters within this word within the grid.

For example:

Grid:
REKNA
TAXIJ
RAREN
ATAEI
YCYAN

Words:
AIR
ANKER
EAT
CYAN
NINJA
RARE
TAXI
TRAY
XRAY
YEN

For AIR we see the following frequency of the letters in the grid: [A:6, I:2, R:3], of which the lowest is I:2. Doing something similar for the other words, the result would be AIR:2, ANKER:1, EAT:2, CYAN:1, NINJA:1, RARE:3, TAXI:1, TRAY:2, XRAY:1, YEN:2.

Challenge rules:

• You can take the inputs in any reasonable format. Could be from STDIN input-lines; as a list of lines; a matrix of characters; as codepoint-integers; etc.
• You can optionally take the dimensions of the grid as additional input.
• The output can be in any reasonable format as well. Can be a key-value map of word + integer as above, but can also just be a list of the integers (e.g. [2,1,2,1,1,3,1,2,1,2] for the example above.
• You can assume the list of words are always in alphabetical order.
• The list of words is guaranteed to contain at least one word, and all words are guaranteed to be present in the given grid.
• All words are guaranteed to have at least two letters.
• You can assume each word is only once in the grid.

General rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Outputs are displayed as integer-lists.

Inputs:
REKNA
TAXIJ
RAREN
ATAEI
YCYAN

AIR
ANKER
EAT
CYAN
NINJA
RARE
TAXI
TRAY
XRAY
YEN

Output:
[2,1,2,1,1,3,1,2,1,2]

---

Inputs:
ABCD
EFGH
IJKL
MNOP

AFK
BCD
FC
PONM

Output:
[1,1,1,1]

---

Inputs:
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

BACKWARD
DIAGONAL
FIND
HORIZONTAL
RANDOM
SEEK
SLEUTH
VERTICAL
WIKIPEDIA
WORDSEARCH

Output:
[1,1,2,1,1,4,1,1,1,3]

---

Inputs:
JLIBPNZQOAJD
KBFAMZSBEARO
OAKTMICECTQG
YLLSHOEDAOGU
SLHCOWZBTYAH
MHANDSAOISLA
TOPIFYPYAGJT
EZTBELTEATAZ

BALL
BAT
BEAR
BELT
BOY
CAT
COW
DOG
GAL
HAND
HAT
MICE
SHOE
TOP
TOYS
ZAP

Output:
[5,5,1,5,4,3,1,3,3,2,4,3,4,3,4,3]

Answer 1

R, 43 bytes

\(w,g,`*`=sapply)w*\(i)min(i*\(j)sum(!g-j))

Attempt This Online!

Since we are allowed to input integer codepoints, here it goes. Takes input as a list of codepoint vectors for words, and codepoint matrix for grid.

Answer 2

Python 3, 42 bytes

lambda g,W:[min(map(g.count,w))for w in W]

Try it online!

Takes the grid as a string, with any non-letter separator, and an iterable of strings.

Answer 3

Haskell, 41 bytes

g#d=[minimum[sum[1|x<-g,x==c]|c<-w]|w<-d]

Attempt This Online!

-3 bytes thanks to @ovs

Answer 4

05AB1E, 3 bytes

ε¢W

Try it online!

How?

^{Note: Uses the current interpretation of https://codegolf.meta.stackexchange.com/a/2216/52210 that seems to be being used, that not only may a string be provided as a list of characters but that it may be provided as a list of single-character strings.}

ε¢W - inputs are: words (list of lists of strings of length one);
                  wordsearch (space separated string)
ε   - for each word:
 ¢  -   count occurrences of each length-one-string in the wordsearch
  W -   minimum

---

Original 4 that does not use a list of lists of strings for the words...

ε€¢W

Try it online!

How?

ε€¢W - inputs are: words (list of strings); wordsearch (space separated string)
ε    - for each word:
 €   -   for each letter:
  ¢  -     count occurrences in the wordsearch
   W -   minimum

---

^{* Taking the words as a list of lists of strings would work, but seems like pre-processing rather than loose IO to me.}

Answer 5

Haskell, 71 64 51 bytes

g#l=[[x|x<-[1..],c<-w,x==sum[1|e<-g,e==c]]!!0|w<-l]

Try it online!

• Massively outgolfed by @pxeger answer, check it out.

Full list comprehension solution

• saved 13 Bytes thanks to @Unrelated String

Old 71 bytes

g#w=sum.f<$>((\y->[1|l<-g,l==y])<$>)<$>w
f(h:t)|h<f t=h|1>0=f t
f[]=[2]

Try it online!

g#w takes g grid as a string with newlines and w words as a list of words.

Each word is transformed into a list of lists of 1's by g before using f to select the shortest(lexicographically) character.

f has an edge case = [2] for the end of the list which is always greater.
Then sum each selection to obtain the output

Answer 6

JavaScript (V8), 73 69 63 bytes

g=>l=>l.map(w=>Math.min(...[...w].map(c=>g.split(c).length-1)))

Try it online!

-4 bytes thanks to emanresu A

-6 bytes thanks to Matthew Jensen

JavaScript (Node.js) + Ramda, 56 bytes

g=>d=>d.map(w=>R.min(...R.map(c=>R.count(x=>x==c,g),w)))

Try it online!

JavaScript + Sugar, 52 bytes

g=>d=>d.map(w=>[...w].map(c=>[...g].count(c)).min())

Sugar.extend();

f=g=>d=>d.map(w=>[...w].map(c=>[...g].count(c)).min())

console.log(f("REKNA,TAXIJ,RAREN,ATAEI,YCYAN")(["AIR", "ANKER", "EAT", "CYAN", "NINJA", "RARE", "TAXI", "TRAY", "XRAY", "YEN"]).join(', '));
console.log(
  f("JLIBPNZQOAJD,KBFAMZSBEARO,OAKTMICECTQG,YLLSHOEDAOGU,SLHCOWZBTYAH,MHANDSAOISLA,TOPIFYPYAGJT,EZTBELTEATAZ")
  (["BALL","BAT","BEAR","BELT","BOY","CAT","COW","DOG","GAL","HAND","HAT","MICE","SHOE","TOP","TOYS","ZAP"])
  .join(', ')
);

<script src="https://cdnjs.cloudflare.com/ajax/libs/sugar/2.0.6/sugar.min.js"></script>

Answer 7

Ruby, 46 bytes

->g,w{w.map{|x|x.chars.map{|c|g.count c}.min}}

Try it online!

Answer 8

Vyxal r, 6 bytes

ƛƛ⁰O;g

Try it Online!

Explained

ƛƛ⁰O;g
ƛ       # Map the first input
 ƛ  ;   # Map for each letter in the word
  ⁰O    # Count how many times the letter appears in the second input
     g  # Get the minimum

Vyxal r, 5 bytes

taking words as list of list of characters instead of list of strings

ƛ⁰vOg

Try it Online!

Answer 9

Jelly, 5 bytes

ċⱮⱮṂ€

Attempt This Online!

Hmmm.

Answer 10

Factor, 38 bytes

[ [ counts values infimum ] with map ]

Attempt This Online!

Answer 11

Husk, 5 bytes

mo▼m#

Try it online!

m           # map over each word in second arg
 o          # compose 2 functions:
  ▼         #  get minimum of
   m        #  mapping
    #       #  number of occurrences in first arg

Answer 12

Wolfram Language (Mathematica), 22 bytes

Min/@Map@Counts@#/@#2&

Try it online!

Input [grid, {words...}], where both the grid and words are 1d lists of characters.

Answer 13

K (ngn/k), 14 bytes

{&/'(#'=,/x)y}

Try it online!

Takes the grid of letters as x (the first arg), and the list of words as y (the second arg).

• (#'=,/x)
  • ,/x flatten the grid of letters into a single string
  • #'= build a dictionary mapping the unique letters to the number of times they occur
• (...)y index into this with the list of words
• &/' get the number of times the least common letter in each word appears in the grid (and implicitly return)

Answer 14

Thunno, \$ 6 \log_{256}(96) \approx \$ 4.94 bytes

ez1scm

Attempt This Online!

Explanation

ez1scm # Implicit input
e      # Map:
   sc  #  Count of each in
 z1    #  Second input
     m #  Minimum
       # Implicit output

Answer 15

Charcoal, 17 bytes

ＷＳ≔⁺ωιωＷＳ⟦Ｉ⌊Ｅι№ωκ

Try it online! Link is to verbose version of code. Takes input as two newline-separated lists of newline-terminated strings. Explanation:

ＷＳ≔⁺ωιω

Input and flatten the grid.

ＷＳ

For each word in the list...

⟦Ｉ⌊Ｅι№ωκ

... output the minimum count of all of its letters in the flattened string.

Save 6 bytes by using a more awkward input format:

ＩＥη⌊Ｅι№⪫θωλ

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

  η         Word list
 Ｅ          Map over words
     ι      Current word
    Ｅ       Map over letters
      №     Count of
          λ Current letter in
        θ   Grid
       ⪫    Joined with
         ω  Empty string
   ⌊        Take the minimuim
Ｉ           Cast to string
            Implicitly print

Answer 16

Retina 0.8.2, 74 bytes

\G(.+)¶
$1
ms`(?<=^(.+)¶.+)$
;$1
1A`
%(`\G(.)(?=(.*?\1)+)
$#2¶
A`;
O#`
1G`

Try it online! Explanation:

\G(.+)¶
$1

Flatten the grid.

ms`(?<=^(.+)¶.+)$
;$1

Append a copy of the grid to each word in the list.

1A`

Delete the original grid.

%(`

Repeat for each pair of word and flattened grid.

\G(.)(?=(.*?\1)+)
$#2¶

Count the number of times each letter in the word appears in the grid. (Note that when a letter in the word is repeated then the count is only correct for the last letter but this doesn't affect the final result.)

A`;

Delete the grid.

O#`

Sort the counts.

1G`

Keep only the first (i.e. smallest).

Answer 17

Perl 5 + -MList::Util+(min), 44 bytes

sub{$g=pop;map{min map$g=~s/$_/$_/g,/./g}@_}

Try it online!

Explanation

Not entirely dissimilar to other solutions, this is a function submission in Perl (unusual I know, but 1 byte shorter than my best "standard" attempt.

Takes the last argument as a string containing the grid, and every other argument as words to find. Iterates over each word (implicitly stored in $_, splits (/./g) and maps over each letter, returning the number of s///ubstitutions replacing the letter for itself, taking the minimum for each word.

Answer 18

PARI/GP, 43 bytes

f(g,d)=[vecmin([#[1|x<-g,x==c]|c<-w])|w<-d]

A port of pxeger's Haskell answer.

Takes the grid as a list of characters, and the word as a list of list of characters.

Attempt This Online!

Answer 19

Burlesque, 18 bytes

f:qsv^mjlnm{)gv<]}

Try it online!

f:   # Count frequency (as {count val}) in grid
qsv  # Save in global map
^m   # Apply to each frequency
j    # Swap
ln   # Split into lines
m{   # Map over words
 )gv # Map over each letter get value from global map
 <]  # Minimum
}