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 "generator.h"
8
9 #include "clock.h"
10 #include "gzip.h"
11 #include "language_settings.h"
12 #include "solver.h"
13 #include "trie.h"
14
15 #include <QCryptographicHash>
16 #include <QDataStream>
17 #include <QDateTime>
18 #include <QDir>
19 #include <QFile>
20 #include <QFileInfo>
21 #include <QSettings>
22 #include <QStandardPaths>
23 #include <QTextStream>
24
25 //-----------------------------------------------------------------------------
26
27 namespace
28 {
29
30 /**
31 * @brief The State class represents a current game being built.
32 */
33 struct State
34 {
35 /**
36 * Constructs a state instance.
37 * @param dice the dice used to fill the board
38 * @param solver the solve used to check the board for solutions
39 * @param target the target amount of words
40 * @param random the random number generator
41 */
State__anon7ce569310111::State42 State(const QList<QStringList>& dice, Solver* solver, int target, QRandomGenerator* random)
43 : m_dice(dice)
44 , m_solver(solver)
45 , m_target(target)
46 , m_random(random)
47 {
48 }
49
50 /**
51 * @return how far off the amount of words on the board is from the target amount of words
52 */
delta__anon7ce569310111::State53 int delta() const
54 {
55 return m_delta;
56 }
57
58 /**
59 * @return the board layout
60 */
letters__anon7ce569310111::State61 QStringList letters() const
62 {
63 return m_letters;
64 }
65
66 /**
67 * Flips individual dice to tweak the board and searches it for solutions.
68 */
permute__anon7ce569310111::State69 void permute()
70 {
71 if (m_random->bounded(2)) {
72 const int index = m_random->bounded(m_dice.count());
73 QStringList& die = m_dice[index];
74 std::shuffle(die.begin(), die.end(), *m_random);
75 m_letters[index] = m_dice.at(index).first();
76 } else {
77 const int index1 = m_random->bounded(m_dice.count());
78 const int index2 = m_random->bounded(m_dice.count());
79 #if (QT_VERSION >= QT_VERSION_CHECK(5,13,0))
80 m_dice.swapItemsAt(index1, index2);
81 m_letters.swapItemsAt(index1, index2);
82 #else
83 m_dice.swap(index1, index2);
84 m_letters.swap(index1, index2);
85 #endif
86 }
87 solve();
88 }
89
90 /**
91 * Rolls the dice to generate a new board and searches it for solutions.
92 */
roll__anon7ce569310111::State93 void roll()
94 {
95 std::shuffle(m_dice.begin(), m_dice.end(), *m_random);
96 m_letters.clear();
97 int count = m_dice.count();
98 for (int i = 0; i < count; ++i) {
99 QStringList& die = m_dice[i];
100 std::shuffle(die.begin(), die.end(), *m_random);
101 m_letters += die.first();
102 }
103 solve();
104 }
105
106 private:
107 /**
108 * Searches the board for solutions and determines how far off the amount of words is from the
109 * target amount of words.
110 */
solve__anon7ce569310111::State111 void solve()
112 {
113 m_solver->solve(m_letters);
114 int words = m_solver->count();
115 m_delta = abs(words - m_target);
116 }
117
118 private:
119 QList<QStringList> m_dice; /**< the dice used to generate a layout */
120 QStringList m_letters; /**< the generated layout */
121 Solver* m_solver; /**< solves the generated layout */
122 int m_target; /**< the target number of words on generated board */
123 int m_delta; /**< how far the actual number of words is from the target */
124 QRandomGenerator* m_random; /**< random number generator */
125 };
126
127 }
128
129 //-----------------------------------------------------------------------------
130
Generator(QObject * parent)131 Generator::Generator(QObject* parent)
132 : QThread(parent)
133 , m_random(QRandomGenerator::securelySeeded())
134 , m_max_score(0)
135 , m_canceled(false)
136 {
137 }
138
139 //-----------------------------------------------------------------------------
140
cancel()141 void Generator::cancel()
142 {
143 blockSignals(true);
144 m_canceled = true;
145 wait();
146 blockSignals(false);
147 }
148
149 //-----------------------------------------------------------------------------
150
create(int density,int size,int minimum,int timer,const QStringList & letters)151 void Generator::create(int density, int size, int minimum, int timer, const QStringList& letters)
152 {
153 m_density = density;
154 m_size = size;
155 m_minimum = minimum;
156 m_timer = timer;
157 m_max_words = (m_timer != Clock::Allotment) ? -1 : 30;
158 m_letters = letters;
159 m_canceled = false;
160 m_max_score = 0;
161 m_solutions.clear();
162 start();
163 }
164
165 //-----------------------------------------------------------------------------
166
run()167 void Generator::run()
168 {
169 update();
170 if (!m_error.isEmpty()) {
171 return;
172 }
173
174 // Store solutions for loaded board
175 Solver solver(m_words, m_size, m_minimum);
176 if (!m_letters.isEmpty()) {
177 solver.solve(m_letters);
178 m_max_score = solver.score(m_max_words);
179 m_solutions = solver.solutions();
180 return;
181 }
182
183 if (m_density == 3) {
184 m_density = m_random.bounded(0, 3);
185 }
186
187 // Find word range
188 int offset = ((m_size == 4) ? 6 : 7) - m_minimum;
189 int words_target = 0, words_range = 0;
190 switch (m_density) {
191 case 0:
192 words_target = 37;
193 words_range = 5;
194 break;
195 case 1:
196 words_target = 150 + (25 * offset);
197 words_range = 25;
198 break;
199 case 2:
200 words_target = 250 + (75 * offset);
201 words_range = 50;
202 break;
203 default:
204 break;
205 }
206
207 // Create board state
208 solver.setTrackPositions(false);
209 State current(dice(m_size), &solver, words_target, &m_random);
210 current.roll();
211 State next = current;
212
213 int max_tries = m_size * m_size * 2;
214 int tries = 0;
215 int loops = 0;
216 do {
217 // Change the board
218 next = current;
219 next.permute();
220
221 // Check if this is a better board
222 if (next.delta() < current.delta()) {
223 current = next;
224 tries = 0;
225 loops = 0;
226 }
227
228 // Prevent getting stuck at local minimum
229 tries++;
230 if (tries == max_tries) {
231 current = next;
232 tries = 0;
233 loops++;
234
235 // Restart if still stuck at local minimum
236 if (loops == m_size) {
237 current.roll();
238 loops = 0;
239 }
240 }
241 } while (!m_canceled && (current.delta() > words_range));
242
243 // Store solutions for generated board
244 m_letters = current.letters();
245 solver.setTrackPositions(true);
246 solver.solve(m_letters);
247 m_max_score = solver.score(m_max_words);
248 m_solutions = solver.solutions();
249 }
250
251 //-----------------------------------------------------------------------------
252
update()253 void Generator::update()
254 {
255 m_error.clear();
256
257 QSettings config;
258 config.beginGroup("Current");
259 LanguageSettings settings(config);
260 m_dictionary_url = settings.dictionary();
261
262 // Load dice
263 QString dice_path = settings.dice();
264 if (dice_path != m_dice_path) {
265 m_dice_path.clear();
266 m_dice.clear();
267 m_dice_large.clear();
268
269 QList<QStringList> dice;
270 QFile file(dice_path);
271 if (file.open(QFile::ReadOnly | QIODevice::Text)) {
272 QTextStream stream(&file);
273 #if (QT_VERSION < QT_VERSION_CHECK(6,0,0))
274 stream.setCodec("UTF-8");
275 #endif
276 while (!stream.atEnd()) {
277 #if (QT_VERSION >= QT_VERSION_CHECK(5,14,0))
278 const QStringList line = stream.readLine().split(',', Qt::SkipEmptyParts);
279 #else
280 const QStringList line = stream.readLine().split(',', QString::SkipEmptyParts);
281 #endif
282 if (line.count() == 6) {
283 dice.append(line);
284 }
285 }
286 file.close();
287 }
288
289 if (dice.count() == 41) {
290 m_dice_path = dice_path;
291 m_dice = dice.mid(0, 16);
292 m_dice_large = dice.mid(16);
293 } else {
294 m_dice = m_dice_large = QList<QStringList>() << QStringList("?");
295 return setError(tr("Unable to read dice from file."));
296 }
297 }
298
299 // Load words
300 QString words_path = settings.words();
301 if (words_path != m_words_path) {
302 m_words_path.clear();
303 m_words.clear();
304
305 // Load cached words
306 constexpr quint32 TANGLET_CACHE_MAGICNUMBER = 0x54524945;
307 constexpr quint32 TANGLET_CACHE_VERSION = 2;
308 QString cache_dir = QStandardPaths::writableLocation(QStandardPaths::AppDataLocation) + "/cache";
309 QString cache_file = QCryptographicHash::hash(words_path.toUtf8(), QCryptographicHash::Sha1).toHex();
310 QFileInfo cache_info(cache_dir + "/" + cache_file);
311 if (cache_info.exists() && (cache_info.lastModified() > QFileInfo(words_path).lastModified())) {
312 QFile file(cache_info.absoluteFilePath());
313 if (file.open(QFile::ReadOnly)) {
314 QDataStream stream(&file);
315 quint32 magic, version;
316 stream >> magic >> version;
317 if ((magic == TANGLET_CACHE_MAGICNUMBER) && (version == TANGLET_CACHE_VERSION)) {
318 stream.setVersion(QDataStream::Qt_5_9);
319 stream >> m_words;
320 }
321 file.close();
322 }
323 }
324
325 // Load uncached words
326 if (m_words.isEmpty()) {
327 emit optimizingStarted();
328
329 m_words = Trie(gunzip(words_path));
330
331 // Cache words
332 if (!m_words.isEmpty()) {
333 QDir::home().mkpath(cache_dir);
334 QFile file(cache_info.absoluteFilePath());
335 if (file.open(QFile::WriteOnly)) {
336 QDataStream stream(&file);
337 stream << TANGLET_CACHE_MAGICNUMBER;
338 stream << TANGLET_CACHE_VERSION;
339 stream.setVersion(QDataStream::Qt_5_9);
340 stream << m_words;
341 file.close();
342 }
343 }
344
345 emit optimizingFinished();
346 }
347
348 if (!m_words.isEmpty()) {
349 m_words_path = words_path;
350 } else {
351 return setError(tr("Unable to read word list from file."));
352 }
353 }
354 }
355
356 //-----------------------------------------------------------------------------
357
setError(const QString & error)358 void Generator::setError(const QString& error)
359 {
360 m_error = error;
361 m_letters.clear();
362 int count = m_size * m_size;
363 for (int i = 0; i < count; ++i) {
364 m_letters.append("?");
365 }
366 }
367
368 //-----------------------------------------------------------------------------
369