Po katastrofalnej przejażdżce kajakiem spadłeś z wodospadu na końcu rzeki. Twoje kajak eksplodowało, ale udało ci się przetrwać eksplozję. Jednak twoja podróż po rzece zbiegła całkowicie z mapy - teraz zagubiłeś się w środku lasu. Na szczęście nadal masz umiejętności programistyczne, więc zdecydujesz się wyrzeźbić program na boku drzewa, aby pomóc ci znaleźć drogę przez las. Jednak na drzewie nie ma zbyt dużej powierzchni, więc program musi być możliwie jak najkrótszy.

W lesie można opisać jako no n( n > 5) kwadratu znaków, które składają się wyłącznie z małych liter a-z. Przykładowy las:

anehcienwlndm
baneiryeivown
bnabncmxlriru
anhahirrnrauc
riwuafuvocvnc
riwnbaueibnxz
hyirorairener
ruwiiwuauawoe
qnnvcizdaiehr
iefyioeorauvi
quoeuroenraib
cuivoaisdfuae
efoiebnxmcsua

Być może zauważyłeś, że w tym lesie abiegnie przez niego przekątna znaków od lewego górnego rogu do prawego dolnego rogu. Jest to „ścieżka” prowadząca przez las, która poprowadzi cię gdzieś, jeśli będziesz podążać. Twoim zadaniem jest napisanie programu, który znajdzie pojedynczą ścieżkę. Teraz bardziej szczegółowo opiszę, co oznacza „ścieżkę” w tym wyzwaniu.

„Ścieżka” w tym wyzwaniu jest definiowana jako linia podobna do linii, która mogła zostać wygenerowana za pomocą algorytmu Bresenham , ale z dodatkowymi wymaganiami, które:

• Linia musi mieć co najmniej 6 znaków
• Każda współliniowa (całkowicie przylegająca) grupa znaków w linii musi mieć tę samą długość .
• Zacznie się na jednym skraju lasu, a skończy na przeciwległym brzegu (patrz mój komentarz tutaj w celu opracowania)

Aby jaśniej wyjaśnić drugie wymaganie, rozważ następującą linię:

aaa
   aaa
      aaa
         aaa
            aaa

Ta linia składa się z kolinearnych „segmentów” znaków, z których każdy ma dokładnie trzy znaki. To kwalifikuje się jako ścieżka. Teraz rozważ tę linię:

a
 aa
   a
    aa
      a
       aa

Ta linia składa się z kolinearnych „segmentów”, które nie są dokładnie tej samej długości znaków (niektóre z nich mają długość 1 znaku, a niektóre 2). Zatem ten nie kwalifikuje się jako ścieżka.

Twój program, mając mapę lasu, identyfikuje znaki użyte na ścieżce. Dane wejściowe są do wszystkiego, co jest dogodne (np. Argument wiersza poleceń, STDIN prompt()itp.). Nie można go wstępnie zainicjować w zmienną. Pierwsza część danych wejściowych to pojedyncza liczba całkowita nreprezentująca rozmiar lasu (las jest zawsze kwadratem). Potem jest spacja, a potem cały las jako pojedynczy ciąg. Na przykład przykładowy las zostałby przedstawiony jako dane wejściowe w następujący sposób:

13  anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua

Dane wyjściowe dla tego będą:

a

ponieważ ścieżka jest tworzona za pomocą litery a. W lesie będzie tylko jedna ścieżka. To jest kod golfowy, więc wygrywa najmniejsza liczba znaków. Jeśli masz pytania, zapytaj w komentarzach.

APL (Dyalog 14) (70)

⎕ML←3⋄Z/⍨1=≢¨Z←∪¨(↓⍉F),(↓F),{(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F←⊃{⍵⍴⍨2/⍎⍺}/I⊂⍨' '≠I←⍞

Wyjaśnienie:

• ⎕ML←3: ustawiony MLna 3, co oznacza, że ⊂ma znaczenie APL2.
• I←⍞: przeczytaj wiersz z klawiatury i zapisz go I
• I⊂⍨' '≠I: podział Ina spacje
• {... }/: zastosuj tę funkcję do dwóch wynikowych ciągów:
  • 2/⍎⍺: oceń lewy argument i powtórz go dwukrotnie, podając rozmiar matrycy
  • ⍵⍴⍨: sformatuj odpowiedni argument, używając tego rozmiaru
• F←⊃: rozpakuj i zapisz F.
• {(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F: pobierz przekątne: z każdego wiersza zarówno ( jak Fi ⌽Flustrzane odbicie F), pobierz wartość w kolumnie X, gdzie X jest numerem wiersza
• (↓⍉F),(↓F),: pobierz wiersze i kolumny F
• Z←∪¨: znajdź unikalne wartości w każdym rzędzie, kolumnie i przekątnej i zapisz je Z.

Ponieważ „las” jest prostokątny, jeśli istnieje poprawna ścieżka, oznacza to, że jeden z nich będzie składał się tylko z jednego znaku, którym jest znak ścieżki, więc:

• Z/⍨1=≢¨Z: weź te podwarstwy, Zktóre mają tylko jeden element.

Spowoduje to wyświetlenie znaków dla wszystkich prawidłowych ścieżek, ale ponieważ powinien być tylko jeden, który nie ma znaczenia.

Lua - 506 380 - bajtów

Czułem się trochę źle, że nie otrzymałeś żadnego poddania się za dobrze przemyślane wyzwanie, więc rzuciłem to razem. Całkiem fajnie było wnioskować, jakie minimalne właściwości dające się wyróżnić na podstawie podanych informacji. Mam nadzieję, że dobrze to zrozumiałem ... I poprawnie go zaimplementowałem.

a=io.read"*l"n=a:match("%d+")+0 m=a:match"[a-z]+"o=""for i=1,n do for k=1,n^2,n do o=o..m:sub(i+k-1,i+k-1)end end q={m,o}for g=1,n^2 do for u=1,2 do l=q[u]:sub(g,g)for r=1,n do i=1 t=0 e=0 while i do s,e=q[u]:find(l:rep(r),e+1)if s then x=s-(e-s)-i-1 print(s,i,r,n,r)if x==n or x==n-2 or t==0 then t=t+1 i=s end else i=nil end end if t*r==n then print(l)os.exit()end end end end

Można to przetestować za pomocą:

lua divisorPath.lua "input"

Jeśli pojawi się dziki pretendent, sprawdzę, czy mój kod jest wart swojej ceny.

Aktualizacja : gra w golfa na cześć tych, którzy wzniosą się ponad nami. W tym czasie musiałem naprawić mój kod, aby rozpoznawał ścieżkę przechodzącą od prawej do lewej. Ups

MATLAB - 270 znaków

Poniżej zdefiniowano funkcję, xktóra akceptuje ciąg znaków lasu jako argument i zwraca znak reprezentujący prawidłową „ścieżkę” przez las zgodnie z podanymi regułami.

function F=x(s),A=sscanf(s,'%d%s');n=A(1);A=reshape(A(2:end),n,n);for c=A(:)',B=A==c;for i=1:n,if~mod(n,i),C=[kron(eye(i),ones(n/i,1)),zeros(n,n-i)];for j=0:n-i,f=@(B)sum(sum(B&circshift(C,[0,j]))==n;D=fliplr(B);if f(B)|f(B')|f(D)|f(D'),F=char(c);end;end;end;end;end;end

Wersja niezminimalizowana to

function F = x(s)
    A = sscanf( s, '%d %s' );
    n = A(1);
    A = reshape( A(2:end), n,n );
    for c = A(:)'
        B = A==c;
        for i = 1:n
            if ~mod( n, i )
                C = [kron( eye(i), ones( n/i,1 ) ), zeros( n,n-i )];
                for j = 0:n-i
                    f = @(B) sum(sum( B & circshift( C, [0 j] ))) == n;
                    D = fliplr(B);
                    if f(B) | f(B') | f(D) | f(D')
                        F = char(c);
                    end
                end
            end
        end
    end
end

Podstawowym założeniem jest zbudowanie maski logicznej dla każdej możliwej prawidłowej ścieżki i zwrócenie dowolnego znaku, którego funkcja indeksu w macierzy obejmuje dowolną maskę. Aby to osiągnąć, tworzone są tylko pionowe lub od góry do dołu maski w kształcie ukośnika, ale matryca lasu jest porównywana we wszystkich czterech orientacjach: tożsamość, odwrócony, obrócony o 90 °, odwrócony obrócony o 90 °.

Funkcja działa dla każdego n. Przykładem wywołania go w wierszu poleceń jest

x('13 anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua')

ans =

    a

Python - 384 325 275

Ten algorytm zasadniczo sprawdza pierwszy i ostatni wiersz macierzy pod kątem pasujących znaków, a następnie oblicza długość każdego segmentu linii

012345
------
aaVaaa|0
aaVaaa|1
aaaVaa|2
aaaVaa|3
aaaaVa|4
aaaaVa|5

W powyższym przykładzie:
V w pierwszym rzędzie ma indeks 2, V w ostatnim rzędzie ma indeks 4.
Zatem długość każdego segmentu linii wynosiłaby n / (4-2) +1 = 2 przy n = 6 .

Następnie sprawdza, czy linia jest poprawna.

Aby znaleźć ścieżkę od lewej do prawej, zamienia wiersze z kolumnami i robi to samo ponownie.

Edycja: Nie mogę dostać się do 270 (Cholera, Python i twoje cholerne wcięcie !!)

n,m=raw_input().split()
n,r=int(n),range
t=r(n)
a=[m[i:i+n]for i in r(0,n*n,n)]
for v in a,["".join([a[i][j]for i in t])for j in t]:
 for i in t:
  for j in t:
   p=1-2*(j-i<0);d,c=p*(j-i)+1,v[0][i]
   if 6<=sum([v[z][i+(z/(n/d))*p*(n%d==0)]==c for z in t])==n:print c;exit()