Utopian tree life cycles

Question

Simple algorithm based HackerRank challenge.

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?

Input Format
The first line contains an integer, T, the number of test cases. T lines follow. Each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints
1 <= T <= 10 0 <= N <= 60

Output Format
For each test case, print the height of the Utopian tree after N cycles.

Test Cases can be found at HackerRank

static int[] LifeCycle(int[] input)
{
    int[] output = new int[input.Length];
    for (int i = 0; i < input.Length; i++)
    {
        int lifeCycleCount = Convert.ToInt32(input[i]);
        if (lifeCycleCount == 0)
        {
            output[i] = 1; //no growth 
        }
        else
        {
            var treeHeight = 1;
            for (int j = 0; j < input[i]; j ++)
            {
                if (j % 2 == 0)
                {
                    treeHeight = treeHeight + treeHeight; //Monsoon Growth
                }
                else
                {
                    treeHeight++; //Summer Growth
                }
            }
            output[i] = treeHeight;
        }
    }
    return output;
}
static void Main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */

    int howMany = Convert.ToInt32(Console.ReadLine());
    int[] input = new int[howMany];
    for (int i = 0; i < howMany; i++)
    {
        input[i] = Convert.ToInt32(Console.ReadLine());
    }

    int[] result = LifeCycle(input);
    for (int i = 0; i < result.Length; i++)
    {
        Console.WriteLine(result[i].ToString());    
    }
}

Simple enough, but do I really need to use all the if statements and for loops?

I passed all the tests they put the code through (0.08s on each, total of 9 tests)

Answer 1

This is a generally good solution. Pretty good adherence to naming conventions, and generally quite easy to read. It's probably just fine as it is, but if you do want to make it better, there are some improvements that can be made:

Extracting the outermost method

First off, we have:

static int[] LifeCycle(int[] input)

We know right from the start that for this method:

• The processing of each individual element is independent from the processing of each other individual element
• Operations performed on individual elements (calculating the growth of a tree) are non-trivial
• Operations performed on entire collections (input and output) are trivial

So this is screaming to have the individual tree processing extracted out:

static int LifeCycle(int input)

Then the contents of your original method can be nice and concise, using LINQ:

static int[] LifeCycle(int[] input)
{
    return input.Select(i => LifeCycle(i)).ToArray();
}

Aside: Naming

Actually, now that we're here, extracting this method has brought into sharper focus that maybe the naming isn't ideal. input is extremely vague- why not lifeCycleCount, which is what you actually use it as inside the method? Likewise LifeCycle would be better as a description of something the method is doing, like CalculateGrowth.

Initializing the height

One of the uglier pieces of logic is the special case for the number of cycles being 0. Is that necessary? What are we actually getting at with this:

if (lifeCycleCount == 0)
{
    output[i] = 1; //no growth 
}

If there aren't any cycles, there's no growth, so we go to the magic number 1. But where's 1 coming from? It's the starting height. Is that encoded somewhere? Yes! Just two lines later:

var treeHeight = 1;

But the starting tree height is 1 no matter whether the cycle count is 0 or not, right? So we can move that outside the if statement. And once we do, immediately it becomes clear the if statement doesn't need to be there at all. If the cycle count is 0, then the for loop will never be executed and you'll stay with the default value of 1, which is what you want.

There's a bit more inconsistency here too. Like you needlessly call Convert.ToInt32 on an integer, and in once place you assign it to a variable with another name (lifeCycleCount), and in another place you keep it as input[i]. This may be left over detritus if you refactored from passing in input as an array of strings.

Extract one more method

At this point, you could happily stop and you'll have a nice piece of code. But there's one more thing that may be an improvement. This:

if (j % 2 == 0)
{
    treeHeight = treeHeight + treeHeight; //Monsoon Growth
}
else
{
    treeHeight++; //Summer Growth
}

Looks to me like its own method. There's quite a lot of information here that the brain has to do some reading/calculation to work out:

• The code alternates between executing the two blocks
• The first block is always executed first of the two
• Both blocks use the tree height as their sole input
• The only effect of either block is to change the tree height
• From the comments, both blocks represent tree growth

A method lets us encode a lot of that in a way that we can read right away:

static int GrowTree(int initialHeight, bool season)

Then, we can just call it inside the loop like:

treeHeight = GrowTree(treeHeight, j%2==0);

Now this reads much more clearly. The tree height is changing because it is growing, how much it grows depends on its initial height and the season, and the season alternates every time the loop is run.

There are other options with the alternation too which, depending on taste, you may find more readable. Like:

season = j%2==0;
treeHeight = GrowTree(treeHeight, season);

or

treeHeight = GrowTree(treeHeight, season);
season = !season;

(In both cases, season would be a bool initialized outside the loop)

Putting it together

And just so you can see how nice it is with all those changes, here's roughly what it would look like:

static int[] CalculateGrowth(int[] cycleCounts)
{
    return cycleCounts.Select(c => CalculateGrowth(c)).ToArray();
}

static int CalculateGrowth(int cycleCount)
{
    var treeHeight = 1;
    var season = true;

    for(int i=0; i<cycleCount; i++)
    {
        treeHeight = GrowTree(treeHeight, season);
        season = !season;
    }

    return treeHeight;
}

static int GrowTree(int initialHeight, bool season)
{
    return season ? initialHeight * 2 : initialHeight + 1;
}

Answer 2

FWIW, the problem has an O(1) solution (i.e. formula, no loops)...

N is season number, h the height (at the end of that season)

In Excel

h = (2^(INT(N/2)+1)-1)*(1+INT(MOD(N,2)))

In C#

  for (int n = 0; n < 10; n++)
  {
    Console.WriteLine($"{n,2}, {(Math.Pow(2, n / 2 + 1) - 1) * (1 + n % 2),3}");
  }

Output

 0,   1
 1,   2
 2,   3
 3,   6
 4,   7
 5,  14
 6,  15
 7,  30
 8,  31
 9,  62