Napisz program, który narysuje 2-wymiarowy schemat węzła na podstawie jego struktury. Węzeł jest dokładnie tak, jak to brzmi: pętla liny, która jest związana. W matematyce schemat węzła pokazuje, gdzie kawałek liny przecina się nad lub pod sobą, tworząc węzeł. Niektóre przykładowe diagramy węzłów pokazano poniżej:

W linii przecina się lina.

Dane wejściowe: dane wejściowe opisujące węzeł to tablica liczb całkowitych. Węzeł, w którym lina przecina się n razy, może być reprezentowany jako tablica n liczb całkowitych, każda o wartości z zakresu [0, n-1]. Nazwijmy tę tablicę K. .

Aby uzyskać tablicę opisującą węzeł, numeruj każdy z segmentów od 0 do n-1. Odcinek 0 powinien prowadzić do odcinka 1, który powinien prowadzić do odcinka 2, który powinien prowadzić do odcinka 3 i tak dalej, dopóki odcinek n-1 nie zapętli się i nie dojdzie do odcinka 0. Segment kończy się, gdy przechodzi przez niego kolejny odcinek liny ( reprezentowane przez przerwanie linii na schemacie). Weźmy najprostszy węzeł - węzeł koniczyny. Po ponumerowaniu segmentów segment 0 kończy się, gdy segment 2 przechodzi nad nim; segment 1 kończy się, gdy segment 0 przechodzi nad nim; a segment 2 kończy się, gdy przecina go segment 1. Zatem tablica opisująca węzeł to [2, 0, 1]. Ogólnie segment x zaczyna się tam, gdzie segment , gdzie zakończył x-1 mod n , i kończy się, gdy przecina go segment K [x] .

Poniższy obrazek pokazuje schematy węzłów z oznaczonymi segmentami i odpowiednimi tablicami opisującymi węzeł.

Trzy górne schematy to prawdziwe węzły, a dolne trzy to pętle liny, które przecinają się, ale nie są tak naprawdę wiązane (ale nadal mają odpowiednie kody).

Twoim zadaniem jest napisanie funkcji, która pobiera tablicę liczb całkowitych K (można to nazwać czymś innym), która opisuje węzeł (lub pętlę liny, która nie jest faktycznie wiązana) i która generuje odpowiedni schemat węzłów, jak opisano powyżej przykłady Jeśli możesz, podaj niestosowną wersję kodu lub wyjaśnienie, a także podaj przykładowe wyniki swojego kodu. Ten sam węzeł może być często reprezentowany na wiele różnych sposobów, ale jeśli schemat węzła, który spełnia dane wyjściowe funkcji, zawiera dane wejściowe jako jedną z możliwych reprezentacji, rozwiązanie jest prawidłowe.

To jest golf golfowy, więc wygrywa najkrótszy kod w bajtach. Linia reprezentująca linę może mieć grubość 1 piksela, jednak pod i nad skrzyżowaniami należy wyraźnie odróżnić (rozmiar zerwania liny powinien być większy niż grubość liny o co najmniej piksel z każdej strony) .

Będę głosować za odpowiedziami, które opierają się na wbudowanych możliwościach teorii węzłów, ale ta, która ostatecznie została wybrana, nie może polegać na wbudowanych możliwościach teorii węzłów.

Wszystko, co wiem o mojej notacji: wierzę, że istnieją sekwencje wartości, które wydają się nie odpowiadać żadnemu węzłu lub rozłączeniu. Na przykład ciąg [2, 3, 4, 0, 1] wydaje się niemożliwy do narysowania.

Poza tym załóżmy, że bierzesz skrzyżowanie i zaczynając od tego skrzyżowania, podążaj ścieżką liny w jednym kierunku i oznaczaj każde nieznakowane przejście, które napotkasz, kolejnymi większymi wartościami całkowitymi. W przypadku naprzemiennych węzłów istnieje prosty algorytm do konwersji mojej notacji na takie etykietowanie, a w przypadku naprzemiennych węzłów banalne jest przekształcenie tego oznakowania w kod Gaussa:

template<size_t n> array<int, 2*n> LabelAlternatingKnot(array<int, n> end_at)
{
    array<int, n> end_of;
    for(int i=0;i<n;++i) end_of[end_at[i]] = i;
    array<int, 2*n> p;
    for(int& i : p) i = -1;
    int unique = 0;
    for(int i=0;i<n;i++)
    {
        if(p[2*i] < 0)
        {
            p[2*i] = unique;
            p[2*end_of[i] + 1] = unique;
            ++unique; 
        }
        if(p[2*i+1] < 0)
        {
            p[2*i+1] = unique;
            p[2*end_at[i]] = unique;
            ++unique;
        }
    }
    return p;
}
template<size_t n> auto GetGaussCode(array<int, n> end_at)
{
    auto crossings = LabelAlternatingKnot(end_at);
    for(int& i : crossings) ++i;
    for(int i=1;i<2*n;i+=2) crossings[i] = -crossings[i];
    return crossings;
}

GNU Prolog, 622 634 668 bajtów na stronie kodowej 850

Aktualizacja : poprzednia wersja programu czasami powodowała, że ​​przejścia były tak ciasne, że nie renderowały się poprawnie, co narusza specyfikację. Dodałem dodatkowy kod, aby temu zapobiec.

Aktualizacja : Najwyraźniej reguły PPCG wymagają dodatkowego kodu, aby program mógł wyjść i przywrócić stan dokładnie tak, jak na początku. To sprawia, że ​​program jest nieco dłuższy i nie dodaje do niego żadnych zainteresowań algorytmicznych, ale w celu zapewnienia zgodności z regułami zmieniłem go.

Program w golfa

Korzystanie z GNU Prolog, ponieważ ma składnię solvera ograniczającego, która jest nieco krótsza niż składnia arytmetyczna przenośnego Prologa, co pozwala zaoszczędzić kilka bajtów.

y(A,G):-A=1;A= -1;A=G;A is-G.
z(A/B,B,G):-y(A,G),y(B,G),A=\= -B.
v(D,E,G):-E=1,member(_-_,D),p(D);F#=E-1,nth(F,D,M),(M=[_];M=L-S/R,z(L,O,G),J is F+O,nth(J,D,I/U-T/Q),(I=O,Q#=R-1,S=T;K is J+O,R=0,n(S-T-V),y(U,G),U\=O,U=\= -O,I=U,nth(K,D,O/_-V/_))),v(D,F,G).
i([H|K],S):-K=[]->assertz(n(S-H-0));T#=S+1,assertz(n(S-H-T)),i(K,T).
t([],1,_):-!.
t(D,R,G):-S#=R-1,t(E,S,G),H#=G-1,length(F,H),append(F,[[x]|E],D).
s(1,2).
s(-1,1).
s(S,T):-S>1->T=3;T=0.
r(I/O-_,C):-s(I,J),s(O,P),N#=J*4+P+1,nth(N,"│┐┌?└─?┌┘?─┐?┘└│",C).
r([X],C):-X\=y->C=10;C=32.
p([]).
p([H|T]):-r(H,C),put_code(C),!,p(T).
g(4).
g(G):-g(H),G#=H+1.
m(K):-i(K,0),g(G),t(D,G,G),length(D,L),v(D,L,G),abolish(n/1).

Algorytm

Jest to jeden z tych problemów, w którym trudno jest wiedzieć, jak zacząć. Nie jest oczywiste, jak obliczyć kształt węzła na podstawie podanej notacji, ponieważ nie informuje on, czy masz zginać linię w lewo czy w prawo w danym miejscu (i jako taki notacja może być niejednoznaczna). Moje rozwiązanie polegało na wykorzystaniu starej gotowości do gry w golfa: napisz niesamowicie nieefektywny program, który generuje wszystkie możliwe dane wyjściowe, a następnie sprawdź, czy pasują do danych wejściowych. (Zastosowany tutaj algorytm jest nieco bardziej wydajny, ponieważ Prolog może od czasu do czasu wyrzucić ślepy zaułek, ale nie ma wystarczających informacji, aby poprawić złożoność obliczeniową).

Wyjście odbywa się za pomocą art. GNU Prolog wydaje się chcieć zestawu znaków jednobajtowych, który jest zgodny z ASCII, ale nie dba o to, który z nich zostanie użyty (ponieważ traktuje znaki z zestawem wysokich bitów jako nieprzezroczyste). W rezultacie użyłem IBM850, który jest szeroko obsługiwany i ma potrzebne nam znaki do rysowania linii.

Wydajność

Program przeszukuje wszystkie możliwe obrazy węzłów, w kolejności odpowiadającej wielkości ich obwiedni, a następnie kończy pracę, gdy znajdzie pierwszy. Oto, jak wygląda wynik m([0]).:

 ┌┐
┌│┘
└┘ 

Uruchomienie na moim komputerze zajęło 290,528 sekund; program nie jest zbyt wydajny. Zostawiłem go na dwie godziny m([0,1])i skończyłem z tym:

┌┐┌┐
└─│┘
 └┘ 

Wersja bez golfa z komentarzami

Podświetlacz składni Stack Exchange wydaje się mieć niewłaściwy symbol komentarza dla Prologa, więc zamiast %komentarzy (których faktycznie używa Prolog), to wyjaśnienie używa % #komentarzy (które są oczywiście równoważne ze względu na początek %, ale poprawnie podświetlone).

