Hope you had a happy Thanksgiving Day with your family. As usual there is lots of anticipation and suddenly it is over.
Some years my wife and I have gone out shopping on Black Friday, but as time goes by, it seems that most of the shopping can be done on-line. For that, the best day seems to be Cyber Monday. Besides the ability of shopping from the computer on Cyber Monday, there was a lot of snow and ice over in the Twin Cities of Minneapolis and St. Paul over the Thanksgiving holiday. One of my wife’s nephews posted on Facebook a video of cars slipping and sliding all over in Minneapolis.
We have two sons and they are both married and have children. One lives in Wisconsin and the other in a suburb of the Twin Cities about 15 minutes away by car. Last year was the last time we celebrated Thanksgiving at home. This year both decided to celebrate it in their places. My wife and I had late lunch last Thursday with our son that lives nearby. He had to leave with his family around 05:00 PM to visit the mother of his wife. We headed home, lit (with the click of a button) the fireplace and watch a movie on Netflix before heading to bed.
We usually shop for groceries on Thursday evenings after work. That was not possible last week so we moved it to Saturday in order to avoid Black Friday. We started around 09:00 AM and after two stops made it home around 11:00 AM. We decided not to fix a turkey this year but we saw some nice fresh turkeys at Costco so we got one. Shortly after 01:00 PM the bird was in the oven.
We had an issue with the oven. I cut some potatoes and sweet potatoes, seasoned them with olive oil, salt and pepper and put them in the oven. The temperature was set to 325 F so we could put in the turkey as soon as it was ready. I inserted the temperature probe in the breast of the bird and we were ready to start roasting or late Thanksgiving meal. So we opened the oven and put in the turkey. My wife was making sure that the cable between the probe and the thermometer was out of the way. We were ready to sit down and chat with some wine while the oven would reach temperature (and beep) again. The turkey started at 39 F so it had to make it to 178 F we could remove it from the oven. It typically gets to 182 F while resting on the counter and before carving.
We were chatting and an hour went by. We could not recall if we heard the oven beep after reaching temperature. I decided to check how things were going. Apparently we missed closing the oven door properly so the oven was not working. Closed the door and the fans and lights came on. After about an hour we pulled out the tray with the potatoes. They looked quite nice. The turkey needed some additional time.
We decided to watch a movie. While watching we got up to graze on some potatoes. Around 05:00 PM the turkey was done. We had very little turkey and a few sweet potatoes. We decided to skip on the pie. We figured we had the rest of the weekend to enjoy our turkey.
Now let’s get to the main subject of this post. I looked up the first MEDIUM rated challenge at HackerRank and decided to tackle it. If you are interested, read more about it on the Organizing Containers of Balls challenge web page.
It took me a few minutes to understand what the challenge was all about. At that point I wrote my own test scaffolding. I like to have some additional time to think and understand the issue at hand before starting on the actual solution. This is the essence of TDD (Test Driven Development).
To make sure I did not waste time, I looked at the code so I could define the same function in my solution. That done I generated the following diagram:
The diagram is based on the second set of test cases provided by HackerRank. The top matrix represents the contents of tree containers. The first container contains three balls of type ‘0’, type ‘1’ and type ‘2’. There is 1 ball of type ‘0’, 3 of type ‘1’ and 1 of type ‘2’.
The contents of the second container are represented by the second row in the same matrix. It contains 2 balls of type ‘0’, 1 ball of type ‘1’ and 2 balls of type ‘2’ for a total count of 5 balls.
The third and last container contains 3 balls of each type for a total of 9 balls.
Note that the sum of balls per container is in a 1 x 3 matrix on the right of the 3 x 3 matrix. In addition we have a third matrix located in the bottom of the first one. This 3 x 1 matrix contains the total counts of balls of each type. The first entry indicates that we have 6 balls of type ‘0’, the second that we have 7 balls of type ‘1’ and the third shows that we have 6 balls of type ‘2’.
Spend some time looking at the diagram and thinking about the sort method specified in this challenge:
“David wants to sort the balls using his sort method. As an example, David has n = 2 containers and 2 different types of balls, both of which are numbered from 0 to n – 1 = 1. The distribution of ball types per container are described by an n x n matrix of integers, M[container][type]. In a single operation, David can swap two balls located in different containers.”
2 2 1 1 1 1 2 0 2 1 1 Possible Impossible
In this example, we have 2 queries. The first uses a 2 x 2 matrix to specify the initial contents of the 2 containers. The first container has 1 ball of type ‘0’ and 1 ball of type ‘1’. The second container has a similar set of balls. The second query has 0 balls of type ‘0’ and 2 balls of type ‘1’. The results indicate that the first configuration can be sorted by David’s method but the second cannot.
2
3
1 3 1
2 1 2
3 3 3
3
0 2 1
1 1 1
2 0 0
organizingContainers <<< hm: {0=6}
organizingContainers <<< hm: {0=6, 1=7}
organizingContainers <<< hm: {0=6, 1=7, 2=6}
Impossible
organizingContainers <<< hm: {0=3}
organizingContainers <<< hm: {0=3, 1=3}
organizingContainers <<< hm: {0=3, 1=3, 2=2}
organizingContainers <<< hm: {1=3, 2=2}
organizingContainers <<< hm: {2=2}
organizingContainers <<< hm: {}
Possible
In this example we switch from a 2 x 2 to a 3 x 3 matrix. We have 3 ball types and 3 containers. We have 2 queries. In this case the first set cannot be sorted and the second can. Note that I have enabled debug statements for the second pass.
The key factor is to incorporate the fact that only 2 balls may be moved at once.
/*
* David wants to perform some number of swap operations such that: - Each
* container contains only balls of the same type. - No two balls of the same
* type are located in different containers.
*
* In a single operation, David can swap two balls located in different
* containers.
*
* Approach: Check if there are any type of balls with the same quantity of that
* of each box.
*/
static String organizingContainers(int[][] container) {
// **** for starters ****
String result = "Possible";
// **** populate hash map of ball counts per type (i.e., '0', '1', ... 'n - 1')
// ****
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for (int col = 0; col < container.length; col++) {
int sum = 0;
for (int row = 0; row < container.length; row++) {
sum += container[row][col];
}
// **** add the type and count to the hashmap ****
hm.put(col, sum);
// ???? ????
System.out.println("organizingContainers <<< hm: " + hm.toString());
}
// **** loop computing the initial number of balls per container ****
for (int row = 0; row < container.length; row++) {
// **** compute number of balls per container (i.e., 0, 1, 2, n - 1) ****
int sum = 0;
for (int col = 0; col < container.length; col++)
sum += container[row][col];
// // ??? ????
// System.out.println("organizingContainers <<< sum: " + sum);
// **** get associated sum (value) ****
if (hm.containsValue(sum)) {
// **** remove key with specified value ****
hm.values().remove(sum);
// ???? ????
System.out.println("organizingContainers <<< hm: " + hm.toString());
} else {
result = "Impossible";
break;
}
}
// **** return result ****
return result;
}
The origanizingContainers() function receives the n x n matrix described above. We start by defining a result string and setting its value to “Possible”.
We then declare a hash map and populate it with the ball counts per type. The first column in the matrix holds the total count of balls of type ‘0’, the second for balls of type ‘1’ and the third for balls of type ‘2’.
We then compute the number of balls per container. This information is key because the final numbers must contain the same counts given the sorting method that David will use.
In the first matrix, we figure out that it is not possible to sort when we get the container count of 5.
In the second matrix, we see that the counts are 3, 3, and 2 for the ball types ‘0’, ‘1’ and ‘2’. The first container has 3 balls so we remove from the hash map an entry with 3 balls. The second container has 3 balls so we remove the next entry with 3 balls. Finally the number of balls in the third container is 2 so we remove the last entry that has a matching count of 2. Given that we exhausted / matched the counts the sort mechanism is possible.
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
Follow me on Twitter: @john_canessa