Arbitrary angle wrapping wordsearch
Sandbox
-
Would you change anything about the test case format?
-
Are there any more edge cases to add to the test cases?
-
Should words that use the same grid position more than once be considered present? (Currently I am leaning towards allowing this, which I imagine is the easier approach to implement and likely easier to golf.)
-
Does there need to be a limit on the horizontal and vertical offsets to keep them less than the grid width and height respectively? It appears that allowing larger offsets would allow the equivalent of some (all?) non-coprime offsets. Examples for a grid of width W and height H:
- If W and H are coprime, then an offset of (W, H) is otherwise valid, but is equivalent to an offset of (0, 0).
- An offset of (W, 1) is equivalent to an offset of (0, 1), which is valid, but an offset of (W, 2) is equivalent to an offset of (0, 2), which is not valid unless H=3 (making it equivalent to (0, -1)).
- If W+2 and H+2 are coprime, then an offset of (W+2, H+2) is otherwise valid, but is equivalent to an offset of (2, 2), which is not valid.
An alternative would be to allow all non-coprime offsets, slightly simplifying the challenge.
-
There is a similar potential problem with negative offsets being equivalent to non-coprime positive offsets:
- An offset of (2, 2) is not coprime, but it is equivalent to an offset of (-W+2, 2), (2, -H+2), or (-W+2, -H+2), all of which are less in magnitude than W and H horizontally and vertically respectively, and any of which can be coprime for some values of W and H.
This is not necessarily a problem, but may influence the decision on whether to allow non-coprime offsets.
Given a rectangular grid of letters and a word to search for, determine whether the word appears in the grid at any arbitrary angle (not just the 8 multiples of 45 degrees usually used), and possibly wrapping over the edges.
Terminology
A standard wordsearch with 8 possible angles can be thought of as looking for a word where each letter is at an offset (a, b) from the previous letter, where a and b are each one of -1, 0, or 1, but not both 0.
-
An arbitrary angle wordsearch is the same as a standard wordsearch, except a and b can be any coprime integers, (which automatically excludes them both being 0).
Note that multiples of a valid offset by N > 1 are not valid, as this would give a word with gaps. For example, an offset of (2, 0) is the same angle as (1, 0). So (1, 0) is a valid offset, but (2, 0) is not as it would have letters in between the letters of the word, that are on the same line but not part of the word. Similarly (2, 1) is a valid offset, but multiples of it such as (4, 2) and (6, 3) are not valid offsets. This is the reason for requiring a and b to be coprime.
-
A wrapping wordsearch is the same as a standard wordsearch, but also allows a word to pass over an edge of the grid and continue on the opposite side, potentially more than once. Equivalently, a word can be found in a larger grid made by tiling together 2 or more identical copies of the wordsearch grid.
-
An arbitrary angle wrapping wordsearch is both an arbitrary angle wordsearch and a wrapping wordsearch.
Examples
In these examples all of the letters are replaced with . apart from the word to be found, for ease of finding.
In every grid the word to be found is WORDSEARCH.
Standard diagonal word, each letter offset by (1, 1):
W.........
.O........
..R.......
...D......
....S.....
.....E....
......A...
.......R..
........C.
.........H
Diagonal word wrapping over the bottom edge:
....S.....
.....E....
......A...
.......R..
........C.
.........H
W.........
.O........
..R.......
...D......
The same example with the grid tiled twice vertically to see how the word then ends up in a straight line (all other letters made lowercase so the unbroken word stands out):
....s.....
.....e....
......a...
.......r..
........c.
.........h
W.........
.O........
..R.......
...D......
....S.....
.....E....
......A...
.......R..
........C.
.........H
w.........
.o........
..r.......
...d......
Diagonal word wrapping over the right edge:
......W...
.......O..
........R.
.........D
S.........
.E........
..A.......
...R......
....C.....
.....H....
The same example with the grid tiled twice horizontally to see how the word then ends up in a straight line (all other letters made lowercase so the unbroken word stands out):
......W.........w...
.......O.........o..
........R.........r.
.........D.........d
s.........S.........
.e.........E........
..a.........A.......
...r.........R......
....c.........C.....
.....H.........H....
Diagonal word wrapping over the right edge then the bottom edge:
...R......
....C.....
.....H....
......W...
.......O..
........R.
.........D
S.........
.E........
..A.......
The same example with the grid tiled twice horizontally and twice vertically to see how the word then ends up in a straight line (all other letters made lowercase so the unbroken word stands out):
...r.........r......
....c.........c.....
.....h.........h....
......W.........w...
.......O.........o..
........R.........r.
.........D.........d
s.........S.........
.e.........E........
..a.........A.......
...r.........R......
....c.........C.....
.....h.........H....
......w.........w...
.......o.........o..
........r.........r.
.........d.........d
s.........s.........
.e.........e........
..a.........a.......
Each letter offset by (2, 1), wrapping over the right edge:
W.........
..O.......
....R.....
......D...
........S.
E.........
..A.......
....R.....
......C...
........H.
The same example with the grid tiled twice horizontally to see how the word then ends up in a straight line (all other letters made lowercase so the unbroken word stands out):
W.........w.........
..O.........o.......
....R.........r.....
......D.........d...
........S.........s.
e.........E.........
..a.........A.......
....r.........R.....
......c.........C...
........h.........H.
Each letter offset by (-3, 2), wrapping over left edge and then bottom edge and then left edge again:
....E....W
..........
.A....O...
..........
...R....R.
..........
D....C....
..........
..H....S..
..........
The same example again but with the grid tiled 3 times horizontally and twice vertically to see how the word then ends up in a straight line (all other letters made lowercase so the unbroken word stands out):
....e....w....e....w....e....W
..............................
.a....o....a....o....a....O...
..............................
...r....r....r....r....R....r.
..............................
d....c....d....c....D....c....
..............................
..h....s....h....S....h....s..
..............................
....e....w....E....w....e....w
..............................
.a....o....A....o....a....o...
..............................
...r....R....r....r....r....r.
..............................
d....C....d....c....d....c....
..............................
..H....s....h....s....h....s..
..............................
Each letter offset by (11, 11), wrapping over both the right and bottom edges every step, showing that this is exactly equivalent to an offset of (1, 1):
W.........
.O........
..R.......
...D......
....S.....
.....E....
......A...
.......R..
........C.
.........H
Input
- A grid of letters and a sequence of letters (a "word") to search for
- The grid of letters may be any ordered data structure of characters, or an ordered data structure of strings representing rows, or a single string containing letters and line delimiters
- The grid will always be rectangular (the rows will all be the same length)
- The grid will always have at least 1 row and at least 1 column (it will never be empty)
- You may optionally also take the width and/or height of the grid as inputs
- The sequence of letters to search for (the word) may be any ordered data structure of characters, or a single string
- The word will always have at least 2 letters
- You may choose to take the inputs in whichever order you prefer
Output
- Any truthy value if the word is present, or any falsy value otherwise
- You may instead choose any 2 distinct values or sets of values to represent true and false if you wish (even if they are not truthy or falsy respectively in your language of choice)
- The word is present if it occurs at any angle with no gaps (no interjacent letters at that precise angle), potentially wrapping over the edges of the grid one or more times (including running over some of the letters more than once if the word contains repeated letters). See the Terminology and Examples sections above if there is doubt over interpretation
- You may choose to work with either only upper case letters or only lower case letters, or both, and your code may be case sensitive or insensitive
Test cases
Each test case is in the format:
[["comma", "separated", "row", "strings"], "word", "true" or "false"]
[
[
[
"ABC",
"DEF",
"GHI"
],
"ABC",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AB",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"BC",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AC",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AF",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"IA",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AI",
"true"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AHC",
"false"
],
[
[
"ABC",
"DEF",
"GHI"
],
"AHF",
"true"
],
[
[
"AXBYC"
],
"AC",
"true"
],
[
[
"AXBYCZ"
],
"AC",
"true"
],
[
[
"AXBYCZ"
],
"ABC",
"true"
],
[
[
"ASGYM",
"ZNBTH",
"UIAOC",
"PDVJB",
"KCQEW",
"FXLDR"
],
"ABCDABCDA",
"false"
],
[
[
"ASGYM",
"ZNBTH",
"UIAOC",
"PDVJB",
"KCQEW",
"FXLDR"
],
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCD",
"true"
],
[
[
"ASGYM",
"ZNBTH",
"UIAOC",
"PDVJB",
"KCQEW",
"FXLDR"
],
"ABCDABCD",
"true"
],
[
[
"XAAAAAAAA",
"AAAAAAAAA",
"AAAAYAAAA",
"AAAAAAAAA",
"AAAAAAAAZ"
],
"XAYAZ",
"true"
],
[
[
"XAAAAAAAA",
"AAAAAAAAA",
"AAAAYAAAA",
"AAAAAAAAA",
"AAAAAAAAZ"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAAA",
"AAAAAAAAAA",
"AAAAYAAAAA",
"AAAAAAAAAA",
"AAAAAAAAZA"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAA",
"AAAAAAAAA",
"AAAAYAAAA",
"AAAAAAAAA",
"AAAAAAAAZ",
"AAAAAAAAA"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAAA",
"AAAAAAAAAA",
"AAAAYAAAAA",
"AAAAAAAAAA",
"AAAAAAAAZA",
"AAAAAAAAAA"
],
"XYZ",
"false"
],
[
[
"XAAAAAAAAA",
"AAAAAAAAAA",
"AAAAYAAAAA",
"AAAAAAAAAA",
"AAAAAAAAZA",
"AAAAAAAAAA",
"AAAAAAAAAA"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAAA",
"AAAAAAAAAA",
"AAAAYAAAAA",
"AAAAAAAAAA",
"AAAAAAAAZA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA"
],
"XYZ",
"false"
],
[
[
"XAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAYAAAAAAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAAAAAAZAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAA"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAAAAAAYAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAZAAAAAAAAA",
"AAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAA"
],
"XYZ",
"true"
],
[
[
"XAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAYAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAZAA",
"AAAAAAAAAAA"
],
"XYZ",
"false"
],
[
[
"XAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAAAA",
"AAAAAYAAAAA",
"AAAAAAAAAAA",
"AAAAAAAAZAA",
"AAAAAAAAAAA"
],
"XZY",
"true"
],
[
[
"YO"
],
"YOYO",
"true"
],
[
[
"EK"
],
"EKE",
"true"
],
[
[
"EK"
],
"EEK",
"false"
],
[
[
"Z"
],
"ZZ",
"true"
],
[
[
"Z"
],
"ZZZZZZZZZZZZZ",
"true"
],
[
[
"ZA"
],
"ZZ",
"true"
],
[
[
"Z",
"A"
],
"ZZ",
"true"
],
[
[
"ZA",
"AA"
],
"ZZ",
"false"
],
[
[
"ZAA",
"AAA"
],
"ZZ",
"true"
],
[
[
"ZA",
"AA",
"AA"
],
"ZZ",
"true"
],
[
[
"Z",
"A",
"A",
"A"
],
"ZZ",
"true"
],
[
[
"ZA",
"AA",
"AA",
"AA"
],
"ZZ",
"false"
],
[
[
"ZAA",
"AAA",
"AAA"
],
"ZZ",
"false"
],
[
[
"ZAA",
"AAA",
"AAZ"
],
"ZZ",
"true"
],
[
[
"ZAAA",
"AAAA",
"AAZA",
"AAAA"
],
"ZZ",
"false"
]
]
Some of the test cases show "true" even though it may not always be obvious how the word can be found in the grid. Below are tiled grids for each "true" test case, showing how the word can be found in a straight line potentially over several grids, to visualise how the wrapping works. The found word shows in UPPER CASE, with all other letters reduced to lower case for contrast.
Test case visual justifications (hidden in case you want to work them out as an exercise)
TODO: this
Explanations are optional, but I'm more likely to upvote answers that have one.
2 comment threads