Farigiraf my Girafarig

Question

A palindrome is a word that is its own reverse. I will define the left palindromic root of a word as the shortest prefix of the word for which the shortest possible palindrome that begins with that prefix is the original word. So the left palindromic root of racecar is race and the left palindromic root of ABBA is ABB.

The second case may not seem obvious at first, so consider this table:

Prefix | Shortest palindrome with same prefix
       |
""     | ""
"A"    | "A"
"AB"   | "ABA"
"ABB"  | "ABBA"
"ABBA" | "ABBA"

Since the shortest prefix which maps to ABBA is ABB, it is the left palindromic root of ABBA.

The process of converting from a prefix to the minimum palindrome is also called the left palindromic closure, as can be found in this related challenge.

Write the shortest code that, given a palindrome as input, returns the shortest palindrome that begins with the reverse of the left palindromic root of the input. Equivalently, find the left palindromic closure of the reverse of the left palindromic root of the input.

You may assume the input is part of some arbitrary alphabet, such as lower-case ASCII or positive integers, as long as it does not trivialise the challenge.

Test cases

girafarig -> farigiraf
farigiraf -> girafarig
racecar -> ecarace
ABBA -> BBABB
 -> 
a -> a
aa ->  aa
aba -> bab
aaa -> aaa
1233321 -> 333212333
11211 -> 2112
ABABA -> BABAB
CBABCCBABC -> CCBABCC

You can make additional cases using this program.

Answer 1

Vyxal, 12 10 9 bytes

-1 byte thanks to Jonathan Allan!

¦:R⋎ḟꜝȯḂ⋎

Test suite

Explanation

¦         # prefixes of input
 :        # duplicate
  R       # reverse of each element
   ⋎      # merge join (vectorises)
          # - combines the strings on their longest common
          #   suffix and prefix respectively
    ḟ     # find the first index of the original input
     ꜝ    # bitwise not
      ȯ   # get this last number of characters in the input
       Ḃ  # push the reverse
        ⋎ # merge join

Answer 2

Jelly, 23 bytes

^{No built-in palindromising :(}

;ⱮṚḊ$ƤŒḂƇḢȯ
ŻḊƤÇ⁼¥Ƈ⁸ḢṚÇ

A monadic Link that accepts a list of characters and yields a list of characters.

Try it online! Or see the test-suite.

How?

;ⱮṚḊ$ƤŒḂƇḢȯ - Helper Link: get shortest palindrome: left palindromic prefix, S
     Ƥ      - for prefixes (of S):
    $       -   last two links as a monad:
  Ṛ         -     reverse
   Ḋ        -     dequeue
 Ɱ          - (S) map (that) with:
;           -   concatenate
        Ƈ   - keep those for which:
      ŒḂ    -   is palindrome?
         Ḣ  - head (Note: when S='' we head [] and get zero)
          ȯ - (that) logical OR (S) (deal with that zero)

ŻḊƤÇ⁼¥Ƈ⁸ḢṚÇ - Main Link: palindrome, P
Ż           - prepend a zero
  Ƥ         - for prefixes (of that):
 Ḋ          -   dequeue
      Ƈ     - keep those for which:
     ¥ ⁸    -   last two links as a monad - f(X=that, P):
   Ç        -     call Helper (X)
    ⁼       -     equals (P)?
        Ḣ   - head
         Ṛ  - reverse
          Ç - call Helper

Answer 3

JavaScript (ES6), 113 bytes

Essentially a port of the Python program provided by the OP. Although I did find shorter methods, I've yet to find a working shorter method.

s=>[...s].some(c=>(F=S=>[...S].some(c=>[p+R==(Q=S+q)][q=c+q,p+=c,0],p=q='')&&Q)(S+=c,R=c+R)==s,R=S='')?F(R,R=S):s

Try it online!

Answer 4

Japt, 33 bytes

U{ÊÆê jUÊXÃfêS Ì
©å+ æ_gV ¥UÃÔgV

Try it

Try all test cases

Explanation:

/n               # Store input as U


U{ÊÆê jUÊXÃfêS Ì # Define a function V which calculates left palindromic closure

U{               # Start defining a function with one input named U
  Ê              # Get the length of U
   Æ      Ã      # For each number X in the range [0...length):
    ê            #  U palindromized
      j  X       #  Remove X characters
       UÊ        #  Starting at index "length of U"
           fêS   # Keep the ones which are palindromes
               Ì # Return the last (shortest) one


©å+ æ_gV ¥UÃÔgV  # Main program

©                # Return U if it is an empty string
 å+              # Otherwise get the prefixes of U
    æ_     Ã     # Find the first (shortest) one where:
      gV         #  The left palindromic closure
         ¥U      #  Is U
            Ô    # Reverse it
             gV  # Return its left palindromic closure

Answer 5

05AB1E, 30 23 22 bytes

ηε‚ε瀨íyì.ΔÂQ]ʒнQ}нθ

Iterative port of the example implementation.

Try it online or verify all test cases.

Explanation:

η            # Get the prefixes of the (implicit) input-string
 ε           # Map over each prefix:
  Â          #  Bifurcate it; short for Duplicate & Reverse copy
   ‚         #  Pair the two together
    ε        #  Map over this pair:
     η       #   Get the prefixes of the current string
      ۬     #   Remove the last character from each prefix
        í    #   Reverse each
         yì  #   Prepend the current string to each
     .Δ      #   Find the first that's truthy for:
       ÂQ    #    Check if it's a palindrome:
       Â     #     Bifurcate; short for Duplicate & Reverse copy
        Q    #     Check if the two strings are the same, thus a palindrome
 ]           # Close the find_first and nested maps
  ʒ  }н      # Find the first pair that's truthy for†:
   н         #  Where the first palindrome in the pair
    Q        #  Equals the (implicit) input-string
       θ     # Only leave the last/second palindrome of the found result-pair
             # (which is output implicitly as result)

