Узловатая ситуация

34

Учитывая нотацию Даукера на узел и его знаки пересечения, вычислите его полином для скобок.

Хотя есть и более технические определения, для этой задачи достаточно думать о узле как о чем-то, что сделано физически, соединяя два конца струны вместе. Поскольку сучки существуют в трех измерениях, когда мы рисуем их на бумаге, мы используем диаграммы узлов - двухмерные проекции, в которых пересечения имеют ровно две линии, одну сверху и одну снизу.

введите описание изображения здесь

Здесь (б) и (в) - разные диаграммы одного и того же узла.

Как мы представляем диаграмму узлов на бумаге? Большинство из нас не Рембрандт, поэтому мы полагаемся на нотацию Даукера , которая работает следующим образом:

Выберите произвольную отправную точку на узле. Переместить в произвольном направлении вдоль узла и количества переездов вы столкнулись, начиная с 1, со следующими изменениями: если это четное число , и вы в настоящее время происходит через переправу, отрицающий , что даже число. Наконец, выберите четные числа, соответствующие 1, 3, 5 и т. Д.

Давайте попробуем пример:

введите описание изображения здесь

На этом узле мы выбрали «1» в качестве отправной точки и продолжили движение вверх и вправо. Каждый раз , когда мы более или под другой куском веревки, мы относим точку пересечения следующего натуральное число. Мы отрицаем четные числа, соответствующие нитям, которые проходят через пересечение, например, [3,-12]на диаграмме. Таким образом, эта диаграмма будет представлена [[1,6],[2,5],[3,-12],[-4,9],[7,8],[-10,11]]. Список друзей 1, 3, 5, 7 и т. Д. Дает нам [6,-12,2,8,-4,-10].

Здесь есть несколько вещей, на которые стоит обратить внимание. Во-первых, нотация Даукера не является уникальной для данного узла, так как мы можем выбрать произвольную начальную точку и направление. Но, учитывая обозначения, можно полностью определить структуру узла (технически, вплоть до отражения его основных компонентов узла). Хотя не все нотации Даукера могут образовывать возможные узлы, в этой задаче вы можете предположить, что ввод представляет собой действительный узел.

Чтобы избежать неоднозначности между отражениями узла и облегчить решение задачи, вам также будет предоставлен список знаков пересечения в качестве входных данных.

введите описание изображения здесь

При положительном пересечении нижняя линия идет влево с точки зрения верхней линии. В отрицательном пересечении это идет направо. Обратите внимание , что изменения направления обхода узел (т.е. задним ходом как по линии и под линией) не меняет знаки пересечения. В нашем примере знаки пересечения есть [-1,-1,-1,1,-1,1]. Они даны в том же порядке, что и нотация Даукера, т. Е. Для пересечений с номерами 1, 3, 5, 7 и т. Д.

A

DD

введите описание изображения здесь

  1. Единственный цикл без каких-либо пересечений имеет полином 1.

  2. DDD(A2A2)

  3. Dвведите описание изображения здесь

введите описание изображения здесь

На изображении выше контурное пересечение на первой диаграмме, имеющее форму введите описание изображения здесь, может быть преобразовано в введите описание изображения здеськак на втором рисунке (так называемое положительное сглаживание ), введите описание изображения здесьтак и в третьем рисунке ( отрицательное сглаживание ).

AA1

введите описание изображения здесь

Смущены еще? Давайте сделаем пример, пытаясь найти скобочный многочлен введите описание изображения здесь(Примечание: это два узла, связанные вместе. Этот вид диаграммы не будет потенциальным входным параметром в этой задаче, так как входные данные будут только одиночными узлами, но он может выглядеть как промежуточный результат в алгоритме.)

Сначала мы используем правило 3

введите описание изображения здесь

Мы снова используем правило 3 на обоих новых узлах

введите описание изображения здесь

Подставим эти 4 новых узла в первое уравнение.

введите описание изображения здесь

Применяя правила 1 и 2 к этим 4, сообщите нам

введите описание изображения здесь

Итак, это скажите нам

введите описание изображения здесь

Поздравляю с завершением краткого введения в теорию узлов!

вход

Два списка:

  • Даукер обозначения, например [6,-12,2,8,-4,-10]. Нумерация пересечений должна начинаться с 1. Соответствующие нечетные числа [1,3,5,7,...]неявны и не должны предоставляться в качестве входных данных.

  • Знаки ( 1/ -1или, если вы предпочитаете 0/ 1или false/ trueили '+'/ '-') для пересечений, соответствующих нотации Даукера, например [-1,-1,-1,1,-1,1].

Вместо пары списков вы можете иметь список пар, например [[6,-1],[-12,-1],...

Выход

A2+5+AA3[[1,-2],[5,0],[1,1],[-1,3]]

kkkN[0,1,0,5,1,0,-1]A0

правила

Это вызов . Ни одна из стандартных лазеек не может быть использована, и библиотеки, которые имеют инструменты для вычисления нотаций Даукера или полиномов Брэкет, не могут быть использованы. (Язык, который содержит эти библиотеки, все еще может использоваться, но не библиотеки / пакеты).

тесты

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

Внешние ресурсы

Не обязательно для вызова, но если вы заинтересованы:


песочница сообщений: 1 , 2

спасибо @ChasBrown и @ H.Pwiz за обнаружение ошибки в моем определении нотации Даукера

Дон Тысяча
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Mego
1
@ngn: намного лучше! Я догадывался, что это было то, что имелось в виду, но это немного странно, чтобы выразить правильно. :)
Час Браун

Ответы:

12

Brain-Flak , 1316 байт

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

Попробуйте онлайн!

Я ни о чем не жалею. Ввод представляет собой плоский список пар.

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

}<>
Nitrodon
источник
Whoaaaaaa. Фантастика!!!! +1
Дон Тысяча
Я чувствую, что мне нужно раздать еще одну награду
Дон Тысяча