Fast way to compute the area covered by parallel lines that can overlap

Question

City is represented by matrix M x N, where rows are enumerated from 1 to N, and columns are enumerated from 1 to M.

Tramways always go straight along the row. Starting point of tramway is (r, c1) and ending point is (r, c2), where r is the number of row, c1 - starting column and c2 - ending column.

We need to determine the number of cells, not occupied by tramways. Attention: tramways can overlap within one row.

Input format: first line contains 3 integer values: N - number of rows, M -number of columns, K - number of tramways. Each next line i from total K lines contains 3 integer values: r, c1, c2.

Output format: integer value that represents the number of cells, not occupied by tramways.

Limitations:

1 <= N, M <= 10^9

0 <= K <= 1000

1 <= r <= N

1 <= c1, c2 <= M

Language: C or C++

Solution:

#include <fstream> template <class T> struct Node { T value; Node *left; // less Node *right; // more bool flag; Node(T value) : value(value), left(0), right(0), flag(false) { } virtual ~Node() { } }; template <class T> class BST { protected: Node<T> *root; virtual Node<T>* constructHelper(T value) { return new Node<T>(value); } Node<T>* getHelper(Node<T> **p, T value) { Node<T> *node, *root, *arr[3]; root = *p; if (root->value > value) { if (!root->left) { node = root->left = constructHelper(value); if (!root->right) root->flag = true; } else { node = getHelper(&root->left, value); if (root->flag) { if (root->left->left) { arr[2] = root->left->left; root->left->left = 0; arr[1] = root->left; root->left->flag = false; root->left = 0; arr[0] = root; root->flag = false; root = arr[1]; root->left = arr[2]; root->right = arr[0]; *p = root; } else if (root->left->right) { arr[2] = root->left->right; root->left->right = 0; arr[1] = root->left; root->left->flag = false; root->left = 0; arr[0] = root; root->flag = false; root = arr[2]; root->left = arr[1]; root->right = arr[0]; *p = root; } } } } else if (root->value < value) { if (!root->right) { node = root->right = constructHelper(value); if (!root->left) root->flag = true; } else { node = getHelper(&root->right, value); if (root->flag) { if (root->right->right) { arr[2] = root->right->right; root->right->right = 0; arr[1] = root->right; root->right->flag = false; root->right = 0; arr[0] = root; root->flag = false; root = arr[1]; root->left = arr[0]; root->right = arr[2]; *p = root; } else if (root->right->left) { arr[2] = root->right->left; root->right->left = 0; arr[1] = root->right; root->right->flag = false; root->right = 0; arr[0] = root; root->flag = false; root = arr[2]; root->left = arr[0]; root->right = arr[1]; *p = root; } } } } else node = root; return node; } void removeHelper(Node<T> *root) { if (root->left) removeHelper(root->left); if (root->right) removeHelper(root->right); delete root; } public: Node<T>* getNode(T value) { Node<T> *node; if (!root) { root = constructHelper(value); node = root; } else { node = getHelper(&root, value); } return node; } BST() : root(0) { } ~BST() { if (root) removeHelper(root); } }; //...................................................................................................................... template <class T, unsigned long long columns_width> class ColumnBST; template <class T, unsigned long long raws_width, unsigned long long columns_width> struct RawNode : public Node<T> { ColumnBST<T, columns_width> *raws[raws_width]; RawNode(T value) : Node(value) { for (T i = 0; i < raws_width; ++i) raws[i] = 0; } virtual ~RawNode() { for (T i = 0; i < raws_width; ++i) if (raws[i]) delete raws[i]; } }; template <class T, unsigned long long raws_width, unsigned long long columns_width> class RawBST : public BST<T> { virtual Node<T>* constructHelper(T value) { return new RawNode<T, raws_width, columns_width>(value); } public: ColumnBST<T, columns_width>* getRaw(T r) { T x, y; RawNode<T, raws_width, columns_width> *node; --r; x = r / raws_width; y = r % raws_width; node = (RawNode<T, raws_width, columns_width>*)getNode(x); if (!node->raws[y]) node->raws[y] = new ColumnBST<T, columns_width>(); return node->raws[y]; } }; //...................................................................................................................... template <class T, unsigned long long columns_width> class RailList; template <class T, unsigned long long columns_width> struct ColumnNode : public Node<T> { RailList<T, columns_width> *rails; ColumnNode(T value) : Node(value), rails(0) { } virtual ~ColumnNode() { if (rails) delete rails; } }; template <class T, unsigned long long columns_width> class ColumnBST : public BST<T> { virtual Node<T>* constructHelper(T value) { return new ColumnNode<T, columns_width>(value); } public: T addRail(T c1, T c2) { T a, b, value; ColumnNode<T, columns_width> *node; --c1; --c2; a = c1 / columns_width; b = c2 / columns_width; if (a == b) { node = (ColumnNode<T, columns_width>*)getNode(a); if (!node->rails) node->rails = new RailList<T, columns_width>(); value = node->rails->addRail(c1 % columns_width, c2 % columns_width); } else { node = (ColumnNode<T, columns_width>*)getNode(a); if (!node->rails) node->rails = new RailList<T, columns_width>(); value = node->rails->addRail(c1 % columns_width, columns_width - 1); ++a; while (a < b) { node = (ColumnNode<T, columns_width>*)getNode(a); if (!node->rails) node->rails = new RailList<T, columns_width>(); value += node->rails->addRail(0, columns_width - 1); ++a; } node = (ColumnNode<T, columns_width>*)getNode(a); if (!node->rails) node->rails = new RailList<T, columns_width>(); value += node->rails->addRail(0, c2 % columns_width); } return value; } }; //...................................................................................................................... template <class T> struct RailNode { RailNode *next; T c1, c2; RailNode(T c1, T c2) : next(0), c1(c1), c2(c2) { } }; template <class T, unsigned long long columns_width> class RailList { RailNode<T> *rail; T total, min, max; T addRailHelper2(RailNode<T> *rail, T c1, T c2) { T value; if (!rail->next) { rail->next = new RailNode<T>(c1, c2); value = (c2 - c1) + 1; } else { value = addRailHelper(rail->next, c1, c2); } return value; } T addRailHelper(RailNode<T> *rail, T c1, T c2) { T value; if ((c1 > rail->c2) || (c2 < rail->c1)) { value = addRailHelper2(rail, c1, c2); } else if ((c1 < rail->c1) || (c2 > rail->c2)) { value = 0; if (c1 < rail->c1) { value += addRailHelper2(rail, c1, rail->c1 - 1); } if (c2 > rail->c2) { value += addRailHelper2(rail, rail->c2 + 1, c2); } } else value = 0; return value; } void removeRailHelper(RailNode<T> *rail) { RailNode<T> *node; while (rail) { node = rail->next; delete rail; rail = node; } } public: RailList() : rail(0), total(0), min(0), max(0) { } ~RailList() { if (rail) removeRailHelper(rail); } T addRail(T c1, T c2) { T value; RailNode<T> *next, *node; if (!rail) { rail = new RailNode<T>(c1, c2); value = (c2 - c1) + 1; min = c1; max = c2; total = value; } else { if (total != columns_width) { if ((c1 > max) || (c2 < min)) { node = new RailNode<T>(c1, c2); next = rail->next; rail->next = node; node->next = next; value = (c2 - c1) + 1; } else { value = addRailHelper(rail, c1, c2); } if (c1 < min) min = c1; if (c2 > max) max = c2; total += value; } else value = 0; } return value; } }; //...................................................................................................................... template <class T, unsigned long long raws_width, unsigned long long columns_width> class City { T n, m, k, i, count; RawBST<T, raws_width, columns_width> *raws; public: City(T n, T m, T k) : i(0), count(0), raws(0) { if (((n >= 1) && (n <= 1000000000)) && ((m >= 1) && (m <= 1000000000)) && (k <= 1000)) { this->n = n; this->m = m; this->k = k; } else throw std::out_of_range(""); } ~City() { if (raws) delete raws; } T getResult() { return ((n * m) - count); } void addRail(T r, T c1, T c2) { ColumnBST<T, columns_width> *raw; if (((i < k) && (r >= 1) && (r <= n)) && ((c1 >= 1) && (c1 <= m)) && ((c2 >= 1) && (c2 <= m) && (c2 >= c1))) { if (!raws) raws = new RawBST<T, raws_width, columns_width>(); raw = raws->getRaw(r); count += raw->addRail(c1, c2); ++i; } else throw std::out_of_range(""); } }; //...................................................................................................................... int main(int argc, char* argv[]) { std::fstream input_file("input.txt", std::ios_base::in); unsigned long long n, m, k; input_file >> n; input_file >> m; input_file >> k; City<unsigned long long, 32, 10000000> *city = new City<unsigned long long, 32, 10000000>(n, m, k); unsigned long long r, c1, c2; for (unsigned long long i = 0; i < k; ++i) { input_file >> r; input_file >> c1; input_file >> c2; city->addRail(r, c1, c2); } unsigned long long result = city->getResult(); delete city; std::fstream output_file("output.txt", std::ios_base::out); output_file << result; return 0; }

