jeremy.william.murphy
BAN USERC++11. I couldn't think of a better name for the sorting semantics.
/*
Given a list of integers, find the highest value obtainable by concatenating
these together.
For example, given 9, 918, 917 - The answer is 9918917.
But given 1,112,113 - The answer is 1131121
Written in C++11.
*/
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
// a < ab < ac < bb < b < cb < c < cd
template <typename Container>
struct pseudo_lexicographical_less
{
bool operator()(Container a, Container b) const
{
bool swapped = false;
if (b.size() < a.size())
{
swap(a, b);
swapped = true;
}
// a.size() <= b.size()
auto const p = mismatch(begin(a), end(a), begin(b));
if (p.first == end(a))
{
if (a.size() == b.size())
return false; // swap is irrelevant
else
{
auto const x = *(begin(b) + a.size() - 1);
auto const f = [&](char z) {
return z == x;
};
auto const q = find_if_not(begin(b) + a.size(), end(b), f);
return q == end(b) ? swapped : (*q < x) == swapped;
}
}
else
return (*p.first < *p.second) != swapped;
}
};
template <typename Container>
struct pseudo_lexicographical_greater
{
bool operator()(Container a, Container b) const
{
return pseudo_lexicographical_less<Container>()(b, a);
}
};
int main(int argc, char **argv)
{
if (argc < 2)
exit(EXIT_FAILURE);
vector<string> data(argv + 1, argv + argc);
sort(begin(data), end(data), pseudo_lexicographical_greater<string>());
for (auto i : data)
cout << i << " ";
cout << endl;
}
I found the edge cases in this problem really kept me on my toes. I'm not 100% happy with my solution -- it's more geared towards simplicity than efficiency (believe it or not), but I'm happy enough to share it with the world. It treats matchboxes as integers and prints out the value of the matchboxes chosen, not their index.
I assume the time complexity is O(C(n, k) ⋅ n).
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>
using namespace std;
template <typename I0, typename I1, typename T = typename iterator_traits<I0>::value_type>
T count_matches(I0 f_matchbox, I0 l_matchbox, I1 f_combination)
{
// Not the most efficient method but straight-forward.
return inner_product(f_matchbox, l_matchbox, f_combination, 0); // O(n)
}
// Select K matchboxes such that M % F == 0 and minimize(M)
// Requires random access iterators to non-const matchbox range.
template <typename I, typename O>
O minimize_M_multiple_F(I first, I last, O result, size_t F, size_t K)
{
assert(F != 0);
assert(K < last - first && K != 0);
using matchbox_t = typename iterator_traits<I>::value_type;
sort(first, last, greater<matchbox_t>()); // O(n lg n) time.
auto const n = last - first;
vector<bool> combination; // O(n) bits space.
combination.resize(n);
fill(combination.rbegin(), combination.rbegin() + K, true);
bool searching = true;
size_t M = count_matches(first, last, begin(combination));
while (M == 0 && searching) // Get past the zero edge case.
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
size_t target = F;
while (searching && M % F)
{
target = M - M % F + F; // Simplifies inner loop condition.
do
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
while (searching && M < target);
}
if (M % F == 0)
{
for (size_t i = n; i > 0; i--)
if (combination[i-1])
*result++ = first[i-1];
}
return result;
}
int main(int argc, char **argv)
{
if (argc < 3)
exit(EXIT_FAILURE);
using matchbox_t = int;
vector<matchbox_t> matchboxes = {0, 0, 1, 2, 2, 7, 12};
vector<matchbox_t> answer;
auto const F = strtoul(argv[1], nullptr, 10);
auto const K = strtoul(argv[2], nullptr, 10);
answer.reserve(K);
minimize_M_multiple_F(begin(matchboxes), end(matchboxes), back_inserter(answer), F, K);
for (auto matchbox : answer)
cout << matchbox << " ";
cout << endl;
}
memoreku makes a great observation that the set for a basic character string can just be an array of bool that fits in a 32-bit integer (or 64-bit if you want mixed case). I decided to stick with the more conservative standard library data structure, mostly for expository purposes.
This algorithm solves the problem in amortized worst-case O(n lg n) by sorting the list of words in decreasing order of size first. This allows you to test the best possible answers in decreasing order by traversing the words appropriately.
It is also worth noting that you only need to store the set of one word at a time and only calculate the set of each word once.
There are trade-offs to be made depending on the average word length M.
- jeremy.william.murphy December 16, 2015