#include <cstddef>
#include <cstdint>
#include <iostream>

// One use of a hash function is to detect whether
// a string has changed.
//
// If two strings are different, we would like there
// to be a small probability that they have the same
// hash value. If they do have the same hash value,
// we say that a collision has occurred.
//
// In the previous exercise, we simply added the
// numerical values of the characters.
//
// One problem with this approach is that transposing
// two characters does not change the hash value.
//
// For example,
//
//     "earth"
//
// and
//
//     "heart"
//
// contain exactly the same characters and therefore
// have the same hash value using our previous hash
// function.
//
// Another problem occurs if one letter is changed
// from lower case to upper case while another is
// changed from upper case to lower case. The changes
// in the character values may cancel each other.
//
// More generally, several changes to a string may
// result in the same sum.
//
// Our goal is to create a hash function that is still
// fast to calculate, but where changes such as those
// described above will usually change the hash value.
//
// Consider each character to be the coefficient of
// a term in a polynomial. For example, for "Hi!",
// we have
//
//         2
//     72 x  + 105 x + 33
//    'H'      'i'    '!'
//
// and for "ECE 150", we have
//
//       6      5      4      3      2
//    69x  + 67x  + 69x  + 32x  + 49x  + 53x + 48
//   'E'    'C'    'E'    ' '    '1'    '5'   '0'
//
// We can evaluate this polynomial at a prime number,
// such as 43, and use the resulting 32-bit unsigned
// integer as our hash value.
//
// Because only 32 bits are retained, sufficiently
// large calculations will wrap around. This is
// well-defined for unsigned integers and effectively
// means that the calculation is performed modulo
// 2^32.
//
// Hint: This is actually quite easy...

// Function declarations
std::uint32_t hash( char const *str );
int main();

// Function definitions
int main() {
    char const *str1a{ "earth" };
    char const *str1b{ "heart" };

    std::cout << hash( str1a ) << std::endl;
    std::cout << hash( str1b ) << std::endl;

    std::cout << std::endl;

    char const *str2a{ "Hi there!" };
    char const *str2b{ "Hi three!" };

    std::cout << hash( str2a ) << std::endl;
    std::cout << hash( str2b ) << std::endl;

    std::cout << std::endl;

    char const *str3a{ "We must contain the adversary." };
    char const *str3b{ "We must contact the adversary." };

    std::cout << hash( str3a ) << std::endl;
    std::cout << hash( str3b ) << std::endl;

    std::cout << std::endl;

    char const *str4a{ "...Where are you?" };
    char const *str4b{ "...where are You?" };

    std::cout << hash( str4a ) << std::endl;
    std::cout << hash( str4b ) << std::endl;

    return 0;
}

std::uint32_t hash( char const *str ) {
    std::uint32_t value{ 0 };

    // Enter your implementation here.

    return value;
}




































// Hint:
//
// For "Hi!", we want to evaluate
//
//         2
//     72 x  + 105 x + 33
//    'H'      'i'    '!'
//
// at x = 43.
//
// Start with 0:
//
//     0
//
// Add 'H':
//
//     72
//
// Multiply by 43:
//
//     72*43
//
// Add 'i':
//
//     72*43 + 105
//
// Multiply by 43:
//
//     (72*43 + 105)*43
//
// Add '!':
//
//     (72*43 + 105)*43 + 33
//
// This is exactly
//
//          2
//     72*43 + 105*43 + 33.
//
// Notice that we never actually have to calculate
// any powers of 43.
































// For "ECE 150", we want to evaluate
//
//       6      5      4      3      2
//    69x  + 67x  + 69x  + 32x  + 49x  + 53x + 48
//   'E'    'C'    'E'    ' '    '1'    '5'   '0'
//
// at x = 43.
//
// Start with 0:
//
//     0
//
// Add 'E':
//
//     69
//
// Multiply by 43:
//
//     69*43
//
// Add 'C':
//
//     69*43 + 67
//
// Multiply by 43:
//
//     (69*43 + 67)*43
//
// Add 'E':
//
//     (69*43 + 67)*43 + 69
//
// Multiply by 43:
//
//     ((69*43 + 67)*43 + 69)*43
//
// Add ' ':
//
//     ((69*43 + 67)*43 + 69)*43 + 32
//
// Continue this process for the remaining characters.
//
// We eventually obtain
//
//     (((((69*43 + 67)*43 + 69)*43 + 32)*43
//         + 49)*43 + 53)*43 + 48
//
// If this expression is expanded, it becomes
//
//          6         5         4         3
//     69*43  + 67*43  + 69*43  + 32*43
//
//          2
//     + 49*43  + 53*43 + 48,
//
// which is exactly the polynomial we wanted to
// evaluate.
































// Here is one solution:

/*
std::uint32_t hash( char const *str ) {
    std::uint32_t value{ 0 };

    // Keep going through the string until we reach
    // the null character '\0'.
    for ( std::size_t k{ 0 }; str[k] != '\0'; ++k ) {
        value = 43*value
                + static_cast<unsigned char>( str[k] );
    }

    return value;
}
*/