And it was rejected by employer (Intern C++ developer position). Can you help to figure out whether it is terrible or not? I was never interested in algorithms and I fell like I am C coder that throws all abstractions away. Thank you.

I have only one suggestion: Meaningful variable names. Your code should be self documenting. i = 0; i < k; ++i){ input_file >> r; input_file >> c1; input_file >> c2; city->addRail(r, c1, c2); is not meaningful. It's jibberish for someone else who has to work on it. YANA, you are not alone. Posted as a comment because I think code review could do it's work better if the code was more readable. — Tschallacka
– Tschallacka, Commented Apr 13, 2018 at 16:03
You implemented your own BST instead of using facilities in the standard library, you created classes where none are necessary, and you turned in 500+ lines of code where 50 or 25 would have sufficed. My recommendation is that, before you start to code, you think about the problem and what it really requires. Also, don't use new. — Cris Luengo
– Cris Luengo, Commented Apr 19, 2018 at 15:26

Toby Speight · Accepted Answer · 2018-04-19 15:01:46Z

This looks like a very complicated and memory-hungry solution. With all that complexity, I'd expect to see quite a few unit tests in the review, but there are none.

I'd expect to see a solution that reads in all the inputs, grouping them by row number (e.g. in a std::multimap), and then iterates over the rows, combining overlapping rails to obtain the total for that row.

There are a number of errors reported when I compile with a recent standard:

Node as a base-class name needs to be Node<T> (in the initializers of RawNode and RawBST)
declarations in dependent base BST<long long unsigned int> are not found by unqualified lookup, so we need to write this->getNode(a) instead of just getNode(a) in a bunch of places.

Even with the errors fixed, there's almost a hundred lines of warnings, when I compile with g++ -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++. I recommend acting on them.

Stack Exchange Network

Fast way to compute the area covered by parallel lines that can overlap

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Fast way to compute the area covered by parallel lines that can overlap

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions