Check if the string is reshaped

Question

Challenge

Given an input string X, determine if X can be obtained from reshaping a strict prefix of itself (a prefix that is not X itself).

Reshaping a string to a length N means repeating the string as many times as needed and then taking the first N characters of it.

Examples:

The string "abba" returns Truthy becacause "abb" can be reshaped to length 4 to obtain "abba".

The string "acc" returns Falsy becacause none of its strict prefixes ("a", "ac") can be reshaped to obtain "acc".

(Outputs must be consistent)

Test cases:

AA => 1
ABAba => 0
!@#$%&()_+! => 1
AAc => 0
ababababba => 1
abcdeabc => 1
abacabec => 0
@|#|#|@#|@||@#@||@|#| => 1
10101101101010110101011101111011110110110101101101010110010101101101010110 => 1
17436912791279205786716328174301174187417348216070707180471896347218574617954278517034215720138543912791279205786716328174301174187417348216070707180471896347218574617954278517034215720286716328174301174187417348216070707180471896347218574617954278517034219127912792057867163281743011741874173482160707071804718963472185746179542785170342157205720475941259275912791279205786716328174301174187417348216070707180471896347218574617954278517034215720475941252867163281743011741874173482160707071804718963472185746179542785170342157204759412517436912791279205786716328174301174187417348216070707180471896347218574617954278517034215720138543912791279205786716328174301174187417348216070707180471896347218574617954278517034215720286716328174301174187417348216070707180471896347218574617954278517034219127912792057867163281743011741874173482160707071804718963472185746179542785170342157205720475941259275912791279205786716328174301174187417348216070707180471896347218574617954278517034215720475941252867163 => 1

Answer 1

Retina, 10 bytes

^(.+).*\1$

Try it online!

Works in any flavor of regex that supports backreferences.

Answer 2

Charcoal, 10 bytes

⊙θ⁼…θκ✂θ±κ

Try it online! Link is to verbose version of code. Explanation: Simply checks whether any prefix of the input is also a suffix. The edge case of the empty prefix is ignored because you can't slice an empty suffix using a negative slice offset.

 θ          Input string
⊙           All indices satisfy
    θ       Input string
   …        Truncated to length
     κ      Current index
  ⁼          Equals
       θ    Input string
      ✂     Sliced from
         κ  Current index
        ±   Negated

Answer 3

Ruby -n, 15+1 bytes

p ~/^(.+).*\1$/

Try it online!

Answer 4

Haskell, 56 bytes

f s=any(and.zipWith(==)s.cycle.(`take`s))[1..length s-1]

Try it online!

---

Haskell, 54 53 bytes

Based on Neil's answer: Checks if any proper prefix is a suffix.

import Data.List
f s=init(1<$s)>(1<$inits s\\tails s)

Try it online!

Answer 5

Jelly, 5 bytes

ṁƤinL

Try it online!

How it works

ṁƤinL - Main link. Takes a string S on the left
 Ƥ    - Over each prefix P of S:
ṁ     -   Mold to length S
  i   - First index of S
    L - Length of S
   n  - Are these two unequal?

Essentially, the index and length will only be equal if the only reshaped prefix equal to S is the full prefix i.e. a non-proper prefix

Answer 6

Haskell, 57 bytes

f x|l<-length x=or[x==take l(cycle$take n x)|n<-[1..l-1]]

Try it Online!

-2 bytes thanks to ovs

Answer 7

Vyxal r, 7 bytes

L?¦ṪvẎc

Try it Online!

   Ṫ    # All but last 
  ¦     # Of prefixes
 ?      # Of the input
    v   # Each
     Ẏ  # Extended to...
L       # Input length
      c # Includes input

Answer 8

BQN, 11 bytes^SBCS

⊑⋈∊≠⥊¨2↓»∘↑

Run online!

Notes:

A train which roughly translates to {⊑(⋈𝕩)∊(≠𝕩)⥊¨2↓»∘↑𝕩} akin to APL, except we have a single byte prefixes builtin.

-1 from ovs.

Answer 9

Brachylog, 5 bytes

~ca₀ᵈ

Try it online!

Ungodly slow on even mid-sized failing inputs; the essentially equivalent ~c₂a₀ᵈ is much more performant: Try it online!

~c       Some partition of the input
    ᵈ    is a list of two elements such that the first has the second as
  a₀     a nonempty prefix.

Answer 10

Husk, 7 bytes

ṁȯ€tṫ¹ḣ

Try it online!

Same approach as Neil's answer and tsh's comment: 'is any prefix of input string also one of its suffixes?'

ṁȯ    ḣ  # map over each of the prefixes of the input:
  €      #  is it present within...
   t     #  the tail of (=drop the first element of)...
    ṫ¹   #  the suffixes of the input?
ṁ        # sum the answers
         # (so output is non-zero (truthy) for re-shapable strings)

Answer 11

Haskell + hgl, 13 bytes

cP$h_<*h'>~ʃ

If you can simply submit a parser object, then that can be 10 bytes:

h_<*h'>~ʃ

Explanation

• h_ parses at least one thing off the front of a list (think .+ in regex).
• h' parses any amount off the front of a list (think .* in regex).
• ʃ is a function which takes an string and produces a parser which matches exactly that string.

We combine the two with <* which runs both sequentially giving the result of the first. Then we bind this to ʃ, so that the result of h_ is passed as the input to ʃ.

In do notation this would be

do x<-h_;h';ʃ x

Described in plain English this matches any string that contains the same non-empty section at both the start and end.

Non-parser, 17 15 bytes

The parsers are obviously the way to go for this challenge, but I thought I'd give it a go without them to see how good hgl does.

lt 2<(cn**sw)sx

Explanation

• sx gets all prefixes of a list
• sw checks if a particular list starts with another.
• cn counts the number of elements that satisfy a predicate.
• (**) is an infix for liftA2.

So altogether (cn**sw)sx counts the number of suffixes of the list are also prefixes.

Now, the empty string and the input string should always pass this test. So we want to test if there is another string which also is both a prefix and a suffix. So we use lt 2 to check that's greater than 2.

Notes

Some things that could have been better for hgl in this challenge.

• There should be a function lt2=lt 2 (and gt1, lt3 etc.). That would have saved a byte here.
• (**) has the default precedence which although not causing any issues here, could probably be improved.
• Variants of px and sx that give for example non-empty or strict prefixes / suffixes would probably be useful. If I had a function that specifically gave non-empty and strict suffixes then I could just do ay**sw$sxS (where sxS is the imagined function) for 10 bytes.

Answer 12

JavaScript (Node.js), 52 bytes

s=>s.replace(/./g,c=>((p+=c)+p).indexOf(s)+1,p='')>1

Try it online!

Partial based on Redwolf Programs's answer.

---

JavaScript (Node.js), 56 bytes

s=>(g=p=>s[0]&&(p+=s.shift())==(q=s.pop()+q)|g(p))(q='')

Try it online!

Answer 13

J, 11 bytes

e.#$&><\@}:

Try it online!

This one is kind of tailor made for J.

• e. Is the input an element of...
• <\@}: Each prefix except the last...
• #$&> Shaped to the original input's length.

Answer 14

Python 3, 55 bytes

lambda s:any(s in s[:x]*len(s)for x in range(1,len(s)))

Try it online!

Porting regexes are boring, so non regex one

Answer 15

Python 3, 49 bytes

f=lambda s,i=1:s>s[:i]and(s[i:]==s[:-i])|f(s,i+1)

Try it online!

Answer 16

JavaScript (ES6), 23 bytes

x=>/^(.+).*\1$/.test(x)

Try it online!

Or if a function that can't be bound to a variable is allowed, 17 bytes:

/^(.+).*\1$/.test

Try it online!

Regex completely stolen from G B's answer, go upvote that!

Answer 17

R, 74 72 70 bytes

Or R>=4.1, 63 bytes by replacing the word function with a \.

Edit: -2 bytes thanks to @Dominic van Essen.

function(s,n=sum(s|1)){for(i in 2:n)T=T&any(s[1:i-1]-s[n+2-i:1]);!T+1}

Try it online!

Non-regex approach (that would be simple port of other answers: function(s)grepl("^(.+).*\\1$",s)).

Takes input as a vector of char codes.

Outputs NA as truthy and FALSE as falsy.

Answer 18

05AB1E, 8 7 bytes

.sI¨ηåà

-1 byte by porting @Neil's Charcoal answer.

Try it online or verify all test cases.

Original 8 bytes answer:

¨ηIgδ∍Iå

Try it online or verify all test cases.

Explanation:

.s        # Get the suffixes of the (implicit) input
  I¨      # Push the input-string, and remove its last character
    η     # Get the prefixes of this string
     åà   # And check if any is in the suffixes-list
          # (after which the result is output implicitly)

¨         # Remove the last character of the (implicit) input-string
 η        # Take its prefixes
    δ     # Map over each prefix:
     ∍    #  And extend each to a length equal to
  Ig      #  the length of the input
      Iå  # Then check if the input is in this list
          # (after which the result is output implicitly)

The second program could have been 7 bytes if the input is never an integer by removing the g, because ∍ will extend to the length of given string and list arguments: verify (almost) all test cases without g, and see how it now fails for 1001 and 1101.

Answer 19

Excel, 72 bytes

=LET(x,SEQUENCE(LEN(A1)/2),OR(SUBSTITUTE(LEFT(A1,x),RIGHT(A1,x),"")=""))

Link to Spreadsheet

String comparisons in Excel are not case sensitive but SUBSTITUTE is.

Answer 20

APL (Dyalog Unicode), 10 bytes

⊂∊≢⍴¨¯1↓,\

Try it online!

From Kamila's answer and upvote that!

Answer 21

R, 77 73 69 bytes

function(s)any(grepl(s,paste0(r<-substring(s,0,nchar(s):1-1),r),f=T))

Try it online!

Outputs TRUE/FALSE.

Answer 22

JavaScript (ES6), 64 bytes

-13 thanks to @pxeger

s=>[...s].some((_,i)=>!s.slice(0,i).repeat(s.length).indexOf(s))

Answer 23

Vyxal, 9 bytes

K'?~•f⁼;₃

Try it Online!

Ah yes, the limitations of type overloading. Returns 0 for Truthy inputs and 1 for Falsey inputs.

Explained

K'?~•f⁼;₃  # Takes input as a list of characters
K          # Prefixes of the input
 '         # Keep items where:
  ?~•      #   The item molded to the shape of the input
     f⁼    #   is the same as the input (i.e. non-vectorised equality)
       ;   # Close filter.
        ₃  # Is the length of the list 1? For falsey inputs, the resulting list will just contain the input meaning it doesn't have any truthy prefixes.

Answer 24

Wolfram Language (Mathematica), 82 Characters

Try Online Practically the most basic answer I could think of. Tried some fancy things like converting into a list of characters or using some sort of trick instead of StringRepeat, but the bytes came out better this way.

Or@@Table[
StringRepeat[StringTake[#,i],∞,StringLength@#]==#,{i,StringLength@#-1}]&

Explanation: Iterates i from 1 to the length of the string - 1, and repeats the first i characters until it matches the length of the original. Then, it compares this value to the original and computes whether any of them are true.

I don't know/remember how many characters Infinity counts as, so if that's a problem, I have an 88 character solution without any special chars:

Block[{v=Characters@#}, 
Or@@Table[
    PadRight[v~Take~i,Tr[1^v],v~Take~i]==v,{i,Tr[1^v]-1}]]&

This converts the string into a list and saves it as a variable, which costs 24 characters, but makes the rest far shorter. I can't just define v as a global variable since that messes up the pure function, and writing out Characters@# is far too long to not be a variable.

Answer 25

Factor + grouping.extras math.unicode sequences.repeating, 59 bytes

[ dup head-clump 1 head* [ over length cycle = ] with ∃ ]

Try it online!

Explanation

                         ! "abba"
dup                      ! "abba" "abba"
head-clump               ! "abba" { "a" "ab" "abb" "abba" }
1 head*                  ! "abba" { "a" "ab" "abb" }
[ over length cycle = ]  ! "abba" { "a" "ab" "abb" } [ over length cycle = ]
with                     ! { "a" "ab" "abb" } [ "abba" [ over length cycle = ] swapd call ]

∃ Alias for any? -- Does the quotation return t for any elements in the sequence? Inside the quotation now for the first element...

                         ! "abba" "a"
over                     ! "abba" "a" "abba"
length                   ! "abba" "a" 4
cycle                    ! "abba" "aaaa"
=                        ! f

Second element

                         ! "abba" "ab"
over                     ! "abba" "ab" "abba"
length                   ! "abba" "ab" 4
cycle                    ! "abba" "abab"
=                        ! f

Third

                         ! "abba" "abb"
over                     ! "abba" "abb" "abba"
length                   ! "abba" "abb" 4
cycle                    ! "abba" "abba"
=                        ! t

Answer 26

Japt -d, 6 bytes

W¶îVîW

Try it

Answer 27

Canvas, 9 bytes

［；Ｌｍ≡］ｋ∑‼

Try it here!

Can remove ‼ to save a byte if any truthy output (not necessarily consistent) is allowed.