Statistics

Problem Statement for "Pipes"

Problem Statement

A system of pipes is set up going vertically into the ground. Water at a certain pressure is sent down through a single starting pipe at the top, and proceeds down through branching pipes as it goes deeper. Each branch gets a fraction of the pressure from all of the pipes above it, using the following algorithm:

Given a parent pipe, calculate the horizontal distance to every branch below it. The fraction of the water pressure that a branch receives from the parent pipe is inversely proportional to the distance between the branch and the parent. So for example, if a parent pipe has 3 branches: the first one 1 unit away, the second one 3 units away, and the third one 4 units away, the first branch would have 3 times as much pressure as the second, and 4 times as much pressure as the third. Mathematically, this works out so that the first branch would have 12/19 of the pressure, the second branch would have 4/19 of the pressure, and the third branch would have 3/19 of the pressure. Thus the first branch has 3 times the pressure as the second branch (12/19 versus 4/19), and 4 times the pressure as the third branch (12/19 versus 3/19).

The total pressure in each branch will be the sum of the pressures from all of the above pipes, converted into a percentage and rounded down to the nearest percent less than or equal to the actual percent. This can be done by multiplying the fractional pressures by 100 and rounding down. Assuming that the starting pipe has a pressure of 1 (100%), return the pressure of the indicated pipe at the bottom of the system as a rounded down percentage. Also, notice that all the percentages are rounded down after each intermediate step, not just the last one.

If there is a branch directly under the parent pipe, it receives all of the water pressure from that parent, and none of the other branches receive any.

The first argument will be a cross-section of the system of pipes in the form of a String[]. Each element will contain only spaces and the pipe ('|') character, and each element will contain at least one pipe character. For example, {" | "," ||","| |"} would represent the system:

" | "
" ||"
"| |"

The first element represents the top row of the system, the second element represents the second row, and so forth. The top row in this example is a single pipe, which branches into 2 pipes, 1 a distance of 1 away, and 1 directly below it. These in turn both branch into 2 more pipes (they branch into the same pipes, not 2 pipes each). The second argument will be the 0-based index of the bottom level pipe (0 being the left-most, n-1 being the rightmost, where n is the number of pipes on the bottom level) in question.

Return the percentage of the original pressure in the indexed pipe. For example, if the pipe receives no pressure (as is possible when there is a branch directly below a parent pipe), the method should return 0, or if the pipe has all of the original pressure, the method should return 100.

Definition

Class:
Pipes
Method:
pressure
Parameters:
String[], int
Returns:
int
Method signature:
int pressure(String[] pipes, int index)
(be sure your method is public)

Notes

  • Round down the percentages at each intermediate level of pipes, not just the last level.

Constraints

  • pipes will contain between 2 and 50 elements, inclusive.
  • each element of pipes will be of length 3 to 50 characters, inclusive.
  • each element of pipes will be the same length.
  • each element of pipes will contain only spaces or the pipe character ('|'), and at least 1 pipe character.
  • index will be an int between 0 and n-1, inclusive, where n is the number of pipe characters in the last element of pipes.
  • the first element of pipes will contain one and only one pipe character ('|').

