The first thing that comes into my mind is that if evapPerDay
is <= 0
the function will continue infinitely - or more precise: until a stack overflow is encountered. So you have to guard against that:
let evaporatorReview (content: float) (evapPerDay: float) (threshold: float): int =
if evapPerDay <= 0. then
failwith "evapPerDay must be greater than 0.0"
else
// ... The original algorithm
The next is that by having the unnecessary local result
variable solve()
isn't tail recursive. You can fix that by simply return directly from the match
-entries:
let evaporator (content: float) (evapPerDay: float) (threshold: float): int =
let minUsefulAmount = content * (threshold / 100.)
let evapAsPercentage = evapPerDay / 100.
let rec solve (content: float) (dayCount: int) =
let amountLost = content * evapAsPercentage
let newContent = content - amountLost
let stillUseful = newContent > minUsefulAmount
match stillUseful with
| true -> solve newContent (dayCount + 1)
| false -> dayCount
solve content 1
IMO all the temporary variables in solve()
blur what actually is going on. By skipping them and do the calculations directly in the recursive call to solve()
the picture is more clear:
let evaporator (content: float) (evapPerDay: float) (threshold: float): int =
if evapPerDay <= 0. then
failwith "evapPerDay must be greater than 0.0"
else
let limit = content * threshold / 100.
let rec solve (content: float) (dayCount: int) =
match content with
| x when x <= limit -> dayCount
| _ -> solve (content * (1. - evapPerDay / 100.)) (dayCount + 1)
solve content 0
In fact you don't have to calculate on the content, you can do it percentage wise:
let evaporatorReview (content: float) (evapPerDay: float) (threshold: float): int =
if evapPerDay <= 0. then
failwith "evapPerDay must be greater than 0.0"
else
let limit = threshold / 100.
let rec solve (remaining: float) (dayCount: int) =
match remaining with
| x when x <= limit -> dayCount
| _ -> solve (remaining * (1. - evapPerDay / 100.)) (dayCount + 1)
solve 1. 0
The mathematical "discipline" in question here is exponential growth (r > 0
) or decay (r < 0
) and there is a formula for that:
Xn = X0 * (1 + r)^n
Where Xn
is threshold
, X0
is 100
or content
, r
is evapPerDay / 100.
and n
is the number of days = the result.
This can be use in sequential calculations ending when the threshold is met:
let evaporatorSeq (content: float) (evapPerDay: float) (threshold: float): int =
if evapPerDay <= 0. then
failwith "evapPerDay must be greater than 0.0"
else
let limit = threshold / 100.0
Seq.initInfinite (fun i -> i)
|> Seq.takeWhile (fun n -> Math.Pow(1.0 - evapPerDay / 100.0, float n) > limit)
|> Seq.last
|> (+) 1
But even better, it can be solved in respect to n
as :
n = log(Xn/X0) / log(1 + r)
which can be used in the function as an O(1) - solution:
let evaporator content evapPerDay threshold =
match evapPerDay with
| x when x = 100. -> 1
| x when x <= 0.0 -> failwith "evapPerDay must be greater than 0.0"
| _ -> int (Math.Ceiling(Math.Log((threshold / 100.) / 1.) / Math.Log(1. - evapPerDay / 100.)))
The division by 1.
is of cause redundant, but it emphasize the relation of the expression to its origin.
if evapPerDay = 100. then 1
is necessary here because if evapPerDay = 100
then Math.Log(1.0 - evapPerDay / 100.)
becomes Math.Log(0.)
which isn't defined.
programming-challenge
. \$\endgroup\$