% # Representation of the drawing is: a list of:
% #     indelta/outdelta-segment/distance  (on path)
% # and [x] or [_]                         (off path; [x] for border).
% # A drawing is valid, and describes a knot, if the following apply
% # (where: d[X] is the Xth element of the drawing,
% #         k[S] is the Sth element of the input,
% #         n[S] is S + 1 modulo the number of sections):
% # d[X]=_/O-S-R, R>1 implies d[X+O]=O/_-S-(R-1)
% # d[X]=_/O-S-0 implies d[X+O]=_/_-k[S]-_
% #                  and d[X+O*2]=O/_-n[S]-_
% # all outdeltas are valid deltas (±1 row/column)

% # not technically necessary, but makes it possible to compile the
% # code (and thus makes the program faster to test):
:- dynamic([n/1]).

% # legal delta combinations:
y(A,G):-A=1;A= -1;              % # legal deltas are 1, -1,
        A=G;A is-G.             % # grid size, minus grid size
z(A/B,B,G):-y(A,G),y(B,G),      % # delta components are valid
            A=\= -B.            % # doesn't U-turn
% # z returns the outdelta for convenience (= byte savings) later on

% # We use v (verify) to verify the first E-1 elements of a drawing D.
% # nth is 1-indexed, so we recurse from length(D)+1 down to 2, with
% # 1 being the trivial base case. After verifying, the grid is printed.
% # This version of the program causes v to exit with success after
% # printing one grid (and uses p to do the work of deciding when that is).
v(D,E,G):-E=1,                  % # base case:
          member(_-_,D),        % # ensure the grid is nonempty
          p(D);                 % # print the grid (and exit)

                                % # otherwise, recursive case:
          F#=E-1,nth(F,D,M),    % # check the last unchecked element
          (
            M=[_];              % # either it's not on the path; or
            M=L-S/R,            % # it's structured correctly, and
            z(L,O,G),           % # it has a valid delta;
            J is F+O,           % # find the outdelta'd element index
            nth(J,D,I/U-T/Q),   % # and the outdelta'd element
            (
              I=O,Q#=R-1,S=T;   % # if not an endpoint, points to next pixel
              K is J+O,         % # else find segment beyond the path:
              R=0,              % # it's an endpoint,
              n(S-T-V),         % # it points to the correct segment,
              y(U,G),           % # ensure we can do NOT comparisons on U
              U\=O,U=\= -O,     % # the line we jump is at right angles
              I=U,              % # the line we jump is straight
              nth(K,D,O/_-V/_)  % # the pixel beyond has a correct indelta,
                                % # and it has the correct segment number
            )
          ),
          v(D,F,G).             % # recurse

% # We use i (init) to set up the k, n tables (k and n are fixed for
% # any run of the program, at least). S is the number of elements that
% # have been removed from K so far (initially 0). To save on characters,
% # we combine k and n into a single predicate n.
i([H|K],S):-K=[]->             % # if this is the last element,
            assertz(n(S-H-0)); % # section 0 comes after S;
            T#=S+1,            % # otherwise, add 1 to S,
            assertz(n(S-H-T)), % # that section comes after S,
            i(K,T).            % # and recurse.

% # We use t (template) to create a template drawing. First argument is
% # the drawing, second argument is the number of rows it has plus 1,
% # third argument is the number of columns it has plus 1.
t([],1,_):-!.
t(D,R,G):-S#=R-1,t(E,S,G),      % # recurse,
          H#=G-1,length(F,H),   % # F is most of this row of the grid
          append(F,[[x]|E],D).  % # form the grid with F + border + E

% # We use s (shrink) to map a coordinate into a value in the range 0, 1, 2, 3.
s(1,2).
s(-1,1).
s(S,T):-S>1->T=3;T=0.
% # We use r (representation) to map a grid cell to a character.
r(I/O-_,C):-s(I,J),s(O,P),N#=J*4+P+1,nth(N,"│┐┌?└─?┌┘?─┐?┘└│",C).
r([X],C):-X\=y->C=10;C=32.
% # We use p (print) to pretty-print a grid.
% # The base case allows us to exit after printing one knot.
p([]).
p([H|T]):-r(H,C),put_code(C),!,p(T).

% # We use g (gridsize) to generate grid sizes.
g(4).
g(G):-g(H),G#=H+1.

% # Main program.
m(K):-i(K,0),                  % # initialize n
      g(G),                    % # try all grid sizes
      t(D,G,G),                % # generate a square knot template, size G
      length(D,L),             % # find its length
      v(D,L,G),                % # verify and print one knot
      % # Technically, this doesn't verify the last element of L, but we know
      % # it's a border/newline, and thus can't be incorrect.
      abolish(n/1).            % # reset n for next run; required by PPCG rules