// --------------------------------------------------------------------
// 
//      *-------------------------
//       \                       
//        \                      
//         \                     
//          \                    
//      -----====================*
// 
// 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 ---