Czy potrafisz sobie wyobrazić rozwiązanie krzyżówki New York Times bez żadnych wskazówek? Może nie z całą kreatywnością, nowymi słowami i frazami pojawiającymi się we współczesnych krzyżówkach, ale z ustaloną listą słów jest trochę nadziei. W tym wyzwaniu tworzysz siatkę krzyżówek, w której jest to teoretycznie możliwe.

Wyzwanie

Zmaksymalizuj liczbę białych kwadratów na siatce krzyżówek 15 x 15 w odcieniach bieli i czerni, tak aby białe kwadraty można było wyjątkowo wypełnić literami, tak aby każde słowo w poprzek i w dół pojawiało się na międzynarodowej liście słów Scrabble.

Wyjaśnienia dotyczące budowy sieci

W gazetach amerykańskich siatki krzyżówek są zwykle skonstruowane w taki sposób, że każda litera jest „sprawdzana”, co oznacza, że ​​jest ona częścią zarówno słowa „w poprzek”, jak i „w dół”. W Wielkiej Brytanii i poza nią (szczególnie w przypadku tajemniczych krzyżówek ) niekoniecznie tak jest: jeśli słowo „w poprzek” lub „w dół” będzie tylko jedną literą, nie musi być rzeczywistym słowem (jak „A” lub „I „). W przypadku tego wyzwania postępuj zgodnie z bardziej swobodnymi zasadami: słowa jednoliterowe nie muszą pojawiać się na liście słów.

Istnieją różne inne tradycje (w Stanach Zjednoczonych i innych krajach), z których żadna nie musi być przestrzegana w tym wyzwaniu. Na przykład słowa mogą mieć tylko dwie litery, słowa mogą się powtarzać, a siatka nie musi mieć symetrii (rotacyjnej).

Czy to w ogóle możliwe?

Tak! Można napisać krótki skrypt, aby sprawdzić, czy unikalnym rozwiązaniem dla poniższej pustej siatki po lewej jest wypełniona siatka po prawej:

Można wyświetlić wypełnioną siatkę w formacie czytelnym dla komputera w następujący sposób:

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

Twoje rozwiązanie

Siatka powyżej ma 56 białych kwadratów z 225 kwadratów ogółem na siatce 15 x 15. Służy to za podstawę tego wyzwania. Siatki z mniejszą liczbą białych kwadratów mogą być również interesujące z powodów innych niż ich wynik, na przykład jeśli spełniają niektóre z wymienionych powyżej tradycji estetycznych.

Prześlij swoje rozwiązanie w tym samym formacie, co powyżej czytelna dla komputera linia bazowa. Podaj kod, który weryfikuje, że istnieje unikalne rozwiązanie dla Twojej sieci.

Doceniamy ciekawe fragmenty kodu (np. Do przeszukiwania przestrzeni możliwości) i dyskusję o tym, jak udało Ci się znaleźć swoją siatkę.

Lista słów

Międzynarodowa lista słów Scrabble była wcześniej znana jako SOWPODS i teraz nazywa się Collins Scrabble Words (CSW). Jest stosowany w większości krajów (z wyjątkiem w szczególności w Stanach Zjednoczonych). Wolimy korzystać z tej listy, ponieważ zawiera ona pisownię brytyjską i ogólnie zawiera znacznie więcej słów niż amerykańska lista słów. Istnieje wiele edycji tej listy, które różnią się nieznacznie. Różne wersje tej listy można znaleźć w Wikipedii , na Github , w Korpusie języka naturalnego Petera Norviga i innych, często nazywanym „SOWPODS”.

To wyzwanie jest bardzo wrażliwe na szeroki wybór listy słów, ale w mniejszym stopniu na mniejsze szczegóły. Na przykład powyższy przykład linii bazowej działa z dowolną edycją CSW, ale CHnie jest słowem na liście słów amerykańskiego Scrabble. W przypadku rozbieżności wolimy używać CSW19, najnowszej edycji CSW. (Jeśli skorzystamy z tej listy, która została wydana w tym roku, możemy spodziewać się, że odpowiedzi na to wyzwanie pozostaną ważne dłużej). Możesz interaktywnie przeszukać tę listę na oficjalnej stronie wyszukiwarki słów Scrabble lub pobrać ją (jak również poprzednie wydanie, CSW15) ze stosu gier planszowych i karcianych lub wymiany r / scrabble firmy Reddit .

Tldr : autorytatywna lista słów dla tego wyzwania jest dostępna jako zwykły plik tekstowy (279 496 słów, po jednym w wierszu) na giełdzie stosów gier planszowych i karcianych .

Dalsza dyskusja

Jednym z problemów poruszonych we wczesnej odpowiedzi i komentarzu jest to, dlaczego istniejące krzyżówki (np. W NYT) nie odpowiadają na to pytanie. Konkretnie, rekord najmniejszej liczby czarnych kwadratów (a tym samym największej liczby białych kwadratów) dla opublikowanej krzyżówki NYT jest już najbardziej znanym zapisem krzyżówek. Dlaczego nie możemy użyć siatki rekordów ? Istnieje kilka problemów:

