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

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
#include
#include
#include
#include
#include
#include
#include

using namespace std;

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

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

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

int inline distance(const tuple a, const tuple b) {

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 `? ? 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> cows;

you'd get:

vector 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 cows;
    read_cows_from_file(cows, "moocast.in");
    
    unordered_map> 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:



• 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_ is better.






• 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:

• You use a breadth-first traversal, whereas they use depth-first.

• 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.

StackExchange Code Review Q#151304, answer score: 6