19
\$\begingroup\$

Challenge

Given a positive-length string \$S\$, a divisor of \$S\$ is another (not necessarily distinct) string for which there exists a number \$a\$ such that when we repeat the divisor \$a\$ times, we get the string \$S\$.

For example, the string abcd is a divisor of the string abcdabcd with \$a=2\$.

Your challenge is, given a positive-length string \$S\$, output all of \$S\$'s divisors.

For example, the string aaaa has three divisors: a, aa, and aaaa.

Input/Output

Input/output can be taken in any reasonable format for taking a string and returning the set of divisors of that string.

The input string will only has lowercase characters, and it contains no whitespace or special characters.

The output list should not contains any duplicates. The strings can appear in any order.

Testcase:

Input -> Output
abcdabcd -> abcd, abcdabcd
aaa -> a, aaa
aaaaaaaa -> a, aa, aaaa, aaaaaaaa
abcdef -> abcdef

This is , so shortest answer (in bytes) wins!

Improve this question
\$\endgroup\$
1
  • 2
    \$\begingroup\$ If \$s\times a=S\$, why only \$s\$ is considered divisor but not \$a\$. :) \$\endgroup\$
    – tsh
    Aug 11, 2022 at 5:37

36 Answers 36

Reset to default
1
2
16
\$\begingroup\$

Brachylog, 3 bytes

ġ=h

Try it online!

Generator.

ġ      Split the input into (roughly) equal slices.
  h    Output one of them
 =     if they're all equal.
Improve this answer
\$\endgroup\$
2
11
\$\begingroup\$

Python, 53 bytes

lambda s,t="":[t for c in s if~-any(s.split(t:=t+c))]

Attempt This Online!

Improve this answer
\$\endgroup\$
11
  • 2
    \$\begingroup\$ This is Python 3.8+ I presume? Due to the walrus operator? \$\endgroup\$
    – justhalf
    Aug 11, 2022 at 16:36
  • \$\begingroup\$ @justhalf Yes, well observed. \$\endgroup\$
    – loopy walt
    Aug 11, 2022 at 16:52
  • \$\begingroup\$ Ah, I see. So we no longer distinguish Python 2 and 3+ here, or .. ? \$\endgroup\$
    – justhalf
    Aug 11, 2022 at 20:17
  • 1
    \$\begingroup\$ @justhalf Python is Python 3, Python 2 is officially no longer supported. Besides, all the boiler plate elements of this post are auto-generated by ato. So if you don't like it take it out with them. I'm sure they'll be very interested to hear from you. \$\endgroup\$
    – loopy walt
    Aug 11, 2022 at 20:35
  • \$\begingroup\$ Oh, I'm just so used to TIO boilerplate that does distinguish them. Nothing against ATO :) Also I thought Python 3.7 and Python 3.8 are considered different too in codegolf. Is it not the case now? \$\endgroup\$
    – justhalf
    Aug 12, 2022 at 4:21
9
\$\begingroup\$

Regex (ECMAScript 2018 or better), 17 bytes

(?<=(.*))(?=\1*$)

Try it online! - ECMAScript 2018
Try it online! - Python (import regex)
Try it online! - .NET
Try it on regex101! - ECMAScript 2018 or .NET

Returns its output as the list of matches' \1 captures.

Ports:
Try it online! - Java, 18 bytes: (?<=(^.*))(?=\1*$)
Try it online! - Perl, 31 bytes: (?=(.*)).((?<=(?=^\1*$|(?2)).))
Try it online! - PCRE2, 31 bytes - same as above
Try it on regex101! - PCRE2
Try it online! - PCRE, 33 bytes: (?=(.*)).((?<=(?=‍¶|^\1*$|(?2)).))
Try it on regex101! - PCRE1

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

05AB1E, 6 5 bytes

ηʒKõQ

Try it online or verify all test cases.

Explanation:

η      # Get all prefixes of the (implicit) input-string
 ʒ     # Filter it by:
  K    #  Remove all occurrences of the prefix-string from the (implicit) input
   õQ  #  Check if what remains is an empty string
       # (after which the filtered list is output implicitly as result)
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Factor + grouping.extras, 73 70 57 48 bytes

[ dup head-clump [ ""replace ""= ] with filter ]

Attempt This Online!

-13 bytes and then -9 more by porting @KevinCruijssen's 05AB1E answer (and then improved version)!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Factor has such crazy builtins, you'd think it's got to have one to get set partitions \$\endgroup\$
    – naffetS
    Aug 11, 2022 at 3:12
  • \$\begingroup\$ @Steffan Sadly, it does not. I would say that is possibly my biggest annoyance about golfing in Factor. \$\endgroup\$
    – chunes
    Aug 11, 2022 at 3:20
