5 kyu

Regex Wordsearch Solver

Description:

Preamble

A wordsearch is a type of word-based puzzle often assigned to school children as a language learning exercise. The objective of the puzzle is to find one or more given words which are concealed within a grid of letters.

Task overview

Your task is to write a function which takes list of words and grid size and returns a regular expression. This regular expression should be able to match all occurrences of the given words inside all possible square grids of the given size - in order to solve the puzzle via replacing them, mimicking the way they are solved via highlighting/crossing out/circling on pencil and paper. The returned regex will be tested against multiple different boards, with the exact testing setup being viewable in the sample tests. See the Specifications section for details.

An example

For size = 3 and words = {CAT, ART} a regular expression such as /[CART]/g would work for some grids, such as this one:

CAT    ***
KRY -> K*Y
JTO    J*O

But it would not work for all possible grids - for example, it would match too many characters in this one:

CAT    ***
RRK -> **K
ATW    **W

Your regular expression must work for ALL arbitrary grids which conform to the constraints provided below in Specifications.

Specifications (see sample tests or shout at me in the discourse if in doubt)

  • Your returned RegExp instance will be recompiled in order to prevent [Symbol] abuse.
  • Boards use a single newline (\n) character between each row, with no trailing newline.
  • Boards are all square.
  • Boards will contain only ASCII uppercase characters, dots, and newlines ([A-Z.\n]).
  • Words will only contain ASCII uppercase characters ([A-Z]).
  • Only ASCII uppercase characters should be matched - all other characters, including ASCII lowercase ([a-z]), should NOT be matched.
  • Each word may appear multiple times in a single board.
  • Words can go in any of the compass directions - (N, S, E, W, NE, NW, SE, SW).
  • Words go only in straight lines.
  • Words can overlap, and should both be matched in this instance.

Test parameters

  • 5 <= board size <= 15
  • 3 <= word size <= board size
  • 1 <= number of words <= 5

Note to translators

This kata is largely designed around the specifications of the regex engine provided by JS, and translating it into the significantly more powerful engines (Perl, Python, Ruby, etc) would change the nature of the kata too much.

Matrix
Regular Expressions
Strings

More By Author:

Check out these other kata created by KayleighWasTaken

Stats:

CreatedJun 5, 2024
PublishedJun 7, 2024
Warriors Trained193
Total Skips25
Total Code Submissions150
Total Times Completed18
JavaScript Completions18
Total Stars8
% of votes with a positive feedback rating100% of 9
Total "Very Satisfied" Votes9
Total "Somewhat Satisfied" Votes0
Total "Not Satisfied" Votes0
Total Rank Assessments6
Average Assessed Rank
5 kyu
Highest Assessed Rank
4 kyu
Lowest Assessed Rank
6 kyu
Ad
Contributors
  • KayleighWasTaken Avatar
  • Kacarott Avatar
Ad