#include <cassert>
#include <cstddef>
#include <iostream>

// ASCII art and grayscale
//
// We can create a crude grayscale image using only
// characters.
//
// Some characters appear very light:
//
//       ` . '
//
// while other characters appear much darker:
//
//       # B M W @
//
// The following arrays associate 92 characters with
// measured grayscale values between 0.0 and 1.0.
//
// For example, a grayscale value close to 0.0 should
// be represented by a light character, while a value
// close to 1.0 should be represented by a dark
// character.
//
// Complete numeric_to_char(...) so that it returns
// the character whose associated value is closest
// to the given grayscale value.
//
// The values are already sorted. Use binary search
// rather than examining all 92 values one at a time.
//
// The output from main() will give you a visual
// indication of whether your function is working.

// Function declarations
int main();

char numeric_to_char(
    double const grayscale
);

// Function definitions
int main() {
    // Print a grayscale ramp from light to dark.

    for ( unsigned int k{ 0 }; k <= 100; ++k ) {
        std::cout << numeric_to_char( k*0.01 );
    }

    std::cout << std::endl
              << std::endl;

    // Now produce a two-dimensional grayscale
    // pattern.
    //
    // Each row begins slightly darker than the
    // preceding row, while each position across
    // a row also becomes progressively darker.

    for ( unsigned int j{ 0 }; j <= 25; ++j ) {
        double const g0{ j*0.02 };

        for ( unsigned int i{ 0 }; i <= 50; ++i ) {
            std::cout
                << numeric_to_char( g0 + i*0.01 );
        }

        std::cout << std::endl;
    }

    std::cout << std::endl;

    return 0;
}


// char numeric_to_char( ... )
//
// @param grayscale
//     A grayscale value between 0.0 and 1.0.
//
// @returns
//     The character whose corresponding grayscale
//     value is closest to grayscale.
//
// @precondition
//
//     0.0 <= grayscale <= 1.0
//
// @algorithm
//     The array values[] is sorted.
//
//     Use binary search to locate either:
//
//       - an entry exactly equal to grayscale, or
//
//       - two consecutive entries between which
//         grayscale lies.
//
//     In the latter case, return the character
//     corresponding to whichever value is closer.
//
// Character ordering and grayscale values adapted
// from a discussion at:
//
//     stackoverflow.com/questions/30097953/
//
// with thanks to Stack Overflow user Chungaloider.

char numeric_to_char(
    double const grayscale
) {
    assert(
        (grayscale >= 0.0)
     && (grayscale <= 1.0)
    );

    std::size_t const CHARS{ 92 };

    char const characters[CHARS + 1]{
        " `.-':_,^=;><+!rc*/z"
        "?sLTv)J7(|Fi{C}fI31t"
        "lu[neoZ5Yxjya]2ESwqk"
        "P6h9d4VpOGbUAKXHm8RD"
        "#$Bg0MNWQ%&@"
    };

    double const values[CHARS]{
        0,      0.0751, 0.0829, 0.0848, 0.1227,
        0.1403, 0.1559, 0.185,  0.2183, 0.2417,
        0.2571, 0.2852, 0.2902, 0.2919, 0.3099,
        0.3192, 0.3232, 0.3294, 0.3384, 0.3609,
        0.3619, 0.3667, 0.3737, 0.3747, 0.3838,
        0.3921, 0.396,  0.3984, 0.3993, 0.4075,
        0.4091, 0.4101, 0.42,   0.423,  0.4247,
        0.4274, 0.4293, 0.4328, 0.4382, 0.4385,
        0.442,  0.4473, 0.4477, 0.4503, 0.4562,
        0.458,  0.461,  0.4638, 0.4667, 0.4686,
        0.4693, 0.4703, 0.4833, 0.4881, 0.4944,
        0.4953, 0.4992, 0.5509, 0.5567, 0.5569,
        0.5591, 0.5602, 0.5602, 0.565,  0.5776,
        0.5777, 0.5818, 0.587,  0.5972, 0.5999,
        0.6043, 0.6049, 0.6093, 0.6099, 0.6465,
        0.6561, 0.6595, 0.6631, 0.6714, 0.6759,
        0.6809, 0.6816, 0.6925, 0.7039, 0.7086,
        0.7235, 0.7302, 0.7332, 0.7602, 0.7834,
        0.8037, 1.0
    };

    // Replace this temporary implementation
    // with a binary search.

    if ( grayscale < values[CHARS/2] ) {
        return characters[0];
    } else {
        return characters[CHARS - 1];
    }
}



































// Hint
//
// This is slightly different from the binary search
// in the previous exercise.
//
// There, we were looking for an exact value.
//
// Here, grayscale will usually NOT occur exactly in
// values[].
//
// Instead, we want to find two neighboring values:
//
//     values[low] <= grayscale <= values[high]
//
// where
//
//     high == low + 1.
//
// For example:
//
//                  grayscale
//                      |
//                      v
//
// values:  0.41    0.42    0.423    0.4247
//                    ^        ^
//                   low      high
//
// Once only two neighboring possibilities remain,
// determine which is closer.
//
//
// First deal with the two endpoints:
//
//     grayscale == 0.0
//
// and
//
//     grayscale == 1.0.
//
// Otherwise, begin with
//
//     low  = 0
//     high = CHARS - 1
//
// and repeatedly find the midpoint.
//
// Important:
//
// In the previous binary search, we could eliminate
// the midpoint itself:
//
//     low = mid + 1
//
// or
//
//     high = mid - 1.
//
// We cannot do that here.
//
// The midpoint may eventually be one of the two
// values closest to grayscale.
//
// Instead, use:
//
//     low = mid
//
// or
//
//     high = mid.
//
// Continue until
//
//     high - low == 1.
//
//
//
// Here is one solution.

/*
char numeric_to_char(
    double const grayscale
) {
    assert(
        (grayscale >= 0.0)
     && (grayscale <= 1.0)
    );

    std::size_t const CHARS{ 92 };

    char const characters[CHARS + 1]{
        " `.-':_,^=;><+!rc*/z"
        "?sLTv)J7(|Fi{C}fI31t"
        "lu[neoZ5Yxjya]2ESwqk"
        "P6h9d4VpOGbUAKXHm8RD"
        "#$Bg0MNWQ%&@"
    };

    double const values[CHARS]{
        0,      0.0751, 0.0829, 0.0848, 0.1227,
        0.1403, 0.1559, 0.185,  0.2183, 0.2417,
        0.2571, 0.2852, 0.2902, 0.2919, 0.3099,
        0.3192, 0.3232, 0.3294, 0.3384, 0.3609,
        0.3619, 0.3667, 0.3737, 0.3747, 0.3838,
        0.3921, 0.396,  0.3984, 0.3993, 0.4075,
        0.4091, 0.4101, 0.42,   0.423,  0.4247,
        0.4274, 0.4293, 0.4328, 0.4382, 0.4385,
        0.442,  0.4473, 0.4477, 0.4503, 0.4562,
        0.458,  0.461,  0.4638, 0.4667, 0.4686,
        0.4693, 0.4703, 0.4833, 0.4881, 0.4944,
        0.4953, 0.4992, 0.5509, 0.5567, 0.5569,
        0.5591, 0.5602, 0.5602, 0.565,  0.5776,
        0.5777, 0.5818, 0.587,  0.5972, 0.5999,
        0.6043, 0.6049, 0.6093, 0.6099, 0.6465,
        0.6561, 0.6595, 0.6631, 0.6714, 0.6759,
        0.6809, 0.6816, 0.6925, 0.7039, 0.7086,
        0.7235, 0.7302, 0.7332, 0.7602, 0.7834,
        0.8037, 1.0
    };

    if ( grayscale == 0.0 ) {
        return characters[0];
    } else if ( grayscale == 1.0 ) {
        return characters[CHARS - 1];
    }

    std::size_t low{ 0 };
    std::size_t high{ CHARS - 1 };

    while ( (high - low) >= 2 ) {
        std::size_t const mid{
            low + (high - low)/2
        };

        if ( values[mid] < grayscale ) {
            low = mid;
        } else if ( values[mid] > grayscale ) {
            high = mid;
        } else {
            return characters[mid];
        }
    }

    assert( (high - low) == 1 );
    assert( values[low] <= grayscale );
    assert( grayscale <= values[high] );

    double const midpoint{
        (values[low] + values[high])/2.0
    };

    if ( grayscale < midpoint ) {
        return characters[low];
    } else {
        return characters[high];
    }
}
*/

































// What did we just make?
//
// The first line printed by main() is a grayscale
// ramp.
//
// It should begin with visually light characters
// and gradually become darker:
//
//     light                                  dark
//       |                                      |
//       v                                      v
//
//       ` . - ' : , _ ^ = ; > < + ... # B W @
//
// The exact appearance depends on the font used by
// your terminal.
//
//
// The second part creates a two-dimensional pattern.
//
// The grayscale value used at position (i, j) is
//
//     j*0.02 + i*0.01.
//
// Moving one position to the right increases the
// grayscale value by
//
//     0.01.
//
// Moving one row downward increases the grayscale
// value by
//
//     0.02.
//
// Thus, lines of equal grayscale run diagonally:
//
//     light
//
//       ........:::::::-------=======+++++++
//        .......:::::::-------=======++++++++
//          .....:::::::-------=======++++++++
//            ...:::::::-------=======++++++++
//              .:::::::-------=======++++++++
//               ::::::-------=======++++++++*
//                 ::::-------=======++++++++**
//                   ::-------=======++++++++**
//                     -------=======++++++++**
//                       -----=======++++++++**
//                         ---=======++++++++**
//                           -=======++++++++**
//                             =====++++++++***
//
//                                           dark
//
// The actual characters will be different because
// numeric_to_char(...) uses the measured brightness
// of 92 different ASCII characters.
//
//
//
// Why binary search?
//
// There are 92 possible characters.
//
// A linear search could examine their grayscale
// values one at a time:
//
//     0  1  2  3  4  5  ...              91
//     |->|->|->|->|->|-> ... ------------>|
//
// In the worst case, this requires examining almost
// every value.
//
// Binary search repeatedly cuts the possibilities
// approximately in half:
//
//     92
//     |
//     v
//     46
//     |
//     v
//     23
//     |
//     v
//     12
//     |
//     v
//      6
//     |
//     v
//      3
//     |
//     v
//      2
//
// Thus, only about six or seven steps are required.
//
// Since
//
//     2^6 = 64
//
// and
//
//     2^7 = 128,
//
// we know that 92 possibilities can be reduced to
// one or two possibilities in about seven halvings.
//
//
//
// Runtime analysis
//
// Suppose we had n characters rather than 92.
//
// A linear search would have worst-case runtime
//
//     O(n).
//
// Binary search has worst-case runtime
//
//     O(log(n)).
//
// Of course, with only 92 entries, either approach
// would be fast.
//
// The more important point is that this exercise
// demonstrates a situation in which binary search
// can be adapted to solve a slightly different
// problem.
//
// We are not asking:
//
//     "Where is this exact value?"
//
// Instead, we are asking:
//
//     "Between which two values does this value lie?"
//
// Once those two neighboring values have been found,
// we choose the closer one.
//
//
//
// A second approach
//
// There is another possible approach.
//
// Instead of searching values[], we could try to
// find a mathematical formula that directly
// estimates which character should be used.
//
// For example, the following polynomial was fitted
// to the data.
//
// This approach is only an approximation. It does
// not necessarily choose exactly the same character
// as the binary-search solution.
//
// It does, however, have an interesting runtime
// property.
//
// The number of arithmetic operations required to
// evaluate this particular polynomial does not
// depend on CHARS.
//
// Thus, with respect to the number of available
// characters, its runtime is
//
//     O(1).
//
// That does not automatically mean that it will run
// faster in practice.
//
// Big O describes how the amount of work grows as
// the size of the problem grows. It does not tell us
// exactly how long a particular computation will
// take on a particular computer.
//
// With only 92 characters, both approaches are very
// fast.
//
// The binary-search solution has another advantage:
// it uses the actual measured grayscale values.
//
// The polynomial solution only approximates them.

/*
#include <cmath>

char numeric_to_char(
    double const grayscale
) {
    assert(
        (grayscale >= 0.0)
     && (grayscale <= 1.0)
    );

    std::size_t const CHARS{ 92 };

    char const characters[CHARS + 1]{
        " `.-':_,^=;><+!rc*/z"
        "?sLTv)J7(|Fi{C}fI31t"
        "lu[neoZ5Yxjya]2ESwqk"
        "P6h9d4VpOGbUAKXHm8RD"
        "#$Bg0MNWQ%&@"
    };

    double const x{ grayscale };

    std::size_t const index{
        static_cast<std::size_t>(
            std::round(
                (((((5048.80*x - 22719.61)*x
                    + 38947.91)*x - 30292.82)*x
                    + 9087.85)*x*x*x - 18.87)*x*x
                    + 37.75*x
            )
        )
    };

    return characters[index];
}
*/