Inspired by CodeWars
We have a string
s
Let's say you start with this: "String"
The first thing you do is reverse it: "gnirtS"
Then you will take the string from the 1st position and reverse it again: "gStrin"
Then you will take the string from the 2nd position and reverse it again: "gSnirt"
Then you will take the string from the 3rd position and reverse it again: "gSntri"Continue this pattern until you have done every single position, and then you will return the string you have created. For this particular string, you would return: "gSntir"
The Task:
In this kata, we also have a numberx
take the above reversal function, and apply it to the stringx
times.
Return the result of the string after applying the reversal function to itx
times.Note:
String lengths may exceed 2 million andx
may exceed a billion. Be ready to optimize.
My solution works but times out and I am having trouble optimizing much further. The code contains a lot of useful comments but here is a summary of what I have attempted to do.
Cycle Length Calculation
Because the above algorithm generates cycles, we can calculate a strings cycle length and perform x % cycleLength
to determine exactly how many iterations we must perform to get our end result, instead of having to calculate all the duplicate cycles. More on cycle lengths can be found here and here.
This method is better than nothing but can still get quite demanding on high cycle lengths. Potentially there is a better way of calculating the cycle length without so many iterations?
public final class XIterations {
public static String xReverse(String s, long x) {
// Using the cycle length and modular arithmetic,
// We can find the exact number of reverse operations we will need to perform.
// This way we will only perform operations we need to complete.
long iterationsRequired = x % calculateCycleLength(s.length());
// TODO: There may exist an algorithm that allows a linear transformation given x
while (iterationsRequired > 0) {
s = reverse(s);
iterationsRequired--;
}
return s;
}
// The xReverse algorithm produces cycles and therefore duplicates.
// This helper method determines the length of the cycle using the number of characters a string contains.
// More detail on the algorithm can be found at:
// https://oeis.org/A003558
// https://oeis.org/A216066
// TODO: There may exist an algorithm that requires less iterations to find the cycle length
private static int calculateCycleLength(int n) {
// Cache these so we only calculate them once.
final int a = 2 * n + 1;
final int b = 2 * n;
int cycleLength = 1;
while (true) {
double c = Math.pow(2, cycleLength);
if (c % a == 1 || c % a == b) {
return cycleLength;
}
cycleLength++;
}
}
public static String reverse(String s) {
StringBuilder sb = new StringBuilder();
int front = 0;
int back = s.length() - 1;
// Does not account for odd length strings. Will not add the middle character.
while (front < back) {
sb.append(s.charAt(back--));
sb.append(s.charAt(front++));
}
// Account for odd length strings. Add the middle character that was never added by loop.
if (front == back) {
sb.append(s.charAt(front));
}
return sb.toString();
}
}
I am mostly interested in optimization tips but of course any feedback is welcome.