NOTE: The empty input "" perhaps requires an additional explanation for the execution path it follows:

1. η on an empty string becomes [], so it won't execute the nested maps ε‚ε瀨íyì.ΔÂQ] and remains [] after it.
2. It also won't enter the filter ʒнQ}, so again remains [].
3. н on an empty list will result in an empty string.
4. θ on an empty string is basically a no-op.

† If I'd used .ΔнQ} ('find first' builtin) instead of ʒнQ}н (filter + 'keep first' builtins), which I initially had when I was working on golfing my program, it would have resulted in -1 for the empty list [], incorrectly giving an output of 1 after the 'keep last' builtin θ.

Answer 6

Retina, 102 90 bytes

L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$&$' $' $^$`
0G`( .*)\1
r`((?(2)$)(?<-2>\2)*.?(.)*) .*
$1$^$`

Try it online! Link includes test cases. Input cannot contain spaces. Explanation:

L$vr`(?(1)$)(?<-1>\1)*.?(.)*

Find the longest palindromic suffix of each prefix of the input.

$&$' $' $^$`

For each match, make a list of the match and its suffix, another copy of the suffix and the reversed prefix. We'll check that the latter two are the same below, after which we know that the match and its suffix is the same as the reverse of the match with its prefix.

0G`( .*)\1

Keep only the result of the match with the shortest prefix that equals its suffix. This means that the left palindromic closure of the match with its prefix is the original input, but also it means that the match and its suffix is the reverse of the match with its prefix, thus avoiding manually reversing it.

r`((?(2)$)(?<-2>\2)*.?(.)*) .*

Find the longest palindromic suffix of the reversed prefix.

$1$^$`

Outputs its palindromic closure and delete the suffix and reversed prefix of the match.

Instead of taking the left palindromic closure of the reverse of the left palindromic root, it's also possible to take the right palindromic closure of the left palindromic root for the same byte count:

L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$`$& $' $^$`
0L$`(.*)( .*)\2
$1
^(.)*.?(?<-1>\1)*(?(1)^)
$^$=

Try it online! Link includes test cases. Input cannot contain spaces. Explanation:

L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$`$& $' $^$`

As above, but directly taking the match with its prefix instead of the match and its suffix.

0L$`(.*)( .*)\2
$1

As above, but removing the suffix and reversed prefix.

^(.)*.?(?<-1>\1)*(?(1)^)
$^$=

Output the right palindromic closure by replacing the longest palindromic prefix with the reverse of the whole value.

Answer 7

Charcoal, 48 bytes

∨⌊ΦＥθ…θ⊕κ⁼⊗⊕κＬ⁺θ⊟ΦＥι…⮌ι⊕μ⁼λ⮌λω‖ＯＯ←Ｌ⊟ΦＥ⊕ⅈ…ＫＡκ⁼ι⮌ι

Attempt This Online! Link is to verbose version of code. Explanation:

∨⌊ΦＥθ…θ⊕κ⁼⊗⊕κＬ⁺θ⊟ΦＥι…⮌ι⊕μ⁼λ⮌λω

Output the shortest prefix whose palindromic closure equals the input to the canvas. This is calculated as the length of longest palindromic suffix of the prefix plus the length of the input equals twice the length of the prefix.

‖ＯＯ←Ｌ⊟ΦＥ⊕ⅈ…ＫＡκ⁼ι⮌ι

Calculate the length of the longest palindromic prefix of the prefix and reflect the canvas to the left with that amount of overlap, thus generating its right palindromic closure.