TopCoder problem "BillOfMaterials" used in SRM 34 (Division I Level Two , Division II Level Two)

Problem Statement


Class name: BillOfMaterials
Method name: explode
Parameters: String, int, String[]
Returns: String[]

Bill of Materials (BOM) is an important aspect of Material Requirements
Planning (MRP).  The BOM describes the components that make up a product.
Consider your PC - it has one monitor, one keyboard, one mouse and one system.
The keyboard is then made up of (probably) 104 keys, one plastic cover, etc.
What was just described is the BOM for a PC.  If we wanted to make 100 PCs, the
BOM would tell us we need 100 monitors, 100 keyboards (and since we are
building the keyboard - we need 10400 keys), etc.  The process of calculating
the quantity of components is called the MRP Explosion.  The PC is called the
final product - all of its individual components are called work-in-progress
(WIP).  Sometimes a WIP can also be a final product - we might not only build
PCs but sell keyboards as well.  The keyboard is considered to be a WIP if we
are building a PC or considered a final product if we are building it to sell.
For this reason, you can 'explode' the requirement for any component anywhere
within the BOM.

Implement a class BillOfMaterials, which contains a method explode.  The method
explodes the requirements for a specific product and returns a list of the
final (lowest-level) components and their quantities.

The method signature is:
String[] explode(String calcProduct, int quantity, String[] BOM);
Be sure your method is public.

calcProduct - name of the product (within the BOM) for which you will calculate
quantity - the number of (calcProduct) products that will be built.
BOM - the Bill of Material elements will be formatted as follows:
	"product component:quantity,component:quantity..."
	product is a String containing the name of the product
	Followed by a single space
	Followed by a String representing a component of the product
	Followed by a single colon
Followed by a int representing the quantity of the component required to make
one unit of the product

If the product has more than one component, a single comma will separate each
Spaces are NOT allowed anywhere except for the single space following the
product name.

The elements in the return String[] will be formatted as follows:
   "component:total quantity" (colon seperates the two sub-elements)
Your return should be ordered alphabetically by component.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
*calcProduct will be a String with a length of 1 to 50 characters (inclusive)
*calcProduct will consist only of letters (a-z, A-Z).
*Every product within the BOM will consist only of letters (a-z, A-Z).
*Every component within the BOM will consist only of letters (a-z, A-Z).
*Every quantity within the BOM will be an int whose value is 1 to 1000
*The BOM will have from 1 to 50 elements (inclusive)
*Each element of BOM will have length less than or equal to 50 characters.
*Each product in the BOM will have at least one component
*The calcProduct will be a product within the BOM
*No duplicate products will be allowed in the BOM (not allowed: {"A B:100","A
C:100"}, product "A" would be duplicated)
*A product may be a component of any other product (allowed: "A B:100", "B
*There will be no circular references.  If "A" requires "B", then "B" cannot
require "A".
*A component can appear multiple times within the BOM.  If "A" requires some
quantity of "B" and "C", it is valid for "B" to require some quantity of "D"
and "C" to require another quantity of "D".
*If a component appears multiple times within the BOM - you should return the
sum of the requirements for the component.  In other words, the returned
String[] should contain only one entry for each final component with its
summed, total requirements.
*A component will not appear more than one time within a specific product.
Example: you cannot specify "A B:10,B:100"
*The inputs will be checked to prevent int overflow (>2147483647) when
calculating the solution

An input of ("A", 10, {"A B:100,C:10"}) would be calculated as follows:

We are calculating requirements for "A" (calcProduct). "B" and "C" are
components of the product. "B" and "C" are the final (lowest-level) componenets
of "A" because "B" and "C" do not have components of their own. Therefore, we
must calculate the amount of "B" and "C" components. Since we need a quantity
of ten "A"'s and for one "A" we need one hundred "B"'s, we will need a total of
10 * 100 = 1000, "B"'s. Similarly, we need ten "C"'s for every "A", so we will
need a total of 10 * 10 = 100, "C"'s.
The method returns {"B:1000","C:100"}

An input of ("A", 10, {"A B:100,C:10", "B D:5"}) returns {"C:100","D:5000"}
An input of ("B", 10, {"A B:100","B C:10"}) returns {"C:100"}
An input of ("A", 10, {"A B:100,C:10","B D:10,E:5", "C D:20,F:10"}) returns
An input of ("WoW", 10, {"A B:100,WoW:10","B D:10,E:5", "WoW D:20,F:10"})
returns {"D:200","F:100"}
An input of ("T", 10, {"A B:100,C:10","T B:10,C:5", "C D:20,F:10"}) returns



Parameters:String, int, String[]
Method signature:String[] explode(String param0, int param1, String[] param2)
(be sure your method is public)

Problem url:

Problem stats url:




Problem categories: