Many different types of train set exist, ranging from wooden tracks like Brio, to fully digital control perfect tiny metal replicas of real trains, but they all require a track to be designed, ideally using as many of your pieces as possible.
So, your task is to determine whether, given input of the available pieces, it is possible to build a complete closed circuit using all of the elements, and if not, how many pieces will be left from the maximum possible circuit.
Since this is a simplified train set, there are only 3 elements: big curve, little curve, and straight. These are all based on a square grid:
- "Big Curve" is a 90 degree corner, covering 2 units in each dimension
- "Little Curve" is a 90 degree corner, covering one unit in each direction
- "Straight" is a straight element, 1 unit long
This means that the minimum circuit possible is formed of 4 little curves - it's a circle, of radius 1 unit. This can be extended by adding pairs of straight elements to form various ovals. There are other circuits possible by adding more curves, or by mixing the types of curve.
This train set doesn't include any junctions, or methods for tracks to cross, so it's not valid for two elements to connect to the same end of an other element (no Y formations) or to cross over one another (no X formations). Additionally, it's a train set, so any formation which doesn't allow a train to pass isn't valid: examples include straights meeting at 90 degree angles (there must always be a curve between perpendicular straights) and curves meeting at 90 degree angles (curves must flow).
You also want to use as many pieces as possible, ignoring what type they are, so you'll always opt for a circuit which has more bits in. Finally, you only have one train, so any solution which results in multiple circuits is unacceptable.
Input
Either an array of three integers, all greater than or equal to 0, corresponding to the number of big curves, little curves, and straights available, or parameters passed to your program, in the same order.
Output
A number corresponding to the number of pieces left over when the maximum possible circuit for the elements provided is constructed.
Test data
Minimal circuit using big curves
Input: [4,0,0]
Output: 0
Slightly more complicated circuit
Input: [3,1,2]
Output: 0
Incomplete circuit - can't join
Input: [3,0,0]
Output: 3
Incomplete circuit - can't join
Input: [3,1,1]
Output: 5
Circuit where big curves share a centre
Input: [2,2,0]
Output: 0
Bigger circuit
Input: [2,6,4]
Output: 0
Circuit where both concave and convex curves required
Input: [8,0,0] or [0,8,0]
Output: 0
Circuit with left over bit
Input: [5,0,0] or [0,5,0]
Output: 1
Notes
- 2 straights and a little curve are equivalent to a big curve, but use more pieces, so are preferred - should never be a situation where this combination is left, if there are any big curves in the circuit
- 4 little curves can usually be swapped for 4 straights, but not if this would cause the circuit to intersect itself
- The train set is also idealised - the track elements take up the widths shown, so it is valid for curves to pass through a single grid square without intersecting, in some cases. The grid just defines the element dimensions. In particular, two big curves can be placed so that the grid square at the top left of the example diagram would also be the bottom right square of another big curve running from left to top (with the diagram showing one running from right to bottom)
- A small curve can fit in the empty space under a big curve (bottom right grid square above). A second big curve could also use that space, shifted one across and one down from the first
- A small curve cannot fit on the same grid space as the outside of a big curve - mostly because there is no way to connect to it which doesn't intersect illegally
[5,0,0]
or[0,5,0]
would be1
. Is that correct? Could you add such a test case? \$\endgroup\$[8,0,0]
, with two 2x2 elements overlapping in the center of the grid? \$\endgroup\$