MobileBalancing | Topcoder Archive

Problem Statement

A children's mobile is a simple structure based on elementary physics. It consists of a number of rods, each with a certain number of evenly-spaced anchor points. One anchor point per rod is the pivot; a string is tied to that point, and the rod is expected to hang from that string. The other end of the string is either connected to an anchor point on another rod, or (for exactly one rod, which we'll call rod 0) to the ceiling. Objects with various weights may also hang from anchor points. Each anchor point may have at most one thing connected to it (either end of a string, or an object). The entire structure must be in static equilibrium: in other words, for each rod, the sum of the products (weight * distance from pivot) for all hanging objects/rods must be equal on both sides of the pivot. (For simplicity we assume that the weight of the rod itself is 0.)

[I suspect an image of a mobile here will be useful.]

You are given the specification of a children's mobile. The specification consists of a String[] mobile. Each String describes one rod's anchor points, in order. Unused anchor points are represented by "-". The pivot anchor point is represented by "P". Anchor points with another rod hanging from them are represented by "Ri", where i is the index in mobile of the hanging rod. Anchor points with an object hanging from them are represented by "Wn", where n is the weight of the object.

Unfortunately, the specification is flawed, as the mobile may not be balanced. You are only allowed to modify it by attaching objects with weight 1 to unused anchor points. Return the minimum number of weights needed to balance the mobile, or -1 if it's impossible.

Definition

Class:: MobileBalancing
Method:: minWeights
Parameters:: String[]
Returns:: int
Method signature:: int minWeights(String[] mobile)
(be sure your method is public)

Constraints

mobile will contain between 1 and 15 elements, inclusive.
Each element of mobile will contain between 1 and 50 characters, inclusive.
Each element of mobile will be a sequence of tokens separated by a single space.
Each token in mobile will be in the format "-", "P", "Ri" with i the non-zero index of an element of mobile, or "Wn" with n between 1 and 9, inclusive.
Each element of mobile will have exactly one "P" token.
Each element of mobile will have at least one "Ri" or "Wn" token.
There will be exactly one "Ri" token for each non-zero index i of mobile.
There will be no cycles formed from connections between rods.

Examples

```
{"- - - - P R1","W3 P - - -"}
```
```
Returns: 2
```
Rods 0 and 1 can both be balanced by adding a weight to their far anchor point.
```
{"R1 - P - - R2", "- - - - P W9", "W6 P - - - -"}
```
```
Returns: 5
```
Rod 1 can be balanced with three more weights, and Rod 2 with two. The two rods, hanging from Rod 0, are in equilibrium.

{"R1 - P - - R2", "- - - - P W8", "W6 P - - - -"}

Returns: -1

Now the weight ratios don't work out quite so well.

```
{"W1 W1 P W3"}
```
```
Returns: 0
```

{"- - - W4 - R1 - W9 - P - - W3 - R4 - - - -",
"- - W6 - - - R2 W1 - P W8 - - - W2 - R3 - - - W1 -",
"- - - W3 - - - - P - - - - - - - -",
"- - - - - - W8 P W1 W1 - W1 - -",
"- - - W1 - R5 W1 - P W1 - W1 W1 - - W1 R6 -",
"- - - W3 W3 - - - - W3 W1 P W1 - - - W3 W4 - - - -",
"- - - - - - - - W2 W1 P - - - -"}

Returns: 38

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.