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.
Similar Kata:
Stats:
Created | Jun 5, 2024 |
Published | Jun 7, 2024 |
Warriors Trained | 193 |
Total Skips | 25 |
Total Code Submissions | 150 |
Total Times Completed | 18 |
JavaScript Completions | 18 |
Total Stars | 8 |
% of votes with a positive feedback rating | 100% of 9 |
Total "Very Satisfied" Votes | 9 |
Total "Somewhat Satisfied" Votes | 0 |
Total "Not Satisfied" Votes | 0 |
Total Rank Assessments | 6 |
Average Assessed Rank | 5 kyu |
Highest Assessed Rank | 4 kyu |
Lowest Assessed Rank | 6 kyu |