Palindrome distance

Question

Find what is the distance for a given string to its closest palindrome of the same length.

For this task I decided to give the characters further away from the string's center more weight (think of it as contributing more torque), proportional to their distance to the center.

Let's define the palindrome distance for a string \$s\$ as the sum of all products of the absolute difference of the corresponding pairs, equally spaced from the string's centre, and their distance to the center.

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

where \$l\$ is the length of \$s\$ and \$d = \left\lfloor\frac{l}{2}\right\rfloor\$

Since the middle character doesn't contribute anything to the sum, \$d\$ for strings with odd length \$l\$ is equal to \$d\$ for strings with length \$l-1\$.

Task

Given string \$s\$ with length > 1 find \$D_p(s)\$

Input

One of the following:

• a string;
• a list of characters;
• a list of numbers.

Output

An integer - the palindrome distance of the input string.

Test cases

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

Winning criteria

The shortest code in bytes in every language wins.

Sandbox

Answer 1

Haskell, 50 bytes

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

Try it online!

Look ma! No multiplication! (or division)

Explanation

Rather than explain what this answer does which I think would only be confusing, I think I will give an abridged explanation how I came to this answer.

First off Haskell is a recursive language, so we want to phrase this in a recursive way. This is pretty easy to do, if we have a list

[ a , d... , c ]

Then we take the "palindrome distance" of the middle bit d and add on abs(a-c)*(div(length d)2). If it is anything else the answer is zero.

Now getting the last element is a little hard in Haskell, but getting the first is dead simple. So one way to get the last element is to reverse the list and get the first one. In order to get the middle we then have to reverse that back to the original order.

Our first breakthrough is to realize that when you reverse a string its "palindrome distance" doesn't change. So we don't have to reverse the middle part back to its original order since computing on the reversed order will give the correct result anyway.

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

So all in all our code is:

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

Ok but length and div are kind of costly. The number of steps left is really just the thing we are looking for so what if we used that to help us.

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

Well that didn't help, but we are onto something here. Multiplication is just repeated addition, so what we really want is to add abs(a-c) once for each remaining iteration. So why don't we keep track of the numbers we want to add and just keep adding them on the way down.

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

So here we have this extra argument u which is just the list of all the absolute differences so far. And each iteration we add the sum of these to the result of the next iteration. This way each difference gets added as many times the number of steps from the center, in essence multiplying it by its distance from the center.

Of course since we are only ever asking u for its sum we don't actually need to separate the values we can just keep track of the running sum to save some bytes.

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

And this gives us the final code.

Answer 2

05AB1E, 8 bytes

-1 byte thanks to Kevin Cruijssen for reminding me that input can be taken as lists of integers.

Âα2äθā*O

Try it online!

Commented:

           # 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

R, 50 47 bytes

Edit: -3 bytes thanks to Giuseppe by using %*% operator to calculate inner product of vectors, rather than summing the product of elements as separate operations

abs((rev(x<-scan())-x)[(y=sum(x|1)/2):1])%*%1:y

Try it online!

Accepts list of numbers.

Un-golfed code:

x=scan()                # x is vector of numbers
y=sum(x|1)/2)           # y is half the length of x
sum(                    # return the sum of...
 abs(                   # the absolute values of...
  (x-rev(x))            # the differences between each element of x
                        # and the same elements reversed...
   [y:1]                # at positions y..1
                        # (so only the first half, backwards)...
    *1:y))              # multiplied by 1..y

Answer 4

C (gcc), ^{74 \$\cdots\$ 52} 51 bytes

Saved 6 7 bytes thanks to AZTECCO!!!
Saved 9 a whooping 15 bytes thanks to Dominic van Essen!!!

f(s,l)int*s;{l=l>1?l/2*abs(*s++-s[l-=2])+f(s,l):0;}

Try it online!

Port of my Python 3 answer.

Answer 5

JavaScript (ES6),  61  57 bytes

Expects a list of ASCII codes.

f=a=>1/a?0:(a.length>>1)*Math.abs(a.shift()-a.pop())+f(a)

Try it online!

How?

This is a pretty straightforward recursive implementation that removes the first and the last entry from the list at each iteration, computes the absolute value of their difference and applies the weight \$\lfloor L/2 \rfloor\$, where \$L\$ is the length of the list before the items are removed.

The halting criterion 1 / a is truthy if either:

• a[] is empty, in which case 1 / a == Infinity. This happens when the length of the input list is even.

• Or a[] is a singleton integer, which happens if the length of the list is odd. We can safely stop the recursion without any other calculation because a single character is a palindrome and we already have the final result at this point.

Answer 6

Python 2, 57 54 bytes

A recursive function that takes input as a list of integers.

f=lambda l:l>[]and len(l)/2*abs(l[0]-l[-1])+f(l[1:-1])

Try it online!

The last part could also be abs(l[0]-l.pop())+f(l[1:]) at the same length.

---

Python 2, 57 bytes

A slightly longer approach without recursion.

lambda l:eval(len(l)/2*'+len(l)/2*abs(l.pop(0)-l.pop())')

Try it online!

Answer 7

Charcoal, 22 bytes

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

Try it online! Link is to verbose version of code. Takes input as a string (halving a string is golfier than halving an array). Explanation:

    θ                   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

Alternative approach, also 22 bytes:

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

Try it online! Link is to verbose version of code. Explanation:

      θ                 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

Answer 8

TECO, 53 Bytes

1. Q-register A has the initialisation code.

*:ga

$$
j0uaz-1ub0uu0uw$$*

2. Q-register M adds it all up. The result remains in Q-register W.

:gm$$


z/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>$$*

3. An Example to calculate the \$D_p\$ of “Neveroddoreven”: kill the whole buffer, insert your word, initialise registers A,B,U, and W and jump to the beginning of the buffer; then iterate z/2 times, accumulating into register W; finally show the numeric content of register W.

hkiNeveroddoreven$mamm$$
*qw=$$
224
*

4. The complete program, and its length.

*ht$$
j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>*z=$$
53

5. The test cases.

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

This shows a TECO session of inserting each test word into the emptied edit buffer, then calling the macros of Q-registers A and M, and finally showing the \$D_p\$ that was accumulated in the numeric Q-register W.

*hkiaa$mammqw=$$
0
*hkibab$mammqw=$$
0
*hkiabca$mammqw=$$
1
*hkicbade$mammqw=$$
6
*hkihello$mammqw=$$
21
*hkicode-golf$mammqw=$$
45
*hkineveroddoreven$mammqw=$$
0
*hkiNeveroddoreven$mammqw=$$
224

Answer 9

APL (Dyalog Unicode), 21 bytes

{+/|⍵×⍳≢⍵}(⌈2÷⍨⍴)↓⊢-⌽

Try it online!

Answer 10

C (gcc), 55 52 bytes

f(a,z)char*a;{z=z/2?z/2*abs(*a++-a[z-=2])+f(a,z):0;}

Try it online!

• Saved a bit stealing from @Noodle9 and rearrangements

f(a,z)char*a;{z=  - function tacking a C-string pointer and its length
                    and returning trough eax register.

z/2?         - if not in the centre :
f(a+1,z-2)   >  recursively call with pointer moved and length decreased 
+abs(*a-a[z-1])*(z/2)  
              - add value of pairs
:0;}         >  else initialize r to 0

Answer 11

Jelly, 7 bytes

ạṚŒHṪḋJ

A monadic Link accepting a list of integers which yields an integer.

Try it online!

How?

ạṚŒHṪḋJ - Link: list of integers, A   e.g. (Abracadabra) [65,98,114,97,99,97,100,97,98,114,97]
 Ṛ      - reverse (A)                                    [97,114,98,97,100,97,99,97,114,98,65]
ạ       - absolute difference (vectorises)               [32,16,16,0,1,0,1,0,16,16,32]
  ŒH    - split in two (1st part longest, if any)        [[32,16,16,0,1,0],[1,0,16,16,32]]
    Ṫ   - tail                                           [1,0,16,16,32]
      J - range of length (of A)                         [1,2,3,4,5,6,7,8,9,10,11]
     ḋ  - dot-product                                    273 (= 1×1+0×2+16×3+16×4+32×5+0×6+...0×11)

Answer 12

J, 24 bytes

+/@(#\.@]*|@-)&(,~inv)|.

Try it online!

Takes input as list of integers.

Another one of those interesting problems that is unexpectedly difficult to express tersely in J. I tried a few approaches and this is my best attempt.

how

• (...)|. The whole phrase is a hook, which means the original input and that input reversed |. will be passed as the left and right arguments, respectively, to the phrase in parentheses.
• (...)&(,~inv) The compose conjunction & transforms both arguments with the specified verb, in this case ,~inv.
  • ,~inv is the inverse of the verb that doubles a list by self-appending ,~. The inverse of that operation is to take the first half of the list, and it happens to "round down" for odd lists, which is what we want here.
• #\.@]*|@- Multiply #\.@] element-wise by |@-
  • |@- subtract the two list arguments element-wise and take the absolute value |. These are the "distances".
  • #\.@] produces, eg, 4 3 2 1 if the lists have length 4. It does this by taking the suffix lengths #\. of the right argument ]. We could have used the left argument just as well here.
• +/@ Sum the result

---

For comparison, the APL solution converted into J is 25 bytes:

>.@-:@#(1#.]*&|#\)@}.]-|.

Try it online!

Answer 13

Husk, 14 12 11 bytes

-2 thanks to Wheat Wizard pointing out you can take input as a list of codepoints

and -1 thanks to HP.Wiz showing that ≠ does absolute difference not just inequality

ΣFoz*ŀ½Sz≠↔

Try it online!

Explanation

       Sz≠      Zip absolute difference the list from
          ↔    The reverse of the list
      ½         Split the list into two halves (with the longer being the first)
 F              Reduce by
  o  ŀ          Converting the first half to range(1, length)
   z*           And zip multiplying with the second half
Σ               Finally sum the absolute values

Answer 14

Python 3, 59 bytes

f=lambda l:len(l)>1and len(l)//2*abs(l.pop(0)-l.pop())+f(l)

Try it online!

Answer 15

JavaScript (Node.js), 53 bytes

f=(a,n=0)=>1/a?n:n+f(a,n+Math.abs(a.shift()-a.pop()))

Try it online!

From Arnauld's

Answer 16

Wolfram Language (Mathematica), 53 45 43 bytes

Apparently left a l= in for no reason.

Sum[Abs[#[[i]]-#[[-i]]],{,Tr[1^#]/2},{i,}]&

Try it online!

Input a list of integers.

$$\sum_{i=1}^{d}\left(d-i+1\right)|s_i-s_{l-i+1}|=\sum_{j=1}^{d}\sum_{i=1}^{j}|s_i-s_{l-i+1}|.$$