Inspired by the Lego gear ratios challenge by Keith Randall.
I, too, plan on building a giant lego robot that will eventually be able to destroy the other robots in the never-before-mentioned competition.* In the process of constructing the robot, I will be using a lot of gear trains to connect different parts of the robot. I want you to write me the shortest program that will help me construct the complex gear trains that are required for such a complex task. I will, of course, only be using gears with radii 1, 2, 3, and 5 arbitrary-lego-units.
Each gear in the gear train has a specific integer coordinate on a 2D grid. The first gear is located at (0,0) and the final gear will be located at non-negative coordinates. The location and size of the first and last gears will be provided as input, your program must tell what gears go where to fill in the gaps.
Additionally, your program must use the minimum possible number of gears in the gear train. Fewer gears / train = more trains** = bigger and better robot of destruction.
Input will consist of one line:
X and Y are the coordinates of the final gear. The first gear is always located at (0,0). B and A are the radii of the final and initial gears, respectively. To add some difficulty, you need to make sure that the output gear rotates in the correct direction. If A and B have the same sign, then the output gear needs to rotate in the same direction, and an odd number of gears must be used. If they have opposite signs, then an even number of gears need to be used.
Output should be a list of the X location, Y location, and radii of each additional gear, one gear per line. If there are multiple minimal-gear solutions, print only one of your choice. The order of gears in the output does not matter.
Examples (more equivalent solutions may be possible):
in 4,0,1,1 out 2,0,1 in 7,7,-2,-2 out 4,3,3 OR 0,7,5 OR the above reflected over y=x line in 7,8,-1,2 out 7,0,5 7,6,1 OR 7,0,5 1,8,5 in 7,7,2,-2 out 4,-3,3 7,1,2 12,1,3 12,7,3 OR any permutation of the above, or reflected over y=x line Now you're thinking with gear trains!
Here's the solutions to the above examples, visualized:
As far as I know, no problem is impossible unless the two input gears overlap or directly connect. You won't have to deal with this.
This is code golf, shortest answer wins.
*A future KOTH, anyone?