24
\$\begingroup\$

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
\$\endgroup\$
10
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – Fmbalbuena
    Dec 19, 2021 at 1:17
  • \$\begingroup\$ Can we output 0 for false, and non-zero for true? \$\endgroup\$ Dec 19, 2021 at 1:21
  • \$\begingroup\$ @cairdcoinheringaahing yes because i said Truthy, not 1 \$\endgroup\$
    – Fmbalbuena
    Dec 19, 2021 at 1:21
  • 6
    \$\begingroup\$ In the other words: is there a strict prefix of input string is its suffix? \$\endgroup\$
    – tsh
    Dec 19, 2021 at 4:09
  • 1
    \$\begingroup\$ Isn't this a decision-problem? \$\endgroup\$
    – hakr14
    Feb 3 at 19:07

27 Answers 27

14
\$\begingroup\$

Retina, 10 bytes

^(.+).*\1$

Try it online!

Works in any flavor of regex that supports backreferences.

\$\endgroup\$
2
  • \$\begingroup\$ How do you found this? \$\endgroup\$
    – Fmbalbuena
    Dec 19, 2021 at 16:23
  • \$\begingroup\$ @Fmbalbuena Suppose there exists a string s that can be reshaped to form our input string. Then the input matches (s)+A=(AB)+A, where A is some nonempty prefix of s and B is the possibly-empty remainder. This means the input starts and ends with two non-overlapping instances of that prefix A, so this regex matches strings consisting of a nonempty prefix A ((.+)), followed by a possibly-empty middle section (.*), followed by that same nonempty prefix A (\1) again. \$\endgroup\$
    – att
    Dec 20, 2021 at 2:09
9
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

Ruby -n, 15+1 bytes

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

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Flags don't count towards scoring, so you can remove the +1 \$\endgroup\$
    – pxeger
    Dec 20, 2021 at 2:24
7
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ You should return same value of Truthy. \$\endgroup\$
    – Fmbalbuena
    Dec 19, 2021 at 1:34
  • \$\begingroup\$ @Fmbalbuena Corrected \$\endgroup\$ Dec 19, 2021 at 1:34
  • \$\begingroup\$ FGITWing in 1 minute. \$\endgroup\$
    – Fmbalbuena
    Dec 19, 2021 at 1:39
5
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can save two bytes by assigning the length of x to a name in a guard: f x|l<-length x=or[x==take l(cycle$take n x)|n<-[1..l-1]] \$\endgroup\$
    – ovs
    Dec 19, 2021 at 14:03
  • \$\begingroup\$ Ah, that's clever! I should review how guards work in Haskell... Thanks for the save! \$\endgroup\$ Dec 19, 2021 at 18:37
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

BQN, 11 bytesSBCS

⊑⋈∊≠⥊¨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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I would argue you don't need the as a singleton list is an accepted return value by default, and 1↓¯1↓↑ can be shortened to 2↓»∘↑ (or ¯1↓∾`). \$\endgroup\$
    – ovs
    Dec 19, 2021 at 9:33
3
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ I actually worked that out over an hour before his comment, sigh... \$\endgroup\$
    – Neil
    Dec 19, 2021 at 11:40
  • \$\begingroup\$ @Neil - I do apologize, and I've credited your approach now. I usually try to answer before checking the other answers first, so I saw tsh's comment before your answer. \$\endgroup\$ Dec 19, 2021 at 17:01
  • \$\begingroup\$ No need to apologise; I blame @tsh anyway. \$\endgroup\$
    – Neil
    Dec 19, 2021 at 17:37
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Python 3, 49 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ Actually, the same regex was already used by att in the Retina answer (I swear I didn't copy that, but the answer was posted before mine). \$\endgroup\$
    – G B
    Dec 19, 2021 at 18:21
  • \$\begingroup\$ But JS doesn't bind this automatically. So you cannot write something like f=/.../.test; f('yourString');. \$\endgroup\$
    – tsh
    Dec 20, 2021 at 1:25
  • \$\begingroup\$ @tsh Hm..., that's interesting. I'm not sure whether this is valid then. I'll add a version that works. \$\endgroup\$
    – emanresu A
    Dec 20, 2021 at 1:36
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice! If you don't mind even wierder (but still consistent) outputs of FALSE/NA, try this for 70 bytes... \$\endgroup\$ Dec 20, 2021 at 11:49
  • 1
    \$\begingroup\$ ...but I'm down to 69 bytes now... \$\endgroup\$ Dec 20, 2021 at 13:26
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 10 bytes

⊂∊≢⍴¨¯1↓,\

Try it online!

From Kamila's answer and upvote that!

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I think you may swap sum to any and have a simple output of TRUE/FALSE (but that doesn't save bytes...) \$\endgroup\$
    – pajonk
    Dec 20, 2021 at 13:30
  • \$\begingroup\$ @pajonk - You're right. I don't remember why I thought I needed sum in some previous version... (and never changed it since...) \$\endgroup\$ Dec 20, 2021 at 13:33
  • \$\begingroup\$ you need to output truthy as one, not non-zero. please make truthy value same \$\endgroup\$
    – Fmbalbuena
    Dec 22, 2021 at 14:53
  • \$\begingroup\$ @Fmbalbuena - no problem, fixed now. \$\endgroup\$ Dec 22, 2021 at 16:43
  • 1
    \$\begingroup\$ @DominicvanEssen nice number of bytes \$\endgroup\$
    – Fmbalbuena
    Dec 22, 2021 at 16:46
2
\$\begingroup\$

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.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why slow? time complexity? \$\endgroup\$
    – Fmbalbuena
    Feb 16 at 23:16
  • \$\begingroup\$ @Fmbalbuena Exponential... \$\endgroup\$ Feb 16 at 23:18
1
\$\begingroup\$

JavaScript (ES6), 64 bytes

-13 thanks to @pxeger

s=>[...s].some((_,i)=>!s.slice(0,i).repeat(s.length).indexOf(s))
\$\endgroup\$
2
  • \$\begingroup\$ Can't Math.ceil(s.length/i) just be s.length, because it can be repeated any number of times as long as it's at least s.length/i? \$\endgroup\$
    – pxeger
    Dec 19, 2021 at 1:32
  • \$\begingroup\$ You may change s.length to 2. Or s=>[...s].some((_,i)=>!((p=s.slice(0,i))+p).indexOf(s)). \$\endgroup\$
    – tsh
    Dec 19, 2021 at 3:56
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Ok, this is fine \$\endgroup\$
    – Fmbalbuena
    Dec 30, 2021 at 15:06
  • \$\begingroup\$ \[Infinity] is 3 bytes, and I don't see why you can't define v as a global variable. Some other basic improvements bring it to 67 bytes. \$\endgroup\$
    – att
    Feb 3 at 23:42
  • \$\begingroup\$ (Of course, the pattern matching approach is much more byte-efficient here: Try it online!) \$\endgroup\$
    – att
    Feb 3 at 23:42
  • \$\begingroup\$ Yes, both of those solutions seem far better. \$\endgroup\$
    – Romanp
    Feb 5 at 15:07
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Perfekt factor program. \$\endgroup\$
    – Fmbalbuena
    Dec 30, 2021 at 19:14
1
\$\begingroup\$

Japt -d, 6 bytes

W¶îVîW

Try it

\$\endgroup\$
1
\$\begingroup\$

Canvas, 9 bytes

[;Lm≡]k∑‼

Try it here!

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

\$\endgroup\$

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.