1 /*
2 SPDX-FileCopyrightText: 2009-2021 Graeme Gott <graeme@gottcode.org>
3
4 SPDX-License-Identifier: GPL-3.0-or-later
5 */
6
7 #include "solver.h"
8
9 #include <QStringList>
10
11 #include <algorithm>
12 #include <functional>
13
14 //-----------------------------------------------------------------------------
15
Solver(const Trie & words,int size,int minimum)16 Solver::Solver(const Trie& words, int size, int minimum)
17 : m_words(&words)
18 , m_node(words.child())
19 , m_size(size)
20 , m_minimum(minimum)
21 , m_track_positions(true)
22 , m_count(0)
23 {
24 // Create neighbors
25 QList<QList<QPoint>> neighbors;
26 const QPoint deltas[] = {
27 QPoint(-1, -1),
28 QPoint(0, -1),
29 QPoint(1, -1),
30 QPoint(-1, 0),
31 QPoint(1, 0),
32 QPoint(-1, 1),
33 QPoint(0, 1),
34 QPoint(1, 1)
35 };
36 for (int r = 0; r < m_size; ++r) {
37 for (int c = 0; c < m_size; ++c) {
38 QList<QPoint> positions;
39 QPoint pos(c, r);
40 for (int i = 0; i < 8; ++i) {
41 QPoint n = pos + deltas[i];
42 if (n.x() > -1 && n.x() < m_size && n.y() > -1 && n.y() < m_size) {
43 positions.append(n);
44 }
45 }
46 neighbors.append(positions);
47 }
48 }
49
50 // Create cells
51 m_cells = QVector<QVector<Cell>>(m_size, QVector<Cell>(m_size));
52 for (int r = 0; r < m_size; ++r) {
53 for (int c = 0; c < m_size; ++c) {
54 int index = (r * m_size) + c;
55 Cell& cell = m_cells[c][r];
56 cell.position = QPoint(c, r);
57 cell.checked = false;
58
59 const auto& n = neighbors.at(index);
60 for (int i = 0; i < n.count(); ++i) {
61 const QPoint& neighbor = n.at(i);
62 cell.neighbors.append(&m_cells[neighbor.x()][neighbor.y()]);
63 }
64 }
65 }
66 }
67
68 //-----------------------------------------------------------------------------
69
solve(const QStringList & letters)70 void Solver::solve(const QStringList& letters)
71 {
72 m_solutions.clear();
73 m_positions.clear();
74 m_word.clear();
75 m_count = 0;
76
77 // Set cell contents
78 for (int r = 0; r < m_size; ++r) {
79 for (int c = 0; c < m_size; ++c) {
80 m_cells[c][r].text = letters.at((r * m_size) + c).toUpper();
81 }
82 }
83
84 // Solve board
85 for (int r = 0; r < m_size; ++r) {
86 for (int c = 0; c < m_size; ++c) {
87 checkCell(m_cells[c][r]);
88 }
89 }
90 }
91
92 //-----------------------------------------------------------------------------
93
score(int max) const94 int Solver::score(int max) const
95 {
96 QList<int> scores;
97 QHashIterator<QString, QList<QList<QPoint>>> i(m_solutions);
98 while (i.hasNext()) {
99 scores += score(i.next().key());
100 }
101 std::sort(scores.begin(), scores.end(), std::greater<int>());
102
103 int count = scores.count();
104 if (max != -1) {
105 count = std::min(max, count);
106 }
107 int result = 0;
108 for (int i = 0; i < count; ++i) {
109 result += scores.at(i);
110 }
111 return result;
112 }
113
114 //-----------------------------------------------------------------------------
115
score(const QString & word)116 int Solver::score(const QString& word)
117 {
118 Q_ASSERT(word.length() <= 25);
119 static constexpr int scores[26] = {
120 0, 0, 0, 1, 1, 2, 3, 5, 11, 11, 11, 11, 11,
121 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11
122 };
123 return scores[word.length()];
124 }
125
126 //-----------------------------------------------------------------------------
127
setTrackPositions(bool track_positions)128 void Solver::setTrackPositions(bool track_positions)
129 {
130 m_track_positions = track_positions;
131 }
132
133 //-----------------------------------------------------------------------------
134
checkCell(Cell & cell)135 void Solver::checkCell(Cell& cell)
136 {
137 const Trie::Node* node = m_node;
138 int length = cell.text.length();
139 for (int i = 0; i < length; ++i) {
140 node = m_words->child(cell.text.at(i), node);
141 if (!node) {
142 return;
143 }
144 }
145
146 cell.checked = true;
147 m_word += cell.text;
148 if (m_track_positions) {
149 m_positions.append(cell.position);
150 }
151 qSwap(m_node, node);
152
153 if (m_node->isWord() && (m_word.length() >= m_minimum)) {
154 m_count++;
155 if (m_track_positions) {
156 m_solutions[m_word].append(m_positions);
157 }
158 }
159 if (!m_node->isEmpty()) {
160 int count = cell.neighbors.count();
161 for (int i = 0; i < count; ++i) {
162 Cell& next = *cell.neighbors.at(i);
163 if (!next.checked) {
164 checkCell(next);
165 }
166 }
167 }
168
169 cell.checked = false;
170 m_word.chop(length);
171 if (m_track_positions) {
172 m_positions.removeLast();
173 }
174 m_node = node;
175 }
176
177 //-----------------------------------------------------------------------------
178