22
\$\begingroup\$

Dowker notation is a common way of representing mathematical knots.

Dowker notation can be derived from a knot diagram in the following way (based on the description from the wikipedium):

We will label each of the \$n\$ intersections with two numbers whose absolute value is on the range \$1, \dots 2n\$ (one odd one even). To do this choose an arbitrary starting point and direction on the knot and begin traversing from there. At every intersection encountered label the intersection \$m\$ where \$m\$ is one more than the number of intersections already encountered (e.g. the first intersection is labeled 1, the second 2 etc.). However, if \$m\$ is even and the strand being followed passes over instead label the intersection with \$-m\$. We do this until we reach the starting point again, at which point every intersection should have two labels.

Now that each intersection is labeled we create a list of the even labels, sorted by their corresponding odd label (in ascending order). You could also think of this as the order we traversed the intersections skipping every other intersection.

This list is our Dowker notation

Consider this example knot:

Taken with permission from wikipedia user Frentos

If we traverse the pairs as indicated in the diagram we get the following labels:

(1, 6) (3, −12) (5, 2) (7, 8) (9, −4) (11, −10)

This gives us a Dowker notation of

[6, -12, 2, 8, -4, -10]

Your task is to take two knots in Dowker notation and determine if they are isotopic (the same knot represented in different ways).

Two knots are isotopic if you can rearrange one into the other without crossing it through itself.

The Reidemeister moves can be used to determine whether two diagrams contain isotopic knots.

Input

Dowker notation is actually the name given to a couple of related ways of representing knots. There are a couple of permissable modifications you can make to the format:

  • You may choose to represent integers as a tuple of a boolean and a positive integer, where the boolean's value represents sign of the original number and the positive integer its magnitude. e.g.

    -5 -> (True, 5)
    14 -> (False, 14)
    
  • Since the values in Dowker notation are always even you can choose to have them all divided by 2. If we use our example from earlier:

    [6, −12, 2, 8, −4, −10]
    =>
    [3, -6, 1, 4, -2, -5]
    

You may make any combination of these modifications to your input format. Of course your input format must be consistent.

Output

Your code should output one of two distinct consistent values. One of these should always be output when the notations represent the same knot and the other should always be output when the notations represent different knots.

Scoring

This is code-golf answers will be scored in bytes with fewer bytes being better.

Test cases

The same

-- Reidemeister move I
[6, -12, 2, 8, -4, -10] [6, -8, 2, -4]
-- Reidemeister move II
[4, 6, 2] [8, 6, 10, -2, 4]
-- Mirror
[6, -12, 2, 8, -4, -10] [-6, 12, -2, -8, 4, 10]
-- Change of starting location
[6, -12, 2, 8, -4, -10] [4, -6, 10, -2, -8, 12]
-- Two trefoils
[4, 6, 2] [ 6, -8, 2, -4]

Different

-- Unknot and trefoil
[] [4, 6, 2]
-- Trefoil and figure 8
[4, 6, 2] [6, 8, 2, 4]
\$\endgroup\$
3
  • \$\begingroup\$ I'm not sure I actually see this being useful, but would one permissible modification to the input format be to encode sign in the ones bit? It just sort of struck me as a pleasant fusion of the two modifications given. \$\endgroup\$ Nov 24, 2020 at 19:17
  • 1
    \$\begingroup\$ @UnrelatedString Sure. I might add some more possible input formats as well. It's the least I can do with a challenge like this. \$\endgroup\$
    – Wheat Wizard
    Nov 24, 2020 at 20:07
  • \$\begingroup\$ I'm definitely not an expert, but from the Wikipedia page (see section "Uniqueness and counting") it looks like the Dowker–Thistlethwaite notations can sometimes be ambiguous, i.e. two non-isotopic knots can have the same Dowker sequence. Is this right? \$\endgroup\$
    – Delfad0r
    Apr 5, 2021 at 14:56

1 Answer 1

4
\$\begingroup\$

JavaScript (ES2020), 736 730 720 bytes

-3 thanks to Kevin Cruijssen

-10 thanks to Neil

(t,e,l="slice",n=0)=>(f=(t,e=Object.assign([],Object.fromEntries(t[a="map"](((a,f)=>[2*f,a<0?-a:a,a>0])).flatMap((([a,f,p])=>[[a,[--f,p]],[f,[a,!p]]])))))=>n=(f[(e.map((a=>e.find((([a,f],p)=>a==p+1?e=[...e[l](0,p),...e[l](p+2)].map((([a,f])=>[a-2*(a>p),f])):p<a&&a==e[p+1][0]+1&e[p+1][1]==f?e=[e[l](0,p),e[l](p+2,a-1),e[l](a+1)].flat().map((([f,m])=>[f-2*(f>p)-2*(f>a),m])):0)))),e)]||(f[e]=t,f(t,[...e[l](1),...e[l](0,1)].map((([a,f])=>[(a||e.length)-1,f]))),f(t,e.map((([a,f])=>[a,!f]))),(m=[1,-1]).map((a=>m.map((m=>e.map((([e,l],n,[...o],s=o[n+1]?.[0])=>s+1&&l==o[n+1][1]&s+m===o[e+a]?.[0]&&f(t,o,[o[n],o[n+1],o[e],o[e+a],o[s],o[s+m]]=[[s+m,l],[e+a,l],[s,p=o[e+a][1]],[n+1,!l],[e,!p],[n,!l]]))))))),t))!=t|n)(t)|f(e)

input.value="# interactive; edit or add lines and the annotation will update\n\n# isotopic\n[6, -12, 2, 8, -4, -10] [6, -8, 2, -4]\n[4, 6, 2] [8, 6, 10, -2, 4]\n[6, -12, 2, 8, -4, -10] [-6, 12, -2, -8, 4, 10]\n[6, -12, 2, 8, -4, -10] [4, -6, 10, -2, -8, 12]\n[4, 6, 2] [6, -8, 2, -4]\n[] [2]\n[2] []\n[2] [2]\n[] [6, 4, 2]\n[] [6, -4, 2]\n[] []\n\n# not isotopic\n[] [4, 6, 2]\n[] [6, -8, 2, -4]\n[2] [6, -8, 2, -4]\n[6, -4, 2] [6, -8, 2, -4]";(input.onchange=input.oninput=()=>{input.style.minHeight="1px";input.style.minHeight = (input.scrollHeight)+"px";output.textContent=input.value.split("\n").map(x=>{if(!x.trim()||x.startsWith("#"))return"";let M=/^(\[\s*((?:-?\d+\s*,\s*)*-?\d+\s*)?\]) (?:\[\s*((?:-?\d+\s*,\s*)*-?\d+\s*)?\])$/.exec(x);if(M){let[A,B]=[M[2],M[3]].map(x=>x?x.trim().split(/\s*,\s*/).map(x=>+x):[]);try{f=(
(t,e,l="slice",n=0)=>(f=(t,e=Object.assign([],Object.fromEntries(t[a="map"](((a,f)=>[2*f,a<0?-a:a,a>0])).flatMap((([a,f,p])=>[[a,[--f,p]],[f,[a,!p]]])))))=>n=(f[(e.map((a=>e.find((([a,f],p)=>a==p+1?e=[...e[l](0,p),...e[l](p+2)].map((([a,f])=>[a-2*(a>p),f])):p<a&&a==e[p+1][0]+1&e[p+1][1]==f?e=[e[l](0,p),e[l](p+2,a-1),e[l](a+1)].flat().map((([f,m])=>[f-2*(f>p)-2*(f>a),m])):0)))),e)]||(f[e]=t,f(t,[...e[l](1),...e[l](0,1)].map((([a,f])=>[(a||e.length)-1,f]))),f(t,e.map((([a,f])=>[a,!f]))),(m=[1,-1]).map((a=>m.map((m=>e.map((([e,l],n,[...o],s=o[n+1]?.[0])=>s+1&&l==o[n+1][1]&s+m===o[e+a]?.[0]&&f(t,o,[o[n],o[n+1],o[e],o[e+a],o[s],o[s+m]]=[[s+m,l],[e+a,l],[s,p=o[e+a][1]],[n+1,!l],[e,!p],[n,!l]]))))))),t))!=t|n)(t)|f(e)
);let r=f(A,B);return" ".repeat(M[1].length)+(r?"=":"≠")}catch(e){}}return" ".repeat(x.length+1)+"?"}).join("\n")})()
#input{width:100%;height:100%;border:0;outline:0;padding:5px}body,html{width:100%;height:100%;margin:0}body{overflow:auto}*{box-sizing:border-box}#output{position:absolute;pointer-events:none;top:0;left:0;padding:5px;white-space:pre;opacity:.5}#input,#output{font-family:monospace;font-size:15px;overflow:hidden}
<div id="output"></div><textarea id="input"></textarea>

Ungolfed / Explanation

// First, we'll convert the dowker notation to a more convenient format:
//   Original:
//     6, -12, 2, 8, -4, -10
//   Reconstruct the pairs:
//     (1,6), (3,-12), (5,2), (7,8), (9,-4), (11,-10)
//   Add in the even pairs:
//     (1,6), (2,-5), (3,-12), (4,-9), (5,2), (6,-1), (7,8), (8,-7), (9,-4), (10,11), (11,-10), (12,3)
//   Extract the sign:
//     (1,6,+), (2,5,-), (3,12,-), (4,9,-), (5,2,+), (6,1,-), (7,8,+), (9,4,-), (10,11,+), (11,10,-), (12,3,+)
//   Zero-index:
//     (0,5,+), (1,4,-), (2,11,-), (3,8,-), (4,1,+), (5,0,-), (6,7,+), (8,3,-), (9,10,+), (10,9,-), (11,2,+)
//   Convert to array: [
//     [5, true],
//     [4, false],
//     [11, false],
//     [8, false],
//     [1, true],
//     [0, false],
//     [7, true],
//     [6, false],
//     [3, false],
//     [10, true],
//     [9, false],
//     [2, true],
//   ]
function dowkerToKnot(dowker) {
  return Array.from({
    // Twice as many pairs
    length: dowker.length * 2,
    ...Object.fromEntries(
      dowker
        .map((x, i) => [i * 2, Math.abs(x) - 1, Math.sign(x) == 1])
        .flatMap(([a, b, x]) => [
          [a, [b, x]],
          [b, [a, !x]],
        ])
    ),
  });
}

// Continually simplify using Reidemeister moves I and II
function simplify(knot) {
  let prev;
  while (prev !== (prev = knot)) {
    for (let a of knot.keys()) {
      /* Reidemeister move I */ {
        // Reidemeister move I resolves simple twists like
        //    \    _
        //   a↘\ /   \
        //      /↙a+1 |
        //     / \ _ /
        //    /
        // This can be expressed by the condition:
        //    a' = a + 1  [where x' is the other number associated with the crossing at x]
        if (knot[a][0] /* a' */ === a + 1) {
          knot = [
            ...knot.slice(0, a), // the crossings before the loop
            ...knot.slice(a + 2), // the crossing after the loop
          ].map(([x, o]) => [x > a ? x - 2 : x /* adjust the indices */, o]);
          break;
        }
      }
      /* Reidemeister move II */ {
        // Reidemeister move II resolves strings tucked under/over another like
        //    \ |
        //   a↘\|
        //      |↑b+1
        //      |\
        //      | |
        //      | |
        //      |/↙a+1
        //    b↑|
        //     /|
        //    / |
        // This can be expressed as the conditions:
        //   b' = a+1
        //   a' = b+1
        //   #a = #(a+1)  [where #x is the over/under sign associated with x]
        let b = knot[a + 1]?.[0]; // (b = (a+1)' is the same as b' = a+1)
        if (
          a < b /* a and b are symmetric, so this dedupes */ &&
          knot[a][1] /* #a */ === knot[a + 1][1] /* #(a+1) */ &&
          knot[a][0] /* a' */ === b + 1
        ) {
          knot = [
            ...knot.slice(0, a) /* before a */,
            ...knot.slice(a + 2, b) /* between a and b (we know that a < b) */,
            ...knot.slice(b + 2) /* after b */,
          ].map(([x, a]) => [
            x - (x > a) * 2 - (x > b) * 2 /* adjust indices */,
            a,
          ]);
          break;
        }
      }
    }
  }
  return prev;
}

// Applies manipulations to a given knot, calling processKnot for every resulting knot.
// Manipulations include:
//  - Shifting the starting location
//  - Mirroring
//  - Reidemeister move III
function manipulate(knot, processKnot) {
  // Shift the starting location by 1
  if (knot.length)
    processKnot(
      knot
        .slice(1)
        .concat([knot[0]]) /* cycle the crossings */
        .map(([a, b]) => [(a || knot.length) - 1 /* adjust indices */, b])
    );

  // Mirror
  processKnot(knot.map(([a, b]) => [a, !b /* reverse over/under */]));

  /* Reidemeister move III */ {
    // Reidemeister move III moves a string across a crossing:
    //    \     /             \     /
    //     \   /           -------------
    //      \ /                 \ /
    //       /         →         /
    //      / \                 / \
    // -------------           /   \
    //    /     \             /     \
    // Let's label the crossings in the original:
    //      \     /
    //       \   /
    //        \ /
    //     b+1↗/↖c+1
    //        / \
    //    a→ /   \ →a+1
    //  ---------------
    //   b↗/       \↖c
    //    /         \
    // This can be expressed with the following conditions:
    //   b = a'
    //   c = (a+1)'
    //   (b+1)' = c+1
    //   #a = #(a+1)
    // Now, the b and c strings could go in either direction.
    // Here's another example, with b reversed (note b-1):
    //      \     /
    //       \   /
    //        \ /
    //     b-1↙/↖c+1
    //        / \
    //    a→ /   \ →a+1
    //  ---------------
    //   b↙/       \↖c
    //    /         \
    // Thus, we'll generalize the conditions as follows, where B and C are each either 1 or -1:
    //   b = a'
    //   c = (a+1)'
    //   (b+B)' = c+C
    //   #a = #(a+1)

    for (let B of [1, -1])
      for (let C of [1, -1])
        for (let a of knot.keys()) {
          let b = knot[a][0];
          // Edge case: a + 1 might not exist, as it could wrap around the array.
          // This is fine, as it will be handled by one of the knots with a shifted starting location.
          let c = knot[a + 1]?.[0];
          if (
            c != null &&
            knot[a][1] /* #a */ === knot[a + 1][1] /* #(a+1) */ &&
            knot[b + B]?.[0] /* (b+B)' */ === c + C
          ) {
            // Now that we've identified a location to apply this manipulation,
            // we need to determine how to modify the knot.
            // Here's the original knot, again (this uses B=1 and C=1, but is generally applicable):
            //      \     /
            //       \   /
            //        \ /
            //     b+1↗/↖c+1
            //        / \
            //    a→ /   \ →a+1
            //  ---------------
            //   b↗/       \↖c
            //    /         \
            // This needs to be transformed to:
            //    \         /
            //     \       /
            //  ---------------
            //       \   /
            //        \ /
            //         /
            //        / \
            //       /   \
            //      /     \
            // Labeling the crossings, we get:
            //    \         /
            //  a→ \       / →a+1
            //  ---------------
            //   c+1↖\   /↗b+1
            //        \ /
            //       b↗/↖c
            //        / \
            //       /   \
            //      /     \
            let newKnot = [...knot];
            newKnot[a] = [c + C, knot[a][1]];
            newKnot[a + 1] = [b + B, knot[a][1]];
            newKnot[b] = [c, knot[b + B][1]];
            newKnot[b + B] = [a + 1, !knot[a][1]];
            newKnot[c] = [b, !knot[b + B][1]];
            newKnot[c + C] = [a, !knot[a][1]];
            processKnot(newKnot);
          }
        }
  }
}

// We can finally checks if two knots are equal!
function isotopic(a, b) {
  // We'll track the result in this variable.
  let result = false;

  // First, we're going to create an empty object to serve as a record.
  // This will serve as a dictionary from knots to either "a" or "b".
  let record = {};

  function processKnot(knot, marker /* either "a" or "b" */) {
    // Before doing anything with the knot, we'll first simplify it.
    knot = simplify(knot);

    // Then, we'll check to see if the record already has an entry for this knot.
    let value = record[knot];
    if (value === undefined) {
      // We've never seen this knot; add it to the record.
      record[knot] = marker;
      // Process all of the knots we can make by manipulating this one.
      manipulate(knot, newKnot => processKnot(newKnot, marker));
    } else if (value === marker) {
      // We've already seen this knot for this marker, so we don't need to do anything.
    } else {
      // We've already seen this knot, but for a different marker.
      // This means that both original knots (a and b) are isotopic to this knot.
      // By transitivity, they're isotopic to each other as well.
      result = true;
    }
  }

  processKnot(a, "a");
  processKnot(b, "b");

  return result;
}

function main(a, b) {
  // Convert each of a and b to our format and then check if they're isotopic.
  return isotopic(dowkerToKnot(a), dowkerToKnot(b));
}
\$\endgroup\$
4
  • \$\begingroup\$ Nice answer! Although it doesn't save much (I'm sure someone who's skilled in codegolfing in JavaScript could help a lot more), Math.abs(a) can be a<0?-a:a to save 3 bytes. :) \$\endgroup\$ Nov 22, 2021 at 16:05
  • \$\begingroup\$ @KevinCruijssen Thanks! Turns out that that whole portion was dumb; I was saving the abs in y to then compare with a to check if it was positive, when a>0 would work just as well. Not sure how I missed that. \$\endgroup\$
    – tjjfvi
    Nov 22, 2021 at 16:10
  • \$\begingroup\$ I think you can Object.assign([],Object.fromEntries()) instead of Array.from. \$\endgroup\$
    – Neil
    Nov 23, 2021 at 0:57
  • \$\begingroup\$ @Neil Oh, yep, thanks. I always forget that [].length is a magic auto-updating property. \$\endgroup\$
    – tjjfvi
    Nov 23, 2021 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.