6
\$\begingroup\$

Curry (PAKCS), 26 bytes

f(g a)=a
g a|a>""=a++g a?a

Try it online!

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Haskell, 42 bytes

f s|p<-scanr(:)""s=[t|t<-p,a<-p,(a*>t)==s]

Try it online!

scanr(:)""s lists the suffixes of the input s. For each suffix t, we look for a suffix a where repeating t once for each character of a (a*>t) gives the original string s.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

J, 19 bytes

<\#~<=<\$~&.>#+#\|#

Try it online!

  • <\$~ Cyclically extend each prefix to the following length:
    • #+#\|# Length of input # + the remainder when we divide that prefix's length into the input's length #\|#. This ensures non-divisible prefixes won't match.
  • <= Which of the extended prefixes matches the input?
  • <\#~ Filter all prefixes using that mask.
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

K (ngn/k), 26 bytes

{((#(,x)^,\(#x)#,:)')_,\x}

Try it online!

I guess this is somewhat a new strategy. For each prefix, tests if the original input appears in the list of 1..(length of input) repetitions of the prefix.

{((#(,x)^,\(#x)#,:)')_,\x}  x: input string of length n
                      ,\x   prefixes
 ((               )')_      remove the items that give nonzero:
         ,\(#x)#,:            repeat the prefix 1..n times
    (,x)^                     set minus from the singleton list of x
   #                          is x still there?
Improve this answer
\$\endgroup\$
1
5
\$\begingroup\$

Jelly, 8 6 bytes

sJEƇḢ€

Try it online!

Port of my Brachylog solution.

s         Slice the input into chunks of
 J        every length.
  EƇ      Keep only partitions with all equal elements,
    Ḣ€    and return the first element of each remaining partition.
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

K (ngn/k), 19 bytes

{(x{#,/y\x}/:)_,\x}

Try it online!

,\x get all prefixes of the input
... _ discard a prefix if:
  y\x split the input by this prefix
  ,/ concatenate parts into a single string
  # length of this string is non-zero.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Ruby, 53 52 bytes

->s{(1..k=s.size).map{|x|w=s[0,x];w*k==s*x ?w:s}|[]}

Try it online!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Vyxal, 8 6 bytes

øṖ~≈vh

Try it Online!

Port of Unrelated String's Jelly answer.

Porting Kevin Cruijssen's 05AB1E answer would be 6 bytes as well:

Vyxal, 6 bytes

¦'?$o¬

Try it Online!

Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

C# (Visual C# Interactive Compiler), 68, 58 bytes

Iterate and replace every substring starting from index 0 and check if it equals an empty string

Credit to @Acer for the syntatic sugar

s=>s.Select((_,i)=>s[..++i]).Where(x=>s.Replace(x,"")=="")

Try it online!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Smart approach, way better than what I had come up with for C#. You can save 9 bytes using s[..++i] instead of s.Substring(0,i+1) Try it online! \$\endgroup\$
    – Acer
    Aug 11, 2022 at 15:34
5
\$\begingroup\$

Nibbles, 5.5 bytes (11 nibbles)

|.,,$<$@~%@

|.,,$<$@~%@
   ,            # get the length of
    $           # the input string
  ,             # and make a range 1..length,
 .              # now, map over these values
     <$         # taking that number of characters
       @        # from the input string
                # (this gets the prefixes),
|               # now, filter these to keep only those that
        ~       # are falsy 
         %@     # when we use them to split the input string
                # (so, string-divisors yield the empty string)

enter image description here

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Python, 65 63 bytes

lambda s:[s[:i]for i in range(1,len(s)+1)if len(s)//i*s[:i]==s]

Attempt This Online!

A very unclever solution.

Saved -2 bytes from @ruancornelli.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can save two bytes by reordering s[:i]*(len(s)//i) as len(s)//i*s[:i] \$\endgroup\$
    – ruancomelli
    Aug 14, 2022 at 1:21
4
\$\begingroup\$

Haskell, 65 bytes

d s|r<-[1..length s]=[z|z<-(`take`s)<$>r,s`elem`[[1..n]>>z|n<-r]]

Try it online!

Improve this answer
\$\endgroup\$
1
4
\$\begingroup\$

Knight, 32 bytes

;=x=yP Wx;I?y*x/LyLxOxN=xGxF-LxT

Try it online!

; = x (= y (PROMPT))                            # x = y = input()
: WHILE x                                       # while x != "":
    ; IF (? y (* x (/ (LENGTH y) (LENGTH x))))  #   if y == x * (len(y) / len(x)):
        : OUTPUT x                              #     print(x)
        : NULL                                  #   else: (do nothing)
    : = x (GET x 0 (- (LENGTH x) 1))            #   x = x[:-1]
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 3.8, 56 bytes

-7 bytes thanks to user loopy walt

lambda s,d='':[d for c in s if len(s)//len(d:=d+c)*d==s]

Attempt This Online!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ lambda s,d='':[d for c in s if len(s)//len(d:=d+c)*d==s] for 56 \$\endgroup\$
    – loopy walt
    Aug 11, 2022 at 9:54
4
\$\begingroup\$

Ruby, 43 bytes

->s{(s+?␀+s).scan(/(?=(.+)␀\1*$)/).flatten}

Try it online!

This concatenates the string to itself with a NUL (ASCII 0) character between, in order to use a regex to find all matches' \1 captures. Since Ruby does not have variable-length lookbehind and can't emulate it with recursion, this approach couldn't work on the unmodified string.

Since this does a manipulation on the input before working on it, thus departing from my idea of what a pure regex is, I'm posting this as a separate answer.

Ruby, 35 34 bytes

->s{(s+?␀+s).scan /(?=(.+)␀\1*$)/}

Try it online!

If it is acceptable to return the output as a list of one-element string lists, then this answer can be even shorter. This returns, for example, [["abcdabcd"], ["abcd"]] instead of ["abcdabcd", "abcd"].

Ruby, 50 47 bytes

->s{(s+s).scan /(?=(.+)(?=.{#{s.size}}$)\1*$)/}

Try it online!

This approach works even on strings containing NUL(s), as it uses the length of the string (rather than a delimiter) as a marker. As with the 35 byte solution above, it returns a list of one-element string lists.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Raku, 25 bytes

{~«m:ex/^(.+)$0*$/»[0]}

Try it online!

m/^(.+)$0*$/ looks for patterns of letters which, repeated, comprise the entire string. The :exhaustive flag on the match operation (shortenable to :ex) looks for every possible match, not just one. Then »[0] extracts just the first submatch (ie, the divisor) from every match, and ~« stringifies each of those match objects.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ you can do something similar to the Perl answer for 23 bytes \$\endgroup\$
    – Jo King ♦
    Aug 13, 2022 at 1:13
3
\$\begingroup\$

Retina 0.8.2, 17 bytes

&!`(.+)$(?<=^\1+)

Try it online! Link includes test cases. Explanation:

&!`

List all overlapping matches.

(.+)$

Match any suffix...

(?<=^\1+)

... which can be repeated to recreate the original string.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Husk, 7 bytes

fȯEC¹Lḣ

Try it online!

      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 ȯ          # result of 3 functions:
   C¹       #  cut the input into pieces
     L      #  with the length of each prefix
  E         #  and check if they're all equal

Alternative, also 7 bytes

foE`x¹ḣ

Try it online!

foE`x¹ḣ
      ḣ     # get the heads (prefixes) of the input
f           # filter these to keep only truthy by
 o          # result of 2 functions:
   x        #  split on given substring
  `         #  (with reversed arguments)
    ¹       #  the input 
            #  (note that first element will always be empty list
            #  when splitting using a prefix)
  E         #  and check if they're all equal
            #  (which will only be the case if all are emty lists, 
            3  meaning that the input was a multiple of the substring)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 15 bytes

ΦＥθ…θ⊕κ№Ｅθ×ι⊕μθ

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

  θ             Input string
 Ｅ              Map over characters
    θ           Input string
   …            Truncated to length
      κ         Current index
     ⊕          Incremented
Φ               Filtered where
         θ      Input string
        Ｅ       Map over characters
           ι    Current prefix
          ×     Repeated by
             μ  Inner index
            ⊕   Incremented
       №        Contains
              θ Input string
                Implicitly print
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

sed -n, 58 46 bytes

s/^/\n/
:a
/^\(.*\)\n\1*$/P
s/\n\(.\)/\1\n/
ta

Attempt This Online!

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ We don't include flags in the length measurement anymore, since years ago. Just put it in your language name, e.g. "sed -n, 58 bytes". The relevant meta post \$\endgroup\$
    – Deadcode
    Aug 11, 2022 at 19:35
  • \$\begingroup\$ This breaks if the input contains ! anywhere... the challenge doesn't state anywhere that input is only alphanumeric. But here is a version of your program that uses NULs instead of !s. Same length in bytes. \$\endgroup\$
    – Deadcode
    Aug 11, 2022 at 20:04
  • 1
    \$\begingroup\$ @Deadcode The challenge states this: "The input string will only has lowercase characters, and it contains no whitespace or special characters." But it is nice surprise for me that NUL character is valid inside sed programs. Also thank you for the information about scoring, but it feels a bit weird as the flag can be removed at cost of 2B (;d). \$\endgroup\$
    – Jiří
    Aug 11, 2022 at 21:06
  • 1
    \$\begingroup\$ Ah, silly me, I looked at the challenge spec several times and somehow missed that. As for the NULs, I put them in ATO and TIO links with these scripts I wrote along with a hex editor. Pipe the URL to the decode script, with the output piped to a binary file. Edit that file, then pipe it to the encode script to get the new URL. Note that while it's easy to change the length of a TIO program in a hex editor, it's a bit more involved to do so to an ATO program, but still easy to make edits that don't change the length. \$\endgroup\$
    – Deadcode
    Aug 11, 2022 at 21:36
3
\$\begingroup\$

Rust, 108 106 bytes

-2 bytes thanks to alephalpha

|a:&str|(1..=a.len()).map(|k|a[..k].repeat(1)).filter(|z|z.repeat(a.len()/z.len())==a).collect::<Vec<_>>()

Playground Link

Improve this answer
\$\endgroup\$
1
3
\$\begingroup\$

Haskell + hgl, 12 bytes

he<<fl lq<pt

Attempt This Online!

Explanation

  • pt gets all ways to partition the input into non-empty lists
  • fl lq filters out all items with duplicates
  • he takes the first value in each result

Reflection

  • A function that gives partitions satisfying a predicate would be immensely useful here. This could be he<<pST lq
  • Similarly we should add a function that gives all partitions where the elements satisfy a predicate.
  • A function that gives all permutations with equal size would not save any bytes here, but it would make this answer a lot faster to run and would probably be useful in the future.
  • ƥ, mP, ms and mS all need flipped versions.
  • A prefix and suffix filter would be useful. There are currently functions to get the longest suffix/prefix satisfying a predicate but not all.
  • Shortcuts to check if a list has a particular length would be useful. There are already ones for checking if it is less than or greater than a value.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Arturo, 56 bytes

$[s][select map 1..size s=>[take s]'y->""=replace s y""]

Try it

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Zsh, 47 bytes

for c (${(s..)1})s+=$c&&[[ $1 = ($s)# ]]&&<<<$s

Try it online!

Fairly straightforward:

for c (${(s..)1})       # (s)split $1 on '' (into characters)
    s+=$c &&            # append character to $s
    [[ $1 = ($s)# ]] && # if $1 equals $s repeated
    <<< $s              # output $s
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Perl -p, 22 bytes

/^(.*)\1+$(??{say$1})/

Try it online!

This uses a "postponed" regular subexpression embedded code block to accomplish the same thing as Raku's exhaustive verb (which is used in Sean's answer), enumerating all possible matches, not just the ones (the one, in fact) that would be found normally.

Once a match of ^(.*)\1+$ that would be successful finishes, the embedded code block is triggered, and say$1 prints the value of the \1 capture group. Since it's of the "postponed" type, it then dynamically compiles the result of say$1 (which is the boolean 1) into the regex, causing the match to fail, since 1 can never occur after the end of a string. A literal 1 placed after the $ would cause the match to fail and give up, due to Perl's regex optimization. But since it's dynamically compiled into the regex, the result of executing a piece of code, Perl doesn't know that it will be 1 every time, so it actually allows the regex to backtrack and try other possible matches.

The regex is intentionally set to not let \1 match the entire input string, only strict substrings. ^(.*)\1*$ would be the version that would also match the entire string. But that is left out, because once the program finishes, Perl's -p flag causes $_ to be printed. That way, all of the string's divisors, including itself, are outputted.

Embedded code capability is a rare thing in regex engines. As far as I know, the only ones that have it are Perl and Raku (embedded code blocks) and PCRE (callouts). It appears that MATLAB allows execution of MATLAB code inside a regex, but I have not tested that yet (and am not sure if GNU Octave, which uses PCRE, has that functionality, or if MATLAB even also uses PCRE).

Another thing to note is that inputs followed by a newline (rather than EOF) will have that newline included in the contents of $_, and this program doesn't use chomp. But that doesn't matter, since $ matches both the true end of string, and the position immediately before a newline at the end of the string, if there is one. This is the case regardless of whether the multiline flag is enabled (which it is not, by default). This is a case where that behavior (as opposed to \z, which strictly matches the end of string) is helpful.

Perl -n, 22 bytes

/^(.*)\1*$(??{say$1})/

Try it online!

This is really the more logical version, printing the divisors in a consistent order. But I'm keeping the -p version up here, since -p is much more commonly used in answers, and as the way flags are treated (as distinct languages, in a certain abstract way) it lets it be in the same playing field as those -p answers. Not to mention that the workaround it uses is kind of fun.

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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