I was ready to tackle another Foobar question from Google. This is what they gave me:
Gearing Up for Destruction
==========================
As Commander Lambda's personal assistant, you've been assigned the task of configuring the LAMBCHOP doomsday device's axial orientation gears. It should be pretty simple -- just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it, the pegs that will support the gears are fixed in place.
The LAMBCHOP's engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last) touches and turns the gear on the next peg to the right.
Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function solution(pegs) which, if there is a solution, returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above, such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if the task is impossible, the function solution(pegs) should return the list [-1, -1].
For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus, the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and solution(pegs) should return [12, 1].
The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution({4, 17, 50})
Output:
-1,-1
Input:
Solution.solution({4, 30, 50})
Output:
12,1
-- Python cases --
Input:
solution.solution([4, 30, 50])
Output:
12,1
Input:
solution.solution([4, 17, 50])
Output:
-1,-1
I found this one to be quite a bit more difficult than the previous. I didn’t know the math behind gear ratios, so I started there with some research. I found that given a chain of gears with radius g1,g2,...gn the output ratio would be given by (g1/g2)*(g2/g3)*...*(gn-1/gn). I then created a diagram to help me visualize what was going on:
With the diagram it became clear that the first gear radius could also be expressed in terms of the peg distances minus the radius of the second gear. This pattern could then continue to the second gear and beyond. Each gear in the chain would cause the next radius to alternate between being added to or subtracted from the sum thus far. Combine this expression with the one for the gear ratios, and we see that the final gear radius can be expressed in terms of that same alternating sum up until the prior gear. Which gives us a recursive base case. Success!
But, alas, when I turned that into code some of the tests were failing. Google does not provide the details of their test cases, what was specifically being tested is left a mystery. That is part of the game. So I only knew that I was missing something.
I spent hours upon hours combing over my solution, but to no avail. It started to become frustrating. I didn’t want to step away from it because it was on a time limit, but I also believe that when code becomes frustrating then it is best to step back and take a break. That turned out to be the right decision, because after some sleep I finally spotted something I’d missed. It said in the question text “you can choose gears of any size, from a radius of 1 on up“. I was checking that the final answer was ≥1 but I had failed to consider the intermediate gears. I realized that checking this within the loop can actually take care of both cases. Finally, success!
But not quite. More tests were passing now, but there was still something failing. It turned out that I was checking something Google hadn’t intended for. I had reasoned that the peg distances were being measured from the LAMBCHOP station wall. If the distance between peg0 and peg1 was greater than the distance from the wall to peg0, then a solution might be found that satisfies all the other conditions yet hits the station wall. So I was checking for that. Once I removed that check all the tests passed.
This one tripped me up for quite a while, but at last, a solution:
# Author: Derek Moran, Level 2 Henchman @ Commander Lambda Space Station
# Date: 23-NOV-2022
def solution(pegs):
# Your code here
return getFirstGearRadiusThatDoublesOutputRotationAsReducedFraction( pegs )
# Takes a list of distinct positive integers named pegs representing the location of each peg along the support beam
# Assuming gears with minimal length 1 are placed on each peg, this returns the first gears radius such that the final gear doubles its rotation
# If a solution is not possible will return [-1,-1]
# Provided pegs must have at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive
def getFirstGearRadiusThatDoublesOutputRotationAsReducedFraction( pegs ):
solutionImpossible = [-1,-1]
numPegs = len(pegs)
if numPegs < 2 or numPegs > 20:
raise Exception("There must be at least 2 pegs and no more than 20")
# In the interest of performance, let's assume the pegs are indeed in ascending order and distinct
# TODO: Verify this assumption with Commander Lambda before shipping!!!
def getGearRadiusThatDoublesOutputRotationAsReducedFraction( pegIndex, previousAlternatingPegSum ):
if not type(pegs[pegIndex]) is int:
raise TypeError("Peg distances must be integers")
if pegs[pegIndex] < 1 or pegs[pegIndex] > 10000:
raise Exception("Peg distances must be between 1 and 10000 inclusive")
currentAlternatingPegSum = 0
if pegIndex > 0:
currentAlternatingPegSum = pegs[pegIndex] - pegs[pegIndex-1] - previousAlternatingPegSum
# Let radius of gears be r1, r2, ... rn
# Then r1 = pegs[1] - pegs[0] - r2
# but r2 = pegs[2] - pegs[1] - r3
# So r1 = pegs[1] - pegs[0] - pegs[2] + pegs[1] + r3
# but r3 = pegs[3] - pegs[2] - r4
# So r1 = pegs[1] - pegs[0] - pegs[2] + pegs[1] + pegs[3] - pegs[2] - r4
# Extending this pattern to rn, then r1 = ( alternatingPegSum + rn ) when n is odd, or r1 = ( alternatingPegSum - rn ) when n is even
# We also know that (r1/r2)*(r2/r3)...*(rn-1/rn) = r1/rn = 2, so we can substitute rn = r1/2
# Therefore r1 = ( 2 * alternatingPegSum ) when n is odd, or r1 = ( 2/3 * alternatingPegSum ) when n is even
# By extension since rn=r1/2, rn = alternatingPegSum when n is odd, or rn = ( alternatingPegSum / 3 ) when n is even
# Thus when we get to the final peg, we subtract the alternatingPegSum if there were odd number of pegs, otherwise add alternatingPegSum/3
if pegIndex == numPegs - 1:
currentGearRadiusNumerator = -1 * currentAlternatingPegSum
currentGearRadiusDenominator = 1
if pegIndex % 2 != 0:
if currentAlternatingPegSum % 3 != 0:
currentGearRadiusNumerator = currentAlternatingPegSum
currentGearRadiusDenominator = 3
else:
currentGearRadiusNumerator = currentAlternatingPegSum / 3
return [currentGearRadiusNumerator,currentGearRadiusDenominator]
nextGearRadiusAsReducedFraction = getGearRadiusThatDoublesOutputRotationAsReducedFraction( pegIndex + 1, currentAlternatingPegSum )
nextGearRadiusNumerator = nextGearRadiusAsReducedFraction[0]
currentGearRadiusDenominator = nextGearRadiusAsReducedFraction[1]
currentGearRadiusNumerator = ( ( pegs[pegIndex+1] - pegs[pegIndex] ) * currentGearRadiusDenominator ) - nextGearRadiusNumerator
if currentGearRadiusNumerator < currentGearRadiusDenominator:
return solutionImpossible
return [currentGearRadiusNumerator,currentGearRadiusDenominator]
firstGearRadiusThatDoublesOutputRotationAsReducedFraction = getGearRadiusThatDoublesOutputRotationAsReducedFraction( pegIndex=0, previousAlternatingPegSum=0 )
# We don't want the first gear's radius to extend into the station wall
# But the test cases fail if we check this, so the peg data may already be taking this into account?
# We should also confirm if the final radius might extend into the other station wall, but we do not presently have enough data to check that
#
# TODO: Bring these concerns up with Commander Lambda before shipping!!!
#
#if firstGearRadiusThatDoublesOutputRotationAsReducedFraction[0] > pegs[0] * firstGearRadiusThatDoublesOutputRotationAsReducedFraction[1]:
# return solutionImpossible
return firstGearRadiusThatDoublesOutputRotationAsReducedFraction
Leave a Reply