// -------------------------------------------------------------------- // // *------------------------- // \ // \ // \ // \ // -----====================* // // The river is 3 miles wide. We need to lay pipe between the starred // points, which are 5 miles apart along the river. Pipe laid on land // costs \$2.00/foot, and pipe laid in the river costs \$4.00/foot. // // What is the minimum cost of the project? // // We brute-force a solution. // // -------------------------------------------------------------------- // // The main function searches for the number of feet of pipe on land // that minimizes total cost, using a loop to examine all values. It // prints the optimal value for land pipe and returns the minimum cost // of the project. // main( waterPerFoot : integer, landPerFoot : integer, widthInMiles : integer, lengthInMiles : integer ) : integer minimumCost( costWithLandPipeOf( 0, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ), 1, // then start loop at 1 foot on land waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ) // // The minimumCost function loops over all possible values for // feetOfLandPipe (arg 2) and replaces the running minimum (arg 1) // every time it finds a smaller value. It uses the function // minimumCostChoose so that it doesn't have to call the function // costWithLandPipeOf twice, and the printNewCandidateAndRecur // function to print the updated minima when they pass by. // minimumCost( minimumSoFar : integer, nextLengthInFeet : integer, waterPerFoot : integer, landPerFoot : integer, widthInMiles : integer, lengthInMiles : integer ) : integer if milesToFeet(lengthInMiles) < nextLengthInFeet then minimumSoFar else minimumCostChoose( costWithLandPipeOf( nextLengthInFeet, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ), minimumSoFar, nextLengthInFeet + 1, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ) endif minimumCostChoose( candidateMinimum : integer, minimumSoFar : integer, nextLengthInFeet : integer, waterPerFoot : integer, landPerFoot : integer, widthInMiles : integer, lengthInMiles : integer ) : integer if candidateMinimum < minimumSoFar then printNewCandidateAndRecur( candidateMinimum, nextLengthInFeet, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ) else minimumCost( minimumSoFar, nextLengthInFeet, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ) endif printNewCandidateAndRecur( minimumSoFar : integer, nextLengthInFeet : integer, waterPerFoot : integer, landPerFoot : integer, widthInMiles : integer, lengthInMiles : integer ) : integer print( minimumSoFar ) minimumCost( minimumSoFar, nextLengthInFeet, waterPerFoot, landPerFoot, widthInMiles, lengthInMiles ) // // cost computations // costWithLandPipeOf( feetOfLandPipe : integer, waterPipePerFoot : integer, landPipePerFoot : integer, widthInMiles : integer, lengthInMiles : integer ) : integer landPipePerFoot * feetOfLandPipe + waterPipePerFoot * feetOfWaterPipe( feetOfLandPipe, widthInMiles, lengthInMiles ) // // geometric computations // feetOfWaterPipe( feetOfLandPipe : integer, widthInMiles : integer, lengthInMiles : integer ) : integer sqrt( square( widthInMiles ) + square(milesToFeet(lengthInMiles) - feetOfLandPipe) ) // // unit conversion functions // feetToMiles( feet : integer ) : integer 5280 * feet milesToFeet( miles : integer ) : integer miles / 5280 // // utility functions // square( n : integer ) : integer n * n // // This is adapted from sqrt.kln. It uses Newton's general method // to approximate a square root in Klein's wonderful world of // integers. The generalized method can be used to compute the // roots of any (real-valued) function. // // Because we know that we are computing a square root, an even // simpler form of Newton's method works: // guess = (n/guess + guess) / 2. // // The sqrt function hard-codes an epsilon of 5. We can tweak that. // sqrt(n : integer) : integer newton(n/2, 5, n) newton( guess : integer, epsilon : integer, n : integer ) : integer newtonAux( guess - f(guess,n)/df(guess), guess, epsilon, n ) newtonAux( guess : integer, previous : integer, epsilon : integer, n : integer ) : integer if epsilon < ABS(previous - guess) then newtonAux( guess - f(guess,n)/df(guess), guess, epsilon, n ) else guess endif f( x : integer, n : integer ) : integer x * x - n df( x : integer ) : integer 2 * x // // This function comes from the Klein standard library. // ABS( n : integer ) : integer if 0 < n then n else -n endif // --- the end ---