À partir de la notation Dowker d’un nœud et de ses signes de croisement, calculez son polynôme de support.

Bien qu’il existe davantage de définitions techniques, il suffit de penser à un nœud comme à un élément fabriqué physiquement en reliant ensemble les deux extrémités d’une ficelle. Comme les nœuds existent en trois dimensions, lorsque nous les dessinons sur papier, nous utilisons des diagrammes de nœuds - des projections bidimensionnelles dans lesquelles les croisements ont exactement deux lignes, une en haut et une en dessous.

Ici (b) et (c) sont différents schémas du même nœud.

Comment représente-t-on un diagramme en nœuds sur du papier? La plupart d'entre nous n'étant pas Rembrandt, nous nous appuyons sur la notation Dowker , qui fonctionne comme suit:

Choisissez un point de départ arbitraire sur le noeud. Déplacez -vous dans une direction arbitraire le long du noeud et le nombre des passages que vous rencontrez, à partir de 1, avec la modification suivante: si elle est un nombre pair et vous êtes actuellement aller sur la traversée, ce nombre Négation même. Enfin, choisissez les nombres pairs correspondant à 1, 3, 5, etc.

Essayons un exemple:

Sur ce nœud, nous avons choisi "1" comme point de départ et nous nous sommes dirigés vers le haut et vers la droite. Chaque fois que nous passons par - dessus ou par- dessous un autre morceau de la corde, nous attribuons au prochain point naturel le numéro naturel. Nous nions les nombres pairs correspondant aux brins qui traversent un croisement, par exemple [3,-12]dans le diagramme. Donc, ce diagramme serait représenté par [[1,6],[2,5],[3,-12],[-4,9],[7,8],[-10,11]]. La liste des copains de 1, 3, 5, 7, etc. nous donne [6,-12,2,8,-4,-10].

Il y a quelques choses à noter ici. Premièrement, la notation Dowker n’est pas unique pour un nœud donné, car nous pouvons choisir un point de départ et une direction arbitraires. Mais, étant donné la notation, on peut déterminer entièrement la structure du nœud (techniquement, jusqu’à la réflexion de ses composants principaux). Bien que toutes les notations Dowker ne puissent pas former de nœuds possibles, dans ce problème, vous pouvez supposer que l'entrée représente un nœud réel.

Afin d'éviter toute ambiguïté entre les réflexions d'un nœud et de faciliter la résolution du problème, une liste de points de passage vous sera également fournie .

En cas de croisement positif, la ligne inférieure passe à gauche du point de vue de la ligne supérieure. Dans un croisement négatif, il va à droite. Notez que l'inversion de la direction du nœud (c'est-à-dire l'inversion de la ligne supérieure et inférieure ) ne modifie pas les panneaux indiquant le passage à niveau. Dans notre exemple, les panneaux de croisement sont [-1,-1,-1,1,-1,1]. Ils sont donnés dans le même ordre que la notation Dowker, c'est-à-dire pour les croisements numérotés 1, 3, 5, 7, etc.

Dans ce défi, nous allons calculer le polynôme de la parenthèse d'un nœud. C'est un objet invariant dans la plupart des transformations du diagramme à nœuds - un concept qui le rend extrêmement utile dans l'analyse par la théorie des nœuds. (Encore une fois, la plupart des théoriciens du nœud calculent le polynôme de la parenthèse comme un produit intermédiaire pour calculer le polynôme de Jones, qui est invariant pour toutes les transformations, mais nous ne le ferons pas.) Comment cela fonctionne-t-il? Le polynôme de la parenthèse est un polynôme de Laurent - celui dans lequel la variable (traditionnellement appelée ) peut être élevée à des puissances négatives et positives.$A$

Pour un diagramme de nœud donné , les trois règles du polynôme, représentées par , sont les suivantes:$D$$\langle D\rangle$

1. Une boucle de semelle sans croisement a le polynôme 1.

2. Si nous avons un diagramme composé de et d’une boucle déconnectée de , le polynôme des deux est le polynôme des temps .$D$$D$$D$$(-A^2-A^{-2})$

3. Cette règle est la plus délicate. Il dit que si vous avez un croisement en qui ressemble à , vous pouvez utiliser cette règle pour simplifier les nœuds de deux manières différentes:$D$

Dans l'image ci-dessus, le croisement indiqué dans le premier diagramme, qui est de la forme , peut être transformé comme dans la deuxième figure ( lissage positif ) ou comme dans la troisième figure ( lissage négatif ).

Ainsi, le polynôme de parenthèse du premier diagramme est le polynôme de parenthèse des secondes fois plus les troisièmes fois , c'est-à-dire$A$$A^{-1}$

Encore confus? Prenons un exemple en essayant de trouver le polynôme de parenthèse de (Remarque: il s’agit de deux nœuds liés. Ce type de diagramme ne constituera pas une entrée potentielle dans ce défi, car les entrées ne seront que des nœuds simples, mais elles peuvent apparaître comme des résultat intermédiaire dans l'algorithme.)

Nous utilisons d'abord la règle 3

Nous utilisons à nouveau la règle 3 sur les deux nouveaux nœuds

Nous substituons ces 4 nouveaux nœuds dans la première équation.

Appliquer les règles 1 et 2 à ces 4 nous dit

Alors, cela nous dit

Félicitations pour avoir terminé votre brève introduction à la théorie des nœuds!

Contribution

Deux listes:

• Notation Dowker, par exemple [6,-12,2,8,-4,-10]. La numérotation des croisements doit commencer à 1. Les nombres impairs correspondants [1,3,5,7,...]sont implicites et ne doivent pas être entrés.

• Des signes ( 1/ -1ou si vous préférez 0/ 1ou false/ trueet '+'/ '-') pour les croisements correspondant à la notation Dowker, par exemple [-1,-1,-1,1,-1,1].

Au lieu d'une paire de listes, vous pouvez avoir une liste de paires, par exemple [[6,-1],[-12,-1],...

Sortie

Imprimer ou renvoyer le polynôme, par exemple , sous la forme d'une liste de paires coefficient-exposant (ou paires d'exposant-coefficient) dans l'ordre croissant des exposants et sans aucun coefficient nul, par exemple .$A^{-2}+5+A-A^3$[[1,-2],[5,0],[1,1],[-1,3]]

Vous pouvez également générer une liste de longueur impaire de coefficients correspondant aux exposants pour certains , par exemple . L'élément central est le terme constant (coefficient avant ). Les éléments les plus à gauche et les plus à droite ne doivent pas être tous les deux 0.$-k\ldots k$$k\in \mathbb{N}$[0,1,0,5,1,0,-1]$A^0$

Règles

Ceci est un défi de code-golf . Aucune des failles standard ne peut être utilisée et les bibliothèques disposant d'outils permettant de calculer les notations de Dowker ou les polynômes de support ne peuvent pas être utilisées. (Un langage contenant ces bibliothèques peut toujours être utilisé, mais pas les bibliothèques / packages).

Des tests

// 4-tuples of [dowker_notation, crossing_signs, expected_result, description]
[
 [[],[],[[1,0]],"unknot"],
 [[2],[1],[[-1,3]],"unknot with a half-twist (positive crossing)"],
 [[2],[-1],[[-1,-3]],"unknot with a half-twist (negative crossing)"],
 [[2,4],[1,1],[[1,6]],"unknot with two half-twists (positive crossings)"],
 [[4,6,2],[1,1,1],[[1,-7],[-1,-3],[-1,5]],"right-handed trefoil knot, 3_1"],
 [[4,6,2,8],[-1,1,-1,1],[[1,-8],[-1,-4],[1,0],[-1,4],[1,8]],"figure-eight knot, 4_1"],
 [[6,8,10,2,4],[-1,-1,-1,-1,-1],[[-1,-7],[-1,1],[1,5],[-1,9],[1,13]],"pentafoil knot, 5_1"],
 [[6,8,10,4,2],[-1,-1,-1,-1,-1],[[-1,-11],[1,-7],[-2,-3],[1,1],[-1,5],[1,9]],"three-twist knot, 5_2"],
 [[4,8,10,2,12,6],[1,1,-1,1,-1,-1],[[-1,-12],[2,-8],[-2,-4],[3,0],[-2,4],[2,8],[-1,12]],"6_3"],
 [[4,6,2,10,12,8],[-1,-1,-1,-1,-1,-1],[[1,-10],[2,-2],[-2,2],[1,6],[-2,10],[1,14]],"granny knot (sum of two identical trefoils)"],
 [[4,6,2,-10,-12,-8],[1,1,1,1,1,1],[[1,-14],[-2,-10],[1,-6],[-2,-2],[2,2],[1,10]],"square knot (sum of two mirrored trefoils)"],
 [[6,-12,2,8,-4,-10],[-1,-1,-1,1,-1,1],[[1,-2],[1,6],[-1,10]],"example knot"]
]

Ressources externes

Pas nécessaire pour le défi, mais si vous êtes intéressé:

• Un article sur les polynômes de noeud

• Un article sur la notation Dowker

poteaux de bac à sable: 1 , 2

merci @ChasBrown et @ H.Pwiz pour avoir détecté une erreur dans ma définition de la notation Dowker

K (ngn / k) , 196 193 octets

{!N::2*n:#x;{+/d,'x,'d:&:'-2!(|/n)-n:#:'x}(+/1-2*s){j::+,/y;,/(&0|2*x;(-1+#?{x[j]&:x@|j;x}/!N){-(d,x)+x,d:&4}/,1;&0|-2*x)}'(N!{(x,'|1+x;x+/:!2)}'((2*!n),'-1+x|-x)@'0 1=/:x>0)@'/:+~(y<0)=s:!n#2}

Essayez-le en ligne!

Brain-Flak , 1316 octets

(({})<({()<(({}<>))><>}){(({})[()()]<{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}>)}<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>{}{}(()){(<({}<({}<>)>)>)<>((){[()](<(({})<>){({}[({})]<>({}<>))}{}({}<>({}<{}<>{({}<>)<>}>)[()])<>({}({})[()])(([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}><>{()((<({}()[({}<>)])<>>))}{}<{}{}>)((){[()]<({}()<({}<({}<<>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}<>>)<>>)>)((){[()](<{}(({})<<>(({})<(<<>({}<<>({}<(()()){({}[()]<([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>)}{}>{})>)>)<>{}{({}<>)<>}<>([({}<>)]<((()))>)(())<>({}<>)<>{}({}[()]){<>({}<<>(()()){({}[()]<({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}(({})<<>({}<>)<>([{}])>)>)}{}{}>)<>({}<(({})())>[()]<>)}{}({}<<>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>{}{}{}>{})>)>)}{}){(<{}(({})<<>(({}{})<<>(<({}<>)>)<>{}{({}<>)<>}<>>(({}){}){})>)>)}>}{}){(<{}([{}]<({}<<>([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>({})({}){})>)>)}{}>)}{}){{}(([{}]){}<>{}{}<<>({}<>{}){([{}]({}()()<{}({}<>)(())<>>))}{}{}{}>{})(())<>{{}({}<>)(())<>}(<>)<>}{}}{}{}<>{}{}({}<{{}({}<>)(())<>}<>{{}{((<(())>))}{}}{}{{}({}<>)(())<>}>)<>{{}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}{}({}<>)<>}<>

Essayez-le en ligne!

Je ne regrette rien. L'entrée est une liste aplatie de paires.

# Part 1: extract edges
(({})<

({()<(({}<>))><>}){

(({})[()()]<

{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}

<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}

>)}

<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>

{}{}(())

# Part 2: Compute bracket polynomial
{

  # Move degree/sign to other stack
  (<({}<({}<>)>)>)<>

  # If current shape has crossings:
  ((){[()](<

    # Consider first currently listed edge in set
    # Find the other edge leaving same crossing
    (({})<>){({}[({})]<>({}<>))}{}

    # Move to top of other stack
    # Also check for twist
    ({}<>({}<{}<>{({}<>)<>}>)[()])

    # Check for twist in current edge
    <>({}({})[()])

    (

      # Remove current edge if twist
      ([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}>

      # Remove matching edge if twist
      <>{()((<({}()[({}<>)])<>>))}{}<{}{}>

    # Push 1 minus number of twists from current vertex.
    )

    # If number of twists is not 1:
    ((){[()]<

      # While testing whether number of twists is 2:
      ({}()<

        # Keep sign/degree on third stack:
        ({}<({}<

          # Duplicate current configuration
          <>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}

        # Push sign and degree on separate stacks
        <>>)<>>)

      # If number of twists is not 2: (i.e., no twists)
      >)((){[()](<{}

        # Make first copy of sign/degree
        (({})<<>(({})<

          # Make second copy of sign/degree
          (<<>({}<<>({}<

            # Do twice:
            (()()){({}[()]<

              # Prepare search for vertex leading into crossing on other side
              ([{}]()<>)

              # While keeping destination on third stack:
              <>({}<

                # Search for matching edge
                <>{({}({})<>[({}<>)])}{}

              # Replace old destination
              {}>)

              # Move back to original stack
              {({}<>)<>}<>

            >)}{}

          # Add orientation to degree
          >{})>)>)

          # Move duplicate to left stack
          <>{}{({}<>)<>}<>

          # Create "fake" edges from current crossing as termination conditions
          ([({}<>)]<((()))>)(())<>

          # Create representation of "top" new edge
          ({}<>)<>{}({}[()])

          # While didn't reach initial crossing again:
          {

            # Keep destination of new edge on third stack
            <>({}<<>

              # Do twice:
              (()()){({}[()]<

                # Search for crossing
                ({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}

                # Reverse orientation of crossing
                (({})<<>({}<>)<>([{}])>)

              >)}{}

              # Remove extraneous search term
              {}

            # Push new destination for edge
            >)

            # Set up next edge
            <>({}<(({})())>[()]<>)

          }

          # Get destination of last edge to link up
          {}({}<

            # Find edge headed toward original crossing
            <>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}

          # Replace destination
          {}{}>)

          # Move everything to left stack
          {({}<>)<>}

          # Clean up temporary data
          <>{}{}{}

        # Push new sign/degree of negatively smoothed knot
        >{})>)

      # Else (two twists)
      # i.e., crossing is the twist in unknot with one half-twist
      >)}{}){(<{}

        # Copy sign and degree+orientation
        (({})<<>(({}{})<

          # Move sign to left stack
          <>(<({}<>)>)

          # Move copy of configuration to left stack
          <>{}{({}<>)<>}

        # Add an additional 4*orientation to degree
        <>>(({}){}){})>)

      >)}

    # Else (one twist)
    >}{}){(<

      # Invert sign and get degree
      {}([{}]<({}<

        # Search term for other edge leading to this crossing
        <>([{}]()<>)

        # With destination on third stack:
        <>({}<

          # Find matching edge
          <>{({}({})<>[({}<>)])}{}

        # Replace destination
        {}>)

        # Move stuff back to left stack
        {({}<>)<>}<>

      # Add 3*orientation to degree
      >({})({}){})>)

    >)}{}

  # Else (no crossings)
  >)}{}){{}

    # If this came from the 2-twist case, undo splitting.
    # If this came from an initial empty input, use implicit zeros to not join anything
    # New sign = sign - 2 * next entry sign
    (([{}]){}<>{}{}<

      # New degree = average of both degrees
      <>({}<>{})

      # Find coefficient corresponding to degree
      {([{}]({}()()<{}({}<>)(())<>>))}{}{}

    # Add sign to coefficient
    {}>{})

    # Move rest of polynomial back to right stack
    (())<>{{}({}<>)(())<>}

    # Set up next configuration
    (<>)<>

  }{}

}{}{}<>{}

# Step 3: Put polynomial in correct form

# Keeping constant term:
{}({}<

  # Move to other stack to get access to terms of highest absolute degree
  {{}({}<>)(())<>}<>

  # Remove outer zeros
  {{}{((<(())>))}{}}

  # Move back to right stack to get access to lower order terms
  {}{{}({}<>)(())<>}

>)<>

# While terms remain:
{

  # Move term with positive coefficient
  {}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}

  # Move term with negative coefficient
  {}({}<>)<>

}<>