Dada a notação Dowker de um nó e seus sinais de cruzamento, calcule seu polinômio entre colchetes.

Embora existam mais definições técnicas, para esse desafio, basta pensar em um nó como algo feito fisicamente, unindo as duas extremidades de uma corda. Como os nós existem em três dimensões, quando os desenhamos no papel, usamos diagramas de nós - projeções bidimensionais nas quais os cruzamentos são exatamente de duas linhas, uma acima e outra abaixo.

Aqui (b) e (c) existem diagramas diferentes do mesmo nó.

Como representamos um diagrama de nós no papel? A maioria de nós não é Rembrandt, por isso contamos com a notação Dowker , que funciona da seguinte maneira:

Escolha um ponto de partida arbitrário no nó. Mova-se em uma direção arbitrária ao longo do nó e numere os cruzamentos que encontrar, começando em 1, com a seguinte modificação: se é um número par e você está passando por cima do cruzamento, negue esse número par. Por fim, escolha os números pares correspondentes a 1, 3, 5, etc.

Vamos tentar um exemplo:

Nesse nó, escolhemos "1" como ponto de partida e passamos para cima e para a direita. Toda vez que passamos por cima ou por baixo de outro pedaço da corda, atribuímos ao ponto de cruzamento o próximo número natural. Negamos os números pares correspondentes aos fios que passam por uma passagem, por exemplo [3,-12]no diagrama. Portanto, este diagrama seria representado por [[1,6],[2,5],[3,-12],[-4,9],[7,8],[-10,11]]. Listar os amigos de 1, 3, 5, 7, etc nos dá [6,-12,2,8,-4,-10].

Há algumas coisas a serem observadas aqui. Primeiro, a notação Dowker não é exclusiva para um dado nó, pois podemos escolher um ponto de partida e uma direção arbitrários. Mas, dada a notação, pode-se determinar completamente a estrutura do nó (tecnicamente, até a reflexão de seus componentes principais do nó). Embora nem todas as notações da Dowker possam formar nós possíveis, nesse problema, você pode assumir que a entrada representa um nó real.

Para evitar a ambiguidade entre as reflexões de um nó e para facilitar o desafio, você também receberá uma lista de sinais de cruzamento como entrada.

Em um cruzamento positivo, a linha inferior vai para a esquerda do ponto de vista da linha superior. Em um cruzamento negativo, vai para a direita. Observe que reverter a direção de dar a volta no nó (ou seja, reverter a linha acima e abaixo da linha) não altera os sinais de cruzamento. No nosso exemplo, os sinais de cruzamento são [-1,-1,-1,1,-1,1]. Eles são fornecidos na mesma ordem que a notação Dowker, isto é, para cruzamentos numerados 1, 3, 5, 7, etc.

$A$

$D$$\langle D\rangle$

1. Um único loop sem cruzamentos possui o polinômio 1.

2. $D$$D$$D$$(-A^2-A^{-2})$

3. $D$

Na imagem acima, o cruzamento descrito no primeiro diagrama, que é da forma , pode ser transformado como na segunda figura (também conhecida como suavização positiva ) ou como na terceira figura ( suavização negativa ).

$A$$A^{-1}$

Confuso ainda? Vamos fazer um exemplo, tentando encontrar o polinômio do colchete de (Nota: são dois nós interligados. Esse tipo de diagrama não será uma entrada em potencial nesse desafio, pois as entradas serão apenas um nó, mas podem aparecer como um nó). resultado intermediário no algoritmo.)

Primeiro usamos a regra 3

Usamos a regra 3 novamente em ambos os novos nós

Substituímos esses 4 novos nós na primeira equação.

A aplicação das regras 1 e 2 a esses 4 nos diz

Então, isso nos diz

Parabéns por completar sua breve introdução à teoria dos nós!

Entrada

Duas listas:

• Notação Dowker, por exemplo [6,-12,2,8,-4,-10]. A numeração dos cruzamentos deve começar a partir de 1. Os números ímpares correspondentes [1,3,5,7,...]estão implícitos e não devem ser fornecidos como entrada.

• Sinais ( 1/ -1ou se você preferir 0/ 1ou false/ trueou '+'/ '-') para os cruzamentos correspondentes à notação Dowker, por exemplo [-1,-1,-1,1,-1,1].

Em vez de um par de listas, você poderia ter uma lista de pares, por exemplo [[6,-1],[-12,-1],...

Saída

$A^{-2}+5+A-A^3$[[1,-2],[5,0],[1,1],[-1,3]]

$-k\ldots k$$k\in \mathbb{N}$[0,1,0,5,1,0,-1]$A^0$

Regras

Este é um desafio do código-golfe . Nenhuma das brechas padrão pode ser usada e as bibliotecas que possuem ferramentas para calcular as notações de Dowker ou os polinômios de Bracket, não podem ser usadas. (Um idioma que contém essas bibliotecas ainda pode ser usado, mas não as bibliotecas / pacotes).

Testes

// 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"]
]

Fontes externas

Não é necessário para o desafio, mas se você estiver interessado:

• Um artigo sobre polinômios de nós

• Um artigo sobre a notação Dowker

mensagens da caixa de areia: 1 , 2

obrigado @ChasBrown e @ H.Pwiz por terem detectado um erro na minha definição de notação Dowker

K (NGN / k) , 196 193 bytes

{!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}

Experimente online!

Flak cerebral , 1316 bytes

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

Experimente online!

Não me arrependo de nada. Entrada é uma lista achatada de pares.

# 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
  {}({}<>)<>

}<>