Toys and Triangles
This problem gives us 10 stick lengths, and asks us to make joined triangles out of them. Assuming the base of one triangle is against a wall, and joined triangles share a side, how far away from the wall is the furthest triangle?
The fact that there are 10 stick lengths is a huge hint this is brute force. Two questions: how do we iterate through the combinations? Is it fast enough?
Intuition: it never makes sense to build twice off the same triangle. That would give us "parallel" triangles paths, which is just wasting sticks. We can't do worse by removing the shorter of the two parallel paths and joining it to the other one.
Intuition: if we choose all permutations, we can always just attach to the MOST previously chosen edge, since we'll try the other edge in some other permutation
- Choose some stick to place against the wall (1)
- Choose two sticks to form the first triangle (2,3)
- Choose two sticks to form the next triangle (4,5, always attach in the same order to side 3)
- Choose two sticks to form the next triangle (6,7, always attach in same order to side 5)
- Choose two sticks to form the next triangle (8,9, always attach in same order to side 7)
Once it is constructed, need to do some nasty trig to calculate the distance.
combinations = 10! = 3628800 = fast enough.
The nasty trig is left to the reader.