Problem Statement
On your previous quest you acquired a priceless "infinite sack". This wondrous piece of luggage will hold an endless number of items but there is a catch. The last item you put in is the first one that comes out. Accounting for this restriction, you plan your next journey.
You begin at location 0, your home. Element k of dests is a space-separated list of locations that can be reached from location k. For each listed location j, element k of trades contains a 2-letter code NG. N is a character describing which item is needed to make the trip from location k to location j. G is also a character, and describes the item you will acquire by taking the trip. At least one of N or G will be '_', meaning you do not need an item, or do not acquire an item for the trip, respectively. For example, suppose element 3 of dests and trades are as given below.
You can only take a trip that requires the next item you can pull out of your sack. Trips that require no item can always be taken. For example, to take the "a_" trip mentioned above, the next item that you pull out of your sack would have to be 'a'. This item is removed. You will return a int[] containing the locations that can be reached via 0 or more trips from location 0. It should be sorted in strictly increasing order. Since we allow 0 trips, the first element will always be 0. Your sack is initially empty, so no item can be pulled out.
You begin at location 0, your home. Element k of dests is a space-separated list of locations that can be reached from location k. For each listed location j, element k of trades contains a 2-letter code NG. N is a character describing which item is needed to make the trip from location k to location j. G is also a character, and describes the item you will acquire by taking the trip. At least one of N or G will be '_', meaning you do not need an item, or do not acquire an item for the trip, respectively. For example, suppose element 3 of dests and trades are as given below.
dests[3] = "0 3 0 4" trades[3] = "a_ __ _B D_"One possible way to get from location 3 to location 0 requires item 'a' and earns you nothing. Another requires no item but you find item 'B'. The trip that returns to location 3 requires no item but also earns no item. Lastly, the trip to location 4 requires 'D', but produces nothing.
You can only take a trip that requires the next item you can pull out of your sack. Trips that require no item can always be taken. For example, to take the "a_" trip mentioned above, the next item that you pull out of your sack would have to be 'a'. This item is removed. You will return a int[] containing the locations that can be reached via 0 or more trips from location 0. It should be sorted in strictly increasing order. Since we allow 0 trips, the first element will always be 0. Your sack is initially empty, so no item can be pulled out.
Definition
- Class:
- SackJourney
- Method:
- canReach
- Parameters:
- String[], String[]
- Returns:
- int[]
- Method signature:
- int[] canReach(String[] dests, String[] trades)
- (be sure your method is public)
Notes
- The only transactions that can be made with your sack are the ones that correspond to trips.
Constraints
- dests will contain between 2 and 20 elements inclusive.
- trades will contain the same number of elements as dests.
- Each element of dests will contain between 0 and 50 characters inclusive.
- Each element of trades will contain between 0 and 50 characters inclusive.
- Each element of dests will be a single-space separated list of integers with no extra leading zeros.
- Each integer in dests will be between 0 and N-1, where N is the number of elements in dests.
- Each element of trades will be a single-space separated list of 2 character sequences. Each character will be a letter ('A'-'Z','a'-'z') or an underscore ('_'). At least one of the characters in each sequence will be an underscore.
- Each element of trades will contain the same number of 2 character sequences as the corresponding element of dests contains integers.
Examples
{"1","2",""}{"_A","A_",""}Returns: {0, 1, 2 }We can get to location 1 with 'A' in our sack. Removing this 'A', we can travel to location 2.{"1","2",""}{"_A","b_",""}Returns: {0, 1 }Unlike the first example, we cannot get to location 2 since we need a 'b'.{"0 0 1","2","3","4","5",""}{"_A _B __","B_","A_","__","C_",""}Returns: {0, 1, 2, 3, 4 }
Back to all problems