Cows with walkie-talkies (USACO Silver Prob. #3; December '16 )

Question

The official problem description is here, which in my opinion is unclear and quite long. Below is my description. I recommend you still read the official description, it has details such as input and output format

---

Input: N cows

• represented as points on a 2D graph (integer x, y pairs)
• each with an integer walkie-talkie power P, the maximum distance that cow can transmit

Output/Problem: What's the maximum number of cows a broadcast from any single cow can reach?

• Cows can relay messages to and from each other, like in a digital network

• Cow A might be able to transmit to Cow B even if Cow B cannot transmit back, due to Cow A's power being larger than that of Cow B.

• The output number should include the originating cow.

Context

I did this for problem for practice. You have three hours to take the actual contest and graded on the number of test cases your program can pass within the time limit. There are three problems total. This solution passes all 10.

Issues

• Verbosity
• Readability
• Performance
• Code-writing Efficiency, e.g. repetition

Faster algorithms exist, but implementing complex algorithms takes more time. The less time spent implementing, the more time I have to work on the other problems.

Regarding using namespace std; - single file programs don't have the namespace conflict problems more complex ones do.

---

#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <fstream>
#include <set>
#include <sstream>
#include <stack>

using namespace std;


void split(const string &s, vector<int> &elems) {
    stringstream ss;
    ss.str(s);
    string item;
    while (getline(ss, item, ' ')) {
        elems.push_back(stoi(item));
    }
}

vector<int> split(const string &s) {
    vector<int> elems;
    split(s, elems);
    return elems;
}

tuple<int, int, int> inline split_tuple(ifstream &stream) {
    string str;
    getline(stream, str);
    istringstream iss(str);
    vector<int> tokens = split(str);
    return tuple<int, int, int>{tokens[0], tokens[1], tokens[2]};
}

int inline distance(const tuple<int, int, int> a, const tuple<int, int, int> b) {
    // without the sqrt(), to make it faster
    // --- note: To me, an extra typecast to int is no more readable, and just adds extra fluff.
    return pow(get<0>(a) - get<0>(b), 2) + pow(get<1>(a) - get<1>(b), 2);
}


int main() {
    ifstream input("moocast.in");
    string line;
    getline(input, line);
    int n = stoi(line);
    vector<int> temp;
    vector<tuple<int, int, int>> cows;
    for (int i = 0; i < n; ++i) {
        cows.push_back(split_tuple(input));
    }
    unordered_map<int, vector<int>> cow_graph;

    // initialize cow_graph
    for (int i = 0; i < cows.size(); ++i) {
        cow_graph[i] = {};
    }
    // fill out cow_graph

    for (int i = 0; i < cows.size(); ++i) {
        tuple<int, int, int> cow = cows[i];
        int cur_power = pow(get<2>(cow), 2);
        for (int j = 0; j < cows.size(); ++j) {
            tuple<int, int, int> cow2 = cows[j];
            if (distance(cow, cow2) <= cur_power) {
                cow_graph[i].push_back(j);
            }
        }
    }

    // do bfs
    set<int> seen;
    stack<int> queue;
    int highest = 0;
    for (int i = 0; i < cows.size(); ++i) {
        tuple<int, int, int> cow = cows[i];
        queue.empty();
        seen.clear();
        queue.push(i);
        while (!queue.empty()) {
            int v = queue.top();
            queue.pop();
            if (seen.count(v) == 0) {
                seen.insert(v);
                for (auto &&adjacent : cow_graph[v]) {
                    queue.push(adjacent);
                }
            }
        }
        if (seen.size() > highest) {
            highest = seen.size();
        }
    }


    ofstream output("moocast.out");
    output << highest;
}

My solution first computes which cows can call other cows and formats it as a directed graph. It then performs BFS for every node in this graph, keeping track of the largest number of nodes seen from each iteration, outputting that number.

distance() calculates Euclidean Distance, squared - the sqrt() function is computationally expensive and A^2 < B^2 only when A < B.

split* are helper functions for getting input.

Answer 1

I'd say that this code has the right amount of verbosity - not too terse, not too wordy. It's very readable, with one exception I'll mention below. In order to assess the performance, I'd probably need to implement it myself a couple different ways. I don't doubt it could be better, but don't have any great suggestions there. (Although, a depth-first search might use less memory at any one time, which might improve the speed, too. I'm not really sure.) I don't find the code to be repetitive, either.

Here are some specific things I'd change:

Use Named Types When Possible

I have mixed feelings about tuple. In general, I find it makes code harder to read and understand. As a return value, it can be very useful, but I don't think they should be passed around when a named type would be much clearer. For one thing, what is the ordering of the tuple in your code? I can't tell at a glance because all the members are the same type. Is it <x,y,P>? <P,x,y>? Something else? Just make a struct like this:

struct cow {
    int x;
    int y;
    int power;
};

This has knock-on effects for other types. Instead of:

vector<tuple<int, int, int>> cows;

you'd get:

vector<cow> cows;

That's much clearer and much easier to type.

Use Functions

You have put helper functionality into separate functions, which is great. I think you need to do the same thing with the main functionality, too. I'd have something like this for your main() function:

int main() {
    vector<cow> cows;
    read_cows_from_file(cows, "moocast.in");
    
    unordered_map<int, vector<int>> cow_graph;
    create_cow_graph(cows, cow_graph);
    
    int highest = find_longest_broadcast(cows, cow_graph);
    
    write_highest_to_file(highest, "moocast.out");
}

This makes it very clear and easy to understand. Each of the functions would just contain the code that's currently in each section of main().

Improve Your Naming

Most of your naming is pretty good. I see 2 things that could be improved:

1. In your main() function, the variable n should have a better name. While n is commonly used to be the "number of something" to act on, it's better to name it num_cows or whatever. If you ever have to count 2 different things in the same function, you start resorting to less and less useful names like n2 or m and it quickly falls apart. So just naming it num_<whatever> is better.
2. Also in main() you have a variable which is a std::stack that you have named queue. But there is a std::queue type already! Don't name a variable something it is not. It's a stack and you're using it as such. Just name it stack. Or better yet, name it cow_stack or current_path or something more meaningful. But whatever you name it, don't lie!

Comparison With Proposed Solution

In the comments I was asked to compare this solution to the proposed solution from the site. Here's their Java solution. And here are my thoughts on it:

Your solution look about as complex as theirs to me.

• You both make a graph of who can talk to whom
• then you both traverse that graph to find the longest path in it

There are 2 main differences between your solutions:

1. You use a breadth-first traversal, whereas they use depth-first.
2. Theirs uses a recursive method to do the traversal whereas you build your own stack and do it in a loop.

Theirs uses less memory, which is nice, but because its recursive they run the risk of running out of stack space for very long paths. I prefer your non-recursive solution because it avoids that problem.

Answer 2

A word on programming competitions

I realize that when solving a problem from a programming competition, you aren't going to end up with the nicest code. It's more about getting something that works and passes all the tests, as fast as possible. Most likely, no one else is even going to read your code. With that in mind, I will say that your code is perfectly fine. The solution was concise, understandable, and fairly readable.

However, in the spirit of code review, there are still improvements that could be made.

Errors and warnings

When I compiled your program I got this compile error:

foo.cc:39:40: error: pow was not declared in this scope

I added #include <cmath> to fix that.

I also got several warnings of this type:

foo.cc:61:23: warning: comparison between signed and unsigned
              integer expressions [-Wsign-compare]
    for (int i = 0; i < cows.size(); ++i) {
                      ^

I changed the type of i (and other variables) to size_t to fix that.

Lastly, you have an unused variable cow in your main bfs loop. I simply removed that line.

Verbosity / Readability

• I agree with the other reviewer that a tuple isn't the best data structure to represent your cow information. It would be easier to read if you used a struct.

• Your input parsing functions are quite verbose. I replaced all of your input parsing code (including 3 functions) with just this:

  int n;
  input >> n;
  
  vector<Cow> cows(n);
  for (int i = 0; i < n; ++i) {
      input >> cows[i].x >> cows[i].y >> cows[i].range;
  }
  

• I'm not sure why you used an unordered_map for your edge lists, and a set for your visited list. Since you know how many vertices you have, and every vertex needs an edge list and a visited boolean, you could just use vector<vector<int>> for the edge lists and vector<bool> for your visited list. This simplifies things internally because maps and sets need to use hashes or comparisons to order their keys, whereas vectors don't need any of that. I tested the timings and using a vector<bool> instead of a set<int> really sped things up (timings are listed later in the review).

• I'm not a fan of using pow() just to compute a square of an integer. It's a personal preference of mine since I know that if you use pow(), you have to convert your integer to floating point, call a function that does some complicated fp math, and then convert the fp result back into an integer, all of which takes more time. Also, if you are squaring large 64-bit numbers, you may lose precision if you use pow().

Is it a BFS or a DFS?

It's strange that you have a variable called queue but it is actually of type stack. In fact, because you are removing things from the back of queue instead of the front, you are actually performing a depth first search instead of a breadth first search. It doesn't really matter because they both work for this program, but you should be careful to use the type that you really want to use.

Small optimization

Currently, the program is \$O(n^3)\$ because it does one BFS which is \$O(n^2)\$ for each of \$n\$ vertices. You can improve on this by not doing the BFS for every vertex. If on one BFS pass, you visit some vertex, you never have to start a new BFS from that vertex. This is because on a pass that you visit some vertex, you must have started at an ancestor of that vertex. Whatever count you got for the ancestor must have been greater than or equal to the count you got for any of its descendants, so you don't have to bother starting a new BFS from any of the descendants. So in the current worst case where where all the cows can reach each other, you will only need to do 1 pass instead of \$n\$ passes. It is really noticeable when the number of cows gets higher. Here are test timings for 1000 cows all reachable by each other:

Original program                  : 34.4 seconds
Replace set<int> with vector<bool>:  3.9 seconds
Also skip BFS from already visited:  0.3 seconds

Now, there are ways to construct a different worst case where even with the optimization, the algorithm will still take \$O(n^3)\$ time. I feel that it is somewhat analogous to quicksort, where the worst case is \$O(n^2)\$ time but the expected case is \$O(n \log n)\$ time. I believe the expected case time with the optimization is \$O(n^2)\$ with a worst case of \$O(n^3)\$. I tested with randomized cow graphs with up to 20000 cows and the optimized solution never took more than 0.5 seconds for any graph.

Sample rewrite

Here is a rewrite that incorporates all of the ideas mentioned:

#include <vector>
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

typedef struct Cow {
    int x;
    int y;
    int range;
} Cow;

static inline int cowDistance(const Cow &a, const Cow &b)
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

int main()
{
    ifstream input("moocast.in");

    // Read input.
    int n;
    input >> n;

    vector<Cow> cows(n);
    for (int i = 0; i < n; ++i) {
        input >> cows[i].x >> cows[i].y >> cows[i].range;
    }

    // Construct cow graph.
    vector<vector<int>> cow_graph(n);
    for (size_t i = 0; i < cows.size(); ++i) {
        Cow &cow = cows[i];
        int cur_power = cow.range * cow.range;
        for (size_t j = 0; j < cows.size(); ++j) {
            if (cowDistance(cow, cows[j]) <= cur_power) {
                cow_graph[i].push_back(j);
            }
        }
    }

    // Do BFS starting from each cow not yet seen.
    queue<int>   cow_queue;
    vector<bool> ever_seen(n);
    int highest = 0;
    for (int i = 0; i < n; ++i) {
        int count = 0;

        if (ever_seen[i])
            continue;

        vector<bool> seen(n);
        cow_queue.push(i);
        while (!cow_queue.empty()) {
            int v = cow_queue.front();
            cow_queue.pop();
            if (!seen[v]) {
                seen[v]      = true;
                ever_seen[v] = true;
                count++;
                for (int adjacent : cow_graph[v]) {
                    if (!seen[adjacent]) {
                        cow_queue.push(adjacent);
                    }
                }
            }
        }
        if (count > highest) {
            highest = count;
        }
    }

    ofstream output("moocast.out");
    output << highest << endl;
}