Écrivez un programme pour dessiner un diagramme 2D d'un nœud basé sur la structure du nœud. Un nœud est exactement ce à quoi il ressemble: une boucle de corde qui est attachée. En mathématiques, un diagramme de nœuds montre où un morceau de corde se croise sur ou sous lui-même pour former le nœud. Voici quelques exemples de diagrammes de nœuds:

Il y a une rupture dans la ligne où la corde se croise.

Entrée: l'entrée décrivant le nœud est un tableau d'entiers. Un nœud où la corde se croise sur elle-même n fois peut être représenté comme un tableau de n entiers, chacun avec une valeur dans la plage [0, n-1]. Appelons ce tableau K .

Pour obtenir le tableau décrivant un nœud, numérotez chacun des segments de 0 à n-1. Le segment 0 doit conduire au segment 1, qui doit conduire au segment 2, qui doit conduire au segment 3, et ainsi de suite jusqu'à ce que le segment n-1 boucle en arrière et mène au segment 0. Un segment se termine lorsqu'un autre segment de corde le traverse ( représenté par une coupure dans la ligne du diagramme). Prenons le nœud le plus simple - le nœud trèfle. Après avoir numéroté les segments, le segment 0 se termine lorsque le segment 2 le traverse; le segment 1 se termine lorsque le segment 0 le traverse; et le segment 2 se termine lorsque le segment 1 le traverse. Ainsi, le tableau décrivant le nœud est [2, 0, 1]. En général, le segment x commence là où le segment x-1 mod n s'est arrêté et se termine là où le segment K [x] le traverse.

L'image ci-dessous montre des diagrammes de nœuds, avec des segments étiquetés et les tableaux correspondants qui décrivent le nœud.

Les trois diagrammes supérieurs sont de vrais nœuds, tandis que les trois derniers sont des boucles de corde qui se croisent mais qui ne sont pas réellement nouées (mais qui ont toujours des codes correspondants).

Votre tâche consiste à écrire une fonction qui prend un tableau d'entiers K (vous pourriez l'appeler quelque chose de différent) qui décrit un nœud (ou une boucle de corde qui n'est pas réellement nouée), et qui produit le diagramme de nœud correspondant, comme décrit ci-dessus exemples. Si vous le pouvez, fournissez une version non golfée de votre code ou une explication, ainsi que des exemples de sorties de votre code. Le même nœud peut souvent être représenté de plusieurs façons différentes, mais si le diagramme de nœuds que votre sortie de fonction satisfait a l'entrée comme l'une de ses représentations possibles, votre solution est valide.

C'est le code-golf, donc le code le plus court en octets gagne. La ligne représentant la corde peut avoir une épaisseur de 1 pixel, mais les traversées et les franchissements doivent être clairement distinguables (la taille de la rupture de la corde doit être supérieure à l'épaisseur de la corde d'au moins un pixel de chaque côté) .

Je vais voter pour des réponses qui reposent sur des capacités de théorie des nœuds intégrées, mais celle qui est finalement sélectionnée ne peut pas s'appuyer sur des capacités de théorie des nœuds intégrées.

Tout ce que je sais de ma notation: je crois qu'il y a des séquences de valeurs qui ne semblent correspondre à aucun nœud ou à un nœud. Par exemple, la séquence [2, 3, 4, 0, 1] semble impossible à tracer.

En dehors de cela, supposez que vous prenez un croisement et, à partir de ce croisement, suivez le chemin de la corde dans une direction et étiquetez chaque croisement sans étiquette que vous rencontrez avec des valeurs intégrales successivement plus grandes. Pour les nœuds alternés, il existe un algorithme simple pour convertir ma notation en un tel étiquetage, et pour les nœuds alternés, il est trivial de convertir cet étiquetage en un code 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 octets dans la page de codes 850

Mise à jour : la version précédente du programme faisait parfois des croisements si serrés qu'ils ne rendraient pas correctement, ce qui viole les spécifications. J'ai ajouté du code supplémentaire pour éviter cela.

Mise à jour : Apparemment, les règles PPCG nécessitent un code supplémentaire pour faire quitter le programme et restaurer l'état exactement comme il était au début. Cela rend le programme un peu plus long et n'y ajoute aucun intérêt algorithmique, mais dans l'intérêt de la conformité aux règles, je l'ai changé.

Programme golf

Utiliser GNU Prolog car il a une syntaxe de solveur de contraintes légèrement plus courte que la syntaxe arithmétique portable de Prolog, économisant quelques octets.

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

Algorithme

C'est l'un de ces problèmes où il est difficile de savoir par où commencer. Il n'est pas évident de déterminer la forme du nœud à partir de la notation donnée, car cela ne vous permet pas de savoir si vous êtes censé plier la ligne vers la gauche ou la droite à un endroit donné (et en tant que tel, le la notation peut être ambiguë). Ma solution était, en fait, d'utiliser l'ancienne veille de golf: écrire un programme incroyablement inefficace qui génère toutes les sorties possibles, puis voir si elles correspondent à l'entrée. (L'algorithme utilisé ici est légèrement plus efficace, car Prolog peut éliminer l'impasse occasionnelle, mais il n'a pas suffisamment d'informations pour améliorer la complexité de calcul.)

La sortie se fait via le terminal art. GNU Prolog semble vouloir un jeu de caractères à un seul octet compatible avec ASCII, mais ne se soucie pas de celui qui est utilisé (car il traite les caractères avec le bit élevé comme opaques). En conséquence, j'ai utilisé IBM850, qui est largement pris en charge et possède les caractères de dessin au trait dont nous avons besoin.

Sortie

Le programme recherche toutes les images de nœuds possibles, dans l'ordre de la taille de leur boîte englobante, puis se ferme lorsqu'il trouve la première. Voici à quoi ressemble la sortie m([0]).:

 ┌┐
┌│┘
└┘ 

Cela a pris 290,528 secondes pour s'exécuter sur mon ordinateur; le programme n'est pas très efficace. Je l'ai laissé fonctionner pendant deux heures m([0,1])et j'ai fini avec ceci:

┌┐┌┐
└─│┘
 └┘ 

Version non golfée avec commentaires

Le surligneur de syntaxe de Stack Exchange semble avoir le mauvais symbole de commentaire pour Prolog, donc au lieu de %commentaires (que Prolog utilise réellement), cette explication utilise des % #commentaires (qui sont bien sûr équivalents en raison du début %, mais surlignent correctement).

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