Statistics

Problem Statement for "InverseSoundex"

Problem Statement

Soundex is a phonetic algorithm, meaning that it indexes words by their pronunciation (in English). The algorithm transforms an input string of letters into a code of the form Cddd, where C is an uppercase letter and each d character represents a digit between 0 and 6, inclusive.

The variant of Soundex we will be using works as follows:

  1. Remember the first letter of the input string.
  2. Remove all H and W characters.
  3. Replace each letter in the word with its phonetic code, given in the following table: 
       A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
   0 1 2 3 0 1 2 - 0 2 2 4 5 5 0 1 2 6 2 3 0 1 - 2 0 2
  4. Compress runs consisting of the same digit, leaving only one occurrence.
  5. Remove all occurrences of the digit zero.
  6. Truncate the result or pad it with zeros from the right so that the resulting code is exactly four characters long (for example, the string 123456 would be truncated to 1234, while the string 43 would be padded with zeros to form 4300).
  7. Replace the first digit by the letter remembered in the first step.

For example, let's run through the algorithm with the word SOMEWHERE:

  1. We remember the letter S as we will need to restore it later.
  2. Removing the H and W characters yields SOMEERE.
  3. Replacing letters with their phonetic codes results in 2050060.
  4. Compressing groups of consecutive codes gives 205060.
  5. Removing all zeros, we get 256.
  6. Padding the result with a single zero gives 2560.
  7. Restoring the first letter gives the final S560.

Find the number of distinct words of length length, consisting only of letters of the English alphabet, for which the above algorithm yields the given Soundex code soundex.

Definition

Class:
InverseSoundex
Method:
howMany
Parameters:
String, int
Returns:
long
Method signature:
long howMany(String soundex, int length)
(be sure your method is public)

Notes

  • The result will fit in a 64-bit signed integer.

Constraints

  • soundex will contain exactly 4 characters, and will be of the form Cddd, where C is an uppercase character and each d character represents a digit between 0 and 6, inclusive.
  • length will be between 1 and 15, inclusive.

Examples

  1. "M146"

    4

    Returns: 4

    The four strings are MBLR, MFLR, MPLR and MVLR.

  2. "B253"

    5

    Returns: 2048

    The digits 2, 5 and 3 can represent 8 * 2 * 2 = 32 combinations of letters. A vowel (including Y), H or W may be included after any character for a total of 8 * 4 * 32 = 1024 strings. Some of the codes may be repeated, such as in the string BCGMD, where C and G have the same code. There are 512 such strings. Also, if the first four letters give the B253 Soundex, then any letter appended to those four letters will not change the Soundex. We can append 16 letters to get strings we have not yet counted, getting 32 * 16 = 512 more strings.

  3. "B255"

    5

    Returns: 192

    There must now be a vowel between the two 5 digits, which significantly brings down the answer.

  4. "E000"

    2

    Returns: 26

    A string consisting of the letter E followed by any letter has a Soundex of E000.

  5. "B212"

    15

    Returns: 6113225198220607488

    Watch out for overflow.

  6. "K405"

    7

    Returns: 0

  7. "Y251"

    6

    Returns: 48256

  8. "Z600"

    5

    Returns: 6145

  9. "R464"

    5

    Returns: 53

  10. "R466"

    6

    Returns: 330

  11. "M543"

    4

    Returns: 0

  12. "F662"

    14

    Returns: 1111080595516512

  13. "N424"

    7

    Returns: 595816

  14. "T133"

    9

    Returns: 190983168

  15. "G111"

    5

    Returns: 0

  16. "M553"

    7

    Returns: 17280

  17. "Q212"

    8

    Returns: 167067648

  18. "P144"

    4

    Returns: 0

  19. "G233"

    11

    Returns: 107782078464

  20. "T023"

    8

    Returns: 0

  21. "F310"

    10

    Returns: 2424737792

  22. "R400"

    13

    Returns: 141837136032

  23. "B000"

    14

    Returns: 1623146053632

  24. "A441"

    3

    Returns: 0

  25. "I552"

    6

    Returns: 3072

  26. "O622"

    12

    Returns: 18568535979648

  27. "E333"

    8

    Returns: 332352

  28. "F242"

    2

    Returns: 0

  29. "T000"

    2

    Returns: 10

  30. "U400"

    3

    Returns: 17

  31. "M100"

    3

    Returns: 88

  32. "K000"

    1

    Returns: 1

  33. "A100"

    4

    Returns: 1960

  34. "H440"

    9

    Returns: 33239490

  35. "W335"

    15

    Returns: 31508888512281696

  36. "H111"

    4

    Returns: 0

  37. "H111"

    8

    Returns: 2483712

  38. "W411"

    5

    Returns: 0

  39. "H355"

    13

    Returns: 46005193650528

  40. "W666"

    12

    Returns: 49897597284

  41. "H041"

    7

    Returns: 0

  42. "H540"

    8

    Returns: 10228080

  43. "W200"

    15

    Returns: 19203445775768240

  44. "A000"

    5

    Returns: 77746

  45. "A000"

    15

    Returns: 1486492147549378

  46. "H000"

    10

    Returns: 12868878518

  47. "J000"

    14

    Returns: 38350732558336

  48. "F100"

    13

    Returns: 1819056463872

  49. "G100"

    10

    Returns: 8913258496

  50. "K123"

    4

    Returns: 64

  51. "K223"

    4

    Returns: 0

  52. "B232"

    15

    Returns: 2779041647285501952

  53. "B346"

    5

    Returns: 114

  54. "B344"

    5

    Returns: 12

  55. "L300"

    5

    Returns: 5774

  56. "H000"

    1

    Returns: 1

  57. "Z600"

    3

    Returns: 25

  58. "L646"

    6

    Returns: 1846

  59. "M646"

    6

    Returns: 1903

  60. "E303"

    7

    Returns: 0

  61. "N105"

    10

    Returns: 0

  62. "A506"

    13

    Returns: 0

  63. "X106"

    5

    Returns: 0

  64. "U212"

    15

    Returns: 4018509113376029184

  65. "H212"

    15

    Returns: 4018509113376029184

  66. "F252"

    15

    Returns: 2779041647285501952

  67. "O121"

    15

    Returns: 2770821810712829184

  68. "Q122"

    15

    Returns: 1905842764597690368

  69. "T221"

    15

    Returns: 1733409117496147968

  70. "M125"

    15

    Returns: 1389520823642750976

  71. "Y500"

    15

    Returns: 1531895718989492

  72. "S660"

    13

    Returns: 411872776200

  73. "J220"

    14

    Returns: 1634095465758720

  74. "V111"

    13

    Returns: 27623977648128

  75. "G222"

    11

    Returns: 493291634688

  76. "L444"

    15

    Returns: 196085402048376

  77. "T333"

    12

    Returns: 99059410944

  78. "R666"

    15

    Returns: 196085402048376

  79. "N555"

    11

    Returns: 3658687488

  80. "E034"

    4

    Returns: 0

  81. "Y000"

    1

    Returns: 1

  82. "F123"

    3

    Returns: 0

  83. "F345"

    3

    Returns: 0

  84. "A123"

    3

    Returns: 0

  85. "A456"

    4

    Returns: 0

  86. "K500"

    2

    Returns: 2

  87. "K200"

    2

    Returns: 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: