Skip to content

Instantly share code, notes, and snippets.

@mosmeh

mosmeh/partial_digest_problem.cpp

Created April 15, 2020 23:35
Show Gist options
  • Save mosmeh/369cd1a9b8e8d9cfacd83451da9a8364 to your computer and use it in GitHub Desktop.
Save mosmeh/369cd1a9b8e8d9cfacd83451da9a8364 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
partial_digest_problem.cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> dd(int y, const vector<int>& x) {
vector<int> ret;
for (int a : x) {
ret.push_back(abs(a - y));
}
return ret;
}
vector<int> difference(vector<int> a, const vector<int>& b) {
for (int x : b) {
const auto it = find(a.begin(), a.end(), x);
if (it != a.end()) {
a.erase(it);
}
}
return a;
}
bool in(const vector<int>& a, const vector<int>& b) {
for (int x : a) {
if (find(b.begin(), b.end(), x) == b.end()) {
return false;
}
}
return true;
}
void print(vector<int> x) {
sort(x.begin(), x.end());
for (int a : x) {
cout << a << " ";
}
cout << "\n";
}
void place(int width, const vector<int>& l, vector<int>& x) {
const int m = *max_element(l.begin(), l.end());
for (int y : { m, width - m }) {
const auto dyx = dd(y, x);
if (in(dyx, l)) {
const auto nl = difference(l, dyx);
x.push_back(y);
if (nl.empty()) {
print(x);
} else {
place(width, nl, x);
}
x.pop_back();
}
}
}
void pdp(vector<int>& l) {
const auto w = max_element(l.begin(), l.end());
const int width = *w;
l.erase(w);
vector<int> x = { 0, width };
place(width, l, x);
}
int main() {
vector<int> x = { 0, 1, 2, 5, 7, 9, 12 };
vector<int> l;
for (int i = 0; i < x.size(); ++i) {
for (int j = 0; j < i; ++j) {
l.push_back(abs(x[i] - x[j]));
}
}
cout << "X = ";
print(x);
cout << "L = ";
print(l);
cout << "X^ = \n";
pdp(l);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment