13
\$\begingroup\$

I got to wondering yesterday if I could write a program to comb through a given word search and output the answers. It was actually surprisingly easy. Now I wonder just how small we can get.

Rules

  • Your first input is a string or collection of n lines, each of which is n characters long
  • Your second input is a list of words in any format to find in the puzzle
  • All words in the search list are guaranteed to be in the puzzle
  • Words can be oriented in any of the four cardinal directions, as well as diagonally both forwards and backwards
  • Only uppercase A-Z characters will be present in the puzzle
  • Your code must find every word in the the search string, and output the coordinate position of the starting letter, where 0,0 is the top left character.
  • In the event that you locate more than one instance of the same word, you may handle it however you like. Output it multiple times, or only once, it's up to you

Examples/Test Cases

Given the following board:

ABCD
EFGH
IJKL
MNOP

And the following search string:

ABCD,CGKO,POMN,NJF,AFKP,CFI,LGB,MJGD

Your program should output the following, in any order:

ABCD at 0,0
CGKO at 0,2
PONM at 3,3
NJF at 3,1
AFKP at 0,0
CFI at 0,2
LGB at 2,3
MJGD at 3,0

As always, shortest answer wins

\$\endgroup\$
  • 6
    \$\begingroup\$ Welcome to PPCG! Nice first challenge! \$\endgroup\$ – AdmBorkBork Apr 20 '18 at 18:52
  • 2
    \$\begingroup\$ Similar, the only real difference seem to be the inclusion of the location in the output. \$\endgroup\$ – FryAmTheEggman Apr 20 '18 at 18:57
  • \$\begingroup\$ @NL628 Yes, all search words are guaranteed to be in the puzzle. If there is more than one occurence, you can either output it both times or ignore it the second, it's up to you. \$\endgroup\$ – morpen Apr 20 '18 at 19:07
  • \$\begingroup\$ @JonathanAllan Great idea. I will update it as you suggested. \$\endgroup\$ – morpen Apr 20 '18 at 19:08
  • 1
    \$\begingroup\$ @RickHitchcock Yes it should :) \$\endgroup\$ – morpen Apr 20 '18 at 19:17
4
\$\begingroup\$

JavaScript (Node.js), 154 152 150 141 bytes

  • thanks to Arnauld for reducing by 2 bytes

returns array of locations (it was a string with new lines before)

(b,w)=>w.map(s=>[...b].map((_,p)=>[1,-1,r=b.search`
`,-r,~r,++r,-~r,~r].map(d=>[...s].every((c,i)=>c==b[p+d*i])?s+=" at "+[p/r|0,p%r]:0))&&s)

Try it online!

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

Python 2, 213 bytes

lambda a,W:[(w,i,j)for w in W for i in R(L(a))for j in R(L(a[0]))for U in R(9)if U-4and g(i,j,U/3-1,U%3-1,a).find(w)==0]
g=lambda i,j,u,v,a,s='':L(a)>i>=0<=j<L(a[0])and g(i+u,j+v,u,v,a,s+a[i][j])or s
L=len;R=range

Try it online!

g takes a starting location i,j and a direction u,v and via recursion extracts the string starting at that location in that direction.

f then visits each starting location i,j and direction U/3-1,U%3-1 and checks each word w to see if the resulting string starts with w.

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

Python 3, 149 147 bytes

def g(b,w):h=b.find('\n')+1;return[f'{y} at {i//h},{i%h}'for y in w for i in range(len(b))for d in(1,h+1,h,h-1,-1,~h,-h,1-h)if y==b[i::d][:len(y)]]

Try it online!

Ungolfed version

def g(b,w):
    h = b.find('\n') + 1                              # width of a row plus the '\n'
    a = []
    for y in w:                                       # iterate over the words
        for i in range(len(b)):                       #   iterate over the game board
            for d in(1,h+1,h,h-1,-1,~h,-h,1-h):       #     for each possible direction
                if y==b[i::d][:len(y)]:               #       see if the word matches
                    a.append(f'{y} at {i//h},{i%h}')
    return a

The main idea is that b[i::d] selects a slice from the game board. The slice starts as position i and extends in the direction d. For example, d = h+1 corresponds to the southeast diagonal, whereas d = ~h, which is the same as -h-1, corresponds to the northwest diagonal. [:len(y)] chops the slice off at the same length as the word being searched.

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