Statistics

Problem Statement for "MarbleMachine"

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

  1. { "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).

  2. {"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.

  3. { "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.

  4. {"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. In total, there are 20+21+20+21=82 marbles.

  5. {"102"}

    {"1E1W","D","0"}

    20

    Returns: 5

    The type 0 device pulls up marbles and sends them East and West in alternating fashion. The marbles that go West to the type 1 device are dumped each turn. The marbles that go East to the type 2 device are stockpiled. After 20 turns, there's 5 marbles at the East end and 1 marble at the West end (that will be dropped next turn).

  6. { "40001", "03222"}

    { "EEE","SS","W","NNNND","11E" }

    2000

    Returns: 4

    For the most part, marbles entering the system from the type 4 device move in a continuous cycle. However, the type 3 device occasionally loses its marbles, which limits the number of marbles that accumulate.

  7. { "51111112", "11111122", "41111222", "44112222", "44403222", "44433322", "44333332", "43333333" }

    { "000000", "00000E", "00000S", "00000W", "00000N", "10000E" }

    390

    Returns: 3

    At 390, the third marble reaches the center.

  8. { "51111112", "11111122", "41111222", "44112222", "44403222", "44433322", "44333332", "43333333" }

    { "000000", "00000E", "00000S", "00000W", "00000N", "10000E" }

    38400000

    Returns: 6399938

    38,400,000/6=6,400,000-62 (all spaces but center and top-left)=6,399,938

  9. { "51111112", "11111122", "41111222", "44112222", "44403222", "44433322", "44333332", "43333333" }

    { "000000", "00000E", "00000S", "00000W", "00000N", "99999E" }

    38399999

    Returns: 287997165

    38,400,000*45/6=288000000-45*63 (all spaces but top-left)=287,997,165

  10. { "51111112", "11111122", "41111222", "44112222", "44403222", "44433322", "44333332", "43333333" }

    { "000000", "00000E", "00000S", "00000W", "00000N", "10000E" }

    389

    Returns: 2

    One time unit before third marble.

  11. { "30000001", "03333330", "06222240", "07219240", "06281240", "06222240", "05555540", "20000004"}

    {"0", "1ESENW", "S2WEE", "WE3NS", "N4SW", "DWE6SN", "N5SWW", "ESW7W", "N8S", "9NEW"}

    6000005

    Returns: 37399929

  12. { "30000001", "03333330", "06222240", "07219240", "06281240", "06222240", "05555540", "20000004"}

    {"1", "DW6WN", "N5SDW", "ESN7W", "3WSENW", "S2WEE", "WE3NS", "N4SS", "E8SW", "9NW"}

    100000000

    Returns: 403333321

  13. { "12000000", "71120120", "13020320", "00011320", "00000020", "06544440", "00000000", "00000000"}

    {"D","EEE","SSS","NNNNN","W","DWD","0","1N2S"}

    60

    Returns: 9

    A 2 just arrived, the previous 1 was lost.

  14. { "75633808", "87049849", "19458165", "36633886", "92725170", "61183034", "39432264", "59384396" }

    { "11SS", "564N", "76W", "7N9W0", "N2DS", "3SS", "628E", "9S1N", "31NN6", "NS" }

    987273

    Returns: 25685297

    (13-20 are just random big cases)

  15. { "43973731", "03832533", "05296793", "51641963", "15210359", "54887735", "47245854", "31526495" }

    { "S99", "SEE", "WW4S", "EE2N", "8S6", "S83", "WN14", "718D3", "0DW", "SNS" }

    77738377

    Returns: 285040712

  16. { "27768282", "91184511", "20756257", "74971670", "44916312", "14955244", "35156974", "71775223" }

    { "NWW0E", "S21", "93", "WN6", "526", "E", "N", "E1", "16NE", "DWE4" }

    100000000

    Returns: 799999998

  17. { "83879245", "42661168", "64258455", "44747523", "13638382", "31546031", "38685629", "36687783" }

    { "0N5WD", "EWN", "E8N", "S75", "3S", "N", "6S", "0S", "N0", "72" }

    6000

    Returns: 42997

  18. { "78415614", "54932535", "43164594", "64111183", "10785851", "63374429", "14657130", "89329244" }

    { "8W1N", "W9N8", "WE0", "EN", "18", "W76", "4W0W", "EW16", "W0S", "038" }

    606060

    Returns: 10151433

  19. { "39165948", "81658417", "77582739", "74161731", "65689217", "56833932", "22254372", "73093744" }

    { "SS", "0E", "W7D", "45", "5E6", "9N", "6", "DNN", "N4", "1ED" }

    2520

    Returns: 40721

  20. { "57398512", "59081678", "48293136", "29249548", "72278643", "82762987", "15178505", "69336456" }

    { "5W85", "3", "DWS6", "W5SW", "9N3", "NE", "D", "109EW", "S0E", "918" }

    2521

    Returns: 44696

  21. { "62798913", "73998929", "18795925", "46037121", "82885731", "32436485", "54673983", "95295083" }

    { "D4N5", "0EES", "N056", "96", "87WN", "64WEE", "WNS", "70E8", "S5", "DS" }

    4000

    Returns: 70914

  22. { "00", "01"}

    {"0","1"}

    6065

    Returns: 6065

  23. { "00", "00"}

    {"0","1","2","3","4","5","6","7","8","9"}

    99886772

    Returns: 0

  24. {"0","0","0","0","0","0","0","0"}

    {"1S"}

    18

    Returns: 7

  25. {"0","0","0","0","0","0","0","0"}

    {"1S"}

    19

    Returns: 8

  26. {"0","0","0","0","0","0","0","0"}

    {"1S"}

    99778991

    Returns: 8

  27. { "01", "01", "01", "21", "01", "01", "01"}

    {"0","NNNSSS","1E11E","D0WN","W0NDE4"}

    1001003

    Returns: 200202

  28. {"012345"}

    {"1","01","001","0001","00001","000001"}

    60

    Returns: 60

  29. {"012345"}

    {"1","02","003","0004","00005","000006"}

    99999959

    Returns: 99999959

  30. { "01", "32"}

    {"1E","S","W","00000W"}

    66666623

    Returns: 3

  31. { "00000001", "00000001", "00000001", "00000001", "00000001", "00000002" }

    { "99999E", "99999S", "999999" }

    6

    Returns: 144

    9*(6+5+5)=144

  32. { "00000001", "00000001", "00000001", "00000001", "00000001", "00000001", "00000001", "00000002" }

    { "99999E", "99999S", "999999" }

    99999996

    Returns: 48149980749

    99999996/6=16666666 16666666*(45*63+9*6)=48149998074 (with the remaining ones still "on the way")

  33. {"01111111", "22222222", "22222222", "22222222", "22222222", "22222222", "22222222", "22222222"}

    {"9","9W","9S"}

    100000000

    Returns: 4049999811

  34. {"13983779", "56620380", "91254988", "20656288", "43363525", "67824559", "93351733", "15817451" }

    {"5EE8", "7", "37S", "S4", "85N5S", "D", "5DD1", "7E9N8S", "5E0", "9" }

    100000000

    Returns: 2184999955

  35. {"01", "32" }

    {"1E", "SSDSS", "W", "00000W" }

    100000000

    Returns: 3

  36. {"055556", "189996", "289996", "389996", "487777" }

    {"1E", "2E1E", "3EE4", "9EEEE1", "E5E6E", "E", "S", "W", "N", "1D" }

    100000000

    Returns: 63750000

  37. {"01111112", "23333333", "11111112", "23333333", "11111112", "23333333", "11111112", "43333333" }

    {"0000E1", "E0EW0W", "N0NSS0", "0EW0WE", "0000E0" }

    100000000

    Returns: 16666666

  38. {"12311114", "12311114", "12311114", "12311114", "12311114", "12311114", "12311114", "12311110" }

    {"9", "99999E", "9999E", "999E", "99999S" }

    100000000

    Returns: 47309982228

  39. {"011112" }

    {"1E", "E", "0" }

    100000000

    Returns: 49999998

  40. {"01111112", "01111112", "01111112", "01111112", "01111112", "01111112", "01111112", "01111112" }

    {"1E", "E", "0" }

    100000000

    Returns: 49999997

  41. {"0001", "3001", "3001", "3222" }

    {"1EEE", "1SSS", "1WWW", "1NNN" }

    100000000

    Returns: 37500000

  42. {"10000002", "10000002", "10000002", "10000002", "10000002", "10000002", "10000002", "10000003" }

    {"E", "9E", "S", "9" }

    100000000

    Returns: 4499999640

  43. {"01010101", "10101010", "01010101", "01010101", "10101010", "01010201", "10101010", "01010101" }

    {"4NWD", "5353S", "9" }

    100000000

    Returns: 1299999980

  44. {"0101", "1010", "0101" }

    {"4", "5353" }

    31231231

    Returns: 124924925

  45. {"01234567", "80124567", "11124567", "11124567", "89014567", "88884567", "99012367", "90123407" }

    {"1E", "SSDSS", "W", "00W", "98SS65", "923D3", "9NNN1", "8S1", "7E374", "45456" }

    98765431

    Returns: 888888860

  46. {"01234567", "90123456", "89012345", "78901234", "67890123", "56789012", "45678901", "34567890" }

    {"9E9E9E", "9W9W9W", "9S9S9S", "9N9N9", "9E9E9E", "9W9W9W", "9S9S9S", "9N9N9", "9E9E9E", "9W9W9W" }

    100000000

    Returns: 945000000

  47. {"01234568", "76503210", "56549214", "26563210", "76043212", "46529910", "70343210", "16749610" }

    {"99WWN9", "77", "WWN99", "999999", "NWSE", "E", "000123", "887EE9", "9", "WWN9N" }

    100000000

    Returns: 1799999937

  48. {"00100010", "00010000", "10000100", "00100001", "00010000", "00001000", "01000100", "00010010" }

    {"95S9WD", "8E7N9" }

    100000000

    Returns: 141

  49. {"00000001", "00000001", "00000001", "00020001", "00000001", "00000001", "00000001", "00000002" }

    {"9E", "0000S", "0" }

    100000000

    Returns: 23399995284

  50. {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000" }

    {"9" }

    100000000

    Returns: 900000000

  51. {"01" }

    {"1E", "0E" }

    100000

    Returns: 1

  52. {"035872", "179234", "235872", "239583", "238957", "328953", "238957", "892370" }

    {"DNEWE5", "23NEE7", "SSWW39", "927NE", "23", "3253NE", "237", "3256NE", "235WN", "4" }

    99999999

    Returns: 2026666513

  53. {"01111111", "04444442", "04444442", "04444442", "04444442", "04444442", "04444442", "33333332" }

    {"9E99E9", "8S98S", "9W", "8N99", "5NESW8" }

    98765443

    Returns: 2423045223

  54. {"0" }

    {"D7" }

    100000000

    Returns: 7

  55. {"0101", "1010", "0101" }

    {"4", "5353" }

    100000000

    Returns: 400000000

  56. {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000" }

    {"999999" }

    100000000

    Returns: 900000000

  57. {"21212121", "01010101", "01010101", "01010101", "01010101", "01010101", "01010101", "42020203" }

    {"8N", "8S", "8E", "8", "9N" }

    100000000

    Returns: 26049984314

  58. {"011111", "000003", "004003", "000003", "222223" }

    {"SSSSS", "WW", "EEE", "NNNN", "12N39W" }

    100000000

    Returns: 83333340

  59. {"01234567", "98765432", "01234567", "98765432", "01234567", "98765432", "01234567", "98765432" }

    {"978", "47W", "9E8", "6DE", "9", "87N", "978", "9EE", "97S", "97E" }

    99999998

    Returns: 2233333212

  60. {"012345", "543210", "010203", "302020", "102020", "120203" }

    {"423315", "ENNS12", "ENS2", "999", "9999", "119SEW", "WN90", "00" }

    100000000

    Returns: 974999997

  61. {"00200", "00200", "11533", "00400", "00400" }

    {"9N9E9S", "9E", "9S", "9W", "9N", "9" }

    100000000

    Returns: 8099999748

  62. {"4000001", "3222222" }

    {"E", "S", "W", "N", "1E" }

    100000000

    Returns: 7142858

  63. {"0" }

    {"D1" }

    5040

    Returns: 1

  64. {"01" }

    {"1E", "E" }

    80640

    Returns: 1

  65. {"00000001", "00000001", "00000001", "00000001", "00000001", "00000001", "00000001", "22222223" }

    {"99999W", "99999S", "99999W", "9999" }

    99999999

    Returns: 6149998836

  66. {"46298429", "53329479", "49219310", "34912321", "42131221", "41234125", "32409401", "21349401" }

    {"E", "D0", "SED", "5321", "9WW78", "040123", "219312", "NSEWSE", "243213", "NEWSSE" }

    100000000

    Returns: 914999969

  67. {"010101", "010101", "212102", "324324", "010101" }

    {"1EE3W", "2E", "3W4", "4NE2", "2" }

    100000000

    Returns: 796666630

  68. {"0111" }

    {"1E", "E" }

    72000

    Returns: 1

  69. {"29298511", "70673258", "59922002", "63633048", "32740689", "41912685", "77960880", "91136945" }

    {"SWSDWS", "EDDDSD", "DDEWWS", "ESDEWS", "EWSWWW", "WESSWD", "EENEDS", "SWDWSE", "DWSNEN", "DWEWDS" }

    100000000

    Returns: 0

  70. {"0" }

    {"12345" }

    37

    Returns: 108

  71. {"40000001", "31222222", "30001000", "32222000" }

    {"E", "S", "W", "N", "1E" }

    100000000

    Returns: 3846154

  72. {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000001" }

    {"9D", "9D" }

    100000000

    Returns: 0

  73. {"67293572", "02959182", "59591914", "19293911", "90123456", "19201001", "11929317", "95919291" }

    {"987651", "S1ENW9", "451W2", "91WN99", "765432", "582858", "NEWSD9", "85818", "9", "9591EW" }

    100000000

    Returns: 1599999927

  74. {"32321", "32312", "13434" }

    {"ED987W", "3D40SN", "12D", "18DES", "E", "0", "1234", "WWWEEE", "EWS", "3477" }

    100000000

    Returns: 4

  75. {"40000001", "31222222", "30001005", "32222006", "40000031", "31222222", "30000001", "32222222" }

    {"E", "S", "W", "N", "1E", "10000E", "SSSSSN" }

    100000000

    Returns: 3846154

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: