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\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender May 19 '17 at 10:23
  • 1
    \$\begingroup\$ previously asked as a CMC: chat.stackexchange.com/transcript/message/37509699#37509699 \$\endgroup\$ – John Dvorak May 19 '17 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 '18 at 17:54

10 Answers 10

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\$
  • \$\begingroup\$ Oh, of course, ungreedy. And here was me struggling with .*(.+)$(?<=^(\1)*)... \$\endgroup\$ – Neil May 19 '17 at 10:30
5
\$\begingroup\$

Jelly, 3 bytes

ṙJċ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Congratulations! \$\endgroup\$ – Leaky Nun May 19 '17 at 11:57
  • \$\begingroup\$ @LeakyNun That was your solution, right? \$\endgroup\$ – Erik the Outgolfer May 19 '17 at 11:57
  • \$\begingroup\$ Indeed, it was. \$\endgroup\$ – Leaky Nun May 19 '17 at 11:58
  • \$\begingroup\$ Is your name a Gauntlet reference? \$\endgroup\$ – user2357112 May 19 '17 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\$ – Erik the Outgolfer May 19 '17 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\$
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\$

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

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\$
  • \$\begingroup\$ f=s=>s.length/s.match`(.+?)\\1*$`[1].length \$\endgroup\$ – l4m2 Mar 10 '18 at 18:00
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\$
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\$
  • \$\begingroup\$ tio should be suggested so the complier flags can be decided added into the code length \$\endgroup\$ – l4m2 Mar 10 '18 at 18:21
0
\$\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\$
  • \$\begingroup\$ You can use drop<>take instead of using (++) to save 3 bytes, like this. \$\endgroup\$ – ბიმო Apr 28 '18 at 22:28
  • \$\begingroup\$ @BMO (<>) isn't in prelude, in the version of Haskell I work with. \$\endgroup\$ – Wheat Wizard Apr 29 '18 at 0:28

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.