TopCoder problem "MarbleMachine" used in SRM 376 (Division I Level Two)



Problem Statement

    

You have built a moving sculpture containing several devices that move marbles around on a grid. Each device occupies a single square on the grid and repeatedly executes a sequence of actions. The possible actions are:

  • Digits 0-9: Bring up 0-9 marbles from the central store (which never runs out of marbles) and place them on the square.
  • N,E,S,W: Move all the marbles on the square one square North, East, South, or West. If this causes the marbles to leave the grid, they will be removed and placed back in the central store.
  • D: Remove all the marbles from the square and drop them back into the central store.

Each device has its own sequence of actions, and different devices may have sequences of different lengths. At time 0, each device executes its first action, at time 1, each device executes its second action, etc. When a device reaches the end of its sequence, it starts again at the beginning of the sequence.

 

During each unit of time, all actions happen simultaneously and only operate on marbles on the squares at the beginning of that time unit. For example, suppose there is one marble on square (0, 0) and one on square (1, 0). Now suppose the first square's action is 'E' and the second square's action is 'D'. At the end of this time unit, the first square will have 0 marbles and the second will have 1. The second square drops the marble that it had at the beginning of the time unit, but it does not drop the marble that arrives from the first square during that time unit.

 

You are given a String[] actions, the i-th element of which is the action sequence for a device of type i (where i is a 0-based index). You are also given a String[] layout, where the j-th character of the i-th element is a digit representing the type of device located in row i, column j of the grid. Rows are numbered in increasing order from North to South, and columns are numbered in increasing order from West to East. Return the maximum number of marbles that exist on a single square after t time units have passed.

 

Definition

    
Class:MarbleMachine
Method:maxMarbles
Parameters:String[], String[], int
Returns:long
Method signature:long maxMarbles(String[] layout, String[] actions, int t)
(be sure your method is public)
    
 

Constraints

-layout will contain between 1 and 8 elements, inclusive.
-Each element of layout will contain between 1 and 8 characters, inclusive.
-Each element of layout will contain the same number of characters.
-Each element of layout will contain only digits between 0 and n-1, inclusive, where n is the number of elements in actions.
-actions will contain between 1 and 10 elements, inclusive.
-Each element of actions will contain between 1 and 6 characters, inclusive.
-Each element of actions will contain only digits ('0'-'9') and the characters 'N', 'E', 'S', 'W' and 'D'.
-t will be between 1 and 100,000,000, inclusive.
 

Examples

0)
    
{
"0101",
"1010",
"0101"}
{"4","5353"}
5
Returns: 21
Devices of type 0 are simple; they pull up 4 marbles on each turn. Over 5 cycles, this is 20 marbles. Devices of type 1 will complete just over 1 cycle in this time - pulling up a total of 5+3+5+3+5=21 marbles. So the maximum marbles at any position will be 21 (which occurs at each location with a device of type 1).
1)
    
{"011112"}

{"1E","E","0"}
1000
Returns: 498
This structure functions as a kind of conveyor belt. At the left, the device of type 0 alternately grabs one marble and pushes it East. The devices of type 1 move the marble along to the East until they reach the device of type 2, which accumulates the marbles. After 1000 cycles, 500 marbles have been brought up. 2 are still on the "conveyor belt", and 498 are on the square at the East end.
2)
    
{
"01",
"32"}
{"1E","SSDSS","W","00000W"}
23
Returns: 3
This machine delivers marbles to the Southwest corner, from which they are periodically dumped off the West edge. The Northeast corner also occasionally loses its marbles.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8045

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10796&pm=8045

Writer:

jmzero

Testers:

PabloGilberto , Olexiy , misof , ivan_metelsky

Problem categories:

Math, Simulation