Over the weekend my wife and I tried baking baba (Italian yeast cake) using a large mold. Typically baba is baked in individual small molds but it takes a while to grease and fill them. We tried for the first time using a large mold. All was going well until we put the mixer bowl covered with plastic in the oven with the lights on for it to ferment and double in size. After a couple hours the dough had pushed its way out of the bowl and spilled over the oven floor. We had to clean the mess before baking. We also moved the contents of the bowl into the large baking mold.
After fermentation was completed, we took out the mold and preheated the 
oven to 350 F. It took about 25 minutes for the baba to bake. We waited for an hour or so for the cake to cool down. We then pour in the mold the syrup. We then tasted it. It was somewhat warm but the flavor was quite good. I did notice that the texture was not quite right. We will try again in a week or two. Practice makes perfection.
I am a firm believer in practicing to achieve perfection knowing that perfection is an unattainable goal. I tend to say “there are many ways to skin a cat, but there is only one way that is best”. With practice and making the necessary changes to the process, eventually one may reach the best approach.
The subject of this post is the problem titled “Larry’s Array” by HackerRank. I find it interesting that some problems require some specific and in most cases obscure knowledge to solve them. It takes additional time but in general you tend to learn something new. This particular problem can be solved with rotations but it can easily be solved with knowledge of inversions.
If you are interested on inversions take a look at the following Wikipedia article Parity of a Permutation. The article is not great but good enough to get a start. I found Solvability of the Tiles Game by Mark Ryan a lot more useful. In general I like to follow the KISS (Keep It Simple and Short) rule and develop elegant and efficient solutions.
When I read the requirements for the problem I figured there had to be a simple approach. I decide to work on the logic and if that would not pan out I would do the research and find the technique required to easily solve the problem without rotations. As it turned out I ended with the two different versions.
I used Java to solve the problem. I used Visual Studio Code for an IDE.
3 3 3 1 2 4 1 3 4 2 5 1 2 3 5 4 YES YES NO 1 6 1 6 5 2 4 3 1 5 2 6 4 3 1 2 6 5 4 3 1 2 6 3 5 4 1 2 3 5 6 4 1 2 3 4 5 6 YES
Not much to say. The samples came from the HackerRank web site.
// **** scanner ****
private static final Scanner scanner = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** ****
// BufferedWriter bufferedWriter = new BufferedWriter(new
// FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** read the number of test cases ****
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** loop once per test case ****
for (int tItr = 0; tItr < t; tItr++) {
// **** read the number of integers fo rthis case ****
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** instantiate array for the integers ****
int[] A = new int[n];
// **** read the integers into a string array ****
String[] AItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** convert the strings to integers and populate array ****
for (int i = 0; i < n; i++) {
int AItem = Integer.parseInt(AItems[i]);
A[i] = AItem;
}
// // **** solve WITH rotations ****
// String result = larrysArrayRotations(A);
// **** solve WITHOUT array rotations ****
String result = larrysArray(A);
// **** display the result ****
bufferedWriter.write(result);
bufferedWriter.newLine();
}
// **** close the buffered writer ****
bufferedWriter.close();
// **** close scanner ****
scanner.close();
}
The code was copied from the HackerRank web site. I added some comments to make sure I understood the input. For ease of use I also changed the output. Note that there are two functions. The first one larrysArrayRotations() checks by attempting rotations in the actual array. The second approach implemented as larrysArray() performs some checks to determine the answer.
/**
* Complete the function below. The elements in the array are rotated as needed.
*/
static String larrysArrayRotations(int[] A) {
// **** traverse ONCE through the array ****
for (int i = 0; i < A.length; i++) {
// **** find the index of the specified value in the array ****
int v = i + 1;
int index = find(A, v);
if (index < 0) {
System.out.println("larrysArrayRotations <<< V: " + v + " UNEXPECTED index: " + index);
return "NO";
}
// // ???? ????
// System.out.println("larrysArray <<< i: " + i + " v: " + v + " index: " + // index); // **** loop rotating values in place **** while (index >= i + 2) {
// // ???? ????
// System.out.println("larrysArray <<< BEFORE A: " + Arrays.toString(A));
// **** rotate ONCE to put v in its proper place ****
A[index - 0] = A[index - 1];
A[index - 1] = A[index - 2];
A[index - 2] = i + 1;
// // ???? ????
// System.out.println("larrysArray <<< AFTER A: " + Arrays.toString(A));
// **** update index (rotations are in groups of 3 consecutive elements) ****
index -= 2;
}
// // ???? ????
// System.out.println("larrysArray <<< index: " + index);
// **** ****
if (index == i + 1) {
// **** reordering not possible (only two elements out of order) ****
if (index == A.length - 1) {
return "NO";
}
// // ???? ????
// System.out.println("larrysArray <<< before A: " + Arrays.toString(A));
// **** rotate TWICE to put v in its proper place ****
A[index - 0] = A[index + 1];
A[index + 1] = A[index - 1];
A[index - 1] = i + 1;
// // ???? ????
// System.out.println("larrysArray <<< after A: " + Arrays.toString(A));
}
}
// **** ****
return "YES";
}
This method traverses the array once. It finds the current index of the integer in the array. For example if the array contains “3, 1, 2” and we are looking for value 2, then we should get an index of 2.
We now rotate values in the array. The groups are of 3 digits. We can only rotate right. Once we are done with the possible rotations of one position, we check if we can perform a rotation of two positions. Note that if we only have two remaining values we cannot perform a rotation with 3 consecutive integers so we have to return “NO”.
If we are able to process the entire array and we exit the loop, then we were able to sort the array.
/**
* Find the index of the specified value in the array.
*/
static int find(int[] A, int v) {
// **** check if value is out of range ****
if ((v < 1) || (v > A.length)) {
return -1;
}
// **** loop looking for the specified value ****
for (int i = 0; i < A.length; i++) {
if (A[i] == v) {
return i;
}
}
// **** value not found ****
return -1;
}
This is a helper function. It just returns the position / index of the specified value in the array.
The second approach is to use inversions. We do not have to perform the actual rotations. We just have to collect some information from the array.
/**
* Solve WITHOUT array rotations.
* https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
*/
static String larrysArray(int[] A) {
// **** get the count of inversions ****
int numInv = inversions(A);
// // ???? ????
// System.out.println("solve <<< numInv: " + numInv);
// **** grid is odd AND inversions is even ****
if (((A.length % 2) == 1) && ((numInv % 2) == 0)) {
return "YES";
}
// **** grid is even AND inversions are odd ****
if (((A.length % 2) == 0) && ((numInv % 2) == 0)) {
return "YES";
}
// **** ****
return "NO";
}
The first thing we need to compute is the number of inversions in the array. An inversion occurs when an array position holds a value lower than the current number. For example, if we use the array “1 6 5 2 4 3” and we check for the number of inversions we would generate the following table:
| Value | Inversions |
| 1 | 0 |
| 6 | 4 |
| 5 | 3 |
| 2 | 0 |
| 4 | 1 |
| 3 | 0 |
| Total: | 8 |
We can now check for the “YES” conditions. If the first condition holds true we return “YES”. If the second condition holds true we also return “YES”. If we get to the end of the function we return “NO” because we cannot sort the array. This mechanism is explained in the “Solvability of the Tiles Game” web page.
/**
* Count the number of inversions in the specified array. An inversion is when a
* tile precedes another tile with a lower number on it.
*/
static int inversions(int[] A) {
// **** count of inversions ****
int inversion = 0;
// **** ****
for (int i = 0; i < A.length; i++) {
int v = A[i];
for (int j = i + 1; j < A.length; j++) { if (v > A[j]) {
inversion++;
}
}
}
// **** return the count of inversions ****
return inversion;
}
The inversions() function counts the number of inversions. It does so by checking each entry in the array against the remaining entries. On each entry it checks to see if the selected value is greater than the current one (the values are inverted). The method returns the sum of all inversions.
Hope you enjoyed this post and most important learned something which perhaps will become relevant to solve a future issue / problem at work.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa