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]

• Kevin Cruijssen: Let's see if someone can beat my prepared 3-bytes 05AB1E answer. ;p (This is one of the easier word-search challenges I've posted lately.)
• chunes: May we take the grid as a flat array/list?
• Kevin Cruijssen: @chunes Sure, but please add the '\n' characters as additional items to the list in that case so it's still a 'grid'.
• coltim: Should "For AIR we see the following frequency of the letters in the grid: [A:6, I:2, R:4]" be [A:6, I:2, R:3]?
• tsh: The grid REKNA/TAXIJ/RAREN/ATAEI/YCYAN contains {N:3,I:2,E:3}. If i want spell NINE, should I output 2 or 1 or 1.5?

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.

• Dominic van Essen: Nice, and even if we don't take codepoints, the code seems to work fine with letters for the same byte-count if we change !- to ==, I think... Try it...

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.}

• Kevin Cruijssen: Taking the list of words as a list of list of characters was indeed the intended 3-byter, although as ¢€ß instead of ε¢W. String are by definition sequences of characters, so taking the input as a list of characters when a challenge asks for strings is allowed by default. And in this challenge the I/O is even more flexible than this default
• Jonathan Allan: @KevinCruijssen I thought that was taking a list of strings rather than a list of characters (since using single quotes does not work). Is there a different format for inputting a list of characters rather than a list of strings?
• Kevin Cruijssen: 05AB1E doesn't have the type 'char'. Kinda similar as Python and JavaScript. Whether you use single or double quotes doesn't really matter in those languages, and it's similar for the legacy version of 05AB1E (which is build in Python). The new version of 05AB1E is build in Elixir, so single quotes no longer work, but whether you use 'A' or "A" doesn't matter too much tbh. In Java it would, one being a char (with codepoint underneath) and the other being String, but in Python and 05AB1E (legacy) both are length-1 strings.
• Jonathan Allan: @KevinCruijssen that's interesting, I did not realise; I have commented under that meta answer about this (I've used it with Python but Jelly has no string type, only lists of characters, barring an interpreter bug where multiplication produces them).
• FryAmTheEggman: @KevinCruijssen I noted the ambiguity between a list of characters and a list of strings a while ago and added an answer to the same meta question which received a mixed response. Since this is your question there's certainly no problem here, but I'm not sure we could really say this is generally accepted at the moment.

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

• Unrelated String: 51: g#l=[[x|x<-[1..],c<-w,x==sum[1|e<-g,e==c]]!!0|w<-l]

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>

• emanresu A: You don't need the RegExp - ato.pxeger.com/…
• Matthew Jensen: 63 bytes using split()

Answer 7

Ruby, 46 bytes

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

Try it online!

• naffetS: 44 bytes with Ruby 2.7+

Answer 8

Vyxal r, 6 bytes

ƛƛ0O;g

Try it Online!

Explained

ƛƛ0O;g
ƛ # Map the first input
 ƛ ; # Map for each letter in the word
 0O # 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

ƛ0vOg

Try it Online!

Answer 9

Jelly, 5 bytes

ċⱮⱮṂ€

Attempt This Online!

Hmmm.

• allxy: Don't you mean "cmmm"?

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

WS≔+ωιωWS⟦I⌊EιNoωκ

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

WS≔+ωιω

Input and flatten the grid.

WS

For each word in the list...

⟦I⌊EιNoωκ

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

Save 6 bytes by using a more awkward input format:

IEη⌊EιNo⪫θωλ

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

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

• Kevin Cruijssen: The 'awkward' input format is completely fine. The I/O formats are very flexible in this challenge.

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.

• Dom Hastings: Oops @KevinCruijssen, I removed it from the header (as it doesn't need to be included for the function), but the test harness required -a. Thanks for letting me know!

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
}