Read on Twitter
[Algorithm Analysis] #algorithms
Today, I will be reviewing an interesting programming question that demonstrates the importance of being aware of the "corner cases".
The problem is as follows:
![[Algorithm Analysis] #algorithmsToday, I will be reviewing an interesting programming question that demonstrates the importance of being aware of the "corner cases".The problem is as follows:](https://pbs.twimg.com/media/Eglt8lyUwAACRK5.png "[Algorithm Analysis] #algorithmsToday, I will be reviewing an interesting programming question that demonstrates the importance of being aware of the \"corner cases\".The problem is as follows:")
Today, I will be reviewing an interesting programming question that demonstrates the importance of being aware of the "corner cases".
The problem is as follows:
Said problem has the following input/output examples:
Example 1. Input:
2 3
4 2
5 7 6
Output: 25
Example 2. Input:
8 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Output: 1
Example 1. Input:
2 3
4 2
5 7 6
Output: 25
Example 2. Input:
8 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Output: 1
My initial solution was to loop through the first line of input and store the smallest number inside another variable, and then doing the same thing with the second line of input. The code more-or-less looks like the following:
And then, once I found the smallest number within the list, I will compare these numbers with the following cases:
1. Whether the numbers are equal to each other
2. If not, whether the "pretty integer" will be the smallest if the digit from the first list is in the tens place
1. Whether the numbers are equal to each other
2. If not, whether the "pretty integer" will be the smallest if the digit from the first list is in the tens place
3. Or, whether the "pretty integer" will be the smallest if the digit from the second list is in the tens place.
This logic can be drawn into code as the following:
This logic can be drawn into code as the following:
With the two code snippet above, I can safely find the smallest number within the two lists AND also check whether the smallest number is equal (which means that a one-digit answer will fulfill the "pretty integer" conditions).
However, what I did NOT consider was whether the repeating integer was NOT the smallest digit in the list. For example, consider two list consisting of only two digits:
1 3
1 2
With the algorithm above, my answer will be 12, while in the correct answer would have been 3.
1 3
1 2
With the algorithm above, my answer will be 12, while in the correct answer would have been 3.
This is because I only relied on finding the smallest integer while assuming that the smallest integer would be the repeating digit between the two lists. With this initial assumption, I missed the fact that the repeating digit might not be the smallest number in the list.
Now, what was interesting in this certain case was that it took me a good 12 hours to finally realize where I went wrong!
It was funny to see how sure I was about the code, and that I had the initial judgement that the Online Judge system was just broken.
It was funny to see how sure I was about the code, and that I had the initial judgement that the Online Judge system was just broken.
This is why practice is so important. The mind isn't used to solving these kinds of problems where you have to view it from multiple angles while also being flexible with your paradigms. Aside from practicing, it is important to take note and document your mistakes.
Anyways, back to the problem. Because of this, I had to edit my algorithm so that it could achieve the following:
1. Check for the same number within the two lists, and find which same number is the smallest.
2. Outside the same number, check for digit placement.
1. Check for the same number within the two lists, and find which same number is the smallest.
2. Outside the same number, check for digit placement.
To check for the same number within the two list, I had to iterate between one digit in the first list and compare it with all the digit in the second list until I find a match. Because it is not sorted, I could not apply any fancy algorithms. So, I used the double-for-loop trick
At a glance, the algorithm to check for the first case is as follows.
I also had to initialize another variable to hold the value of the current same digits, so that I can compare it with the current iteration and check whether one is smaller than the other.
I also had to initialize another variable to hold the value of the current same digits, so that I can compare it with the current iteration and check whether one is smaller than the other.
Next, I had to loop through the same list individually and find the smallest number within the list. This is the same logic as the initial algorithm:
Lastly, I had to compare between the answers.
Overall, this is what the whole code looks like (do excuse the comments)
Now, after writing this Twitter thread, I realized that we could make one optimization. The fact that if the computer found an integer that appears in both list, and has confirmed that it is the smallest integer, then it will definitely be the smallest "pretty integer".
Because of this, I might try and add another conditional statement after checking for "current_same" and see whether it has changed in value (meaning that the computer has found the smallest "pretty integer").
Will update on whether it works or not.
Will update on whether it works or not.
Thank you for taking the time to read this thread! Keep practicing.
