Word Search Solver

13

Wczoraj zacząłem się zastanawiać, czy mógłbym napisać program, który przeczesuje dane słowo i wyszukuje odpowiedzi. To było naprawdę zaskakująco łatwe. Teraz zastanawiam się, jak małe możemy być.

Zasady

  • Twoje pierwsze wejście to ciąg lub kolekcja n linii, z których każda ma długość n znaków
  • Drugie wejście to lista słów w dowolnym formacie do znalezienia w układance
  • Gwarantujemy, że wszystkie słowa na liście wyszukiwania znajdują się w układance
  • Słowa mogą być zorientowane w dowolnym z czterech głównych kierunków, a także ukośnie, zarówno do przodu, jak i do tyłu
  • W układance będą obecne tylko wielkie litery AZ
  • Kod musi znaleźć każde słowo w ciągu wyszukiwania i podać współrzędne początkowej litery, gdzie 0,0 to lewy górny znak.
  • W przypadku zlokalizowania więcej niż jednego wystąpienia tego samego słowa możesz sobie z tym poradzić w dowolny sposób. Wydrukuj go wiele razy lub tylko raz, to zależy od Ciebie

Przykłady / przypadki testowe

Biorąc pod uwagę następującą tablicę:

ABCD
EFGH
IJKL
MNOP

I następujący ciąg wyszukiwania:

ABCD,CGKO,POMN,NJF,AFKP,CFI,LGB,MJGD

Twój program powinien wypisać następujące, w dowolnej kolejności:

ABCD at 0,0
CGKO at 0,2
PONM at 3,3
NJF at 3,1
AFKP at 0,0
CFI at 0,2
LGB at 2,3
MJGD at 3,0

Jak zawsze, najkrótsza odpowiedź wygrywa

morpen
źródło
6
Witamy w PPCG! Ładne pierwsze wyzwanie!
AdmBorkBork
2
Podobnie , jedyną prawdziwą różnicą wydaje się być włączenie lokalizacji do wyniku.
FryAmTheEggman
@ NL628 Tak, wszystkie wyszukiwane słowa znajdują się w układance. Jeśli wystąpi więcej niż jedno wystąpienie, możesz je wydrukować dwa razy lub zignorować za drugim razem, to zależy od ciebie.
morpen
@JathanathanAllan Świetny pomysł. Zaktualizuję to, jak zasugerowałeś.
morpen
1
@ RickHitchcock Tak, powinno być :)
morpen

Odpowiedzi:

4

JavaScript (Node.js) , 154 152 150 141 bajtów

  • dzięki Arnauldowi za zmniejszenie o 2 bajty

zwraca tablicę lokalizacji (wcześniej był to ciąg z nowymi liniami)

(b,w)=>w.map(s=>[...b].map((_,p)=>[1,-1,r=b.search`
`,-r,~r,++r,-~r,~r].map(d=>[...s].every((c,i)=>c==b[p+d*i])?s+=" at "+[p/r|0,p%r]:0))&&s)

Wypróbuj online!

DanielIndie
źródło
3

Python 2 , 213 bajtów

lambda a,W:[(w,i,j)for w in W for i in R(L(a))for j in R(L(a[0]))for U in R(9)if U-4and g(i,j,U/3-1,U%3-1,a).find(w)==0]
g=lambda i,j,u,v,a,s='':L(a)>i>=0<=j<L(a[0])and g(i+u,j+v,u,v,a,s+a[i][j])or s
L=len;R=range

Wypróbuj online!

gprzyjmuje położenie początkowe i,ji kierunek, u,va poprzez rekurencję wyodrębnia ciąg rozpoczynający się w tym miejscu w tym kierunku.

fnastępnie odwiedza każdą początkową lokalizację i,ji kierunek U/3-1,U%3-1oraz sprawdza każde słowo, waby sprawdzić, czy wynikowy ciąg zaczyna się od w.

Chas Brown
źródło
2

Python 3 , 149 147 bajtów

def g(b,w):h=b.find('\n')+1;return[f'{y} at {i//h},{i%h}'for y in w for i in range(len(b))for d in(1,h+1,h,h-1,-1,~h,-h,1-h)if y==b[i::d][:len(y)]]

Wypróbuj online!

Wersja bez golfa

def g(b,w):
    h = b.find('\n') + 1                              # width of a row plus the '\n'
    a = []
    for y in w:                                       # iterate over the words
        for i in range(len(b)):                       #   iterate over the game board
            for d in(1,h+1,h,h-1,-1,~h,-h,1-h):       #     for each possible direction
                if y==b[i::d][:len(y)]:               #       see if the word matches
                    a.append(f'{y} at {i//h},{i%h}')
    return a

Główną ideą jest b[i::d]wybranie wycinka z planszy. Plasterek zaczyna się od pozycji ii rozciąga w kierunku d. Na przykład d = h+1odpowiada południowo-wschodniej przekątnej, podczas gdy d = ~h, która jest taka sama jak -h-1, odpowiada północno-zachodniej przekątnej. [:len(y)] odcina plasterek na tej samej długości, co wyszukiwane słowo.

RootTwo
źródło