Statistics

Problem Statement for "Mail"

Problem Statement

You work at a mail distribution center which has to send letters to branch distribution hubs that each handle a certain zip code. However, you may have letters whose zip codes are not correct. Therefore, you must make the best estimate as to where the author of the letter intended to send it.

You are to deliver each letter to the office which handles the zip code closest to the read zip code. Closeness to a zip code is measured by a score. You should deliver the letter to the office which has the highest score. The score for each comparison between a pair of zip codes starts at 0 and is calculated as follows:

1) For every digit in one zip code that is identical to the digit in the other zip code at the same position, add 6.

2) For every two digits that are transposed (that is, two digits next to each other in one zip code are in the same positions in the other zip code, but swapped), add 5. (see example 1)

3) Sometimes people write numbers that look like other numbers, for example a "1" may look like a "7" or vice versa. Therefore, if a digit in one zip code is the first number in one of the following pairs, and the digit in the other zip code in the same position is the second number, add 2:
(9 and 6)
(9 and 0)
(7 and 2)
(7 and 1)

4)If a digit in one zip code and the digit in the other zip code at the same position have a difference of 1, add 1.

You should apply each rule to every digit that satisfies the rule, starting with the left digit and ending with the right. A digit can only be used to add points to the score once. For example, when comparing "23232" and "32323", you can use the digits at position 0 and 1 to apply the transposition rule. However, since you already used digit 1, you cannot apply the transposition rule to digits 1 and 2.

You should also apply the rules in the order given above, e.g. apply rule 1, then rule 2, etc. If a digit is used to add points in a previous rule, it cannot be used to add points in a later rule. For example, when comparing "23232" and "32323" you cannot use the difference-of-one rule on digits 0 and 1 because they were used in the transposition rule.

If the score of an office is less than 10, that office cannot be used for that letter since the zip codes are too different. If there are no offices with a score greater than or equal to 10, the letter should be returned to the sender, and not included in the return value.

Create a class Mail that contains the method handleBadZips, which takes two arguments:
offices: a String[] where each element is the zip code that a particular office handles.
letters: a String[] where each element is the zip code that is written on a letter.
The return value should be a int[] the same length as offices, which contains the number of letters sent to each office. The first element is the number of letters sent to the first office in offices, the second element is the number sent to the second office, etc..

Definition

Class:
Mail
Method:
handleBadZips
Parameters:
String[], String[]
Returns:
int[]
Method signature:
int[] handleBadZips(String[] offices, String[] letters)
(be sure your method is public)

Notes

  • If two offices have the same score, send the letter to the one which comes first in offices.
  • For rule 3, the comparisons should be made both ways. For example, zip code A can have a 9, and B have a 6, or A can have a 6, and B have a 9.

Constraints

  • offices will have between 1 and 50 elements inclusive.
  • letters will have between 1 and 50 elements inclusive.
  • Elements in offices and letters will consist of 5 numeric digits '0' - '9'.
  • There will be no repeat elements in offices.

