简化循环

Question

或者:我忘记了我在沙箱里遇到的一个挑战，是关于离散数学的东西，就像5-6个月前我学到的，有点不记得了。

给定在图上形成圈的顶点的路径，输出循环的一个简单版本。也就是说，如果一个顶点出现了两次，那么在两个外观之间剪掉这个部分。

上下文

设u和v是图G的顶点。如果有一个从u到v of length n的循环，那么就会存在一个简单的循环，从u到具有length \le n的v。

这是因为任何具有顶点访问两次的循环v_1, e_1, v_2, e_2, ..., e_m, v_m (即v_i = v_j对G中的某些v_i和v_j，其中的i < j)可以简化为v_1, e_1, ..., e_i, v_j, e_{j+1}，并且仍然是u和v之间的一个有效循环。

为了应对这一挑战，将忽略连接顶点的边，因为在顶点之间所取的边是任意的。

工作示例

取图K_5：

顶点1和3之间的一个循环可能如下所示：

也就是说，所走的道路是[1, 2, 5, 4, 2, 3, 5]。然而，这一周期可以简化为：

它有路径[1, 2, 3, 5]。这个循环是一个简单的循环，因为只有第一个顶点和最后一个顶点是相等的。

请注意，周期是按其出现的顺序缩短的。

规则

• 在输入中总是有一个更简单的循环。
• 输入将是图中的顶点列表。你是否把这些当作数字、字符或其他方式取决于你。
• 总有至少两个顶点。
• 每个顶点都有度>= 2。
• 输入和输出可以以任何合理和方便的格式提供。
• 由于输入代表一个周期，因此周期的开始和结束的顶点将不在输入中。
• 输入中不会有多个重叠的简化路径。
• 每个输入只有一个输出。

注意，简单循环可能不是最短周期，最短周期可能不是简单循环。

测试用例

假设数字被用作顶点标签

[1,2,3,4,2,5] -> [1,2,5]
[4,3,6,2,3,8,5,2,8,7] -> [4,3,8,7]
[1,1,2] -> [1,2]
[1,2,7,2,7,2,3,7] -> [1,2,3,7]

这是代码高尔夫，所以请确保简化了答案的字节计数。

Answer 1

JavaScript (Node.js)，35字节

f=a=>a&&a[0]+f(a.split(a[0]).pop())

在网上试试！链接包括测试用例。将输入作为字符串接受。

Answer 2

Python3.8 (预发行版)，67字节

f=lambda x,b=[]:x and f(x[len(x)-x[::-1].index(x[0]):],b+x[:1])or b

在网上试试！

反向查找方法我们找到最后一次，然后跳过去。

Python3.8 (预发行版)，78字节

f=lambda x,b=[]:x and f(x[1:],(b[:b.index(x[0])]if x[0]in b else b)+x[:1])or b

在网上试试！

获取整数列表。

如果我们遇到一个我们已经通过的元素，我们就会修剪它们之间的所有元素。

Answer 3

05AB1E，14 字节数

.œR.Δε¬Qθ}P}€н

在网上试试或验证所有测试用例.

解释：

.œ         # Get all partitions of the (implicit) input-list
  R.Δ      # Find the last one (first one of the reversed list) that's truthy for:
     ε     #  Map over each part of the current partition:
      ¬    #   Get the head (without popping the list)
       Qθ  #   Check if it's equal to the last item in the list
     }P    #  After the map: check if all parts were truthy by taking the product
    }€     # After the findFirst, map over the parts of the found partition:
      н    #  Only leave their first integer
           # (after which this list is output implicitly as result)