Fission FSN
Loading...
Searching...
No Matches
gfCLetterPath.h
Go to the documentation of this file.
1/********************************************************************
2*
3* File: gfCLetterPath.h
4*
5* Purpose: Finds a word laid out in a grid of letter tiles - engine
6* free, so it can be tested alone
7*
8*********************************************************************/
9
10#ifndef gfCLetterPathhdr
11#define gfCLetterPathhdr
12
13#include <algorithm>
14#include <string>
15#include <vector>
16
17
18// A tile can hold more than one letter ("qu"). Cells are (column, row).
20{
21public:
22
23 struct sCell
24 {
26 int mRow;
27
28 bool operator==(const sCell& pRHS) const { return mColumn == pRHS.mColumn && mRow == pRHS.mRow; }
29 };
30
31 // pLetters holds each tile's letters, row by row. Straight lines are tried first, then, if pSnake,
32 // a path turning in any of eight directions. No tile is used twice. Empty if the word isn't there.
33 static std::vector<sCell> find(int pColumns, int pRows, const std::vector<std::string>& pLetters,
34 const std::string& pWord, bool pSnake)
35 {
36 const std::vector<sCell> orthogonal = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
37 const std::vector<sCell> diagonal = {{1, -1}, {-1, -1}, {1, 1}, {-1, 1}};
38 std::vector<sCell> any = orthogonal;
39 any.insert(any.end(), diagonal.begin(), diagonal.end());
40
41 struct sPass
42 {
43 const std::vector<sCell>* mDirections;
44 bool mSnaking;
45 };
46 std::vector<sPass> passes = {{&orthogonal, false}, {&diagonal, false}};
47 if (pSnake)
48 {
49 passes.push_back({&any, true});
50 }
51
52 for (const sPass& pass : passes)
53 {
54 for (int row = 0; row < pRows; ++row)
55 {
56 for (int column = 0; column < pColumns; ++column)
57 {
58 std::vector<sCell> path = pathFrom({column, row}, pColumns, pRows, pLetters, pWord, pass.mDirections, pass.mSnaking);
59 if (!path.empty())
60 {
61 return path;
62 }
63 }
64 }
65 }
66 return {};
67 }
68
69private:
70
71 struct sStep
72 {
73 sCell mCell;
74 std::vector<sCell> mUntested;
75 // How much of the word the path covers up to and including this tile.
76 std::size_t mEnd;
77 };
78
79 static bool continues(const std::string& pWord, std::size_t pAt, const std::string& pLetters)
80 {
81 return !pLetters.empty() && pWord.compare(pAt, pLetters.size(), pLetters) == 0;
82 }
83
84 static std::vector<sCell> pathFrom(sCell pStart, int pColumns, int pRows, const std::vector<std::string>& pLetters,
85 const std::string& pWord, const std::vector<sCell>* pDirections, bool pSnaking)
86 {
87 auto letterAt = [&](sCell pCell) -> const std::string& { return pLetters[pCell.mColumn + pCell.mRow * pColumns]; };
88
89 if (!continues(pWord, 0, letterAt(pStart)))
90 {
91 return {};
92 }
93
94 std::vector<sStep> path = {{pStart, *pDirections, letterAt(pStart).size()}};
95 while (!path.empty())
96 {
97 if (path.back().mUntested.empty())
98 {
99 path.pop_back();
100 continue;
101 }
102
103 const sCell direction = path.back().mUntested.back();
104 path.back().mUntested.pop_back();
105 const sCell next = {path.back().mCell.mColumn + direction.mColumn, path.back().mCell.mRow + direction.mRow};
106 if (next.mColumn < 0 || next.mColumn >= pColumns || next.mRow < 0 || next.mRow >= pRows)
107 {
108 continue;
109 }
110
111 const bool used = std::any_of(path.begin(), path.end(), [&](const sStep& pStep) { return pStep.mCell == next; });
112 const std::string& letters = letterAt(next);
113 if (used || !continues(pWord, path.back().mEnd, letters))
114 {
115 continue;
116 }
117
118 const std::size_t end = path.back().mEnd + letters.size();
119 path.push_back({next, pSnaking ? *pDirections : std::vector<sCell>{direction}, end});
120 if (end == pWord.size())
121 {
122 std::vector<sCell> cells;
123 for (const sStep& step : path)
124 {
125 cells.push_back(step.mCell);
126 }
127 return cells;
128 }
129 }
130 return {};
131 }
132};
133
134#endif
Definition gfCLetterPath.h:20
static std::vector< sCell > find(int pColumns, int pRows, const std::vector< std::string > &pLetters, const std::string &pWord, bool pSnake)
Definition gfCLetterPath.h:33
decltype(sizeof(void *)) size_t
Definition doctest.h:524
Definition gfCLetterPath.h:24
int mRow
Definition gfCLetterPath.h:26
int mColumn
Definition gfCLetterPath.h:25
bool operator==(const sCell &pRHS) const
Definition gfCLetterPath.h:28