9
\$\begingroup\$

A rotation "is made by splitting a string into two pieces and reversing their order". An object is symmetrical under an operation if the object is unchanged after applying said operation. So, a "rotational symmetry" is the fact that a string remains unchanged after "rotation".

Given a non-empty string s consisting of only letters from a to z, output the highest order of the rotational symmetry of the string.

Testcases:

input        output
a            1
abcd         1
abab         2
dfdfdfdfdfdf 6

This is . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
3
  • \$\begingroup\$ Related. \$\endgroup\$ May 19, 2017 at 10:23
  • 1
    \$\begingroup\$ previously asked as a CMC: chat.stackexchange.com/transcript/message/37509699#37509699 \$\endgroup\$ May 19, 2017 at 10:30
  • \$\begingroup\$ This is the same as finding the number of symmetric rotations smaller than the size of the string. As @0' points out they form a cyclic group so finding the highest order is the same as finding the size of the group. This would make the explanation of the task which is currently pretty unclear much clearer. \$\endgroup\$
    – Wheat Wizard
    Mar 10, 2018 at 17:54

12 Answers 12

8
\$\begingroup\$

Retina, 15 bytes

(^.+?|\1)+$
$#1

Try it online!

Matches the entire string by repeating a substring (shorter substrings are prioritised due to the ungreedy .+?) and replaces the entire string with the number of repetitions we used.

\$\endgroup\$
1
  • \$\begingroup\$ Oh, of course, ungreedy. And here was me struggling with .*(.+)$(?<=^(\1)*)... \$\endgroup\$
    – Neil
    May 19, 2017 at 10:30
6
\$\begingroup\$

Jelly, 3 bytes

ṙJċ

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Congratulations! \$\endgroup\$
    – Leaky Nun
    May 19, 2017 at 11:57
  • \$\begingroup\$ @LeakyNun That was your solution, right? \$\endgroup\$ May 19, 2017 at 11:57
  • \$\begingroup\$ Indeed, it was. \$\endgroup\$
    – Leaky Nun
    May 19, 2017 at 11:58
  • \$\begingroup\$ Is your name a Gauntlet reference? \$\endgroup\$ May 19, 2017 at 17:12
  • \$\begingroup\$ @user2357112 No it refers to outgolfing i.e. when you post a solution that's shorter than another posted solution. \$\endgroup\$ May 19, 2017 at 17:13
3
\$\begingroup\$

05AB1E, 8 bytes

gGDÀ})QO

Try it online!

Explanation

gG  }      # len(input)-1 times do:
  D        # duplicate
   À       # rotate left
     )     # wrap result in a list
      Q    # compare each to input for equality
       O   # sum
\$\endgroup\$
3
\$\begingroup\$

Prolog (SWI), 64 bytes

A+B:-findall(X,(append(X,Y,A),append(Y,X,A)),[_|Z]),length(Z,B).

Try it online!

Defines a predicate +/2 that takes a string (in the form of a list of character codes) as its first argument (A) and sets its second argument (B) to the order of the highest order symmetric rotation.

Explanation

This program uses the fact that the set of symmetric rotations on a string are a cyclic group and so the order of the set of symmetric rotations is equal to the order of the highest order symmetric rotation. Thus the program is able to calculate the desired result by finding the total number of symmetric rotations on the input string.

Code Explanation

The majority of the heavy lifting is done by a call to the findall/3 predicate. The findall/3 predicate finds all the different possible values for the first argument (X in this case) such that the expression given as the second argument is true ((append(X,Y,A),append(Y,X,A)), more on that later). Finally it stores each of these possible values of X as a list in the final argument ([_|Z]).

The expression passed into findall/3 as the second arugment, (append(X,Y,A),append(Y,X,A)) uses the append/3 predicate to specify that X concatenated with some yet undefined Y must be equal to A, the input string, and that the same Y concatenated with X must also be equal to A. This means that X must be some prefix of A such that if it is removed from the front of A and added to the back then the resulting string is the same as A. The set of Xs with this property almost has a one-to-one correspondence with the symmetric rotations of A. There is always exactly one case of double counting which is caused by the fact that both the empty string and A are prefixes of A that correspond to the 0-rotation of A. Since the 0-rotation of A is always symmetric the length of the resulting list of Xs from findall/3 will be one greater than the number of symmetric rotations on A.

