A Rather Knotty Conundrum

Question

Write a program to draw a 2-D diagram of a knot based on the knot's structure. A knot is exactly what it sounds like: a loop of rope that's tied up. In mathematics, a knot diagram shows where a piece of rope crosses over or under itself to form the knot. Some example knot diagrams are shown below:

There's a break in the line where the rope crosses over itself.

Input: the input describing the knot is an array of integers. A knot where the rope crosses over itself n times can be represented as an array of n integers, each with a value in the range [0, n-1]. Let's call this array K.

To get the array describing a knot, number each of the segments 0 through n-1. Segment 0 should lead to segment 1, which should lead to segment 2, which should lead to segment 3, and so on until segment n-1 loops back and leads to segment 0. A segment ends when another segment of rope crosses over it (represented by a break in the line in the diagram). Let's take the simplest knot - the trefoil knot. After we've numbered the segmnents, segment 0 ends when segment 2 crosses over it; segment 1 ends when segment 0 crosses over it; and segment 2 ends when segment 1 crosses over it. Thus, the array describing the knot is [2, 0, 1]. In general, segment x starts where segment x-1 mod n left off, and ends where segment K[x] crosses over it.

The below image show knot diagrams, with labeled segments and the corresponding arrays that describe the knot.

The top three diagrams are true knots, while the bottom three are loops of rope that cross over themself but aren't actually knotted (but which still have corresponding codes).

Your task is to write a function which takes an array of integers K (you could call it something different) that describes a knot (or loop of rope that's not actually knotted), and which produces the corresponding knot diagram, as described in the above examples. If you can, provide an ungolfed version of your code or an explanation, and also provide sample outputs of your code. The same knot can often be represented in multiple different ways, but if the knot diagram your function outputs satisfies has the input as one of it's possible representations, your solution is valid.

This is code-golf, so shortest code in bytes wins. The line representing the rope can have a thickness of 1 pixel, however under and over-crossings must be clearly distinguishable (the size of the break in the rope should be greater than the thickness of the rope by at least a pixel on either side).

I will upvote answers that rely on built-in knot theory capabilities, but the one that's selected in the end can't rely on built-in knot theory capabilities.

Everything I know about my notation: I believe that there are sequences of values that don't seem to correspond to any knot or unknot. For example, the sequence [2, 3, 4, 0, 1] seems to be impossible to draw.

Aside from that, suppose that you take a crossing and, starting from that crossing, follow the path of the rope in one direction and label every unlabeled crossing that you come across with succesively greater integral values. For alternating knots, there is a simple algorithm to convert my notation into such a labeling, and for alternating knots it's trivial to convert this labeling into a Gauss Code:

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;
}

Answer 1

GNU Prolog, 622 634 668 bytes in code page 850

Update: The previous version of the program was sometimes making crossings so tight that they wouldn't render properly, which violates the spec. I've added in some extra code to prevent that.

Update: Apparently PPCG rules require extra code to make the program exit and restore the state exactly as it was at the start. This makes the program somewhat longer and adds no algorithmic interest to it, but in the interests of rule compliance, I've changed it.

Golfed program

Using GNU Prolog because it has a constraint solver syntax that's slightly shorter than portable Prolog's arithmetic syntax, saving a few 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).

Algorithm

This is one of those problems where it's hard to know how to start. It's not obvious how to work out the shape of the knot from the notation given, because it doesn't let you know whether you're meant to bend the line to the left or the right at any given location (and as such, the notation might be ambiguous). My solution was, effectively, to use the old golfing standby: write an incredibly inefficient program which generates all possible outputs and then see if they match the input. (The algorithm used here is slightly more efficient, as Prolog can throw out the occasional dead end, but it doesn't have enough information to improve the computational complexity.)

The output is via terminal art. GNU Prolog seems to want a single byte character set that's consistent with ASCII, but doesn't care which one is used (as it treats characters with the high bit set as opaque). As a result, I used IBM850, which is widely supported and has the line drawing characters we need.

Output

The program searches all possible knot images, in the order of the size of their bounding box, then exits when it finds the first. Here's what the output looks like for m([0]).:

 ┌┐
┌│┘
└┘ 

This took 290.528 seconds to run on my computer; the program isn't very efficient. I left it running for two hours on m([0,1]), and ended up with this:

┌┐┌┐
└─│┘
 └┘ 

Ungolfed version with comments

Stack Exchange's syntax highlighter seems to have the wrong comment symbol for Prolog, so instead of % comments (which Prolog actually uses), this explanation uses % # comments (which are of course equivalent due to starting with %, but highlight correctly).

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