4
\$\begingroup\$

This is the Utopian Tree in F# (from HackerRank)

The Utopian tree goes through 2 cycles of growth every year. The first growth cycle of the tree occurs during the monsoon, when it doubles in height. The second growth cycle of the tree occurs during the summer, when its height increases by 1 meter. Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

This helped me understand what to do:

//N = 0 ret initial height
//N = 1 ret double height
//N = 2 ret double height, +1 
//N = 4 ret double, +1, double, + 1

Anywhere that I could improve this F# code? I'm trying to stay within the parameters of functional language programming. Per the doc on HackerRank, I had to take in n parameters, 0 being the number of test cases followed by the number of growth cycles:

[<EntryPoint>]
let main argv = 

    let tests = System.Int32.Parse(System.Console.ReadLine())
    let cycles = [for i in 1..tests -> System.Int32.Parse(System.Console.ReadLine())]

    let even h = h * 2
    let odd h = h + 1
    let rec height acc cycle n =
        match cycle - cycle + n with
            | c when c = cycle -> acc
            | c when c % 2 = 0 -> height (even acc) cycle (n+1)
            | _ -> height (odd acc) cycle (n+1)

    cycles |> List.map (fun c -> height 1 c 0) |> List.map (fun x -> System.Console.WriteLine x)

    0 // return an integer exit code

Example input/ouput:

3
0
1
4
1
2
7
\$\endgroup\$
7
\$\begingroup\$

A few points:

  1. The value i on the second line is not used. It is customary to use underscore to name such values.
  2. The expression cycle - cycle + n seems a bit redundant :-)
  3. If you swap the last two arguments of height, you can use it in partially applied form as argument to List.map on the last line (i.e. List.map (height 1 0)), instead of introducing extra lambda.
  4. The parameter cycle is improperly named: it doesn't signify a "cycle", but rather the "total number of cycles".
  5. In the "real world" (e.g. if you were designing a library or something), you shouldn't expose your "temporary state" parameters (i.e. acc and n) to the consumer. Instead, you should expose just the function with one parameter ("total number of cycles"), and have the actual recursive function private.
  6. Functions even and odd seem weirdly named: they don't do what they say. Either name them correctly (like, evenYearGrowth) or get rid of them altogether (personally I prefer the latter).
  7. The very last lambda (the one calling WriteLine) is also redundant: it just passes its argument directly to another function, so it can be replaced with that function.
  8. The last List.map call has a result of non-unit type (namely, List<unit>), which causes the compiler to produce a warning on that line (along the lines of "the result is being discarded, blah-blah-blah"). If you want to call a function on every element of the list solely for its side effects, use List.iter.
  9. Depending on performance considerations and expected problem size, the use of List may be a problem: mapping over a list (i.e. List.map) allocates a new list, which you don't actually need, because you're just reading values and "passing them through a pipeline", so to say. You don't need to remember them. In these circumstances, I use seq.
    On the other hand, the use of Seq all through will result in outputting each result right after receiving each input, which may or may not be the desired behavior. I don't know if it is, so I will leave the input acquisition as is.
  10. The System.Int32.Parse(System.Console.ReadLine()) piece looks kinda scary and unclean. Plus, it's repeated twice. So I would make it a separate function.
  11. Lastly (though this one is a matter of taste), I would use a string of ifs instead of the match. Seems shorter and cleaner.

So, having said all of the above, here is my version:

let main argv = 

    let height =
      let rec h acc n totalCycles =
        if n = totalCycles then acc
        elif n % 2 = 0 then h (acc * 2) (n+1) totalCycles 
        else h (acc + 1) (n+1) totalCycles 
      h 1 0

    let readInt = System.Console.ReadLine >> System.Int32.Parse
    let tests = readInt()
    let cycles = [for _ in 1..tests -> readInt()]

    cycles
      |> Seq.map height 
      |> Seq.iter System.Console.WriteLine

    0 // return an integer exit code
\$\endgroup\$
  • 1
    \$\begingroup\$ Oh god #2... I'm a moron! LOL \$\endgroup\$ – C Bauer Sep 14 '15 at 15:07
  • \$\begingroup\$ I've only recently started but this is much cleaner... thank you for the detailed run-down! There's a lot of things I can learn from this rewrite. \$\endgroup\$ – C Bauer Sep 14 '15 at 15:10
  • \$\begingroup\$ Glad to help :-) \$\endgroup\$ – Fyodor Soikin Sep 14 '15 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.