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.
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.
A number corresponding to the number of pieces left over when the maximum possible circuit for the elements provided is constructed.
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
- 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