Wprowadzenie

Po dniu spędzonym na piciu i oglądaniu mistrzostw świata możesz usiąść i zagrać w przyjazną grę boggle. Temperament rośnie, gdy jesteś oskarżany o marnowanie czasu na bzdury słowami, których nawet nie ma na tablicy! Być może widzisz podwójnie, ale na pewno myślisz wystarczająco prosto, aby napisać program, który sprawdzi, czy twoje słowa są na tablicy.

Twoje zadanie

Napisz program, skrypt lub funkcję, która pobiera tablicę manipulacyjną i słowo jako dane wejściowe i zwraca True, jeśli słowo znajduje się na tablicy, i False, jeśli słowo nie jest.

Dane wejściowe będą miały postać sześciu \noddzielonych linii. Pierwsze pięć wierszy będzie zawierać tablicę boggle 5x5 i każda będzie zawierać pięć wielkich liter. Szósty wiersz będzie zawierał słowo, o którym mowa, również wielkimi literami.

Przykładowe dane wejściowe:

AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER

Wynikiem może być wszystko, co jednoznacznie oznacza Prawdę lub Fałsz w wybranym języku programowania i jest zgodne ze standardowymi konwencjami zero, zero i puste, oznaczające fałsz.

Przykładowe dane wyjściowe dla powyższego wejścia:

1

Wytyczne I / O

• Dane wejściowe można odczytać ze standardowego wejścia, a odpowiedź na standardowe wyjście.

Lub

• Dane wejściowe mogą być argumentem pojedynczego ciągu funkcji, a odpowiedzią może być wartość zwracana przez tę funkcję.

Zasady Boggle

• Słowo jest „na planszy”, jeśli możesz je zbudować ścieżką kolejnych, sąsiadujących ze sobą, powtarzających się kafelków na planszy.
• Płytkę uważa się za sąsiadującą z ośmioma otaczającymi ją płytkami (dozwolone są ścieżki diagonalne). Płytki na krawędzi planszy sąsiadują tylko z pięcioma płytkami. Płytki w rogu sąsiadują tylko z trzema.
• Kolejne litery w słowie muszą przylegać, ilitera w słowie musi przylegać do i-1th i i+1th.
• Litera może pojawić się w słowie więcej niż jeden raz, ale nie możesz użyć tego samego kwadratu na tablicy rozdzielczej więcej niż raz na słowo.
• Internetowa witryna boggle wordsplay.net może być przydatna, jeśli nigdy wcześniej nie grałeś w boggle, ale chcesz poznać te zasady.

W przeciwieństwie do zwykłego bagna:

• NIE musisz się martwić, że słowo jest poprawnym słowem angielskim.
• Nie będzie ŻADNEJ Qupojedynczej płytki.
• To pytanie może mieć dowolną długość> 0

Przykład

Na pokładzie

AJNES
TNFTR
LSAIL
UDNEX
EQGMM

Te słowa powinny zwrócić wartość Prawda: Los, randki, postacie, windy.

Te słowa powinny zwracać wartość False: SADDEN, SULTANS, EXIST, SUEDE, QUEST

To wyzwanie dla golfa, więc wygrywa najkrótszy kod!

GolfScript, 74 znaki

:^n%5>)]){{^@==}+29,\,{{+}+1$/}%\;}/{:s$..&=[s{.@-\}*;]1567`{7&.~)}%-!&},,

Dane wejściowe należy podać na STDIN. Drukuje liczbę prawidłowych ścieżek na tablicy, tj. 0Dla żadnej i liczby dodatniej (prawda) w innym przypadku.

Możesz przetestować przykład online .

Kod z kilkoma komentarzami:

:^              # assign the input to variable ^
n%              # split at newlines
5>              # truncate array such that [WORD] remains
)])             # prepares [[]] and WORD on the stack

# the following loop generates all possible paths (valid and invalid ones)
# by looking up all index combinations which yield the correct word
{               # loop over all characters
  {^@==}+29,\,  # get all indices of current character in the board
  {{+}+1$/}%\;  # append any index to all lists in the result set
}/              # end loop

# filter the results list for valid paths
{               # {...}, -> apply filter
  :s            # save path to variable s
  $..&=         # check if all numbers in path are unique
  [s{.@-\}*;]   # calculate differences along the path
  1567`{7&.~)}% # generate the array [1 -1 5 -5 6 -6 7 -7] of valid
                # differences
  -!            # check if all differences were valid
  &             # are both conditions fulfilled?
},              # end of filter block

,               # count the number of remaining paths

JavaScript (E6) 137 160 175 190

Mniej niż 2 * skrypt golfowy. Moralne zwycięstwo ...

F=a=>[...a].some((e,p,b)=>(Q=(p,n)=>p>29||b[p]!=b[n]||(b.r|=!b[++n])||(b[p]=b[n+~[1,5,6,7].map(q=>Q(p+q,n)|Q(p-q,n),b[p]=0)]))(p,30)&b.r)

Edytuj reorganizację kodu Golfed. Znowu i znowu

Ungolfed Ostatnia wersja, nieco trudna do naśladowania

F = a => 
  [...a] // input string to array, 30 chars of board then the target word
  .some ( // use some to scan the board, return true when found
      (e,p,b)=> // params to callback: element, position, complete array 
      (         // NB array b has no .r property, so use it for return value (it's undefined at start) 
        Q = (p,n) =>         // Scan function, p=position in board, n=nth char of target word
          p > 29 ||          // Chaek if going outside the board to the target word
          b[p] != b[n] ||    // if invalid char at current position, return
          (b.r |= !b[++n]) ||  // if at end of target, set r to 1 and return (also increment n )
          (                  // else... (NB next tree lines are coalesced in golfed code)
            b[p] = 0,        // remove current char (to avoid reusing) 
            [1,5,6,7].map( q => Q(p+q,n)|Q(p-q,n)), // recursive call for + - 1,5,6,7
            b[p] = b[n-1]    // put current char into array again 
          )
      )(p,30) & b.r // initial position 0 in target word is 30 in the array
  ) 

Ungolfed Pierwsza wersja powinna być jaśniejsza

F = a => (
  b = a.split('\n'),
  w = b.pop(),
  r = 0,
  Q = (p, n) => 
    (r |= !w[n]) || 
    (
      b[p] = 0,
      [1,5,6,7,-1,-5,-6,-7].map( q => b[q+=p]==w[n] && Q(q,n+1)),
      b[p] = w[n-1]
    ),
  b = [...b+''],
  b.map((e, p) => e==w[0] && Q(p,1)),
  r
)

Stosowanie

F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\nLIFTS\nDAFTER")

Test

['DAFTER', 'STANDS', 'LIFTS', 'FATE', 'DATING' ,
 'SADDEN','SULTANS', 'EXIST', 'SUEDE', 'QUEST']
.map(w => [w, F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\n" +w)])

Wydajność:

[["DAFTER", true], ["STANDS", true], ["LIFTS", true], ["FATE", true], ["DATING", true], 
["SADDEN", false], ["SULTANS", false], ["EXIST", false], ["SUEDE", false], ["QUEST", false]]

Python, 207 204 203

g=raw_input
r=range
b=''.join(g()for _ in r(5))
w=g()
s=lambda b,w,i:0<=i<25and(not w or(b[i]==w[0])*any(s(b[:i]+'_'+b[i+1:],w[1:],i+j+k*5-6)for j in r(3)for k in r(3)))
print any(s(b,w,i)for i in r(25))

Zastąpienie ... (b[i]==w[0])*any ...przez ... b[i]==w[0]and any ...daje znacznie lepszą wydajność kosztem 2 znaków.

J - 75 znaków

Eugh, ten wygląda paskudnie. I nawet nie wiąże się z Golfscript! Jest to funkcja przyjmująca ciąg jako jedyny argument. Możesz użyć dowolnego jednoznakowego separatora, o ile znajduje się on na końcu każdej linii, w tym ostatniej.

+/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)

Wyjaśnienie następuje. Zauważ, że funkcję można rozdzielić na 5 odrębnych części najwyższego poziomu, z których każda jest oddzielona @, więc każdą z tych części będziemy traktować osobno, od prawej do lewej.

• (<;._2)- To dzieli linie na znaki nowego wiersza / separatora. Używa znaku na końcu łańcucha jako znaku, na którym ma się rozdzielić. Umieszczamy wszystko w boxach ( <), ponieważ jeśli nie dostaniemy problemów z dopełnianiem, gdy J zwróci nam wynik.

• (((<@#:i.)5 5)<@#~&,"2{:=/&:>}:) - Dla każdej litery w słowie do sprawdzenia utwórz listę wskaźników na tablicy Boggle, w której można znaleźć tę literę.

  • {:jest ostatnim podzielonym elementem (słowem do sprawdzenia) i }:jest wszystkim oprócz ostatniego (plansza Boggle).

  • &:>otwiera skrzynki, które wcześniej stworzyliśmy, z użytecznym produktem ubocznym przekształcania }:się w szereg znaków 2D. =/następnie tworzy kopię tej planszy Boggle dla każdej litery w słowie i zamienia pozycje w logiczne w zależności od tego, czy litera na planszy pasuje do tej litery w słowie.

  • ((<@#:i.)5 5)to krótki sposób wyrażenia tablicy wskaźników 5x5. x#:yjest konwertowany yna tablicę xreprezentacji podstawowej . (Cóż, prawie. Prawda jest bardziej złożona, ale działa to na nasze cele.)

  • <@#~&,"2- Dla wynikowej macierzy boolowskiej każdej litery zbierz razem wszystkie odpowiednio prawdziwe wskaźniki. "2sprawia, że ​​wszystko działa na właściwe wyniki, #~&,dokonuje wyboru i <@gromadzi każdy wynik w polu, aby przygotować się do następnego kroku.

• {- Ten czasownik, używany monadycznie, nazywa się Katalog i przyjmuje jako argument listę pól. Łączy wnętrze każdego pudełka na wszystkie możliwe sposoby. Tak więc np. Katalog niektórych pól zawierający ciągi „AB” i „abc” dałby wyniki „Aa”, „Ab”, „Ac”, „Ba”, „Bb”, „Bc”.

  Uruchomienie tego na naszej pudełkowej liście list indeksów tworzy każdą możliwą kombinację indeksów. Może to być duży zestaw, jeśli słowo jest długie i jest wiele powtarzających się liter, ale także puste, jeśli żadnej litery nie ma na planszy. Zauważamy również, że ponownie wykorzystujemy kafelki w niektórych z tych ścieżek: wyjaśnimy to później.

• ([:*/"1^:2(2(=*)@-/\>@~.)S:1) - Tutaj sprawdzamy każdą ścieżkę, aby sprawdzić, czy jest poprawna.

  • (...)S:1stosuje (...)każdą ścieżkę i zbiera wyniki do płaskiej listy. Jest to kluczowe, ponieważ wynikiem {jest tablica wielowymiarowa, a my nie dbamy o strukturę tej tablicy, tylko jej zawartość w każdym pudełku.

  • 2(=*)@-/\>daje 1, jeśli każda współrzędna każdego indeksu znajduje się co najwyżej jeden od następnego, a 0 w przeciwnym razie. 2I /\są odpowiedzialne za robienie tego parami.

  • */"1^:2logiczne-I to wszystko na końcu. Ta [:część jest strukturalną rzeczą w J, nie martw się o to.

  • Dodanie @~.do >jest w rzeczywistości sprytnym sposobem na wykluczenie ścieżek z powtarzającymi się wpisami. ~.pobiera unikalne elementy listy, więc lista jest skracana, jeśli się przecina, a krótsze listy są automatycznie uzupełniane zerami po ich złożeniu, podobnie jak sposób łączenia wyników, gdy wychodzą S:. Jest to ostatecznie krótsze niż jednoznaczne wykluczenie przecinających się ścieżek.

• +/- Na koniec po prostu dodajemy wszystko razem na końcu. Wynikiem jest liczba prawidłowych ścieżek tworzących słowo na tablicy, przy czym 0 oznacza brak ścieżek, tzn. Tego słowa nie ma na tablicy. Za koszt jednego znaku możemy +./zamiast tego napisać (logiczne ORowanie wszystkiego razem), co wyraźnie da wartość logiczną 1 lub 0.

Oto kilka przykładowych przebiegów. Można dostać tłumacza J w jsoftware.com lub spróbować go online na tryj.tk .

   NB. the  0 : 0 ... )  thing is how you do multiline strings in J
   +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2) 0 : 0
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER
)
1
   b =: +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)
   b 'AJNES TNFTR LSAIL UDNEX EQGMM FATE '    NB. any separator will do
1
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SADDEN '  NB. not on the board
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SANDS '   NB. self-intersecting path
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM MEND '    NB. multiple paths
2

Prolog - 315

r(L):-get_char(C),(C='\n',!,L=[];r(T),L=[C|T]).
b(0,[]):-!.
b(N,[R|T]):-M is N-1,r(R),b(M,T).
d(-1). d(0). d(1).
d([A,B],[C,D]):-d(X),C is A+X,d(Y),D is B+Y.
f([L|W],B,P,U):-P=[X,Y],nth(Y,B,R),nth(X,R,L),\+member(P,U),(W=[];d(P,Q),f(W,B,Q,[P|U])).
m:-b(5,B),r(W),f(W,B,_,[]),write(t);write(f).
:-initialization(m).

Myślałem, że Prolog może być dobrym językiem dla tego, z wbudowaną obsługą cofania, ale myślę, że jest to bardziej upośledzone, ponieważ potrzebuje zmiennej dla prawie każdej obliczonej wartości.

Testowane z GNU Prolog; powinien być zgodny z ISO Prolog.

Nie golfowany:

get_line(Line) :-
    get_char(C),
    (   C='\n', !, Line=[]
    ;   get_line(Tail), Line=[C|Tail]
    ).

% The cut prevents recursion to help_get_board(-1, MoreRows)
% (and golfs one character shorter than putting N>0 in the second rule).
help_get_board(0, []) :- !.
help_get_board(N, [Row|Tail]) :-
    M is N-1, get_line(Row), help_get_board(M, Tail).

% The golfed version doesn't define an equivalent to get_board/1.
% help_get_board(5,Board) is used directly instead.
get_board(Board) :- help_get_board(5,Board).

small(-1). small(0). small(1).
step([X1,Y1],[X2,Y2]) :-
    small(DX), X2 is X1+DX,
    small(DY), Y2 is Y1+DY.

% The golfed version doesn't define an equivalent to letter_at/3.
% See find_word/4.
letter_at([X,Y], Letter, Board) :-
    nth(Y, Board, Row),
    nth(X, Row, Letter).

find_word([Letter|Word], Board, Pos1, Used) :-
%    letter_at(Pos1, Letter, Board),  % "inlined" to next three lines:
    ( Pos1 = [X,Y],
      nth(Y, Board, Row),
      nth(X, Row, Letter) ),
    \+member(Pos1, Used),
    (   Word=[]
    ;
        step(Pos1, Pos2),
        find_word(Word, Board, Pos2, [Pos1|Used])
    ).

main :-
    get_board(Board),
    get_line(Word),
    % Begin at any position. Initially no positions are "Used".
    find_word(Word, Board, _, []).