Un acertijo bastante nudoso

23

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:

ingrese la descripción de la imagen aquí

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.

ingrese la descripción de la imagen aquí

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;
}
J. Antonio Perez
fuente
44
Probablemente deberías prohibir los builtins por hacer esto. (En este punto, me sorprendería si Mathematica no tiene uno.)
77
@ ais523 Ahora no puedo usar KnotDataen Mathematica ...: '(
JungHwan Min
1
Tengo curiosidad sobre la notación que usa para el diagrama de cruce de nudos. Eso tiene un nombre? ¿Es posible que dos nudos no equivalentes tengan la misma matriz?
xnor
2
@ ais523: ¡Mathematica tiene totalmente Knotincorporado! Ejemplo de uso: << Units`; Convert[Knot, Mile/Hour]rendimientos 1.1507794480235425 Mile/Hour. (Creo que esto es divertido independientemente de si es verdadero o falso; pero en realidad es cierto.)
Greg Martin
1
[0], [0,1], [0,1,2], [1,0] y una variedad de otros arreglos producen "nudos" que son equivalentes al nudo, sin embargo, generar un bucle simple sería incorrecto en cualquiera de esos casos La notación [0] significa muy específicamente un lazo de cuerda que se cruza exactamente una vez, y es muy fácil saber si una figura dibujada en la pantalla satisface la notación de entrada o no.
J. Antonio Perez

Respuestas:

22

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

fuente
Descargué el prólogo de GNU, copié su código en un archivo .txt, lo guardé como un archivo .pl codificado en ascii y en la consola llamada m ([0])
J. Antonio Perez
¿Hay alguna forma de hacer que el programa sea más eficiente?
J. Antonio Perez
Sospecho que el programa se puede hacer más eficiente, pero no hay una manera obvia o fácil. Cambiar el orden de evaluación para moverse a lo largo del nudo, en lugar de izquierda a derecha / de arriba a abajo, probablemente ayudaría, pero no estoy seguro de cuánto ayudaría (y también sería sustancialmente más código, por lo tanto, no es viable en un código de golf ).
Entiendes por qué soy reacio, ¿verdad? Quiero decir ... incluso el mejor código necesita ser probado, y su solución es tan compleja que ni siquiera puedo verificar que reproduzca el nudo más simple (el nudo [2, 0, 1]).
J. Antonio Perez
Entiendo que si. Sin embargo, esto es algo inherente al código golf , especialmente cuando se trata de Prolog. El código es realmente muy simple, razón por la cual se ejecuta tan lentamente; code-golf en un problema complejo casi siempre conduce a una solución de fuerza bruta que verifica todas las salidas posibles contra la especificación. Hacer algo para que el programa sea más eficiente lo haría considerablemente más largo, y posiblemente también dificultaría su comprensión y su corrección.