12
\$\begingroup\$

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 , 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]
\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ Apr 12 at 10:42
  • \$\begingroup\$ May we take the grid as a flat array/list? \$\endgroup\$
    – chunes
    Apr 12 at 11:23
  • \$\begingroup\$ @chunes Sure, but please add the '\n' characters as additional items to the list in that case so it's still a 'grid'. \$\endgroup\$ Apr 12 at 11:38
  • 1
    \$\begingroup\$ 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]? \$\endgroup\$
    – coltim
    Apr 12 at 18:40
  • \$\begingroup\$ 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? \$\endgroup\$
    – tsh
    Apr 13 at 2:00

18 Answers 18

8
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ Apr 12 at 17:33
5
\$\begingroup\$

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.

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

Haskell, 41 bytes

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

Attempt This Online!

-3 bytes thanks to @ovs

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Apr 13 at 6:38
  • \$\begingroup\$ @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? \$\endgroup\$ Apr 13 at 9:47
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 13 at 10:04
  • \$\begingroup\$ @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). \$\endgroup\$ Apr 13 at 12:18
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Apr 13 at 19:37
3
\$\begingroup\$

Ruby, 46 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 44 bytes with Ruby 2.7+ \$\endgroup\$
    – Steffan
    Apr 12 at 18:02
3
\$\begingroup\$

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!

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 51: g#l=[[x|x<-[1..],c<-w,x==sum[1|e<-g,e==c]]!!0|w<-l] \$\endgroup\$ Apr 12 at 23:16
3
\$\begingroup\$

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>

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

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!

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

Jelly, 5 bytes

ċⱮⱮṂ€

Attempt This Online!

Hmmm.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Don't you mean "cmmm"? \$\endgroup\$
    – allxy
    Apr 12 at 19:48
2
\$\begingroup\$

Factor, 38 bytes

[ [ counts values infimum ] with map ]

Attempt This Online!

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

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 17 bytes

WS≔⁺ωιωWS⟦I⌊Eι№ωκ

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ι№ωκ

... 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ι№⪫θωλ

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

  η         Word list
 E          Map over words
     ι      Current word
    E       Map over letters
      №     Count of
          λ Current letter in
        θ   Grid
       ⪫    Joined with
         ω  Empty string
   ⌊        Take the minimuim
I           Cast to string
            Implicitly print
\$\endgroup\$
1
  • \$\begingroup\$ The 'awkward' input format is completely fine. The I/O formats are very flexible in this challenge. \$\endgroup\$ Apr 12 at 11:21
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ Apr 13 at 7:13
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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