code golf - A Knotty situation - Code Golf Stack Exchange

New: Stack Overflow For Agents. The next generation of knowledge exchange.

Learn more.

Stack Internal

Knowledge at work

Bring the best of human thought and AI automation together at your work.

Explore Stack Internal

A Knotty situation

Ask Question

Asked<br>7 years, 10 months ago

Modified<br>5 years, 4 months ago

Viewed<br>2k times

37

\$\begingroup\$

Given the Dowker notation of a knot and its crossing signs, calculate its bracket polynomial.

Although there are more technical definitions, for this challenge it is enough to think of a knot as something made physically by attaching the two ends of a string together. Since knots exist in three dimensions, when we draw them on paper, we use knot diagrams - two-dimensional projections in which the crossings are of exactly two lines, one over and one under.

Here (b) and (c) are different diagrams of the same knot.

How do we represent a knot diagram on paper? Most of us aren't Rembrandt, so we rely on Dowker notation , which works as follows:

Pick an arbitrary starting point on the knot. Move in an arbitrary direction along the knot and number the crossings you encounter, starting from 1, with the following modification: if it's an even number and you're currently going over the crossing, negate that even number. Finally, pick the even numbers corresponding to 1, 3, 5, etc.

Let's try an example:

Taken with permission from wikimedia user Czupirek

On this knot, we chose "1" as our starting point and proceeded to move up and to the right. Every time we go over or under another piece of the rope, we assign the crossing point the next natural number. We negate the even numbers corresponding to strands that go over a crossing, for example [3,-12] in the diagram. So, this diagram would be represented by [[1,6],[2,5],[3,-12],[-4,9],[7,8],[-10,11]]. Listing the buddies of 1, 3, 5, 7, etc gives us [6,-12,2,8,-4,-10].

There are a few things to note here. First, the Dowker notation is not unique for a given knot, as we can choose an arbitrary starting point and direction. But, given the notation, one can fully determine the structure of the knot (technically, up to reflection of its prime knot components). While not all Dowker notations can form possible knots, in this problem you can assume that the input represents an actual knot.

To avoid the ambiguity between a knot's reflections, and to make the challenge easier to solve, you will also be given a list of crossing signs as input.

In a positive crossing the lower line goes to the left from the point of view of the upper line. In a negative crossing it goes to the right. Note that reversing the direction of going around the knot (i.e. reversing both the over line and under line) doesn't change the crossing signs. In our example the crossing signs are [-1,-1,-1,1,-1,1]. They are given in the same order as the Dowker notation, i.e. for crossings numbered 1, 3, 5, 7, etc.

In this challenge we will be calculating the bracket polynomial of a knot. It's an object that is invariant across most transformation of the knot diagram - a concept which makes it supremely useful in knot theory analysis. (Again, most knot theorists compute the bracket polynomial as an intermediate product on their way to computing the Jones polynomial, which is invariant across all transformations, but we will not be doing that.) So how does it work? The bracket polynomial is a Laurent polynomial - one in which the variable (traditionally named \$A\$) can be raised to negative powers, as well as positive.

For a given knot diagram \$D\$, the three rules for the polynomial, represented as \$\langle D\rangle\$, are:

A sole loop without any crossings has polynomial 1.

If we have a diagram consisting of \$D\$ and a loop disconnected from \$D\$, the polynomial for both is the polynomial for \$D\$ times \$(-A^2-A^{-2})\$.

This rule is the trickiest. It says that if you have a crossing in \$D\$ that looks like , then you can use this rule to simplify the knots in two different ways:

In the image above, the outlined crossing in the first diagram, which is of the form , can be transformed into as in the second figure (a.k.a. positive smoothing ), or as in the third figure (negative smoothing ).

So, the bracket polynomial of the first diagram is the bracket polynomial of the second times \$A\$ plus the third times \$A^{-1}\$, i.e.,

Confused yet? Let's do an example, trying to find the bracket polynomial of (Note: this is two knots linked together. This sort of diagram will not be a potential input in this challenge since the inputs will only be single knots, but it may appear as an intermediate result in the algorithm.)

We first use rule 3

We use rule 3 again on both of the new knots

We substitute these 4 new knots into the first equation.

Applying rules 1 and 2 to these 4 tell us

So, this tell us

Congrats on completing your brief intro to knot theory!

Input

Two lists:

Dowker...