Based on this question:

Heaviest Stone algorithm time complexity

Problem:

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

I implemented an `O(n * log(n))`

solution using `std::*_heap`

functions in C++.

Since those functions have an optional generic argument – the comparision function – I decided to implement my functions with that generic argument as well.

```
#include <algorithm>
template<class Iterator, class Compare>
typename Iterator::value_type stone_smash_destructive(Iterator first, Iterator last, Compare comp)
{
std::make_heap(first, last, comp);
while (first < last)
{
std::pop_heap(first, last--, comp);
auto y = *last;
if (first < last) {
std::pop_heap(first, last--, comp);
auto x = *last;
if (comp(x, y)) {
*last = y - x;
std::push_heap(first, ++last, comp);
}
} else {
return y;
}
}
return {0};
}
#include <functional>
template<class Iterator>
typename Iterator::value_type stone_smash_destructive(Iterator first, Iterator last)
{
return stone_smash_destructive(first, last, std::less<typename Iterator::value_type>());
}
#include <vector>
template<class Iterator>
std::vector<typename Iterator::value_type> make_vector(Iterator first, Iterator last)
{
return {first, last};
}
template<class Iterator, class Compare>
typename Iterator::value_type stone_smash(Iterator first, Iterator last, Compare comp)
{
auto v = make_vector(first, last);
return stone_smash_destructive(v.begin(), v.end(), comp);
}
template<class Iterator>
typename Iterator::value_type stone_smash(Iterator first, Iterator last)
{
auto v = make_vector(first, last);
return stone_smash_destructive(v.begin(), v.end());
}
```

To take use of it I implemented a comparator that counts number of it’s invocations.

```
#include <cstddef>
template<class BinaryCondition>
struct binary_condition_counter
{
std::size_t & count;
BinaryCondition condition;
public:
using result_type = typename BinaryCondition::result_type;
using first_argument_type = typename BinaryCondition::first_argument_type;
using second_argument_type = typename BinaryCondition::second_argument_type;
binary_condition_counter(std::size_t & count, BinaryCondition && condition): count(count), condition(condition) {}
bool operator () (first_argument_type a, second_argument_type b) const
{
++count;
return condition(a, b);
}
};
#include <utility>
template<class BinaryCondition>
binary_condition_counter<BinaryCondition> make_binary_condition_counter(std::size_t & count, BinaryCondition && condition)
{
return {count, std::move(condition)};
}
```

The code of the tests may be a bit messy and they just spit out the numbers of comparisions to the `std::cout`

but I am not much concerned about that.

```
#include <cassert>
#include <iostream>
void test_stone_smash(std::size_t expected, std::vector<std::size_t> v)
{
std::size_t count = 0;
auto comp = make_binary_condition_counter(count, std::less<std::size_t>());
assert(expected == stone_smash(v.begin(), v.end(), comp));
assert(expected == stone_smash(v.cbegin(), v.cend(), comp));
assert(expected == stone_smash_destructive(v.begin(), v.end(), comp));
std::cout << "{";
if (v.size())
{
auto limit = v.end() - 1;
for (auto i = v.begin(); i < limit; ++i)
{
std::cout << *i << ", ";
}
std::cout << *limit;
}
std::cout << "}(" << v.size() << "): " << count / 3 << " comparisions.n";
}
void test_stone_smashes_logarithmic(std::size_t exp, std::size_t base = 2)
{
assert(exp < 23);
std::size_t count;
auto comp = make_binary_condition_counter(count, std::less<std::size_t>());
std::size_t limit = ipow(base, exp) + 1;
std::vector<std::size_t> v;
v.reserve(limit);
std::size_t mod = base;
for (std::size_t i = 1; i <= limit; ++i)
{
v.push_back(i);
if (i % mod == 0 || (mod > base && (i - 1) % (mod / base) == 0))
{
count = 0;
auto result = stone_smash(v.begin(), v.end(), comp);
std::cout << "(1, " << i << ") = " << result << ": " << count << " comparisions.n";
assert(((i - 1) % 4 < 2 ? 1 : 0) == result);
if (i % mod == 0)
{
mod *= base;
}
}
}
}
void test_stone_smashes_linear(std::size_t n, std::size_t step = 1, std::size_t start = 1)
{
std::size_t count;
auto comp = make_binary_condition_counter(count, std::less<std::size_t>());
std::vector<std::size_t> v;
v.reserve(n);
for (std::size_t i = 0; i < n; ++i)
{
auto val = start + i * step;
v.push_back(val);
count = 0;
auto result = stone_smash(v.begin(), v.end(), comp);
std::cout << "(" << start << ", " << val << ")(n=" << i + 1 << ",step="<< step << ") = " << result << ": " << count << " comparisions.n";
if (step == 1 && start == 1)
{
assert(((val - 1) % 4 < 2 ? 1 : 0) == result);
}
}
}
int main()
{
test_stone_smash({0}, {});
test_stone_smash({0}, {0});
test_stone_smash({2}, {0, 1, 2, 5});
test_stone_smash({1}, {1});
test_stone_smash({0}, {5, 5});
test_stone_smash({1}, {1, 2});
test_stone_smash({1}, {2, 1});
test_stone_smash({0}, {3, 1, 2});
test_stone_smash({1}, {1, 2, 3, 4, 5});
test_stone_smash({0}, {1, 1, 2, 3, 5, 8, 13, 21});
test_stone_smash({4}, {1, 3, 8});
test_stone_smashes_logarithmic(20);
test_stone_smashes_linear(2000);
test_stone_smashes_linear(100, 3);
return 0;
}
```

I am more concerned about standard algorithm and templates usage.

For example, is there a standard alternative to my make_vector function with type deduction?

Also I know I should use some testing framework, but I am not concerned about that as well. Actually with asserts it should be just copy-paste from this post without need to install additional libs.

The `ipow(base, exponent)`

(used in tests) is just an exponentiation `base^exponent`

, I am not including it here.

The `#include`

s are located above the code that uses them but I am not actualy showing the file system structure. Module separation is also no concern here.

But of course, feel free to comment on anything you want ðŸ™‚

The tests output:

```
{}(0): 0 comparisions.
{0}(1): 0 comparisions.
{2, 2, 3, 5}(4): 12 comparisions.
{1}(1): 0 comparisions.
{5, 5}(2): 2 comparisions.
{1, 2}(2): 2 comparisions.
{1, 2}(2): 2 comparisions.
{1, 1, 3}(3): 6 comparisions.
{1, 1, 1, 3, 5}(5): 19 comparisions.
{1, 1, 2, 2, 5, 8, 8, 21}(8): 36 comparisions.
{4, 5, 8}(3): 6 comparisions.
(1, 2) = 1: 2 comparisions.
(1, 3) = 0: 6 comparisions.
(1, 4) = 0: 12 comparisions.
(1, 5) = 1: 19 comparisions.
(1, 8) = 0: 42 comparisions.
(1, 9) = 1: 47 comparisions.
(1, 16) = 0: 108 comparisions.
(1, 17) = 1: 115 comparisions.
(1, 32) = 0: 263 comparisions.
(1, 33) = 1: 270 comparisions.
(1, 64) = 0: 629 comparisions.
(1, 65) = 1: 638 comparisions.
(1, 128) = 0: 1450 comparisions.
(1, 129) = 1: 1465 comparisions.
(1, 256) = 0: 3296 comparisions.
(1, 257) = 1: 3303 comparisions.
(1, 512) = 0: 7350 comparisions.
(1, 513) = 1: 7365 comparisions.
(1, 1024) = 0: 16250 comparisions.
(1, 1025) = 1: 16278 comparisions.
(1, 2048) = 0: 35607 comparisions.
(1, 2049) = 1: 35571 comparisions.
(1, 4096) = 0: 77263 comparisions.
(1, 4097) = 1: 77261 comparisions.
(1, 8192) = 0: 166782 comparisions.
(1, 8193) = 1: 166815 comparisions.
(1, 16384) = 0: 358181 comparisions.
(1, 16385) = 1: 358585 comparisions.
(1, 32768) = 0: 766300 comparisions.
(1, 32769) = 1: 765531 comparisions.
(1, 65536) = 0: 1629347 comparisions.
(1, 65537) = 1: 1629708 comparisions.
(1, 131072) = 0: 3455996 comparisions.
(1, 131073) = 1: 3455976 comparisions.
(1, 262144) = 0: 7305131 comparisions.
(1, 262145) = 1: 7307617 comparisions.
(1, 524288) = 0: 15401610 comparisions.
(1, 524289) = 1: 15413884 comparisions.
(1, 1048576) = 0: 32400609 comparisions.
(1, 1048577) = 1: 32380097 comparisions.
...
```

To compile: `g++ -Wall -std=c++17 stone_smash_test.cpp -o stone_smash_test`

```
$ g++ --version
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```