回文距离

Question

查找给定字符串到其长度相同的最近回文的距离。

在这个任务中，我决定让字符远离字符串的中心更多的重量(把它看作是贡献更多的扭矩)，与它们与中心的距离成比例。

让我们将字符串s的回文距离定义为对应对的绝对差的所有乘积之和，与字符串的中心等距，以及它们到中心的距离。

D_p=\displaystyle\sum_{i=1}^{d}\left(d-i+1\right)|s_i-s_{l-i+1}|

其中l是s和d = \left\lfloor\frac{l}{2}\right\rfloor的长度

由于中间字符对和没有任何贡献，所以对于长度为奇数l的字符串，D6为d，对于长度为l-1的字符串，为D7。

任务

给定长度>1的字符串s查找D_p(s)

输入

下列之一：

• 一根绳子；
• 一份字符列表；
• 一张号码列表。

输出

整数-输入字符串的回文距离。

测试用例

"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224

获奖标准

每种语言中以字节为单位的最短代码获胜。

沙盒

Answer 1

哈斯克尔，50字节

u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
(0#)

在网上试试！

看妈妈！没有乘法！(或分部)

解释

与其解释我认为只会令人费解的答案，我想我会简单地解释一下我是如何得出这个答案的。

首先，Haskell是一种递归语言，所以我们想用递归的方式来表达它。如果我们有一个清单，这很容易做到。

[ a , d... , c ]

然后取中间位d的“回文距离”，在abs(a-c)*(div(length d)2)上加法。如果是其他的话，答案是零。

在Haskell中，获得最后一个元素有点困难，但是获得第一个元素非常简单。因此，获得最后一个元素的一种方法是反转列表，得到第一个元素。为了得到中间位置，我们必须将其反转回原来的顺序。

我们的第一个突破是要认识到，当你反转一个字符串时，它的“回文距离”不会改变。所以我们不需要将中间部分反回到它原来的顺序，因为对倒序的计算无论如何都会给出正确的结果。

f(a:b)|c:d<-reverse b= ...

所以我们所有的代码都是：

f(a:b)|c:d<-reverse b=f d+abs(a-c)*div(length d)2
f _=0

好的，但是length和div有点贵。剩下的步骤实际上就是我们正在寻找的东西，所以如果我们用它来帮助我们，该怎么办？

f(a:b)|c:d<-reverse b,(k,n)=(k+abs(a-c)*n,n+1)
f _=(0,1)
g=fst.f

这没什么用，但我们正在查些东西。乘法只是重复的加法，所以我们真正想要的是为剩下的每一次迭代添加一次abs(a-c)。那么，我们为什么不跟踪我们想要添加的数字，然后在下降的过程中继续添加它们。

u#(a:b)|c:d<-reverse b=sum u+(abs(c-a):u)#d
u#_=sum u
g=([]#)

这里我们有一个额外的参数，u，它只是到目前为止所有绝对差异的列表。每次迭代，我们将它们的和加到下一次迭代的结果中。通过这种方式，每个差异都会被添加到距离中心的步骤数的多倍，实质上是将其与中心的距离相乘。

当然，由于我们只要求u的和，我们实际上不需要分离值，我们只需要跟踪运行的和来保存一些字节。

u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
g=(0#)

这给了我们最后的密码。

Answer 2

05AB1E，8字节

-1字节，感谢凯文·克鲁伊森提醒我输入可以作为整数列表。

Âα2äθā*O

在网上试试！

注释：

           # implicit input: a list of codepoints
          # push codepoints and codepoints reversed
 α         # take the (element-wise) absolute difference
  2ä       # split into 2 pieces
           # the last one will be shorter for odd lengths
    θ      # take the last piece
     ā     # length-range: [1, ..., length] (doesn't pop the TOS)
      *    # multiply element-wise
       O   # take the sum

Answer 3

木炭，22字节

ＩΣＥ∕θ²×⁻Ｌ∕θ²κ↔⁻℅ι℅§⮌θκ

在网上试试！链接是详细的代码版本。将输入作为字符串(将字符串减半比将数组减半)。解释：

    θ                   Input string
   ∕ ²                  First half
  Ｅ                     Map over characters
            κ           Current index
       ⁻                Subtracted from
        Ｌ∕θ²            Length of half of string
      ×                 Multiplied by
             ↔⁻         Absolute difference of
               ℅ ℅      Ordinals of
                ι       Current character and
                  §     Character at
                     κ  Current index in
                   ⮌    Reversed
                    θ   Input string
 Σ                      Take the sum
Ｉ                       Cast to string
                        Implicitly print

替代方法，也是22个字节：

ＩΣＥ⮌∕⮌θ²×⊕κ↔⁻℅ι℅§⮌∕θ²κ

在网上试试！链接是详细的代码版本。解释：

      θ                 Input string
     ⮌                  Reversed
    ∕  ²                "First" half
   ⮌                    Reversed i.e. last "half"
  Ｅ                     Map over characters
          κ             Current index
         ⊕              Incremented
        ×               Multiplied by
           ↔⁻           Absolute difference of
             ℅ ℅        Ordinals of
              ι         Current character and
                §       Character at
                     κ  Current index in
                 ⮌      Reversed
                  ∕θ²   First half of input string
 Σ                      Take the sum
Ｉ                       Cast to string
                        Implicitly print