14
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ I do like this challenge, and the test cases make it clear, but it might be an idea to include a little picture or scheme to visually explain how the 'palindrome distance' (including the weighting) is calculated. Some people (like me!) find a long sigma-notation formula quite daunting! \$\endgroup\$ – Dominic van Essen Oct 2 at 10:32
  • \$\begingroup\$ @DominicvanEssen Thank you for your suggestion, I'll have it in mind when designing other challenges! \$\endgroup\$ – Galen Ivanov Oct 2 at 10:42

15 Answers 15

9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Can you add an explanation? I know some Haskell but don't understand all the features used here. \$\endgroup\$ – Jonah Oct 3 at 4:42
  • 1
    \$\begingroup\$ @Jonah This answer is in my opinion quite complex. It does a number of weird things just because they save bytes. I don't know how helpful an explanation I can write because even if you do understand Haskell 100% the code doesn't implement things in a straight forward way. I will write one but it may not resolve everything so feel free to ask more specific questions. \$\endgroup\$ – Wheat Wizard Oct 3 at 13:17
7
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 47 bytes \$\endgroup\$ – Giuseppe Oct 2 at 19:32
  • \$\begingroup\$ Beautiful. I think I've never used %*% before. Thanks. \$\endgroup\$ – Dominic van Essen Oct 2 at 21:12
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Oops I posted a C answer just after you, btw you can pass string length to save something \$\endgroup\$ – AZTECCO Oct 2 at 12:22
  • \$\begingroup\$ When l is 1, l/2 is zero in the calculation, so changing l>1 to simply l saves 2 bytes, I think.. \$\endgroup\$ – Dominic van Essen Oct 2 at 12:47
  • \$\begingroup\$ @AZTECCO Same thing happened with my Python answer and ovs! T_T Thanks for the golf! :-) \$\endgroup\$ – Noodle9 Oct 2 at 13:26
  • \$\begingroup\$ @Dominic Unfortunately, that doesn't work now with passing in the string length, but thanks anyway! :-) \$\endgroup\$ – Noodle9 Oct 2 at 13:28
  • 1
    \$\begingroup\$ This is a crazy C battle! \$\endgroup\$ – Dominic van Essen Oct 2 at 21:10
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Didn't see yours, just posted more or less the same (but longer) in Python 3. \$\endgroup\$ – Noodle9 Oct 2 at 11:23
3
\$\begingroup\$

Charcoal, 22 bytes

IΣE∕θ²×⁻L∕θ²κ↔⁻℅ι℅§⮌θκ

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
  E                     Map over characters
            κ           Current index
       ⁻                Subtracted from
        L∕θ²            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
I                       Cast to string
                        Implicitly print

Alternative approach, also 22 bytes:

IΣE⮌∕⮌θ²×⊕κ↔⁻℅ι℅§⮌∕θ²κ

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

      θ                 Input string
     ⮌                  Reversed
    ∕  ²                "First" half
   ⮌                    Reversed i.e. last "half"
  E                     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
I                       Cast to string
                        Implicitly print
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

TECO, 53 Bytes

  1. Q-register A has the initialisation code.
*:ga

$$
j0uaz-1ub0uu0uw$$*
  1. 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>$$*
  1. 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
*
  1. The complete program, and its length.
*ht$$
j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>*z=$$
53
  1. 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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi, welcome to the site! Seems like a cool answer, although I don't have much experience with this language, so I can't really tell which one's the actual code (or if they're individual pieces). \$\endgroup\$ – Redwolf Programs Oct 7 at 23:40
  • 2
    \$\begingroup\$ Hi, the second line under paragraph 4., up to the asterisk is the TECO code. (For development convenience the macro is split over two Q-registers A, and M,) j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b> \$\endgroup\$ – Gunter Liszewski Oct 7 at 23:52
2
\$\begingroup\$

APL (Dyalog Unicode), 21 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Question: is it Ok to assume that you can use the length of the string as an additional input? Why doesn't the function need to calculate this itself (and include it in the byte-count)? \$\endgroup\$ – Dominic van Essen Oct 2 at 12:38
  • \$\begingroup\$ @Dominic van Essen i applied codegolf.meta.stackexchange.com/a/13262/84844 , hope it's fine also in this case \$\endgroup\$ – AZTECCO Oct 2 at 13:02
  • 1
    \$\begingroup\$ Looks fine according to the consensus, then. I guess I found it funny because I was thinking about a 'string' (so you could use strlen()), but of course this question also applies to lists of numbers... (for which the length would make sense, and also be essential). +1. \$\endgroup\$ – Dominic van Essen Oct 2 at 13:30
  • \$\begingroup\$ @Dominic van Essen yes string is a bit misleading in C because it's not a string but just a pointer. Strlen on the other hand just computes the distance between a pointer and a \0 which is usually fine on "strings" \$\endgroup\$ – AZTECCO Oct 2 at 16:17
2
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Not a Raku answer this time? :) \$\endgroup\$ – Galen Ivanov Oct 3 at 14:20
  • 1
    \$\begingroup\$ I don't think you need to map to codepoints. You can just expect integer input. \$\endgroup\$ – Wheat Wizard Oct 3 at 15:12
  • \$\begingroup\$ gives the absolute difference \$\endgroup\$ – H.PWiz Oct 4 at 9:18
  • 1
    \$\begingroup\$ Note that works for chars too. So you wouldn't need the header \$\endgroup\$ – H.PWiz Oct 4 at 9:21
1
\$\begingroup\$

Wolfram Language (Mathematica), 53 bytes

f@_:0=0
f[a_,b___,c_]:=Abs[a-c]⌈Length@a?b/2⌉+f@b

Try it online!

Takes a list of integers.

Length@a?b saves one byte over Tr[1^{a,b}]/Length[a.b] thanks to PatternTest's high precedence.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3, 59 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice use of inv \$\endgroup\$ – Galen Ivanov Oct 3 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.