Good morning software developers and engineers. Hope your work week has started on the right note! After a few rather warm days, we are back to highs in the low 70’s F. Trees in this area are losing leaves. It is very typical for the season. This year it seems that fall has been delayed by a couple weeks.
My wife and I will have company for lunch. A family member is joining this afternoon. Due to the changes in weather my wife and I no longer walk in the mornings. We are walking around noon. The sun (if it shows its face today) is above us at that time. Having it on our face on our way back is no fun. In addition it seems that around 06:00 PM bugs like to be active.
We just lost Internet access. I reset the router but at no avail. My wife will call our provider to see if the problem is wide spread or specific to us. It is amazing how dependent on technology we have grown to be accustomed to.
It seems that this blog at this time has reached 9,434 subscribers. Thanks to all of you that have subscribed to it.
Yesterday morning I tackled the HackerRank problem “New Year Chaos” using Java. I did not have a chance to generate a post. I am doing so between 2-hour blocks.
It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others. Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print `Too chaotic`.
For some reason the description of this problem is more complicated than what it should be. Not only that; but the signature of the function of interest does not seem to match the description. I guess that with time changes are made to descriptions and the entire problem is not properly updated.
In this post we will try to solve the problem using the Java programming language using the VSCode IDE on a Windows computer. The simplest way to solve the problem is to use the IDE provided by HackerRank. That said; you may run into issues with the supported Java versions and additional libraries you might have to include.
Since we are solving this problem on my computer, we will need a test scaffold to collect the input, declare and populate the input data, and call the function of interest. In this case it seems that values are not returned so the function of interest must display results.
In a nutshell we are given a list of integers in the range [1 … n] which represents a queue of people waiting to board a roller coaster. It seems that some people may get ahead in the queue. We need to count how many people got ahead by one, two or more places. We need to count the number of bribes that were incurred by the unruly people. There is a caveat. If someone buys their way ahead in the queue by more than two spots, we give up counting and print the following message “Too chaotic” to indicate that things are out of control and we will stop counting.
In general HackerRank likes to generate lengthy descriptions for most of the problems. It seems this one is somewhat on the top of verbose.
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
*/
public static void minimumBribes(List<Integer> q) {
// Write your code here
}
The signature for the function of interest seems to indicate that the input is an array of int[], but the actual argument is a List<Integer>. We will use the input list and then extract the associated array.
1 8 5 1 2 3 7 8 6 4 main <<< q: [5, 1, 2, 3, 7, 8, 6, 4] <<< bribes: 0 arr: [5, 1, 2, 3, 7, 8, 6, 4] <<< bribes: 2 arr: [5, 1, 2, 3, 7, 6, 4, 8] <<< bribes: 4 arr: [5, 1, 2, 3, 6, 4, 7, 8] <<< bribes: 5 arr: [5, 1, 2, 3, 4, 6, 7, 8] Too chaotic 1 8 1 2 5 3 7 8 6 4 main <<< q: [1, 2, 5, 3, 7, 8, 6, 4] <<< bribes: 0 arr: [1, 2, 5, 3, 7, 8, 6, 4] <<< bribes: 2 arr: [1, 2, 5, 3, 7, 6, 4, 8] <<< bribes: 4 arr: [1, 2, 5, 3, 6, 4, 7, 8] <<< bribes: 5 arr: [1, 2, 5, 3, 4, 6, 7, 8] <<< bribes: 7 arr: [1, 2, 3, 4, 5, 6, 7, 8] 7 1 4 4 1 2 3 main <<< q: [4, 1, 2, 3] <<< bribes: 0 arr: [4, 1, 2, 3] Too chaotic 1 5 2 1 5 3 4 main <<< q: [2, 1, 5, 3, 4] <<< bribes: 0 arr: [2, 1, 5, 3, 4] <<< bribes: 2 arr: [2, 1, 3, 4, 5] <<< bribes: 3 arr: [1, 2, 3, 4, 5] 3 1 5 2 5 1 3 4 main <<< q: [2, 5, 1, 3, 4] <<< bribes: 0 arr: [2, 5, 1, 3, 4] Too chaotic 1 5 1 2 3 5 4 main <<< q: [1, 2, 3, 5, 4] <<< bribes: 0 arr: [1, 2, 3, 5, 4] <<< bribes: 1 arr: [1, 2, 3, 4, 5] 1 1 5 3 1 4 2 5 main <<< q: [3, 1, 4, 2, 5] <<< bribes: 0 arr: [3, 1, 4, 2, 5] <<< bribes: 1 arr: [3, 1, 2, 4, 5] <<< bribes: 3 arr: [1, 2, 3, 4, 5] 3
There are a few test cases provided. The first input line indicates the number of test cases. For ease of use I have set it to `1` so we deal with a single problem at a time.
The second input line contains the number of elements / people in the queue.
The third and last input line contains the final order for people in the queue.
Our test scaffold will ignore the first two input lines.
After processing the input data, our test code displays the input data to make sure all is well so far. Note that the description suggests an array but the signature calls for a queue / list.
The last line in the set displays our result. The intermediate lines ARE NOT PART OF THE SOLUTION. We will use them to check how the process is working.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** skip # of test cases ****
br.readLine();
// **** skip # of elements in the queue ****
br.readLine();
// **** read the list of integers ****
List<Integer> q = Arrays.stream(br.readLine().trim().split(" "))
.map(Integer::parseInt)
.collect(Collectors.toList());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< q: " + q.toString());
// **** call the function of interest which displays the result ****
minimumBribes(q);
}
Not much to add to the test scaffolding code. We read the input line into a List<Integer> which we then pass to the function of interest.
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
* Failed to pass initial test set.
*/
public static void minimumBribes0(List<Integer> q) {
// **** initialization ****
int bribes = 0;
// **** traverse the q forwards ****
for (int i = 0; i < q.size() - 1; i++) {
// **** person (for ease of use) ****
int p = q.get(i);
// **** check if this person used a bribe ****
if (p - (i + 1) > 0 ) {
// ???? ????
System.out.println("<<< p: " + p + " (p - (i + 1)): " + (p - (i + 1)));
// **** check if this person is chaotic ****
if (p - (i + 1) >= 3) {
System.out.println("Too chaotic");
return;
}
// **** increment the bribe count ****
bribes += (p - (i + 1));
}
}
// **** display # of bribes ****
System.out.println(bribes);
}
I started with a different approach which I dropped at some point.
The idea was to not perform the swaps and just count them. The reason I stopped was due to the fact that the process started simple but started to get complicated when addressing the case when a person moved forward two or more places in the queue.
If interested, you may complete this code and let me know. I will update this post and will give you credit.
/**
* Auxiliary function.
* Swaps two elements in the array.
*/
static private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
This is just a simple auxiliary function that I was going to use. I ran into issues while posting my code to HackerRank. It worked fine on my computer, but that does not count. I ended removing the calls to the swap() function.
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
*
* Execution: O(n) - Space: O(1)
*/
public static void minimumBribes(List<Integer> q) {
// **** initialization ****
int bribes = 0;
int tmp = 0;
// **** generate array from queue (for ease of use) ****
// Integer[] arr = q.toArray(Integer[]::new);
int[] arr = new int[q.size()];
for (int i = 0; i < arr.length; i++)
arr[i] = q.get(i);
// ???? ????
System.out.println("<<< bribes: " + bribes + " arr: " + Arrays.toString(arr));
// **** traverse the array backwards swapping elements back in place ****
for (int i = arr.length - 1; i > 0; i--) {
// **** person in proper place in the queue ****
if (arr[i] == (i + 1))
continue;
// **** swap people one appart ****
else if (arr[i - 1] == (i + 1)) {
// **** ****
// swap(arr, i - 1, i);
tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
// **** increment bribe count ****
bribes++;
}
// **** swap people two appart ****
else if (arr[i - 2] == (i + 1)) {
// **** ****
// swap(arr, i - 2, i - 1);
tmp = arr[i - 2];
arr[i - 2] = arr[i - 1];
arr[i - 1] = tmp;
// swap(arr, i - 1, i);
tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
// **** increment bribe count ****
bribes += 2;
}
// **** too many swaps ****
else {
System.out.println("Too chaotic");
return;
}
// ???? ????
System.out.println("<<< bribes: " + bribes + " arr: " + Arrays.toString(arr));
}
// **** display # of bribes ****
System.out.println(bribes);
}
We start by initializing a couple variables.
We then populate an int[] array with the contents of the input queue. The commented line works fine in the VSCode IDE I used for development.
Please note that the print statements proceeded by “// ???? ????” lines are NOT PART OF THE SOLUTION. They are used to help us visualize how the algorithm progresses.
We then enter a loop used to traverse the input array backwards.
We then process data base on the position of the current individual in the queue. The first condition addresses a person in their proper spot (no bribes).
Next we address people that moved one spot ahead their place in the queue. To handle them we need to swap positions and increment the number of bribes by one.
In the next if we handle the situation when a person bribed two places ahead in the queue. In such cases we need to swap the two previous locations and increment the bribe count by two.
In the default else we address individuals that bribed their way more than two spots in the queue. As instructed we display the “Too chaotic” message (make sure you spell it correctly of your submission will fail) and return to indicate we are done processing the rest of the queue.
This solution was accepted by HackerRank. The problem runs in O(n) time and O(1) space.
I had a good time working on this problem despite the convoluted description. In general when encountering a problem one should distill requirements to a simple description before attempting to write code.
The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John