// ////////////////////////////////////////////////////////
// # Title
// Cuboid layers
//
// # URL
// https://projecteuler.net/problem=126
// http://euler.stephan-brumme.com/126/
//
// # Problem
// The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.
//
// ![cuboids](p126.gif)
//
// If we then add a second layer to this solid it would require forty-six cubes to cover every visible face,
// the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.
//
// However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.
//
// We shall define `C(n)` to represent the number of cuboids that contain n cubes in one of its layers. So `C(22) = 2`, `C(46) = 4`, `C(78) = 5`, and `C(118) = 8`.
//
// It turns out that 154 is the least value of n for which `C(n) = 10`.
//
// Find the least value of n for which `C(n) = 1000`.
//
// # Solved by
// Stephan Brumme
// August 2017
//
// # Algorithm
// The initial cuboid (without any layers) has six sides:
// - front and back side, both with an area of `width * height`
// - left and right side, both with an area of `height * depth`
// - top and bottom side, both with an area of `depth * width`
// The total surface area is `2 * (width * height + height * depth + depth * width)`.
// Each part of the surface is covered by the first layer. That means:
// `C(1) = 2 * (width * height + height * depth + depth * width)`.
//
// For the 3 x 2 x 1 cuboid: `C(1) = 2 * (3 * 2 + 2 * 1 + 1 * 3) = 2 * (6 + 2 + 3) = 2 * 11 = 22`
//
// The computation of the second, third, fourth, ... layer wasn't obvious to me. My drawing skills are sub-par at best.
// So I decided to write some code: start with a shape and move that shape one unit left, right, up, down, forward and backward
// (start each move at the initial position). The difference between the old shape and the shape created by these six movements is the volume of the new layer.
// My function ''naive()'' (last lines of my code) performs exactly these steps. Starting with a specified cuboid it finds the volume of each additional layer and prints it.
//
// Playing around with several cuboid sizes I saw a pattern:
// `C(2) = C(1) + 4 * (width + height + depth)`
// `C(3) = C(2) + 4 * (width + height + depth) + 8`
// `C(4) = C(3) + 4 * (width + height + depth) + 16`
// `C(5) = C(4) + 4 * (width + height + depth) + 24`
//
// A bit more general:
// `C(1) = 2 * (width * height + height * depth + depth * width)`.
// `C(n) = C(n-1) + 4 * (width + height + depth) + 8 * (n - 2)`
//
// You can convert the second formula into a closed form but then the equation looks a bit messy.
// The C++ compiler won't generate much faster code, too. The function ''Cuboid::calculate'' evaluates these two equations.
//
// In order to solve `C(n) = x` for arbitrary `x` (it's `x = 1000` in the original problem) I wrote code based on ''std::map'':
// - each cuboids is represented by ''Cuboid'', it stores the size of the initial cuboid and the number of layers
// - ''Cuboid'' can be sorted by the size of the outermost layer (and then by it's sides)
// - since ''std::map'' is an ascendingly sorted container, it's first element is the cuboid with the smallest outermost layer
//
// Starting with the most basic cuboid (1,1,1) with only 1 layer I repeat the following:
// - pick and remove the first (= smallest) cuboid from the container
// - add a cuboid with ''width + 1'' to the container
// - add another cuboid with ''height + 1''
// - and a cuboid with ''depth + 1''
// - finally add a cuboid with ''layer + 1'' to that container
//
// Adding a cuboid is encapsulated in the ''add()'' function. It rejects cuboids where ''height > width'' and ''depth > height'' to avoid
// having the same (rotated) cuboid multiple times in the container. Adding exactly the same container twice is prevented, too.
// On top of that, ''add()'' keeps track of the volume of the most recent layer (in ''count[]'').
//
// That algorithm stops when the smallest cuboid has exactly 1000 "siblings" (==> the ''count'' of the current volume is 1000).
// It shows the correct result after about 4 seconds.
//
// However, my profiler showed that a few million cuboids where added (and removed) from the container.
// The overhead of memory allocation was responsible for the majority of the execution time.
//
// A much faster approach is to guess an upper limit of the result and then create all cuboids (and layers) that fit into that limit.
// Keeping track of just the various values of `C()` instead of the cuboids can be done with a small ''std::vector''.
// The program becomes about 50x faster and has almost no memory consumption. See my function ''fast()''.
//
// The main problem is to find a good guess for the upper limit.
// ''fast()'' returns 0 if no result was found, that's when the initial guess has to be incremented and another call to ''fast()'' is required.
// Starting with a very high guess will find the result but might waste lots of time computing cuboids with too large volumes.
// Currently, I use a ''StepSize = 10000'' ... yes, I know it's not optimal (it doesn't find the result in its first iteration)
// but I deliberately keep it this way.
// If ''StepSize = 50'' then ''fast()'' isn't faster than my original code.
// If ''StepSize = 150000'' then ''fast()'' isn't faster than my original code.
// That means for the original problem, ''fast()'' is only truly faster if ''50 < StepSize < 150000''.
//
// # Note
// Even though the code of ''fast()'' is shorter (and can be faster), I have a strange feeling about it:
// somehow it needs a good guess but I haven't found a way to come up with a straightforward way to generate that guess.
//
// I was stuck for a while because initially I stopped when I found a layer volume with __at least__ 1000 matching cuboids (instead of __exactly__ 1000).
// There are a few volumes below the correct solution with more than 1000 cuboids.
//
// Kristian Edlund visualized a nice way to enumerate the cubes added in each layer. His blog can found in my [links](#links).
#include
#include
#include
#include