10
\$\begingroup\$

Introduction:

In my recent Strikethrough the Word Search List challenge I mentioned the following:

When I do the word-search puzzles, I (almost) always go over the words in order, and strike them through one by one.

In some cases I do them in reversed order as a change of pace, although that doesn't matter too much right now. When I do them in the correct alphabetical order however, I sometimes already see the word after the one I'm currently searching for. In those cases, I usually 'sneakily' strike through that next word already, before I continue searching for the actual current word.

In almost™ all cases, this occurs when both words have the same starting letter, and the next word that I find accidentally is in a horizontal left-to-right direction.

Brief explanation of what a word search is:

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:

Today's challenge is simple. Given a grid of letters and a list of words, output the maximum amount of times what I describe above can occur.

We do this with two steps:

  1. Find all words from the given list which can be found in the grid in a horizontal left-to-right direction.
  2. For each of those words, check if the word before it in the given list starts with the same letter.

Example:

Grid:
JLIBPNZQOAJD
KBFAMZSBEARO
OAKTMICECTQG
YLLSHOEDAOGU
SLHCOWZBTYAH
MHANDSAOISLA
TOPIFYPYAGJT
EZTBELTEATAZ

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

Horizontal left-to-right words:

enter image description here

Word-pairs of these horizontal left-to-right words, with its preceding word in the list:

Words:
BAT,BEAR   ← B
BEAR,BELT  ← B
CAT,COW    ← C
GAL,HAND
HAT,MICE
MICE,SHOE
SHOE,TOP

From these pairs, three start with the same letters, so the output is 3.

Challenge rules:

  • As you may have noted above, we only look at the word directly preceding it. For the BELT in the example, BALL,BAT,BEAR are all three before it and start with a B as well, but we only look at the word directly preceding it (BEAR in this case), and the counter would only increase by 1 for the output.
  • If the very first word in the list is a horizontal left-to-right word, there is obviously no word before it.
  • The list of words is guaranteed to contain at least two words, and all words are guaranteed to be present in the given grid.
  • You can take the inputs in any reasonable format. Could be from STDIN input-lines; as a list of lines; a matrix of characters; etc.
  • You can optionally take the dimensions of the grid as additional input.
  • All words are guaranteed to have at least two letters.
  • You can assume each word is only once in the grid.
  • You can assume the list of words are always in alphabetical order.

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:

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: 3

Inputs:
ABC
SRO
KAX

AB
ASK
ARB
ARX
AX

Output: 1

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

BACKWARD
DIAGONAL
FIND
HORIZONTAL
RANDOM
SEEK
SLEUTH
VERTICAL
WIKIPEDIA
WORDSEARCH

Output: 1

AYCD
EFGH
DCBA

ABC
AYC
CB
CBA
CD
EF
EFGH

Output: 4    
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Just to be 100% sure, the list of words is always in alphabetical order? \$\endgroup\$
    – Neil
    Mar 23 at 17:55
  • \$\begingroup\$ @Neil Woops.. In the linked challenge it was irrelevant but I did mention it, and here it IS relevant and I forgot to add it. I've just added it to the rules, but yes: you can assume the list of words is always in alphabetical order. \$\endgroup\$ Mar 23 at 18:04
  • \$\begingroup\$ Thanks, that makes a subtle difference to my Retina answer, as I had two versions for the same byte count but the alphabetical ordering allowed me to save a byte on one version. \$\endgroup\$
    – Neil
    Mar 23 at 20:02
  • \$\begingroup\$ @Neil Now I'm curious about your alternative Retina answer. :) \$\endgroup\$ Mar 24 at 9:49
  • 1
    \$\begingroup\$ It wasn't clear whether it was better to take the grid first or the list of words first. With the grid first I match <gridword>...<initial>...<listword>, and it doesn't matter which word the initial matches (although in practice the regex engine will pick the previous word) but with the list of words first I have to ensure I only match one <initial>, which costs a byte, although it would be faster on really large grids. \$\endgroup\$
    – Neil
    Mar 24 at 9:59

8 Answers 8

5
\$\begingroup\$

R, 73 69 68 bytes

Edit: -1 byte thanks to pajonk

function(g,w)sum((c(l<-substr(w,1,1),T)==c(T,l))[sapply(w,grepl,g)])

Try it online!

Function with arguments g=grid, as a single string with each line in the grid separated by spaces (newlines would also be fine), and w=words, as a vector of individual words.

\$\endgroup\$
2
  • \$\begingroup\$ Simple -1 \$\endgroup\$
    – pajonk
    Mar 23 at 13:03
  • \$\begingroup\$ @pajonk - Ah, yes, thanks! \$\endgroup\$ Mar 23 at 13:05
4
\$\begingroup\$

Jelly,  12 11  8 bytes

-3 thanks to @KevinCruijssen (take the wordsearch as a mulitline list of characters).

=Ḣ¥ƝŻḋẇ€

A dyadic Link that accepts the list of words on the left and the wordsearch (a multiline list of characters) on the right and yields a non-negative integer.

Try it online!

How?

=Ḣ¥ƝŻḋẇ€ - Link: words W (list of lists of characters); wordsearch P (list of characters)
   Ɲ     - for neighbouring words in W:
  ¥      -   last two links as a dyad - f(left, right):
=        -     left equals right (vectorises)
 Ḣ       -     head
    Ż    - prepend a zero
           -> E = a list of 1s and 0s identifying whether the previous
                  word stated with the same letter.
       € - for each Word in W:
      ẇ  -   is Word a sublist of P?
           -> F = a list of 1s and 0s identifying whether the current
                  word is in the wordsearch
     ḋ   - E dot-product F
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you save bytes by taking the grid as a multi-line string so you don't need the K? \$\endgroup\$ Mar 23 at 13:47
  • \$\begingroup\$ Oh, yes I could - thanks! \$\endgroup\$ Mar 23 at 14:01
4
\$\begingroup\$

Python 3.8 (pre-release), 58 bytes

lambda n,k:sum(a[0]==b[0]*(b in n)for a,b in zip(k,k[1:]))

Try it online!

Takes the grid (n) as a string that includes newlines, and the list of words (k) as a... list of words.

Simple. Find the number of consecutive pairs in k that have the same starting letter and where the second word in the pair is in the grid. The grid is a newline string, so if a word is present horizontally, then somewhere in the grid, there is a run of letters equal to that word that is not cut off by any newline.

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

Charcoal, 33 bytes

WS⊞υι≔⁰θWS«≧⁺∧№⪫υ¶ι⁼§ι⁰ψθ≔§ι⁰ψ»Iθ

Try it online! Link is to verbose version of code. Takes both grid and list as a newline-terminated list of newline-separated strings. Explanation:

WS⊞υι

Read in the grid.

≔⁰θ

Start with no matching words.

WS«

Loop through the list.

≧⁺∧№⪫υ¶ι⁼§ι⁰ψθ

If the current word is a left-to-right word and its first letter is the same as that of the previous word then increment the count.

≔§ι⁰ψ

Save the first letter of this word for the next iteration of the loop.

»Iθ

Output the final count.

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

Vyxal, 13 bytes

2lƛvh≈⁰ẋntc;∑

Try it Online or run all the test cases.

How?

2lƛvh≈⁰ẋntc;∑
2l            # Get a list of overlapping pairs in the (implicit) first input
  ƛ           # Map over them:
   vh         # Get the first character of both
     ≈        # Are they equal?
      ⁰       # Push the second input
       ẋ      # Repeat (so if the first characters are not equal, empty string, else second input)
        n     # Push the pair again
         t    # Get the second item in the pair
          c   # Does the other string contain this string?
           ;  # Close map lambda
            ∑ # Summate
\$\endgroup\$
1
\$\begingroup\$

J, 36 31 bytes

1#.(0,2=&{.&>/\[)*1#.,@E.&>/@,:

Try it online!

-5 stealing dominic's idea of taking the matrix lines as a single space-delimited string

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

Retina 0.8.2, 25 bytes

&`((.).+).*;.*\b\2.+,\1\b

Try it online! Takes input as two semicolon-separated comma-delimited lists but link includes header that converts from newline-separated for convenience. Explanation:

&`

Count the number of overlapping matches (except only match once at any given starting position).

((.).+).*;

Match a word in the grid.

.*\b\2.+

Check that its first letter appears in another word in the list.

,\1\b

Check that the word appears in the list.

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

05AB1E, 12 bytes

ü2ε€нË×yθå}O

Since there hasn't been a 05AB1E answer yet, I'm gonna post my prepared solution.

First input is a list of words; second the grid as a multi-line string.

Try it online or verify all test cases.

Explanation:

ü2         # Create overlapping pairs of the first (implicit) input-list of words
  ε        # Map over each overlapping pair:
   €       #  Map over both words:
    н      #   Only leave their first character
     Ë     #  Check if both first characters are the same
      ×    #  Repeat the second (implicit) input-grid by that check
           #  (so the grid itself if truthy, or an empty string if falsey)
       y   #  Push the pair of words again
        θ  #  Pop and leave the last word
         å #  Check if its in the grid (or empty string)
  }O       # After the map: sum to get the amount of truthy values
           # (after which the result is output implicitly)
\$\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.