Statistics

Problem Statement for "DateFieldCorrection"

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 String input, return a correct date (in the format described above) that has the smallest distance from the input. In case of a tie, return the date that is earlier in the year.

Definition

Class:
DateFieldCorrection
Method:
correctDate
Parameters:
String
Returns:
String
Method signature:
String correctDate(String input)
(be sure your method is public)

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 (' ').

Examples

  1. "Novebmer 10"

    Returns: "November 10"

    Swapping "b" and "m" is just a little typo and should be corrected easily.

  2. "September 15"

    Returns: "September 15"

    A date that is typed in correctly shouldn't be changed at all.

  3. "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.

  4. "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).

  5. "TopCoder"

    Returns: "April 24"

  6. "fantastic 9"

    Returns: "February 29"

  7. "darnley"

    Returns: "March 6"

  8. "good luck"

    Returns: "August 30"

  9. "have fun"

    Returns: "March 26"

  10. "yesterday"

    Returns: "January 6"

  11. "today"

    Returns: "May 6"

  12. "tomorrow"

    Returns: "August 2"

  13. "ALWAYS"

    Returns: "June 2"

  14. "SoMeTiMeS"

    Returns: "August 22"

  15. "never"

    Returns: "May 4"

  16. "1010101010"

    Returns: "October 10"

  17. "121212121212"

    Returns: "September 12"

  18. "MnjGVZpZ"

    Returns: "March 31"

  19. "JNpSuQ "

    Returns: "June 10"

    36 ties

  20. "KtQWOvk9l "

    Returns: "November 2"

    if days start from 0, fails with 'november 0'

  21. "test "

    Returns: "May 2"

  22. "test "

    Returns: "June 2"

  23. " "

    Returns: "May 2"

  24. "June 3 "

    Returns: "June 30"

  25. "catcbrctaf"

    Returns: "February 4"

  26. "satcbrctaf"

    Returns: "December 4"

  27. "shushpunchik"

    Returns: "September 30"

  28. "qwertyuiop"

    Returns: "February 9"

  29. "asdfghjkl"

    Returns: "August 30"

  30. "zxcvbnm "

    Returns: "August 2"

  31. "1234567890"

    Returns: "February 9"

  32. "mrhzx5"

    Returns: "June 5"

    checks that there's no edge('z', ' ')=3

  33. "OrImxz"

    Returns: "May 21"

    checks that 'm' and ' ' are connected by an edge of length 3

  34. "Zarih 15"

    Returns: "March 15"

    Checks that penalty('z', 'm') = 6

  35. "oCTOPUS 0"

    Returns: "October 9"

  36. " if "

    Returns: "June 2"

  37. "tbe6in0t"

    Returns: "March 25"

  38. "34567890"

    Returns: "August 9"

  39. "kEuIrctLEQ"

    Returns: "January 31"

  40. "8 if eq"

    Returns: "July 31"

  41. "february 30"

    Returns: "February 20"

  42. "apron 31"

    Returns: "April 21"

  43. "M00 32"

    Returns: "May 22"

  44. "sovetSKiY 31"

    Returns: "September 21"

  45. "noWONDERing"

    Returns: "November 25"

  46. "a wonder 31"

    Returns: "December 31"

  47. "vyhunter 31"

    Returns: "November 21"

  48. "CATcbrct 3o"

    Returns: "December 30"

  49. "ytvcbrcf 31"

    Returns: "December 31"

    equidistant from Feb, Nov and Dec

  50. "yTvCbrCftep"

    Returns: "November 30"

  51. "August 31"

    Returns: "August 31"

  52. "gbrIA qU"

    Returns: "April 17"

    Checks that penalty(A, L)=8

  53. "cqriL "

    Returns: "April 20"

    Checks that distance(P, Q)=9

  54. "be P "

    Returns: "December 20"

    Checks that distance(M, P)=3

  55. "a1rhi OK"

    Returns: "March 30"

    Checks that distance(A, 1)=2

  56. "B0RE D"

    Returns: "April 23"

  57. "Ju0c GO"

    Returns: "July 30"

    Chechs that distance(L, 0)=2

  58. " E 0 7"

    Returns: "September 7"

    Checks that distance(0, M)=3

  59. "AELB A1"

    Returns: "September 1"

    Checks that penalty(P, L)=1

  60. " E K 1"

    Returns: "September 1"

    Checks that penalty(K, M)=1

  61. "9E 9 L99991"

    Returns: "September 1"

    "Checks that distance(M, L)=2"

  62. " IR 5"

    Returns: "March 5"

    Checks that penalty(' ', L)=5

  63. " 9R 5"

    Returns: "April 5"

  64. " 0R1H 25"

    Returns: "March 25"

  65. " NRBK 09"

    Returns: "March 29"

  66. "AZR6KV00"

    Returns: "March 30"

  67. "239566"

    Returns: "July 6"

  68. "566239"

    Returns: "June 9"

  69. "PBBJAER 15"

    Returns: "October 15"

  70. "day 39"

    Returns: "May 29"

  71. "JUKFU4"

    Returns: "July 4"

  72. "MDVember 16"

    Returns: "November 16"

  73. "SQaaBD 1"

    Returns: "August 1"

  74. "C1RIL 11"

    Returns: "April 11"

  75. "C1RKLOOO"

    Returns: "March 30"

  76. "Ybri1OO"

    Returns: "March 9"

  77. "Gbri1OO"

    Returns: "April 9"

  78. "TPZbZLind1"

    Returns: "January 31"

  79. "C5I923pGjs"

    Returns: "February 2"

  80. "MB6yUxcgst9"

    Returns: "February 29"

  81. "V2enBFAYZEk"

    Returns: "December 30"

  82. "Lqfgvheq"

    Returns: "March 31"

  83. "YOsVn3Us"

    Returns: "August 2"

  84. "wqBMO37k"

    Returns: "April 30"

  85. "3TC9vxEZ"

    Returns: "August 1"

  86. "psGwYA"

    Returns: "May 31"

  87. "Vg6W5x"

    Returns: "June 2"

  88. "yKTsmO0"

    Returns: "June 30"

  89. "z9xyc3a"

    Returns: "July 31"

  90. "LioTd4Z"

    Returns: "July 31"

  91. "LDlsITS"

    Returns: "March 2"

  92. "1F4Fs7uE1"

    Returns: "August 31"

  93. "TdaMR6Zf2"

    Returns: "October 2"

  94. "H9AIT4zfg38l"

    Returns: "September 30"

  95. "xgDOgU8Jpjia"

    Returns: "September 21"

  96. "KTPZXEsbe1"

    Returns: "October 31"

  97. "Kg07NXLcJS"

    Returns: "October 22"

  98. "Zj5AGy1Q6i "

    Returns: "November 30"

  99. "40N7GUDf7hz"

    Returns: "November 21"

  100. "u1JvmH6wGgQ"

    Returns: "December 31"

  101. "qJfazfd3ZKW"

    Returns: "September 2"

  102. "wraThofkHan9"

    Returns: "September 29"

  103. "February 29"

    Returns: "February 29"

  104. "AAAAAAAA"

    Returns: "March 11"

  105. "nrhcz4"

    Returns: "May 14"

  106. "z a wzu"

    Returns: "March 7"

  107. "January 0"

    Returns: "January 9"

  108. "may "

    Returns: "May 2"

  109. "klfjhkj"

    Returns: "April 7"

  110. " p l "

    Returns: "January 2"

  111. " "

    Returns: "June 2"

  112. "May "

    Returns: "May 2"

  113. "Jun 11"

    Returns: "May 11"

  114. "ghjh "

    Returns: "May 2"

  115. "U5C1ZOsv"

    Returns: "March 24"

  116. " "

    Returns: "November 2"

  117. "0u8a "

    Returns: "May 2"

  118. " mmm"

    Returns: "March 30"

  119. " AAAAA"

    Returns: "March 1"

  120. "kuam 1"

    Returns: "July 1"

  121. " "

    Returns: "October 2"

  122. "Noveber 11"

    Returns: "October 11"

  123. "LpP 1 27"

    Returns: "March 27"

  124. "July 3131"

    Returns: "August 31"

  125. "Ma v 5"

    Returns: "June 5"

  126. "Aprist11"

    Returns: "April 11"

  127. "QesdP K2"

    Returns: "April 22"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: