My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

The code contains #ifdefs to switch between the original problem and the Hackerrank version.
Enable #ifdef ORIGINAL to produce the result for the original problem (default setting for most problems).

       
#include <iostream>
       
#include <vector>
       
#include <map>
       
 
       
#define ORIGINAL     // disable for Hackerrank
       
#define SYMMETRIC_ID // identify rows in reverse order as similar
       
 
       
// total height

       
unsigned int height    = 8;
       
unsigned int numColors = 3;
       
 
       
// "scratchpad", used while processing the colorings

       
typedef char Color;
       
std::vector<Color> triangles;
       
 
       
// cache result for completed rows, index is determined by getId()

       
#ifdef ORIGINAL
       
std::vector<unsigned long long> cache(5102 + 1, 0); // sufficient for height<=8 and numColors<=3
       
#else
       
std::map<unsigned int, unsigned long long> cache;   // handle bigger input values, too
       
#endif
       
 
       
// compute hash value of a row

       
unsigned int getId(unsigned int row)
       
{
       
  auto first = row * row;
       
  auto width = 2 * row + 1;
       
 
       
  // compute hash of triangles: find differences between adjacent triangles of the same orientation
       
  unsigned int result = row;
       
  for (auto i = first + 2; i < first + width; i += 2)
       
  {
       
    auto diff = triangles[i - 2] - triangles[i];
       
    if (diff < 0)
       
      diff += numColors;
       
 
       
    result = result * numColors + diff;
       
  }
       
 
       
#ifdef SYMMETRIC_ID
       
  // simple optimization based on symmetry: process the same triangles in reverse order:
       
  unsigned int reverse = row;
       
  for (auto i = first + width - 1; i >= first + 2; i -= 2)
       
  {
       
    // exactly the same as above but "i" is running in reverse
       
    auto diff = triangles[i - 2] - triangles[i];
       
    if (diff < 0)
       
      diff += numColors;
       
 
       
    reverse = reverse * numColors + diff;
       
  }
       
  if (result > reverse)
       
    result = reverse;
       
#endif
       
 
       
  return result;
       
}
       
 
       
// simple enumeration, solves triangle with 5 rows in about a second

       
unsigned long long search(unsigned int row = 0, unsigned int column = 0)
       
{
       
  // index of the first triangle in the current row
       
  auto first = row * row;
       
  // index of the current triangle
       
  auto index = first + column;
       
  // number of triangles in the current row
       
  auto width = 2 * row + 1;
       
 
       
  // "coordinates" of the next triangle
       
  auto nextRow    = row;
       
  auto nextColumn = column + 1;
       
  if (nextColumn == width)
       
  {
       
    // start a new row
       
    nextRow++;
       
    nextColumn = 0;
       
  }
       
 
       
  // hash value of the previous row, only needed when starting a new row
       
  unsigned int prevId = 0;
       
  if (column == 0)
       
  {
       
    // finished ?
       
    if (row == height)
       
      return 1; // found another valid coloring
       
 
       
    if (row == 0)
       
      cache.clear(); // only relevant when computing multiple triangle sizes (as I did while developing my solution)
       
    else // row > 0
       
    {
       
      // already cached ?
       
      prevId = getId(row - 1);
       
      if (cache[prevId] != 0)
       
        return cache[prevId];
       
    }
       
  }
       
 
       
  // recursively process current position
       
  unsigned long long result = 0;
       
  if (column % 2 == 0) // even: no contact to triangle in row above
       
    for (Color color = 1; color <= (Color)numColors; color++)
       
    {
       
      // exclude color of left neighbor (but first triangle in a row can have any color because it has no left neighbor)
       
      if (column > 0 && triangles[index - 1] == color)
       
        continue;
       
      triangles[index] = color;
       
      result += search(nextRow, nextColumn);
       
    }
       
  else                 // odd: must respect triangle in row above
       
    for (Color color = 1; color <= (Color)numColors; color++)
       
    {
       
      // exclude color of left neighbor and neighbor in row above
       
      if (triangles[index - 1] == color || triangles[index - 2 * row] == color)
       
        continue;
       
      triangles[index] = color;
       
      result += search(nextRow, nextColumn);
       
    }
       
 
       
#ifndef ORIGINAL
       
  // Hackerrank only
       
  result %= 1000000007;
       
#endif
       
 
       
  // store result
       
  if (column == 0 && row > 0)
       
    cache[prevId] = result;
       
 
       
  return result;
       
}
       
 
       
int main()
       
{
       
  std::cin >> height >> numColors;
       
  triangles.resize(height * height);
       
 
       
  // let's go !
       
  std::cout << search() << std::endl;
       
  return 0;
       
}

This solution contains 20 empty lines, 22 comments and 12 preprocessor commands.