# Count the number of cyclic words in an input

Cyclic Words

Problem Statement

We can think of a cyclic word as a word written in a circle. To represent a cyclic word, we choose an arbitrary starting position and read the characters in clockwise order. So, "picture" and "turepic" are representations for the same cyclic word.

You are given a String[] words, each element of which is a representation of a cyclic word. Return the number of different cyclic words that are represented.

Fastest wins (Big O, where n = number of chars in a string)

• If you're looking for criticism of your code then the place to go is codereview.stackexchange.com . – Peter Taylor Jan 17 '13 at 8:21
• Cool. I'll edit for emphasis on the challenge and move the criticism part to code review. Thanks Peter. – eggonlegs Jan 17 '13 at 8:31
• What's the winning criteria? Shortest code (Code Golf) or anything else? Are there any limitataions on the form of input and output? Do we need to write a function or a complete program? Does it have to be in Java? – ugoren Jan 17 '13 at 12:46
• @eggonlegs You specified big-O - but with respect to which parameter? Number of strings in array? Is string comparison then O(1)? Or number of chars in string or total number of chars? Or anything else? – Howard Jan 17 '13 at 14:13
• @dude, surely it's 4? – Peter Taylor Jan 17 '13 at 23:12

# Python

Here's my solution. I think it might still be O(n2), but I think the average case is much better than that.

Basically it works by normalizing each string so that any rotation will have the same form. For example:

'amazing' -> 'mazinga'
'mazinga' -> 'mazinga'
'azingam' -> 'mazinga'
'zingama' -> 'mazinga'
'ingamaz' -> 'mazinga'
'ngamazi' -> 'mazinga'
'gamazin' -> 'mazinga'

The normalization is done by looking for the minimum character (by char code), and rotating the string so that character is in the last position. If that character occurs more than once, then the characters after each occurrence are used. This gives each cyclic word a canonical representation, that can be used as a key in a map.

The normalization is n2 in the worst case (where every character in the string is the same, e.g. aaaaaa), but most of the time there's only going to be a few occurrences, and the running time will be closer to n.

On my laptop (dual core Intel Atom @ 1.66GHz and 1GB of ram), running this on /usr/share/dict/words (234,937 words with an average length of 9.5 characters) takes about 7.6 seconds.

#!/usr/bin/python

import sys

def normalize(string):
# the minimum character in the string
c = min(string) # O(n) operation
indices = [] # here we will store all the indices where c occurs
i = -1       # initialize the search index
while True: # finding all indexes where c occurs is again O(n)
i = string.find(c, i+1)
if i == -1:
break
else:
indices.append(i)
if len(indices) == 1: # if it only occurs once, then we're done
i = indices[0]
return string[i:] + string[:i]
else:
i = map(lambda x:(x,x), indices)
for _ in range(len(string)):                       # go over the whole string O(n)
i = map(lambda x:((x[0]+1)%len(string), x[1]), i)  # increment the indexes that walk along  O(m)
c = min(map(lambda x: string[x[0]], i))    # get min character from current indexes         O(m)
i = filter(lambda x: string[x[0]] == c, i) # keep only the indexes that have that character O(m)
# if there's only one index left after filtering, we're done
if len(i) == 1:
break
# either there are multiple identical runs, or
# we found the unique best run, in either case, we start the string from that
# index
i = i[0][0]
return string[i:] + string[:i]

def main(filename):
cyclic_words = set()
with open(filename) as words:
cyclic_words.add(normalize(word[:-1])) # normalize without the trailing newline
print len(cyclic_words)

if __name__ == '__main__':
if len(sys.argv) > 1:
main(sys.argv[1])
else:
main("/dev/stdin")

## Python (3) again

The method I used was to calculate a rolling hash of each word starting at each character in the string; since it's a rolling hash, it takes O(n) (where n is the word length) time to compute all the n hashes. The string is treated as a base-1114112 number, which ensures the hashes are unique. (This is similar to the Haskell solution, but more efficient since it only goes through the string twice.)

Then, for each input word, the algorithm checks its lowest hash to see if it's already in the set of hashes seen (a Python set, thus lookup is O(1) in the set's size); if it is, then the word or one of its rotations has already been seen. Otherwise, it adds that hash to the set.

The command-line argument should be the name of a file that contains one word per line (like /usr/share/dict/words).

import sys

def rollinghashes(string):
base = 1114112
curhash = 0
for c in string:
curhash = curhash * base + ord(c)
yield curhash
top = base ** len(string)
for i in range(len(string) - 1):
curhash = curhash * base % top + ord(string[i])
yield curhash

def cycles(words, keepuniques=False):
hashes = set()
uniques = set()
n = 0
for word in words:
h = min(rollinghashes(word))
if h in hashes:
continue
else:
n += 1
if keepuniques:
return n, uniques

if __name__ == "__main__":
with open(sys.argv[1]) as words_file:
print(cycles(line.strip() for line in words_file)[0])

Not sure about the efficiency of this, most likely rather bad. The idea is to first create all possible rotations of all the words, count the values that uniquely represent the strings and select the minimum. That way we get a number that is unique to a cyclic group.
We can group by this number and check the number of these groups.

If n is the number of words in the list and m is the length of a word then calculating the 'cyclic group number' for all the words is O(n*m), sorting O(n log n) and grouping O(n).

import Data.List
import Data.Char
import Data.Ord
import Data.Function

