Можете ли вы представить решение кроссворда New York Times без каких-либо подсказок? Может быть, не со всей креативностью и новыми словами и фразами, появляющимися в современных кроссвордах, но с фиксированным списком слов есть некоторая надежда. В этом задании вы создаете сетку кроссвордов, в которой это теоретически возможно.

Соревнование

Максимизируйте количество белых квадратов в сетке кроссвордов 15x15 белого и черного оттенков, чтобы белые квадраты можно было однозначно заполнить буквами, чтобы каждое слово в поперечном и нижнем словах появлялось в международном списке слов Эрудит.

Решения по строительству сетки

В американских газетах сетки кроссвордов обычно составляются таким образом, что каждая буква «проверяется», что означает, что она является частью как слова «поперек», так и слова «вниз». В Великобритании и других странах (особенно в загадочных кроссвордах ) это не обязательно так: если слово «поперек» или «вниз» будет состоять только из одной буквы, оно не обязательно должно быть фактическим словом (например, «A» или «I»). «). Для этого испытания следуйте более мягким правилам: однобуквенные слова не должны появляться в списке слов.

Существуют различные другие традиции (в США и других странах), ни одна из которых не должна соблюдаться в этом вызове. Например, слова могут состоять только из двух букв, слова могут повторяться, и сетка не должна иметь (вращательную) симметрию.

Это вообще возможно?

Да! Можно написать короткий скрипт, чтобы убедиться, что единственным решением для следующей пустой сетки слева является заполненная сетка справа:

Заполненную сетку можно отобразить в машиночитаемом формате следующим образом:

###CH##########
###YE##########
###AM##########
CYANOCOBALAMINE
HEMOCHROMATOSES
###CH##########
###OR##########
###BO##########
###AM##########
###LA##########
###AT##########
###MO##########
###IS##########
###NE##########
###ES##########

Ваше решение

Сетка выше имеет 56 белых квадратов из 225 квадратов в сетке 15х15. Это служит основой для этой задачи. Сетки с меньшим количеством белых квадратов также могут быть интересны по причинам, отличным от их оценки, например, если они удовлетворяют некоторым эстетическим традициям, упомянутым выше.

Пожалуйста, отправьте ваше решение в том же формате, что и читаемый компьютером базовый уровень выше. Пожалуйста, включите код, который подтверждает, что существует уникальное решение для вашей сетки.

Ценится интересные фрагменты кода (например, для поиска пространства возможностей) и обсуждения того, как вы нашли свою сетку.

Список слов

Международный список слов Scrabble ранее был известен как SOWPODS и теперь называется Collins Scrabble Words (CSW). Он используется в большинстве стран (за исключением США). Мы предпочитаем использовать этот список, потому что он включает в себя британскую орфографию и, как правило, содержит значительно больше слов, чем список американских слов. Есть несколько редакций этого списка, которые немного отличаются. Вы можете найти различные версии этого списка, связанные из Википедии , на Github , в Корпусе естественных языков Питера Норвига и в других местах, часто называемые «SOWPODS».

Эта проблема очень чувствительна к широкому характеру выбора списка слов, но в меньшей степени к мелким деталям. Например, приведенный выше базовый пример работает с любым изданием CSW, но CHне входит в список слов американского скрэббла. В случае расхождений мы предпочитаем использовать CSW19, самую последнюю версию CSW. (Если мы используем этот список, который был выпущен в этом году, мы можем ожидать, что ответы на этот вопрос будут оставаться в силе дольше). Вы можете запросить этот список в интерактивном режиме на официальном сайте поиска слов Scrabble или загрузить его (как и предыдущую версию, CSW15) с биржи стека настольных и карточных игр или Reddit's r / scrabble .

Tldr : официальный список слов для этого задания доступен в виде простого текстового файла (279 496 слов, по одному на строку) на бирже стека настольных и карточных игр .

Дальнейшее обсуждение

