Escriba un programa para dibujar un diagrama 2D de un nudo basado en la estructura del nudo. Un nudo es exactamente lo que parece: un lazo de cuerda que está atado. En matemáticas, un diagrama de nudos muestra dónde un trozo de cuerda se cruza sobre o debajo de sí mismo para formar el nudo. A continuación se muestran algunos diagramas de nudos de ejemplo:

Hay una ruptura en la línea donde la cuerda se cruza sobre sí misma.

Entrada: la entrada que describe el nudo es una matriz de enteros. Un nudo donde la cuerda se cruza sobre sí misma n veces puede representarse como una matriz de n enteros, cada uno con un valor en el rango [0, n-1]. Vamos a llamar a esta matriz K .

Para obtener la matriz que describe un nudo, numere cada uno de los segmentos del 0 al n-1. El segmento 0 debería conducir al segmento 1, que debería conducir al segmento 2, que debería conducir al segmento 3, y así sucesivamente hasta que el segmento n-1 regrese y conduzca al segmento 0. Un segmento termina cuando otro segmento de cuerda lo cruza ( representado por un salto en la línea del diagrama). Tomemos el nudo más simple: el nudo trébol. Después de haber numerado los segmentos, el segmento 0 termina cuando el segmento 2 lo cruza; el segmento 1 termina cuando el segmento 0 lo cruza; y el segmento 2 termina cuando el segmento 1 cruza sobre él. Por lo tanto, la matriz que describe el nudo es [2, 0, 1]. En general, el segmento x comienza donde quedó el segmento x-1 mod n , y termina donde el segmento K [x] lo cruza.

La siguiente imagen muestra diagramas de nudos, con segmentos etiquetados y las matrices correspondientes que describen el nudo.

Los tres diagramas superiores son nudos verdaderos, mientras que los tres inferiores son bucles de cuerda que se cruzan sobre sí mismos pero que en realidad no están anudados (pero que todavía tienen los códigos correspondientes).

Su tarea es escribir una función que tome una matriz de enteros K (podría llamarse algo diferente) que describa un nudo (o lazo de cuerda que en realidad no está anudado), y que produzca el diagrama de nudos correspondiente, como se describe en el anterior ejemplos Si puede, proporcione una versión no codificada de su código o una explicación, y también proporcione resultados de muestra de su código. El mismo nudo a menudo se puede representar de múltiples maneras diferentes, pero si el diagrama de nudos que satisface su salida tiene la entrada como una de sus posibles representaciones, su solución es válida.

Este es el código de golf, por lo que gana el código más corto en bytes. La línea que representa la cuerda puede tener un grosor de 1 píxel, sin embargo, los cruces inferiores y superiores deben ser claramente distinguibles (el tamaño de la rotura de la cuerda debe ser mayor que el grosor de la cuerda en al menos un píxel a cada lado) .

Votaré las respuestas que se basan en las capacidades de la teoría de nudos incorporadas, pero la que se selecciona al final no puede confiar en las capacidades de la teoría de nudos incorporadas.

Todo lo que sé sobre mi notación: creo que hay secuencias de valores que no parecen corresponder a ningún nudo o nudo. Por ejemplo, la secuencia [2, 3, 4, 0, 1] parece ser imposible de dibujar.

Aparte de eso, suponga que toma un cruce y, a partir de ese cruce, siga el camino de la cuerda en una dirección y etiquete cada cruce sin etiquetar que encuentre con valores integrales sucesivamente mayores. Para nudos alternos, hay un algoritmo simple para convertir mi notación en tal etiquetado, y para nudos alternos es trivial convertir este etiquetado en un Código Gauss:

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 bytes en la página de códigos 850

Actualización : la versión anterior del programa a veces hacía cruces tan apretados que no se representaban correctamente, lo que viola las especificaciones. He agregado un código extra para evitar eso.

Actualización : Aparentemente, las reglas PPCG requieren un código adicional para que el programa salga y restaure el estado exactamente como estaba al principio. Esto hace que el programa sea algo más largo y no agrega ningún interés algorítmico, pero en aras del cumplimiento de las reglas, lo he cambiado.

Programa de golf

Usando GNU Prolog porque tiene una sintaxis de resolución de restricciones que es ligeramente más corta que la sintaxis aritmética de Prolog portátil, ahorrando unos pocos bytes.

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).

Algoritmo

Este es uno de esos problemas en los que es difícil saber cómo comenzar. No es obvio cómo calcular la forma del nudo a partir de la notación dada, porque no le permite saber si está destinado a doblar la línea hacia la izquierda o hacia la derecha en un lugar determinado (y como tal, el la notación puede ser ambigua). Mi solución fue, efectivamente, utilizar el viejo modo de espera de golf: escribir un programa increíblemente ineficiente que genera todas las salidas posibles y luego ver si coinciden con la entrada. (El algoritmo utilizado aquí es un poco más eficiente, ya que Prolog puede arrojar un callejón sin salida ocasional, pero no tiene suficiente información para mejorar la complejidad computacional).

La salida es a través del terminal art. GNU Prolog parece querer un conjunto de caracteres de un solo byte que sea consistente con ASCII, pero no le importa cuál se use (ya que trata los caracteres con el conjunto de bits alto como opacos). Como resultado, utilicé IBM850, que es ampliamente compatible y tiene los caracteres de dibujo lineal que necesitamos.

Salida

El programa busca todas las imágenes de nudos posibles, en el orden del tamaño de su cuadro delimitador, luego sale cuando encuentra la primera. Así es como se ve la salida m([0]).:

 ┌┐
┌│┘
└┘ 

Esto tardó 290.528 segundos en ejecutarse en mi computadora; El programa no es muy eficiente. Lo dejé funcionando durante dos horas m([0,1])y terminé con esto:

┌┐┌┐
└─│┘
 └┘ 

Versión sin golf con comentarios

El resaltador de sintaxis de Stack Exchange parece tener el símbolo de comentario incorrecto para Prolog, por lo que en lugar de %comentarios (que Prolog realmente usa), esta explicación usa % #comentarios (que, por supuesto, son equivalentes debido a comenzar %, pero resaltar correctamente).

% # 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