groupUnsortedOn f = groupBy ((==) on f) . sortBy(compare on f)
allCycles w = init $zipWith (++) (tails w)(inits w) wordval = foldl (\a b -> a*256 + (fromIntegral$ ord b)) 0
uniqcycle = minimumBy (comparing wordval) . allCycles
cyclicGroupCount = length . groupUnsortedOn uniqcycle

# Mathematica

Decided to start again, now that I understand the rules of the game (I think).

A 10000 word dictionary of unique randomly composed "words" (lower case only) of length 3. In similar fashion other dictionaries were created consisting of strings of length 4, 5, 6, 7, and 8.

ClearAll[dictionary]
dictionary[chars_,nWords_]:=DeleteDuplicates[Table[FromCharacterCode@RandomInteger[{97,122},
chars],{nWords}]];
n=16000;
d3=Take[dictionary[3,n],10^4];
d4=Take[dictionary[4,n],10^4];
d5=Take[dictionary[5,n],10^4];
d6=Take[dictionary[6,n],10^4];
d7=Take[dictionary[7,n],10^4];
d8=Take[dictionary[8,n],10^4];

gtakes the current version of dictionary to check. The top word is joined with cyclic variants (if any exist). The word and its matches are appended to the output list, out, of processed words. The output words are removed from the dictionary.

g[{wds_,out_}] :=
If[wds=={},{wds,out},
Module[{s=wds[[1]],t,c},
t=Table[StringRotateLeft[s, k], {k, StringLength[s]}];
c=Intersection[wds,t];
{Complement[wds,t],Append[out,c]}]]

f runs through all words dictionary.

f[dict_]:=FixedPoint[g,{dict,{}}][[2]]

Example 1: actual words

r = f[{"teaks", "words", "spot", "pots", "sword", "steak", "hand"}]
Length[r]

{{"steak", "teaks"}, {"hand"}, {"pots", "spot"}, {"sword", "words"}}
4

Example 2: Artificial words. Dictionary of strings of length 3. First, timing. Then the number of cycle words.

f[d3]//AbsoluteTiming
Length[%[[2]]]

5402

Timings as a function of word length. 10000 words in each dictionary.

I don't particularly know how to interpret the findings in terms of O. In simple terms, the timing roughly doubles from the three character dictionary to the four character dictionary. The timing increases almost negligibly from 4 through 8 characters.

• Can you possibly post a link to the dictionary you used so I can compare against yours? – eggonlegs Jan 19 '13 at 11:21
• The following link to dictionary.txt should work: bitshare.com/files/oy62qgro/dictionary.txt.html (Sorry about the minute you'll have to wait for the download to begin.) BTW, the file has the 3char, 4char...8char dictionaries all together, 10000 words in each. You'll want to separate them. – DavidC Jan 19 '13 at 14:49
• Awesome. Thanks very much :) – eggonlegs Jan 20 '13 at 0:41

This can be done in O(n) avoiding quadratic time. The idea is to construct the full circle traversing the base string twice. So we construct "amazingamazin" as the full circle string to check all cyclic strings corresponding to "amazing".

Below is the Java solution:

public static void main(String[] args){
//args[0] is the base string and following strings are assumed to be
//cyclic strings to check
int arrLen = args.length;
int cyclicWordCount = 0;
if(arrLen<1){
System.out.println("Invalid usage. Supply argument strings...");
return;
}else if(arrLen==1){
System.out.println("Cyclic word count=0");
return;
}//if

String baseString = args[0];
StringBuilder sb = new StringBuilder();
// Traverse base string twice appending characters
// Eg: construct 'amazingamazin' from 'amazing'
for(int i=0;i<2*baseString.length()-1;i++)
sb.append(args[0].charAt(i%baseString.length()));

// All cyclic strings are now in the 'full circle' string
String fullCircle = sb.toString();
System.out.println("Constructed string= "+fullCircle);

for(int i=1;i<arrLen;i++)
//Do a length check in addition to contains
if(baseString.length()==args[i].length()&&fullCircle.contains(args[i])){
System.out.println("Found cyclic word: "+args[i]);
cyclicWordCount++;
}

System.out.println("Cyclic word count= "+cyclicWordCount);
}//main

I don't know if this is very efficient, but this is my first crack.

private static int countCyclicWords(String[] input) {
HashSet<String> hashSet = new HashSet<String>();
String permutation;
int count = 0;

for (String s : input) {
if (hashSet.contains(s)) {
continue;
} else {
count++;
for (int i = 0; i < s.length(); i++) {
permutation = s.substring(1) + s.substring(0, 1);
s = permutation;
}
}
}

return count;
}

## Perl

not sure i understand the problem, but this matches the example @dude posted in the comments at least. please correct my surely incorrect analysis.

for each word W in the given N words of the string list, you have to step through all characters of W in the worst case. i have to assume the hash operations are done in constant time.

use strict;
use warnings;

my @words = ( "teaks", "words", "spot", "pots", "sword", "steak", "hand" );

sub count
{
my %h = ();

foreach my $w (@_) { my$n = length($w); # concatenate the word with itself. then all substrings the # same length as word are rotations of word. my$s = $w .$w;

# examine each rotation of word. add word to the hash if
# no rotation already exists in the hash
$h{$w} = undef unless
grep { exists $h{substr$s, $_,$n} } 0 .. $n - 1; } return keys %h; } print scalar count(@words),$/;