Одна проблема, поднятая в раннем ответе и комментарии, состоит в том, почему существующие кроссворды (например, в Нью-Йорк Таймс) не отвечают на этот вопрос. В частности, рекорд по наименьшему количеству черных квадратов (и, следовательно, наибольшему количеству белых квадратов) для опубликованного кроссворда NYT уже является самой известной записью в кроссвордах. Почему мы не можем использовать сетку записи ? Есть несколько вопросов:

Многие из ответов в кроссвордах NYT не появляются в нашем списке слов. Например, сетка записей включает в себя PEPCID(название бренда), APASSAGETOINDIA(собственное имя из четырех слов для фильма и романа, написанное без пробелов) и STE(сокращение от «Sainte»). Похоже, что сетка записи не разрешима словами Scrabble.
Простое расширение списка слов для включения большего количества слов не обязательно поможет с этой проблемой: даже если бы все слова в сетке записей появились в нашем списке слов, решение не было бы уникальным без подсказок. Часто можно изменить некоторые буквы в конце ответов, сохраняя все слова. (Например, крайнюю правую нижнюю букву можно изменить с a Dна R.) Действительно, это часть (человеческого) процесса построения при написании кроссворда, пытающегося получить «лучшие» слова.

Причина, по которой обычные кроссворды (как правило) имеют уникальное решение, заключается в том, что подсказки помогают сузить правильные ответы. Если вы просто попытаетесь заполнить сетку словами, не используя подсказки, вполне вероятно, что либо не будет никаких возможностей, либо будет много возможностей. Вот пример трех разных заливок (используя список слов для этой задачи!) Для одной и той же сетки (тот, который относительно часто используется в Нью-Йорк Таймсе):

Другая проблема, поднятая в комментариях, - это некоторое недоверие к тому, что этот вопрос является проблемой кодирования . Возможно, это не сразу понятно, но трудно даже найти хоть один верный ответ на этот вызов . Для определения вышеуказанного базового уровня потребовалось несколько специально созданных программ поиска, которые не гарантировали, что найдут ответ. Лично я даже не знаю общего способа решения произвольной сетки, если вы хотите получить ответ в разумные сроки. Существующие программы построения кроссвордов могут помочь, но я предполагаю (возможно, неправильно), что они на самом деле не выполняют полный поиск возможностей. (Я использовал такую программу для трех соседних сеток выше; это работало, потому что эта конкретная сетка допускает множество решений.)

code-challenge optimization crossword А. Рекс
источник

Мета пост, связанный с этим общим типом вопросов: codegolf.meta.stackexchange.com/questions/18117/…

А. Рекс