To solve the double counting problem, I use pattern matching on the third argument of the findall/3 predicate. In Prolog lists are represented as pairs of their head (the first element) and their tail (the rest). Thus [_|Z] represents a list whose tail is equal is equal to Z. This means that the length of Z is one less than the number of prefixes found by the findall/3 predicate and thus equal to the number of symmetric rotations of A. Finally, I use the length/2 predicate to set B to the length of Z.

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

Python, 31 bytes

lambda s:len(s)/(s+s).find(s,1)

Find the first nonzero index of s in s+s to figure out how far we have to rotate it to get s back, then divide the length of s by that number. Based on ideas I saw elsewhere.

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

JavaScript (ES6), 42 41 bytes

Saved 1 byte thanks to @l4m2

s=>s.length/s.match`(.+?)\\1*$`[1].length

Test cases

let f =

s=>s.length/s.match`(.+?)\\1*$`[1].length

console.log(f("a"))            // 1
console.log(f("abcd"))         // 1
console.log(f("abab"))         // 2
console.log(f("dfdfdfdfdfdf")) // 6

\$\endgroup\$
1
  • \$\begingroup\$ f=s=>s.length/s.match`(.+?)\\1*$`[1].length \$\endgroup\$
    – l4m2
    Mar 10, 2018 at 18:00
2
\$\begingroup\$

Vyxal r, 4 bytes

żvǓO

Try it Online!

Port of Jelly answer.

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

Japt, 7 bytes

¬x@¥UéY

Test it online!

Explanation

 ¬ x@   ¥ UéY
 q xXY{ ==UéY}  // Expanded
Uq xXY{U==UéY}  // Variable introduction
                // Implicit: U = input string
Uq              // Split U into chars.
   xXY{      }  // Map each item X and index Y by this function, then sum the results:
       U==UéY   //   Return U equals (U rotated by Y characters).
                // Implicit: output result of last expression
\$\endgroup\$
1
\$\begingroup\$

Haskell, 49 bytes

g x=sum[1|a<-[1..length x],drop a x++take a x==x]

Try it online!

Haskell, 49 bytes

g x=sum[1|(a,_)<-zip[1..]x,drop a x++take a x==x]

Try it online!

Explanation

This uses the simple solution @0' pointed out. Since the rotations of the string form a cyclic group the highest order element is the same as the size of the group thus we can get the order of the unit by finding the number of symmetric rotations.

The codes simple does a list comprehension and counts the number of rotations that preserve the original string.

\$\endgroup\$
2
  • \$\begingroup\$ You can use drop<>take instead of using (++) to save 3 bytes, like this. \$\endgroup\$ Apr 28, 2018 at 22:28
  • \$\begingroup\$ @BMO (<>) isn't in prelude, in the version of Haskell I work with. \$\endgroup\$
    – Wheat Wizard
    Apr 29, 2018 at 0:28
1
\$\begingroup\$

Factor, 42 38 bytes

[ dup all-rotations [ = ] with count ]

Try it online!

Count how many rotations of the input are equal to the input.

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

PHP, 66 Bytes

for(;strtr($a=$argn,[substr($a,0,++$i)=>""]););echo strlen($a)/$i;

Try it online!

PHP, 67 Bytes

preg_match('#^(.+?)\1*$#',$argn,$t);echo substr_count($argn,$t[1]);

Try it online!

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

C (gcc), 59 bytes

-Df(d,s)=for(d=n=strlen(s);n%d|memcmp(s,s+n/d,n-n/d);d--)

n;

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ tio should be suggested so the complier flags can be decided added into the code length \$\endgroup\$
    – l4m2
    Mar 10, 2018 at 18:21
  • \$\begingroup\$ Suggest bcmp() instead of memcmp() \$\endgroup\$
    – ceilingcat
    Oct 31, 2022 at 7:43

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.