Scralphabet
Обычный пакет плиток Эрудит содержит следующие буквы ( ?
это пустая плитка, которая может обозначать любую другую букву):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
Буквы имеют следующее значение:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Учитывая обычный пакет плиток Эрудит, составьте набор непересекающихся слов с наибольшим количеством очков (т. Е. Отдельные слова, а не на доске Эрудит) при следующих условиях:
- Оценка для каждого слова
sum(letter_values) * length(word)
. - Вы можете включить не более одного слова, начиная с каждой буквы алфавита (т. Е. Максимум 26 слов).
- Только действительные слова Эрудит (из этого словаря ) могут быть включены. Вы можете прочитать словарь из файла, жестко закодировать его (тьфу) или почистить его с сайта.
- Вам не нужно использовать каждую плитку, но все неиспользуемые плитки образуют одно слово с одинаковым счетом, которое вычитается из вашей оценки.
При желании ваш код может принимать два ввода: содержимое пакета в виде строки и буквенные значения в некотором формате, похожем на Python dict
(как указано выше); Кроме того, вы можете жестко закодировать содержимое пакета и буквенные значения. Он должен выводить слова в вашем наборе, их соответствующие оценки и ваш общий счет в некотором разумном формате.
Выигрывает набор слов, набравший наибольшее количество очков.
code-challenge
string
optimization
scrabble
sirpercival
источник
источник
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Ответы:
С 2765 (оптимально)
редактировать
Теперь все в одном C-файле. Это просто находит все оптимальные решения. Все они должны содержать 6 слов по 15 букв и одно 10-буквенное слово, состоящее из 8 букв значения 1 и двух пробелов. Для этого мне нужно только загрузить часть словаря, и мне не нужно искать слова из 15 букв с пробелами. Код представляет собой простой исчерпывающий поиск в глубину.
Использование:
Обратите внимание, что каждое решение печатается дважды, потому что при добавлении слова «W» из 15 букв создаются 2 ордера, потому что есть 2 плитки «W».
Первое решение, найденное с разбивкой по точкам:
Изменить: объяснение
Что делает возможным поиск по всему пространству? При добавлении нового слова я принимаю во внимание только те слова, которые имеют самую редкую оставшуюся букву. В любом случае, эта буква должна быть в каком-то слове (и 15-буквенном слове, поскольку это будет не однозначное письмо, хотя я не проверяю это). Итак, я начинаю со слов,
J, Q, W, W, X, Z
которые имеют значение50, 100, 100, 100, 200, 500
. На более низких уровнях я получаю больше отсечения, потому что некоторые слова исключаются из-за отсутствия букв. Ширина дерева поиска на каждом уровне:Конечно, много обрезания достигается не проверкой неоптимальных решений (пробелы в 15 буквенных словах или более короткие слова). Так что, к счастью, решение 2765 может быть достигнуто с помощью этого словаря (но он был близок, только 2 комбинации из 15 буквенных слов дают разумный остаток). С другой стороны, легко модифицировать код, чтобы находить комбинации с меньшим количеством очков, где не все оставшиеся 10 букв являются 1-значными, хотя было бы сложнее доказать, что это будет оптимальным решением.
Также в коде показан классический случай преждевременной оптимизации. Эта версия
matches
функции делает код только на 30% медленнее:Я даже придумал, как сделать параллельное сравнение с битами еще короче, чем в моем исходном коде (в этом случае нельзя использовать наивысший клев, но это не проблема, поскольку мне нужно только 26 из 32 клевов):
Но это дает нулевое преимущество.
редактировать
При написании объяснения выше я понял, что большую часть времени тратится на сканирование списка слов для тех, которые содержат конкретную букву, не входящую в
matches
функцию. Предварительный расчет списков дал 10-кратное ускорение.источник
Python 2, оценка:
18402162Эта программа сначала находит лучшее слово для подсчета очков, доступное с данными плитками (без использования подстановочных знаков), затем делает 10000 попыток включить случайные слова, которые соответствуют ограничениям уникального первого символа и имеют доступные плитки. С текущими константами, программа занимает 27 секунд для запуска на моей машине. Использование больших констант, вероятно, поможет найти более высокую комбинацию слов.
ОБНОВЛЕНИЕ: теперь используется двухэтапный алгоритм выбора, поэтому он находит лучшее из 50 слов на каждом этапе выбора. Оценка штрафа теперь также используется в алгоритме оценки.
Я включил сюда лучшее из нескольких трасс:
Обратите внимание, что я не использую групповые символы и плачу больше штрафа (из-за длины слова). Будущее улучшение может включать использование подстановочных знаков.
источник
Имитация отжига (оценка 2246)
К сожалению, это недетерминировано. Я постараюсь исправить это и найти детерминированное семя, которое дает лучшую ценность.
источник
Python, оценка
263826752676268926992717Результат:
Код:
Объяснение:
Поиск в глубину, который ищет все дерево, выбирая
picks
лучшие слова на каждом этапе.Я сортирую весь список слов один раз по счету в начале. После выбора каждого слова для следующей итерации я отфильтровываю все слова, которые теперь больше невозможны, сохраняя порядок, поэтому мне не нужно сортировать список на каждом шаге. Чтобы иметь дело с подстановочными знаками, если есть возможность, что подстановочные знаки необходимы, я выбираю 10000 лучших кандидатов, заменяю пропущенные буквы подстановочными знаками, если это необходимо, и делаю повторную сортировку на основе новых (более низких) баллов.
Этот выход предназначен для
picks=5
и начал8m01s
работать на моей 8-машине ядра.источник
Java 8, оценка
26412681Программа начинается с 40 лучших слов. Для каждого слова он находит 40 лучших слов, чтобы идти вместе. Из 1600 комбинаций программа берет 40 лучших. Для каждой комбинации 40 лучших слов найдены, и цикл повторяется.
Когда осталось всего несколько плиток, оставшиеся буквы объединяются с двумя пробелами для последнего слова.
Обновить
Я увеличил порог до 50 лучших слов. Кроме того, каждая комбинация добавляет только слова, которые меньше тех, которые уже присутствуют. Это предотвращает множественные перестановки одной и той же группы.
Программа:
источник
Perl, оценка: 2655
2630Использование:
Использование пробелов на самом деле не так уж много, но значительно замедляет выполнение:
После добавления некоторых эвристик:
источник
Python 3, оценка 2735
(Оптимальная оценка 2765, «6 слов из 15 букв и одно 10-буквенное слово, состоящее из 8 букв значения 1 и двух пробелов» была достигнута nutki .)
Я использовал жадный подход, похожий на чужой:
Я начну с одноэлементных списков, содержащих лучшие слова, содержащие Q.
На каждом шаге для каждого элемента списка я создаю
k = 800
новые списки с лучшими юридическими словами для списка. Из агрегированного списка списков я сохраняю спискиk
лучших заездов и повторяю процесс 10 раз.Обратите внимание, что вы можете получить верхние
k
элементыn
списка -long в O (n + k * log n), который равен O (n), если,k<<n
как в нашем случае (k = 800, n ~= 250000
), с очередью кучи. Я предполагаю, что этот метод не используется в других представлениях, следовательно, меньшиеk
значения.Я использую подстановочные знаки по пути, если это необходимо для слов.
Время выполнения составляет пару минут
k = 800
. Большие значения и другие оптимизации еще не дали лучших результатов.Результат:
Я экспериментировал с продуктом Декарта из лучших слов, содержащих Q, J и X, так как эти буквы почти не разделяют слова. Моя лучшая оценка с этой стратегией была 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).Ненужный сложный спагетти-код (со следами экспериментов с другими методами):
источник