1. Отбросьте эстетическую опцию ("

Grids with fewer white squares may also be interesting for reasons other than their score, for example if they satisfy some of the aesthetic traditions mentioned above.

") - подобно тому, как избегать бонусов в гольф-коде, я бы предпочел, чтобы вызов кода был только одной вещью. Это означает, что все ответы можно сравнивать как для лайков. Это также делает его явно объективным, что поможет с возобновлением голосования.

Трихоплакс

2. Выберите один список слов и настаивайте на нем для всех ответов. В tldr упоминается авторский список слов, но предварительное обсуждение может привести людей к мысли, что они могут выбрать любой из упомянутых. Это может помочь сохранить строгие требования в верхней части поста и прояснить, что другие детали не являются частью спецификации задачи. В идеале, опускать что-либо лишнее в спецификации, чтобы пост был коротким и сразу однозначным.

Трихоплакс

3. Сделайте включение кода, используемого для нахождения решения, требованием для правильного ответа.

Трихоплакс

Это своего рода вызов, который может быть полезен в чате для обсуждения подходов. Если вы настроили чат-комнату и сделали ссылку на нее в конце спецификации, вы можете опубликовать обсуждение там в качестве начальных сообщений и упомянуть об этом в конкурсе для людей, которые хотят узнать больше.

Трихоплакс

180 белых квадратов

Моя стратегия состояла в том, чтобы просто найти меньший прямоугольник без черных квадратов, чтобы его можно было заполнить уникальным образом. Все 2×kпрямоугольники имеют несколько решений. Для 3×kпрямоугольников существует несколько решений kот 3 до 14, но существует ровно одно решение для k=15.

Затем я помещаю 4 таких прямоугольника в сетку. Это означает, что каждое слово встречается в решении 4 раза, что обычно встречается в построении кроссвордов, но это нормально для этой задачи. С другой стороны, это решение имеет симметрию слева / справа и сверху / вниз!

Машиночитаемая сетка:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES

Вот код R, который я использовал, чтобы найти все решения для данного размера сетки. Перебирать все тройки 15-буквенных слов слишком медленно. Вместо этого я пытаюсь заполнить прямоугольники

установка первых двух столбцов (два трехбуквенных слова)
затем перебирая все 15-буквенные слова, начиная с первых двух букв, которые теперь установлены.
для каждого возможного выбора 15-буквенных слов я проверяю, все ли сгенерированные 3-буквенные слова присутствуют в словаре.

Например, для окончательного решения, код первого положить в HOPи EVO, затем завершается в HETERNORMATIVE, OVEROPINIONATEDи POSSESSEDNESSES, наконец , проверить все 3- х букв ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS, VEE, EDS).

Код R

library(fastmatch)
f = "scrabble-wordlist.txt"
d = read.table(f, skip=2, as.is=T, na.strings=NULL)

d$l = apply(d, 2, nchar)
d3 = d[d$l==3, 1]

sp = function(s) strsplit(s, "")[[1]]
cm = function(v) paste0(v, collapse="")
d3s = sapply(d3, sp)

f3 = function(l){
  m = matrix("", 3, l)

  md = sapply(d[d$l == l, 1], sp)
  nf = 0

  a1 = seq(1, 3*l, by=3); a2 = a1 + 1; a3 = a1 + 2

  for(i in 1:ncol(d3s)){
    m[, 1] = d3s[, i]

    id1 = as.matrix(md[, md[1, ] == m[1, 1]])
    id2 = as.matrix(md[, md[1, ] == m[2, 1]])
    id3 = as.matrix(md[, md[1, ] == m[3, 1]])

    if(any(ncol(id1) == 0, ncol(id2) == 0, ncol(id3) == 0)) next

    for(j in 1:ncol(d3s)){
      m[, 2] = d3s[, j]

      jd1 = as.matrix(id1[, id1[2, ] == m[1, 2]])
      jd2 = as.matrix(id2[, id2[2, ] == m[2, 2]])
      jd3 = as.matrix(id3[, id3[2, ] == m[3, 2]])

      if(any(ncol(jd1) == 0, ncol(jd2) == 0, ncol(jd3) == 0)) next

      for(k1 in 1:ncol(jd1)){
        m[1, ] = jd1[, k1]

        for(k2 in 1:ncol(jd2)){
          m[2, ] = jd2[, k2]

          for(k3 in 1:ncol(jd3)){
            m[3, ] = jd3[, k3]

            w = paste0(m[a1], m[a2], m[a3])
            if(all(w %fin% d3)){
              nf = nf + 1
              print(m)
            }
            if(nf >= 2){
              print(c(l, nf))
              return()
            }
          }
        }
      }
    }
  }

  return(nf)
}

Называется как f3(15). Заняло несколько часов на моем персональном компьютере.

Робин Райдер
источник

@ downvoter Не могли бы вы прокомментировать?

Робин Райдер

Мой ответ также был отклонен. 🤷

А. Рекс

Создайте уникально разрешимый кроссворд ... без подсказок

Соревнование

Решения по строительству сетки

Это вообще возможно?

Ваше решение

Список слов

Дальнейшее обсуждение

Ответы:

180 белых квадратов

Код R

182 белых квадрата