TopCoder problem "OrderParser" used in TC China 08 - 1A (Division I Level Two)

Problem Statement


Your company takes orders on-line. But instead of making users enter data into a rigid on-line form, they allow users to write letters containing information about their orders. You are to write a program that figures out what a user's order really is.

You will be given the customer's message, and an array of items that they can order. By using the following rules, you can figure out what they want to order.

  • Each element of the message is an individual sentence.
  • Each sentence is composed of words, which are continuous sequences of letters, and numbers, which are contiguous sequences of digits, with no extra leading zeros. Words or numbers are separated by single spaces and there are no leading or trailing spaces. For example, "1 apple or 2 pears" and "table and chair" are valid inputs, and "3tables" and "  007   agent    " is not.
  • Each sentence that includes a number followed (one or more words later) by one of the items, should be considered an order request. Only consider the closest number that appears before an item to be an order request for that quantity of that item. Similarly, only consider the closest item that appears after a number to be an order request for that quantity of that item. See the Notes section and Examples 2 and 4 for additional clarification.
  • A sentence can contain more than one order request.

You are to return a int[] containing the items ordered by the customer. Each element of the returned int[] should indicate how many of the corresponding entry in the items array the customer ordered in the message.

As an example, if you were given the items {"hats", "shoes"} and the message was {"I would like to order 2 pairs of shoes and 3 hats"}, you would return {3, 2}.



Parameters:String[], String[]
Method signature:int[] orderAmount(String[] items, String[] message)
(be sure your method is public)


-If a number "n" occurs in an element of messages, and "i" is the closest item following "n" in that same element, then we interpret this as an order for "i" with quantity "n".
-Note that a single element of messages may have many orders. Also note that a number with no following item before the next number is ignored. Conversely, an item name not preceded by a number should be ignored.
-Only find the exact words given in the item list.


-items will contain between 1 and 50 elements, inclusive.
-Each element of items will contain between 1 and 50 character, inclusive, and will contain lowercase letters ('a' - 'z') only.
-The elements of items will be unique.
-message will contain between 1 and 50 elements, inclusive.
-Each element of message will be a sentence as described in the problem statement.
-Each element of message will contain between 1 and 50 characters, inclusive.
-Each element of message will contain only letters ('a'-'z' and 'A'-'Z'), digits ('0'-'9') or spaces.
-Each element of message will contain at least one letter.
-Each "number" in an element of message will be an integer between 0 and 1000, inclusive, with no extra leading zeros.


{"apples", "bananas", "oranges"}
{"Please send me 3 apples and 2 oranges", 
 "Do not mix the apples and oranges",
 "I need 12 more apples",
 "And 7 bananas"}
Returns: {15, 7, 2 }
In the first sentence, the closest preceding number to "oranges" is 2. The reference to 'apples' and 'oranges' in the second sentence is ignored, since neither is preceded by a number. They want a total of 15 apples.
{"hats", "gloves", "scarves"}
{"I ordered 2 hats but I want to return them",
 "Can I please order 3 pairs of gloves", 
 "Also I ordered 1 scarf but I will keep that"}
Returns: {2, 3, 0 }
Clearly 'scarf' does not match 'scarves'.
{"motherboards", "cpus", "keyboards", "mobos", "kbs", "mcus", "mouses"}
{"Dude gimme 3 dozen mobos and 2 CPUs", 
 "The 3 mice I got were broken",
 "so send me 2 or 3 mouses instead"}
Returns: {0, 0, 0, 3, 0, 0, 3 }
Matching is case-sensitive. In the third sentence, the 2 is ignored, because the 3 is the closest number preceding the item name "mouses".
{"trains", "planes", "automobiles"}
{"You can get there by bus or subway",
 "But not by train",
 "You have to take the 3 train",
 "Take 2 trains and an automobile"}
Returns: {2, 0, 0 }
Exact matches only.
{"a", "b", "as", "bs", "es"}
{"a a a a 2 a as as a 3 a A a 4 a b A", 
 "A tisket a tasket", 
 "Send me 3 as and four es"}
Returns: {9, 0, 3, 0, 0 }
In the last sentence, the 3 is used by the item "as" so there is no number for "es".
{"hats", "shoes"}
{"I would like to order 2 pairs of shoes and 3 hats"}
Returns: {3, 2 }
This is the example from the problem statement.
{"I want to buy 2",
Returns: {0 }
"2" and "apples" are in different sentences, so there are no order requests here.

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479 , Olexiy , ivan_metelsky

Problem categories:

String Parsing