DateFieldCorrection
SRM 375 · 2007-11-10 · by darnley
Problem Statement
An application you're working on contains an input text field where a user types in a date.
The user is instructed to type in a date in the form "<Month> <Day>" (quotes for clarity), where <Month> is the English name of the month ("January", "February", etc.) and <Day> is the day of the month, without leading zeroes.
However, a user can make errors when typing. The following model is suggested: the user always presses the correct number of keys, but he or she can mistype one key for another. Let's define the penalty for a typing error as the length of the shortest path between the key that was actually pressed and the intended key in the graph shown below.
Here red lines denote edges of length 1 and green lines denote edges of length 3. When calculating the penalty, the cases of the letters are ignored.
Obviously, the penalty for typing a correct key is 0. Now, define the distance between the input of the user and a correct date of the same length as the sum of the penalties for mistyping over all corresponding characters.
For example, distance("TopCoder", "March 31") = penalty("T", "M") + penalty("O", "A") + ... + penalty("R", "1") = 4 + 8 + 6 + 0 + 3 + 4 + 1 + 4 = 30
Given a
Notes
- Consider February 29 a valid date (as it is in leap years).
- The names of the months are "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" and "December".
- The lengths of the corresponding months are 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30 and 31 days.
Constraints
- input will contain between 5 and 12 characters, inclusive.
- input will contain only uppercase and lowercase letters ('A'-'Z', 'a'-'z'), digits ('0'-'9') and spaces (' ').
"Novebmer 10" Returns: "November 10"
Swapping "b" and "m" is just a little typo and should be corrected easily.
"September 15" Returns: "September 15"
A date that is typed in correctly shouldn't be changed at all.
"Juny 4" Returns: "June 4"
"Juny" could stand both for "June" and "July". The penalty for mistyping is 3 in each case. If that's the case, June is preferred because it is earlier than July.
"Juny 31" Returns: "July 31"
Once again, both June and July could have been meant by the user. However, if it's June then there is at least one typo in the day (there is no 31th day in June).
"TopCoder" Returns: "April 24"
"JNpSuQ " Returns: "June 10"
36 ties
"KtQWOvk9l " Returns: "November 2"
if days start from 0, fails with 'november 0'
"mrhzx5" Returns: "June 5"
checks that there's no edge('z', ' ')=3
"OrImxz" Returns: "May 21"
checks that 'm' and ' ' are connected by an edge of length 3
"Zarih 15" Returns: "March 15"
Checks that penalty('z', 'm') = 6
"ytvcbrcf 31" Returns: "December 31"
equidistant from Feb, Nov and Dec
"gbrIA qU" Returns: "April 17"
Checks that penalty(A, L)=8
"cqriL " Returns: "April 20"
Checks that distance(P, Q)=9
"be P " Returns: "December 20"
Checks that distance(M, P)=3
"a1rhi OK" Returns: "March 30"
Checks that distance(A, 1)=2
"Ju0c GO" Returns: "July 30"
Chechs that distance(L, 0)=2
" E 0 7" Returns: "September 7"
Checks that distance(0, M)=3
"AELB A1" Returns: "September 1"
Checks that penalty(P, L)=1
" E K 1" Returns: "September 1"
Checks that penalty(K, M)=1
"9E 9 L99991" Returns: "September 1"
"Checks that distance(M, L)=2"
" IR 5" Returns: "March 5"
Checks that penalty(' ', L)=5
Submissions are judged against all 127 archived test cases, of which 21 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DateFieldCorrection with a public method string correctDate(string input) · 127 test cases · 2 s / 256 MB per case