Examples

  1. {" | "," | | | "}

    1

    Returns: 63

    The distances of the branches are 3, 1, and 4 respectively. This is the situation from above, so the method returns 12/19 rounded down to the nearest percent, which is 63.

  2. {" | ","|||"}

    0

    Returns: 0

    All of the pressure goes into the center branch. {" | ","|||"} 1 Returns: 100 All of the pressure goes into the center branch. {" | "," | | | "} 1 Returns: 63 The distances of the branches are 3, 1, and 4 respectively. This is the situation from above, so the method returns 12/19 rounded down to the nearest percent, which is 63. {" | ","| | |"} 0 Returns: 0 {" | " ,"|| | |" ," | || " ," | | |"} 1 Returns: 22 The pressures are as follows: first row: 100% second row: 24%, 49%, 16%, 9% third row: 9/65, 18/325, 3/65 (from first pipe) + 49/145, 49/580, 49/725 (from second pipe) + 0, 4/25, 0 (from third pipe) + 9/850, 9/340, 9/170 (from fourth pipe) --------- ------- ------ 48% 32% 16% fourth row: 12/25, 0, 0 (from first pipe) + 16/275, 48/275, 24/275 (from second pipe) + 4/175, 8/175, 16/175 (from third pipe) --------- ------- ------ 56% 22% 17% Therefore, the method returns 22. {" | " ," | | | | || | | | | | | | | | | " ,"| | | | | | | | | | | | | | | | " ," | | | | | | | | | | | | | | | |" ,"| | | | | | | | | | | | | | | | " ," | | | | | | | | | | | | | | | |" ,"| | | | | | | | | | | | | | | | " ," | | | | | | | | | | | | | | | |"} 6 Returns: 4 {" | " ,"| ||||| | " ," | | | | | || " ,"|||||| || " ,"| | |||| | | |" ,"| || || | || " ," ||| | ||| || | " ,"|| || || || ||" ,"| | ||| |||" ,"| | | ||||| " ," || | ||||| " ,"| | | ||||| | ||" ,"|||| ||| | | ||||" ,"|| | | |||| || "} 9 Returns: 8

  3. {" | ","| | |"}

    1

    Returns: 100

    All of the pressure goes into the center branch.

  4. {" | ","|| | |"," | || "," | | |"}

    1

    Returns: 22

    The pressures are as follows: first row: 100% second row: 24%, 49%, 16%, 9% third row: 9/65, 18/325, 3/65 (from first pipe) + 49/145, 49/580, 49/725 (from second pipe) + 0, 4/25, 0 (from third pipe) + 9/850, 9/340, 9/170 (from fourth pipe) --------- ------- ------ 48% 32% 16% fourth row: 12/25, 0, 0 (from first pipe) + 16/275, 48/275, 24/275 (from second pipe) + 4/175, 8/175, 16/175 (from third pipe) --------- ------- ------ 56% 22% 17% Therefore, the method returns 22.

  5. {" | "," | | | | || | | | | | | | | | | ","| | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | |"}

    6

    Returns: 4

  6. {" | ","| ||||| | "," | | | | | || ","|||||| || ","| | |||| | | |","| || || | || "," ||| | ||| || | ","|| || || || ||","| | ||| |||","| | | ||||| "," || | ||||| ","| | | ||||| | ||","|||| ||| | | ||||","|| | | |||| || "}

    9

    Returns: 8

  7. {"| "," | "," | "," | "," |"}

    0

    Returns: 100

  8. {"| "," | "," | "," | "," | |"}

    0

    Returns: 50

  9. {"| "," | "," | "," | "," ||"}

    1

    Returns: 0

  10. {"| "," |||||||||||||||||||||||||||||||||||||||||||||||||"}

    5

    Returns: 3

  11. {"| "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |"}

    4

    Returns: 0

  12. {"| "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "}

    0

    Returns: 4

  13. {" | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "," | | | | | | | | | | | | | | | | | | | | | | | | |","| | | | | | | | | | | | | | | | | | | | | | | | | "}

    5

    Returns: 2

  14. {" | "," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | "}

    0

    Returns: 49

  15. {" | "," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"}

    1

    Returns: 42

  16. {" | "," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"," | | ","| | |"}

    2

    Returns: 28

  17. { "| ", " |||||||||||||||||||", "| |" }

    0

    Returns: 68

  18. { " | ", "| ||||| | ", " | | | | | || ", "|||||| || ", "| | |||| | | |", "| || || | || ", " ||| | ||| || | ", "|| || || || ||", "| | ||| |||", "| | | ||||| ", " || | ||||| ", "| | | ||||| | ||", "|||| ||| | | ||||", "|| | | |||| || " }

    9

    Returns: 8

  19. { " | ", " | | | | || | | | | | | | | | | ", "| | | | | | | | | | | | | | | | ", " | | | | | | | | | | | | | | | |", "| | | | | | | | | | | | | | | | ", " | | | | | | | | | | | | | | | |", "| | | | | | | | | | | | | | | | ", " | | | | | | | | | | | | | | | |" }

    6

    Returns: 4

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: