2 ms·

One of the problems of old on CodeGolf.SE - Knot or Not - https://codegolf.stackexchange.com/questions/30292/knot-or-not https://codegolf.stackexchange.com/ques

by shagie 4y ago

One of the problems of old on CodeGolf.SE - Knot or Not - https://codegolf.stackexchange.com/questions/30292/knot-or-not https://codegolf.stackexchange.com/questions/30292/knot-or-n... I took a crack at it one time (even ordered a back issue of Scientific American - https://www.scientificamerican.com/article/the-theory-of-knots/ https://www.scientificamerican.com/article/the-theory-of-kno... ) and didn't even get something that had a working internal representation that I could use. It's a hard problem.

kadoban 4y ago
Did you try a representation that's a graph where the nodes are crossings (colored for over or under), and there's an edge between any two crossings iff there's a string that directly connects them (not going through any other crossing first)? That's what comes to mind to me at least. It seems like it should at least preserve the important parts of the input and be possibly useful to work on. I haven't figured out the algorithm yet though, so maybe that's misguided.
- shagie 4y ago
  It's been too long and I'd have to look at it again. Consider the question of "what internal structure would you use to represent the trefoil knot?" - https://en.wikipedia.org/wiki/Trefoil_knot https://en.wikipedia.org/wiki/Trefoil_knot // https://mathworld.wolfram.com/TrefoilKnot.html https://mathworld.wolfram.com/TrefoilKnot.html And then figure out how to convert an ascii art image that represents that knot into that internal format... and you do a "I'll do it later" which never comes around.
  - kadoban 4y ago
    Yeah that seems pretty tricky. I'm somewhat convinced that the graph representation will work (it can represent the input correctly), but I'm not yet sure if it's actually useful or not for an algorithm to work through.
    - shagie 4y ago
      It needs to be in a format that you can then use existing algorithms with - the Reidemeister move being the "easiest" https://en.wikipedia.org/wiki/Reidemeister_move https://en.wikipedia.org/wiki/Reidemeister_move
      - kadoban 4y ago
        Yeah that's along the lines of the transformations I was thinking of, though I only considered 2 of those...

by shagie 4y ago

kadoban 4y ago

Did you try a representation that's a graph where the nodes are crossings (colored for over or under), and there's an edge between any two crossings iff there's a string that directly connects them (not going through any other crossing first)? That's what comes to mind to me at least. It seems like it should at least preserve the important parts of the input and be possibly useful to work on. I haven't figured out the algorithm yet though, so maybe that's misguided.

shagie 4y ago
It's been too long and I'd have to look at it again. Consider the question of "what internal structure would you use to represent the trefoil knot?" - https://en.wikipedia.org/wiki/Trefoil_knot https://en.wikipedia.org/wiki/Trefoil_knot // https://mathworld.wolfram.com/TrefoilKnot.html https://mathworld.wolfram.com/TrefoilKnot.html And then figure out how to convert an ascii art image that represents that knot into that internal format... and you do a "I'll do it later" which never comes around.
- kadoban 4y ago
  Yeah that seems pretty tricky. I'm somewhat convinced that the graph representation will work (it can represent the input correctly), but I'm not yet sure if it's actually useful or not for an algorithm to work through.
  - shagie 4y ago
    It needs to be in a format that you can then use existing algorithms with - the Reidemeister move being the "easiest" https://en.wikipedia.org/wiki/Reidemeister_move https://en.wikipedia.org/wiki/Reidemeister_move
    - kadoban 4y ago
      Yeah that's along the lines of the transformations I was thinking of, though I only considered 2 of those...