// ////////////////////////////////////////////////////////
// # Title
// Tri-colouring a triangular grid
//
// # URL
// https://projecteuler.net/problem=189
// http://euler.stephan-brumme.com/189/
//
// # Problem
// Consider the following configuration of 64 triangles:
//
// ![grid](p189_grid.gif)
// We wish to colour the interior of each triangle with one of three colours: red, green or blue, so that no two neighbouring triangles have the same colour. Such a colouring shall be called valid. Here, two triangles are said to be neighbouring if they share an edge.
// Note: if they only share a vertex, then they are not neighbours.
//
// For example, here is a valid colouring of the above grid:
//
// ![colored grid](p189_colours.gif)
// A colouring C' which is obtained from a colouring C by rotation or reflection is considered distinct from C unless the two are identical.
//
// How many distinct valid colourings are there for the above configuration?
//
// # Solved by
// Stephan Brumme
// September 2017
//
// # Algorithm
// I solved this problem in classic Dynamic Programming way:
// - generate each possible row triangle-by-triangle, beginning with the top row
// - whenever I start a new row check if I already fully processed a row __similar__ to the most previous row
//
// The trick is to define the word "similar": I call rows similar to each other if they are followed by the same number of combinations for all rows beneath it.
// For example, each color of the top-most triangle is similar to each other because I can permute the color such that I can produce the original coloring.
//
// My function ''getId()'' returns a hash value of a row stored in ''triangle''. If two rows share the same hash then they must be similar.
// Only a row's triangles that share an edge with the row beneath it are relevant (in general: each triangle with an even index).
// In the third row of the example, only the left-most green and the two blue triangles have to be considered by ''getId()''.
//
// Each color is represented by an integer: Red = 1, Green = 2, Blue = 3.
// Initially I used these codes to get a hash value
// `id = row * (color[0] * 3^0 + color[2] * 3^1 + color[4] * 3^2 * ...)`
//
// Then it occurred to me that the differences between those relevant triangles are sufficient (plus 3 if difference is negative):
// `id = row * ((color[2] - color[0]) * 3^0 + (color[4] - color[2]) * 3^1 + (color[6] - color[4]) * 3^2 + ...)`
//
// Due to symmetry, each row is similar to itself when all relevant triangles are in reverse order (see ''#define SYMMETRIC_ID'').
// So I compute two hashes and choose the smaller one because I want to have as many rows as possible to share the same hash value / ID.
//
// # Hackerrank
// The number of colors can be larger than 3 and the maximum height of the triangle is 11.
// My solution times out for about every fifth test case.
//
// # Alternative
// There is something called "chromatic polynomials" which can solve this problem, too (see https://en.wikipedia.org/wiki/Chromatic_polynomial ).
// I haven't tried it but it seems to be a faster way.
#include
#include
#include