• Wiele odpowiedzi w krzyżówkach NYT nie pojawia się na naszej liście słów. Na przykład siatka rekordów obejmuje PEPCID(markę), APASSAGETOINDIA(czterosłowową nazwę właściwą filmu i powieści, napisaną bez spacji) oraz STE(skrót do „Sainte”). Wygląda na to, że siatki zapisów nie da się rozwiązać za pomocą słów Scrabble.

• Samo poszerzenie listy słów o więcej słów niekoniecznie pomaga w tym wyzwaniu: nawet jeśli wszystkie słowa w siatce rekordów pojawią się na naszej liście słów, rozwiązanie nie byłoby unikalne bez wskazówek. Często można zmienić niektóre litery na końcu odpowiedzi, zachowując wszystko jednym słowem. (Na przykład prawą dolną prawą literę można zmienić z a Dna anR .) Rzeczywiście, jest to część (ludzkiego) procesu konstruowania, gdy pisze się krzyżówkę, próbując uzyskać „lepsze” słowa.

  Powodem, dla którego zwykłe krzyżówki mają (zazwyczaj) unikalne rozwiązanie, jest to, że wskazówki pomagają zawęzić prawidłowe odpowiedzi. Jeśli po prostu spróbujesz wypełnić siatkę słowami bez użycia wskazówek, prawdopodobnie nie będzie żadnych możliwości lub wielu możliwości. Oto przykład trzech różnych wypełnień (przy użyciu listy słów dla tego wyzwania!) Dla tej samej siatki (tej, która jest stosunkowo często używana w NYT):

• Kolejną kwestią poruszoną w komentarzach jest niedowierzanie, że to pytanie stanowi wyzwanie kodowania . Być może nie jest to od razu jasne, ale trudno jest nawet znaleźć jedną prawidłową odpowiedź na to wyzwanie . Znalezienie powyższej linii bazowej wymagało wielu specjalnie spreparowanych programów wyszukiwania, które nie miały gwarancji znalezienia odpowiedzi. Nawet osobiście nie znam ogólnego sposobu rozwiązania arbitralnej siatki, jeśli chcesz uzyskać odpowiedź w rozsądnym czasie. Istniejące programy do budowy krzyżówek mogą pomóc, ale zakładam (być może niepoprawnie), że tak naprawdę nie przeprowadzają pełnego poszukiwania możliwości. (Użyłem takiego programu dla trzech powyższych siatek obok siebie; działało to, ponieważ ta konkretna siatka pozwala na wiele rozwiązań).

180 białych kwadratów

Moją strategią było po prostu znalezienie mniejszego prostokąta bez czarnych kwadratów, tak aby można go było wypełnić w unikalny sposób. Wszystkie 2×kprostokąty mają wiele rozwiązań. W przypadku 3×kprostokątów istnieje wiele rozwiązań dla kprzedziału od 3 do 14, ale istnieje dokładnie jedno rozwiązanie k=15.

Następnie dopasowuję 4 takie prostokąty do siatki. Oznacza to, że każde słowo pojawia się 4 razy w rozwiązaniu, co zwykle budzi grymas w krzyżówce, ale OK na to wyzwanie. Z drugiej strony to rozwiązanie ma symetrię zarówno lewą / prawą, jak i górną / dolną!

Siatka czytelna dla komputera:

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

Oto kod R, którego użyłem do znalezienia wszystkich rozwiązań dla danego rozmiaru siatki. Pętla wszystkich trzech 15-literowych słów jest zbyt wolna. Zamiast tego staram się wypełnić prostokątami

• ustawianie pierwszych dwóch kolumn (dwa trzyliterowe słowa)
• następnie przeglądając wszystkie 15-literowe słowa, zaczynając od pierwszych dwóch liter, które są już ustalone.
• dla każdego możliwego wyboru 15-literowych słów sprawdzam, czy wszystkie wygenerowane 3-literowe słowa znajdują się w słowniku.

Na przykład, do ostatecznego roztworu kod najpierw umieścić w HOPi EVO, po czym zakończono w HETERNORMATIVE, OVEROPINIONATEDi POSSESSEDNESSES, a na końcu zweryfikowane wszystkie 3 litery słowa ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS,VEE , EDS).

Kod 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)
}

Nazywany jako f3(15). Trwało kilka godzin na moim komputerze osobistym.

182 białe kwadraty

Zainspirowany przez Robina Rydera próbowałem wcisnąć jeszcze kilka białych kwadratów. Uważam, że to rozwiązanie jest wyjątkowe i wkrótce opublikuję odpowiednio kod weryfikacyjny.

Siatka czytelna dla komputera:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS