4
\$\begingroup\$

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 comparison 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 its 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 #includes are located above the code that uses them but I am not actually 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
\$\endgroup\$
0

2 Answers 2

Reset to default
2
\$\begingroup\$

I confess I was initially surprised to see the low-level heap functions rather than std::priority_queue<>. But this makes sense, as it avoids having to copy the elements into the queue's container. It's good that we mention this destructiveness in the name!

The logic is clear and precise. I might suggest turning around the test if … else return to test whether it can return:

        std::pop_heap(first, last--, comp);
        if (first == last) {
            // single element - return it
            return *first;
        }

We can also provide extra clarity that we don't modify x and y by declaring them auto const:

        auto const y = *last;
        std::pop_heap(first, last--, comp);
        auto const x = *last;
        if (comp(x, y)) {
            *last = y - x;
            std::push_heap(first, ++last, comp);
        }

We don't need separate overloads for defaulting the comparator - just provide a default argument:

#include <algorithm>
#include <functional>

template<class Iterator, class Compare>
typename Iterator::value_type stone_smash_destructive(Iterator first, Iterator last,
                                                      Compare comp = std::less<>{})

template<class Iterator, class Compare>
typename Iterator::value_type stone_smash(Iterator first, Iterator last,
                                          Compare comp = std::less<>{})

I don't like make_vector's use of explicit constructor { } - we normally use ( ) for non-initialiser-list construction:

template<class Iterator>
auto make_vector(Iterator first, Iterator last)
{
    return std::vector<typename Iterator::value_type>(first, last);
}

With current standard library's deduction guides, we can omit the template argument:

template<class Iterator>
auto make_vector(Iterator first, Iterator last)
{
    return std::vector(first, last);
}

At this point, it doesn't merit being a function - it's clearer just inlined where we need it.

The constructor of binary_condition_counter accepts a forwarding reference, but then copies into condition where it should std::forward<>():

    binary_condition_counter(std::size_t& count, BinaryCondition&& condition)
        : count(count),
          condition(std::forward<BinaryCondition>(condition))
    {}

However, we don't need to write this constructor, as it's exactly the same as the aggregate initialiser.

We might as well make condition const, since the class is already unassignable due to the reference member count.

We declare our result_type but then return bool from operator(). I would return auto or result_type, even if we expect the wrapped comparator to return bool.

make_binary_condition_counter() also accepts a forwarding reference, but this time chooses std::move() instead of std::forward<>(). I would simply remove this function, as type deduction works perfectly fine for the constructor.

One alternative to separate "destructive" and "copying" functions that I've used successfully in the past is to accept the collection by value. Then a caller can use std::move() to avoid copying elements when they do not need to be preserved.

That might look like this:

#include <algorithm>
#include <concepts>
#include <functional>
#include <ranges>

template<std::ranges::bidirectional_range Container,
         std::predicate<std::ranges::range_value_t<Container>, std::ranges::range_value_t<Container>> Compare>
auto stone_smash(Container values, Compare comp = std::less<>{})
{
    auto const first = values.begin();
    auto last = values.end();
    ⋮ 
    return std::ranges::range_value_t<Container>{};
}

And we'd call it slightly differently:

    assert(expected == stone_smash(v, comp));
    assert(expected == stone_smash(std::move(v), comp));

Or we can call it destructively from an iterator pair by constructing a std::range::subrange from them.

Modified code

Corrected and simplified:

#include <algorithm>
#include <concepts>
#include <functional>
#include <ranges>

template<std::ranges::bidirectional_range Container,
         std::predicate<std::ranges::range_value_t<Container>, std::ranges::range_value_t<Container>> Compare>
auto stone_smash(Container values, Compare comp = std::less<>{})
{
    auto const first = values.begin();
    auto last = values.end();

    std::make_heap(first, last, comp);
    while (first < last)
    {
        std::pop_heap(first, last--, comp);
        if (first == last) {
            return *first;
        }

        auto const y = *last;
        std::pop_heap(first, last--, comp);
        auto const x = *last;
        if (comp(x, y)) {
            *last = y - x;
            std::push_heap(first, ++last, comp);
        }
    }
    return std::ranges::range_value_t<Container>{};
}

#include <cstddef>

template<class BinaryCondition>
struct binary_condition_counter
{
    std::size_t& count;
    BinaryCondition const condition;

    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;

    auto operator()(first_argument_type a, second_argument_type b) const
    {
        ++count;
        return condition(a, b);
    }
};
\$\endgroup\$
1
\$\begingroup\$ 
    while (first < last)
    {
        std::pop_heap(first, last--, comp);
        auto y = *last;
        if (first < last) {
  • If you know the distance from first to last is at least \$2\$, you don't need the inner check. For range distances of \$2\$ or greater, you always pop twice and maybe push. When the distance is less than \$2\$, either the final stone exists at first (first < last) or is \$0\$ (first == last).
                *last = y - x;
  • y - x works fine if the comparator is std::less<>. What happens when the comparator switches to std::greater<>? The ordering changes. y would be the smaller value, so y-x would produce a negative value for signed numeric types and underflow for unsigned numeric types. If you want to support comparators, you should provide a difference function to ensure the ordering is applied correctly.
    template<class Iterator>
    typename Iterator::value_type stone_smash_destructive(Iterator first, Iterator last)
    {
        std::make_heap(first, last);
        while (last - first > 1)
        {
            std::pop_heap(first, last--);
            auto first_popped = *last;
            std::pop_heap(first, last--);
            auto second_popped = *last;
            if (second_popped < first_popped)
            {
                *last = first_popped - second_popped;
                std::push_heap(first, ++last);
            }
        }

        if (first == last) {
            return {0};
        }
        return *first;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.