Examples

  1. {"90211", "09210", "12345", "88888", "69779"}

    {"90210"}

    Returns: { 1, 0, 0, 0, 0 }

    There is only one letter, "90210". The scores for the offices are described as follows "90211": 25 - the first four characters match the letter, yielding 24 points, and the final character is one different, adding 1 point. "09210": 23 - the last three characters match, and the first two are swapped, scoring 3x6 + 5. "12345": 1 - third character is 1 away. "88888": 1 - the first character is 1 away. "69779": 10 - each character could be miswritten for another character. 6 could be a 9, 9 could be a 0, 7 could be a 2 or a 1, and 9 could be a 0.

  2. {"88888", "66666", "22222"}

    {"84444", "77771", "99999"}

    Returns: { 0, 1, 0 }

    For the first letter ("84444"): "88888": 6 - only one character matches. "66666": 0 "22222": 0 Since no office scored 10 or above, this letter is returned to the sender Second letter ("77771"): "88888": 4 - 4 characters are one away "66666": 4 - again, 4 characters are one away "22222": 9 - 4 characters are misprints, and the last character is one away. Since no office scored 10 or above, this letter is returned to the sender. Third letter ("99999"): "88888": 5 - 5 characters are one away "66666": 10 - all 5 characters are misprints "22222": 0 This letter is sent to the second office, since its score barely makes the 10 point cutoff.

  3. {"14736", "23741", "09284", "27481", "56456", "89148"}

    {"12375", "99642", "12763", "84564"}

    Returns: { 2, 0, 0, 0, 0, 1 }

  4. {"99741", "43676", "29658", "51324", "63050", "40201", "56022", "05849", "14530", "95320", "78483", "87520", "65968", "11448", "41706", "56938", "55547", "61772", "53683", "16845", "26576", "32434", "38942", "02605", "85569", "24182", "56250", "45620", "29924", "60094", "41872", "65462", "49503", "66523", "07303", "64730", "57092", "03646", "78272", "52249", "51412", "72873", "57880", "66012", "14746", "82393", "11797", "44792", "93143", "18375"}

    {"08206", "78796", "04882", "56929", "60604", "40830", "09365", "37726", "32444", "01451", "03499", "32353", "36587", "80743", "52645", "05758", "26574", "89852", "48852", "17674", "18422", "36017", "93203", "81219", "21999", "16751", "53110", "51611", "81677", "68246", "63250", "22491", "41806", "06058", "83359", "36906", "13082", "80426", "90397", "21943", "95730", "90046", "32130", "25284", "55551", "50690", "38965", "21679", "56922", "75037"}

    Returns: { 3, 0, 2, 0, 3, 1, 2, 1, 0, 0, 0, 1, 0, 1, 4, 0, 2, 1, 1, 0, 3, 3, 2, 1, 0, 3, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0, 1, 2, 0, 1, 2 }

  5. {"17777", "77777"}

    {"18888", "22222"}

    Returns: { 1, 1 }

  6. {"18888", "22222"}

    {"17777", "77777"}

    Returns: { 1, 1 }

  7. {"54321","23451"}

    {"12345", "12345"}

    Returns: { 0, 0 }

  8. {"11111","22222","33333","44444","55555","66666","77777","88888","99999","00000"}

    {"12457","11111","12121","45654","99988","12345","98765"}

    Returns: { 2, 0, 0, 0, 1, 1, 1, 0, 1, 0 }

  9. {"12121"}

    {"23232"}

    Returns: { 0 }

  10. {"12121"}

    {"21232"}

    Returns: { 0 }

  11. {"67876","87878"}

    {"98789"}

    Returns: { 1, 0 }

  12. {"67876","87898"}

    {"98789"}

    Returns: { 0, 1 }

  13. {"54320","54310","54210","53210"}

    {"54321","54721","43210"}

    Returns: { 2, 0, 0, 1 }

  14. {"66666","22222","11111"}

    {"99999","77777","10101"}

    Returns: { 1, 1, 1 }

  15. {"99999","66666"}

    {"11111","55555"}

    Returns: { 0, 0 }

  16. {"12345","23456","34567","45678","56789","67890","78901","89012","90123","01234"}

    {"11111","22222","33333","44444","55555","66666","77777","88888","99999","00000"}

    Returns: { 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 }

  17. { "19900" }

    { "16622" }

    Returns: { 1 }

  18. { "66666" }

    { "61199" }

    Returns: { 1 }

  19. { "90210" }

    { "90210" }

    Returns: { 1 }

  20. { "12348" }

    { "21435" }

    Returns: { 1 }

  21. { "44444" }

    { "33333" }

    Returns: { 0 }

  22. { "99999" }

    { "00000" }

    Returns: { 1 }

  23. { "14189" }

    { "41437" }

    Returns: { 0 }

  24. { "39993" }

    { "36668" }

    Returns: { 1 }

  25. { "12188" }

    { "21211" }

    Returns: { 0 }

  26. { "45998" }

    { "54662" }

    Returns: { 0 }

  27. { "99990" }

    { "66661" }

    Returns: { 0 }

  28. { "00000" }

    { "01111" }

    Returns: { 1 }

  29. { "90210" }

    { "44444" }

    Returns: { 0 }

  30. { "56456", "14736", "23741", "09284", "27481", "12974" }

    { "12375", "99642", "12763" }

    Returns: { 0, 1, 0, 0, 0, 1 }

  31. { "77711" }

    { "72255" }

    Returns: { 1 }

  32. { "12145" }

    { "21284" }

    Returns: { 0 }

  33. { "13137" }

    { "31315" }

    Returns: { 1 }

  34. { "69279" }

    { "96368" }

    Returns: { 0 }

  35. { "19166" }

    { "96899" }

    Returns: { 0 }

  36. { "12999" }

    { "21666" }

    Returns: { 1 }

  37. { "11111" }

    { "77777" }

    Returns: { 1 }

  38. { "44771" }

    { "06217" }

    Returns: { 0 }

  39. { "12146" }

    { "21284" }

    Returns: { 0 }

  40. { "13746" }

    { "15964" }

    Returns: { 1 }

  41. { "88888", "66666", "22222" }

    { "84444", "77771", "99999" }

    Returns: { 0, 1, 0 }

  42. { "19900" }

    { "16622" }

    Returns: { 1 }

  43. { "66666" }

    { "61199" }

    Returns: { 1 }

  44. { "90210" }

    { "90210" }

    Returns: { 1 }

  45. { "12348" }

    { "21435" }

    Returns: { 1 }

  46. { "44444" }

    { "33333" }

    Returns: { 0 }

  47. { "99999" }

    { "00000" }

    Returns: { 1 }

  48. { "14189" }

    { "41437" }

    Returns: { 0 }

  49. { "39993" }

    { "36668" }

    Returns: { 1 }

  50. { "12188" }

    { "21211" }

    Returns: { 0 }

  51. { "45998" }

    { "54662" }

    Returns: { 0 }

  52. { "99990" }

    { "66661" }

    Returns: { 0 }

  53. { "00000" }

    { "01111" }

    Returns: { 1 }

  54. { "90210" }

    { "44444" }

    Returns: { 0 }

  55. { "56456", "14736", "23741", "09284", "27481", "12974" }

    { "12375", "99642", "12763" }

    Returns: { 0, 1, 0, 0, 0, 1 }

  56. { "77711" }

    { "72255" }

    Returns: { 1 }

  57. { "12145" }

    { "21284" }

    Returns: { 0 }

  58. { "13137" }

    { "31315" }

    Returns: { 1 }

  59. { "69279" }

    { "96368" }

    Returns: { 0 }

  60. { "19166" }

    { "96899" }

    Returns: { 0 }

  61. { "12999" }

    { "21666" }

    Returns: { 1 }

  62. { "11111" }

    { "77777" }

    Returns: { 1 }

  63. { "44771" }

    { "06217" }

    Returns: { 0 }

  64. { "12146" }

    { "21284" }

    Returns: { 0 }

  65. { "13746" }

    { "15964" }

    Returns: { 1 }

  66. { "88888", "66666", "22222" }

    { "84444", "77771", "99999" }

    Returns: { 0, 1, 0 }

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: