В этой статье я делюсь найденным кое-как решением бесполезной задачи, поэтому не относитесь к ней очень серьёзно. Но вы можете поучаствовать в поиске решения или поделиться готовыми в комментариях.
Задача
Нужно найти одну или несколько групп по 5 слов из 5 букв, которые отвечают следующим условиям:
-
Это существительные, в именительном падеже, единственном числе
-
Состоят из 25 разных букв, то есть одна буква в группе встречается один раз
-
Слова существуют в русском языке и употребляются в современной речи
Формулировка задачи собственная, мотивирована игрой «5 букв» из банковского приложения. Суть игры в том, чтобы отгадать какое слово было загадано игрой.
Даётся 6 попыток, поэтому чем больше букв можно проверить за 5 попыток, тем вероятнее, что к шестой придёшь с полным набором букв.
Никакой практической ценности в этом нет, что только усугубило желание найти заветный список слов.
Поиск решения
-
Гугление не дало результата. Удалось найти похожую на тему по английским словам на Reddit, но русскоязычных статей не нашёл. Это одна из причин почему написана эта.
-
Нейросети с задачей как-то не справились. Может, надо как-то хитро описать промт и докопаться до нейросети, но человеческое описание задачи не приводило к результатам. Обычно все сдавались либо к третьему, либо к четвёртому слову.
-
Собственный поиск привёл меня на сайт sanstv.ru, откуда удалось набрать такую пятёрку: блюдо, связь, фрейм, шухна, щипцы. Но последнее слово не подходит под условия и не принимается игрой. Но эта пятёрка слов для меня стала проверочной в последствии.
-
Комбинаторика, цепи Маркова и другие технически решения, которые я сам бы закодить не смог.
С выходом ChatGPT 5 мне стало интересно решить эту задачу всё-таки финально.
Идеальная симуляция бурной деятельности
Подход попросить ChatGPT по-человечески привёл меня к очень человеческому результату. Нейросеть обещала сделать, но с каждым разом становилась всё дальше от бога и результата:
С промптами, как видите, я не старался, оставляю этот вариант решения для гуру промптов. Решать задачу таким образом я отказался и пошёл иначе:
-
С ранее упомянутого сайта скачал все слова из 5 букв, которые есть в их словаре. Получилось 7588 слов. Там не только существительные и совсем редкие и странные слова (например, вы знали что такое «гзымс»?), но всё реально существующие.
-
Несколько часов пытал нейросеть, чтобы он выдал скрипт, который быстро и корректно отработает.
-
Вручную проверял получаемые результаты. Самый объёмный результат получился на 407 559 173 строк из групп по 5 слов, размер файла 22.42Гб. Но там быстро нашлись повторы в группах, а моя «проверочная» группа слов не была записана.
И вот я был вознаграждён финальным скриптом:
Скрытый текст
const fs = require("fs"); const path = require("path"); const OUTFILE = process.argv.includes("--output") ? process.argv[process.argv.indexOf("--output") + 1] : "groups.csv"; const MAX_GROUPS = process.argv.includes("--max") ? parseInt(process.argv[process.argv.indexOf("--max") + 1], 10) : 0; const PROGRESS_EVERY = process.argv.includes("--progressEvery") ? parseInt(process.argv[process.argv.indexOf("--progressEvery") + 1], 10) : 200; function uniqCount5(s) { return new Set(s).size === 5; } function buildMasks(words) { const charIndex = new Map(); let next = 0; const masks = []; for (let w of words) { let m = 0n; for (let ch of w) { let id = charIndex.get(ch); if (id === undefined) { id = next++; charIndex.set(ch, id); } m |= 1n << BigInt(id); } masks.push(m); } return masks; } function popcntBigInt(bn) { let c = 0n; while (bn) { bn &= (bn - 1n); c++; } return c; } const wordsPath = path.resolve("words.json"); let words = JSON.parse(fs.readFileSync(wordsPath, "utf8")) .map(w => String(w).trim().toLowerCase()) .filter(w => w.length === 5 && uniqCount5(w)); const N = words.length; console.log(`Слов с 5 уникальными буквами: ${N}`); const masks = buildMasks(words); // совместимость — соседи только с бОльшими индексами const neighbors = Array.from({ length: N }, () => []); for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { if ((masks[i] & masks[j]) === 0n) neighbors[i].push(j); } } const out = fs.createWriteStream(OUTFILE, { encoding: "utf8" }); out.write("word1,word2,word3,word4,word5\n"); let found = 0; let buf = []; const started = Date.now(); function flushBuf() { if (buf.length === 0) return true; const ok = out.write(buf.join("")); buf = []; return ok; } function printProgress(i) { const elapsed = ((Date.now() - started) / 1000).toFixed(1); const pct = ((i / Math.max(1, N - 5)) * 100).toFixed(2); process.stdout.write(`\rПрогресс i: ${i}/${N - 5} (${pct}%), найдено: ${found}, время: ${elapsed}s`); } (async () => { const mark = new Uint8Array(N); outer: for (let i = 0; i <= N - 5; i++) { const ni = neighbors[i]; if (ni.length < 4) { if (i % PROGRESS_EVERY === 0) printProgress(i); continue; } for (const v of ni) mark[v] = 1; for (const j of ni) { const candK = []; for (const v of neighbors[j]) if (v > j && mark[v]) candK.push(v); if (candK.length < 3) continue; for (const v of candK) mark[v] = 2; for (const k of candK) { const candL = []; for (const v of neighbors[k]) if (v > k && mark[v] === 2) candL.push(v); if (candL.length < 2) continue; for (const v of candL) mark[v] = 3; for (const l of candL) { const candM = []; for (const v of neighbors[l]) if (v > l && mark[v] === 3) candM.push(v); for (const m of candM) { const u = masks[i] | masks[j] | masks[k] | masks[l] | masks[m]; if (popcntBigInt(u) !== 25n) continue; buf.push(`${words[i]},${words[j]},${words[k]},${words[l]},${words[m]}\n`); found++; if (buf.length >= 1000) { if (!flushBuf()) await new Promise(res => out.once("drain", res)); } if (MAX_GROUPS && found >= MAX_GROUPS) break outer; } } for (const v of candL) mark[v] = 2; } for (const v of candK) mark[v] = 1; } for (const v of ni) mark[v] = 0; if (i % PROGRESS_EVERY === 0) printProgress(i); } flushBuf(); await new Promise(res => out.end(res)); printProgress(N - 5); const dt = ((Date.now() - started) / 1000).toFixed(1); console.log(`\nГотово. Найдено групп: ${found}. Время: ${dt}s. Файл: ${OUTFILE}`); })();
Консольные команды я не просил и не использовал, но скрипт какой получил, такой и оставил.
Результат
Этот скрипт выдал мне финальный файл на 241 Мб, где было 4 392 707 групп по 5 слов. Всего из первоначальных 7 588 слов получилось 5 131 с уникальными буквами, то есть были исключены слова, типа «масса», где буквы повторяются.
Проверочная группа с неподходящим словом «щипцы» вошла в финальный файл и я смог найти там вариант, где нет множественного числа. А также, ещё одну группу слов, подходящую под условия. Вот обе группы:
-
блюдо, связь, фрейм, цыган, щупик
-
акциз, выгон, судья, тэмбр, шлейф
Убрав прилагательные, редкие слова, множественное число, сократить получилось до 2 013 390 групп, но это явно не предел. Так как свой интерес я удовлетворил и нашёл пару подходящих групп, то дальше раскручивать эту задачу не стал.
Тем не менее, мне интересно было бы узнать, можно ли искать решение «по науке» / дожать нейросеть корректным промтом / закодить задачу в ML или как-то ещё. Поэтому делитесь в комментариях своими идеями.
ссылка на оригинал статьи https://habr.com/ru/articles/939012/
Добавить комментарий