/ HackerRank Functional Challenges

HR F#: Area Under Curves and Volume of Revolving a Curve

Screen-Shot-2017-09-03-at-18.07.13-1

The next problem, Area Under Curves and Volume of Revolving a Curve, in mathematically advance so I introduce some therms and facts first.

Numerical integration is the measuring the area between function and axis, which is done by evaluating function in many points closing to each other and adding together all rectangles (or trapezoids) formed by points on axis and points on the functional curve. For many functions decreasing step between points decreases difference between calculated value and actual area.

Continuous function is a function that, roughly speaking, has graph without "holes" or "jumps", e.g. its graph is a single unbroken curve. The continuouty can be local, e.g. on some interval.

Revolving a Curve is a transformation of 2D curve into 3D shape by revolving the curve around the axis. The are many examples of such figures in turning machine YouTube videos.

Volume of cylinder can be computed by using the formula

$$V = π r^2 h$$

I'm going to rephrase the problem statement a bit:

Consider the algebraic expression given by:
$$a_1 x ^{b_1} + a_2 x ^{b_2} + ... + a_n x ^{b_n}$$
Evaluate a) the area bounded by the function between the given limits L and R and b) the volume of the solid figure obtained by revolving this curve around the x-axis. Use the step length 0.001. Limits can be from 1 to 20. b ∈ [-20, 20] ∩ ℕ.

The given function is continous on [1, 20] so it is ok to integrate it numerically.

The number of steps required to solve the problem is

$$ \frac{R - L} {step length} b n c < \frac{19} {0.001} 20 n c = 380000 n c$$

where n is the number of items in the expression (which is probably less than 50) and c is a some constant representing number of operations required to compute area and volume (probably about 5). So the rough estimation is 10^8 arithmetic operations in worst case. The cost of devision is something about 10^-8 so the worst case computation time should be around 1 second, which is good enough to just try to solve the problem without optimisations at all.

Let's split the problem into smaller chunks:

  1. Calculate x^y
  2. Calculate single item of the expression
  3. Calculate expression
  4. For every point calculate area and volume and return their sum

The expression can be defined as a list of two-items tuples:

let pi = System.Math.PI

let item a b x =
  // x ** b is x^b (power operator)
  a * (x ** b)

let expr cs x =
  cs
  |> List.fold (fun s c -> s + (item (fst c) (snd c) x)) 0.0
  
let numIntAndVol cs l r =
  let folding s y =
    let s, v, prev = s
    (s + 0.001 * y, v + 0.001 * y * y * pi, y) 
  seq { l .. 0.001 .. r }
  |> Seq.map (fun x -> expr cs x)
  |> Seq.fold folding (0.0, 0.0, 0.0)

And now the main method:

[<EntryPoint>]
let main argv = 
  let a = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
  let b = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
    
  // this is a nice trick - it converts two lists to a list of tuples
  let cs = List.zip a b
    
  let limits = Console.ReadLine().Split(' ') |> Array.toList |> List.map float
  let l, r = limits.[0], limits.[1]
  let area, volume, _ = numIntAndVol cs l r
  printfn "%A" area
  printfn "%A" volume    
  0 // return an integer exit code

Input:

1 2 3 4 5
6 7 8 9 10
1 4

Output:

414.023
36024.18118
Alex Netkachov

Alex Netkachov

Alex Netkachov is a Senior Software Developer, currently working in Central London on new generation of energy trading solutions for brokers, traders and exchanges.

Read More

Why not to chat about this post? Join Telegram group Alex@Net or message on Twitter to alex_at_net. Alternatively, use the comments form below.