12
\$\begingroup\$

This is an interview take-home challenge that has been translated to avoid compromising the company's question.

Problem statement

You are a goat that needs to race up a hill. Designated waypoint rocks on the hill must each be visited in sequence or skipped and a score penalty incurred. For the goat to get its balance, it must pause ten seconds on each rock. Travel between rocks occurs on a straight line at two metres per second.

Coordinates and penalties per rock are all integral and exist in the open interval (0, 100). Rock designations are spatially unique. The start rock at (0, 0) and the finish rock at (100, 100) are implied and not included in input.

Minimise the total cost of the goat's chosen path, calculated as the sum of all time spent and all penalties incurred.

Input is specified on stdin as one or more races followed by a final 0. Each race is specified by an integer n on one line - the number of rocks (excluding the start and finish) - followed by n lines, each an integer triple x y p, the coordinates of the rock and the penalty incurred if it is skipped.

Output on stdout is a single line per race, the path cost to three digits after the decimal.

Test cases

Input (sample_input_small.txt):

1
50 50 20
3
30 30 90
60 60 80
10 90 100
3
30 30 90
60 60 80
10 90 10
0

Output (sample_output_small.txt):

90.711
156.858
110.711

Implementation

I have a long-winded explainer that I might not paste here, but suffice to say that the implementation is amortised O(n). I used C++ because I need to catch up on best practices for versions 11+. The current compiler invocation looks like

 g++ -O3 -s -march=native -fomit-frame-pointer --std=c++20 -Wall -Wextra -pedantic

It's pretty fast - for the biggest well-formed input of 9801 rocks, it executes in less than 10ms.

Review

Any feedback welcome, but I'm particularly interested in idiomatic use of modern C++ and associated data structures, and performance.

Code

#include <algorithm>
#include <cassert>
#include <cmath>
#include <exception>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <set>
#include <sstream>
#include <string>
#include <vector>


namespace {
    constexpr int
        delay = 10,
        speed = 2;
    constexpr double
        dist_min = 1,
        dist_max = 100*M_SQRT2,
        time_min = dist_min / speed,
        time_max = dist_max / speed;

    class Waypoint {
    public:
        const int x, y, penalty = 0;

        Waypoint(int x, int y) : x(x), y(y) { }
        Waypoint(int x, int y, int penalty) : x(x), y(y), penalty(penalty) { }

        static Waypoint read(std::istream &in) {
            int x, y, penalty;
            in >> x >> y >> penalty;
            return Waypoint(x, y, penalty);
        }

        double time_to(const Waypoint &other) const {
            int dx = x - other.x, dy = y - other.y;
            double distance = sqrt(dx*dx + dy*dy);
            return distance / speed;
        }
    };


    class OptimisedWaypoint {
    public:
        const Waypoint &waypoint;
        const double best_cost = 0;
        const int penalty = 0;

        OptimisedWaypoint(const Waypoint &visited): waypoint(visited) { }

        OptimisedWaypoint(const Waypoint &visited, double best_cost, int penalty):
            waypoint(visited), best_cost(best_cost), penalty(penalty) { }

        double cost_for(const Waypoint &visited) const {
            double time = visited.time_to(waypoint);
            return time + best_cost - penalty + delay;
        }

        double invariant_cost() const {
            return best_cost - penalty;
        }

        bool operator<(const OptimisedWaypoint &other) const {
            return invariant_cost() < other.invariant_cost();
        }
    };


    void prune(std::multiset<OptimisedWaypoint> &opt_waypoints) {
        double to_exceed = opt_waypoints.cbegin()->invariant_cost() + time_max - time_min;

        for (auto w = opt_waypoints.crbegin(); w != opt_waypoints.crend(); w++) {
            if (w->invariant_cost() < to_exceed) {
                opt_waypoints.erase(w.base(), opt_waypoints.end());
                break;
            }
        }
    }


    double get_best_cost(
        const Waypoint &visited,
        const std::multiset<OptimisedWaypoint> &opt_waypoints
    ) {
        double best_cost = std::numeric_limits<double>::max();

        for (const OptimisedWaypoint &skipto: opt_waypoints) {
            double cost = skipto.cost_for(visited);
            if (best_cost > cost) best_cost = cost;
        }

        return best_cost;
    }


    double solve(const std::vector<Waypoint> &waypoints) {
        std::multiset<OptimisedWaypoint> opt_waypoints;
        opt_waypoints.emplace(waypoints.back());
        const auto end = std::prev(waypoints.crend());

        int total_penalty = 0;

        for (auto visited = std::next(waypoints.crbegin());; visited++) {
            total_penalty += visited->penalty;
            double best_cost = get_best_cost(*visited, opt_waypoints);
            if (visited == end)
                return best_cost + total_penalty;

            opt_waypoints.emplace(*visited, best_cost, visited->penalty);

            prune(opt_waypoints);
        }
    }


    void process_streams(std::istream &in, std::ostream &out) {
        constexpr std::ios::iostate mask = std::ios::failbit | std::ios::badbit;
        in.exceptions(mask);
        out.exceptions(mask);

        for (;;) {
            int n;
            in >> n;
            if (n == 0) break;

            std::vector<Waypoint> waypoints;
            waypoints.reserve(n+2);
            waypoints.emplace_back(0, 0);
            for (int i = 0; i < n; i++)
                waypoints.push_back(Waypoint::read(in));
            waypoints.emplace_back(100, 100);

            out << std::fixed << std::setprecision(3) << solve(waypoints) << std::endl;
        }
    }


    void compare(std::istream &out_exp, std::istream &out_act) {
        for (;;) {
            std::string time_exp, time_act;
            if (!std::getline(out_exp, time_exp)) {
                if (out_exp.eof()) break;
                throw std::ios::failure("getline");
            }
            out_act >> time_act;
            std::cout << time_exp << " == " << time_act << std::endl;
            assert(time_exp == time_act);
        }
    }


    void test() {
        constexpr const char *cases[] = {"small", "medium", "large"};

        for (const char *const case_name: cases) {
            std::stringstream out_act;

            {
                std::ostringstream fnin;
                fnin << "sample_input_" << case_name << ".txt";
                std::ifstream in;
                in.open(fnin.str());
                process_streams(in, out_act);
            }

            std::ostringstream fnout;
            fnout << "sample_output_" << case_name << ".txt";
            std::ifstream out_exp;
            out_exp.exceptions(std::ios::badbit);
            out_exp.open(fnout.str());

            out_act.seekp(0);
            compare(out_exp, out_act);
        }
    }


    void main() {
        process_streams(std::cin, std::cout);
    }
}


int main(int argc, const char **argv) {
    try {
        if (argc > 1 && std::string(argv[1]) == "-t")
            test();
        else main();
    } catch (const std::exception &ex) {
        std::cerr << ex.what() << std::endl;
        return 1;
    }
    return 0;
}
\$\endgroup\$
2

3 Answers 3

10
\$\begingroup\$

M_SQRT2 is not part of the standard library and does not exist on all conforming implementations. The portable C++20 version is

#include <numbers>

constexpr double dist_max = 100 * std::numbers::sqrt2;

Before C++20, you may consider supplying your own definition of the constant since std::sqrt is not constexpr.

The spacing style T& x is much more common than T &x in C++.

I don't think it is useful to put everything (other than main) in an anonymous namespace for a one-file script.

Since the conversion factor \$\sqrt{2}\$ is unavoidable, you might as well store everything in double to save type conversions.

const data members are generally a mistake (outside rare use cases) — usually, a const object is intended instead. Also, it is more idiomatic to define simple data structures like Waypoint as aggregates:

struct Waypoint {
    int x, y, penalty = 0;

    // no user-defined constructors
}

so that it can be constructed like Waypoint { x, y, penalty }. The same goes for OptimizedWaypoint.

Prefer std::hypot(dx, dy) over std::sqrt(dx * dx, dy * dy).. As Reinderien pointed out in comments, the extra precision guaranteed by hypot may cause performance degradation. If performance is the concern, we might consider creating a handmade even faster version if we don’t need the extra precision (since we are dealing with integers anyway).

Prefer ++w over w++ (especially) when w is an iterator, unless you need the return value of w++.

In prune, I believe you are looking for lower_bound. In that case, you probably need to refactor the code a bit, though. (In fact, I feel that the whole OptimizedWaypoint design should be replaced by something like std::multimap<double, Waypoint>.)

Similarly, in get_best_cost, use std::min_element.

The effect of std::setprecision(3) remains until the precision is changed again, so you do not need to do it every time you print a number.

Instead of creating a default-initialized stream and then calling open, simply pass the file as an argument when creating the stream.

Finally, std::string(argv[1]) == "-t" can be simplified to argv[1] == "-t"sv if you have using namespace std::string_view_literals;.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ The reason for the anonymous namespace is that it acts as the C-equivalent static linkage - don't expose symbols you don't need to expose, and offer the optimiser an opportunity to do what it wants with function bounds. Would you suggest a different way to accomplish the same thing? \$\endgroup\$
    – Reinderien
    Sep 5, 2022 at 12:19
  • 1
    \$\begingroup\$ I suspect that's because std::hypot() takes great care to get the result right even in pathological cases (avoiding underflow and overflow). We're not going to hit those cases here, but still pay the cost, unfortunately. You could always define a naive_hypot() function, and perhaps even allow choice of which implementation to use. \$\endgroup\$ Sep 5, 2022 at 12:43
  • 2
    \$\begingroup\$ Yup, looks like neither GCC nor Clang optimize hypot() yet. Here’s the GCC bug for it. Looks like it’s just not a priority. \$\endgroup\$
    – indi
    Sep 5, 2022 at 16:01
  • 1
    \$\begingroup\$ @hanshenrik It can make a real difference for complex types. \$\endgroup\$ Sep 6, 2022 at 5:23
  • 3
    \$\begingroup\$ The spacing style T& x is much more common than T &x in C++. - well people should cut it out. It's easy to see what T &x, y means, but it's not easy to see what T& x, y means.. the & is tied to the first variable, thus it should be T &x,y not T& x,y \$\endgroup\$
    – hanshenrik
    Sep 6, 2022 at 14:21
8
\$\begingroup\$

I prefer to keep the tests separate from the production code, rather than mixed together like this. One reason is that when building a product, we don't need to link the tests into the shipping binary, for a large saving in footprint.

We have the process_streams() interface that accepts an input stream and an output stream; that should be the point where we can seamlessly drive from the production code or from the test framework, without having any test-specific functions in our implementation.

Tests are better if they include everything needed right there. So instead of storing test data in separate files (which adds complexity to the test code), I would prefer to see those inputs and expected outputs right there as literals, and use string-streams to pass to process_streams().

Also, I dislike the use of the name main() for a function in the anonymous namespace. That's too similar to global main() for comfort.

\$\endgroup\$
4
\$\begingroup\$

I think you can simplify the algorithm a little. Performance will stay roughly the same, but you gain readability.

  • Use one struct instead of two.

  • Don't write a constructor, use the default one and curly braces initialization.

  • Use double for everything (because why not).

  • Use std::hypot() for distance calculation. It's a little slower, but more accurate and more idiomatic.

  • Let time_to() return the time for the full path up to that waypoint.

  • Put the remainder of the algorithm all in one place.

  • Run the algorithm front-to-back instead of storing the input and processing it back-to-front.

  • Use a std::vector instead of a priority queue. You have to inspect all (non-pruned) items anyway.

Simplified waypoint struct:

struct Waypoint {
    double x, y, cost;
    
    static Waypoint read(std::istream &in) {
        double x, y, cost;
        in >> x >> y >> cost;
        return { x, y, cost };
    }
    
    double time_to(const Waypoint &other) const {
        return cost + delay + std::hypot(x - other.x, y - other.y) / speed;
    }
};

and algorithm:

void insert(Waypoint waypoint, std::vector<Waypoint>& waypoints) {
    double best = std::numeric_limits<double>::infinity();        
    for (auto& old : waypoints) {
        // Option 1: Find fastest route to newly inserted waypoint.
        best = std::min(best, old.time_to(waypoint));
        // Option 2: Keep old waypoint and incur penalty for skipping new one.
        old.cost += waypoint.cost;
    }
    // Prune old waypoints and insert new one with full path cost.
    std::erase_if(waypoints, [best](Waypoint old) { return old.cost > best + time_max; });
    waypoint.cost = best;
    waypoints.push_back(waypoint);
}

Create a vector, insert all points, then print the cost of the endpoint.

void process_streams(std::istream &in, std::ostream &out) {
    constexpr std::ios::iostate mask = std::ios::failbit | std::ios::badbit;
    in.exceptions(mask);
    out.exceptions(mask);

    for (;;) {
        int n;
        in >> n;
        if (n == 0) break;
        
        std::vector<Waypoint> waypoints;
        waypoints.push_back({ 0, 0, 0 });
        for (int i = 0; i < n; i++)
            insert(Waypoint::read(in), waypoints);
        insert({ 100, 100, 0 }, waypoints);
        
        out << std::fixed << std::setprecision(3) << waypoints.back().cost << std::endl;
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ I don't think std::hypot() would be any slower (it can use FMA instructions which don't work with integers), but it would also not be any more accurate than OP's code. \$\endgroup\$
    – G. Sliepen
    Sep 5, 2022 at 18:55
  • \$\begingroup\$ This doesn't compile - out << std::fixed << std::setprecision(3) << waypoint.back().cost << std::endl; refers to an undefined waypoint \$\endgroup\$
    – Reinderien
    Sep 6, 2022 at 1:59
  • \$\begingroup\$ When I fix your syntax errors, this only outputs 0.000. \$\endgroup\$
    – Reinderien
    Sep 6, 2022 at 2:03
  • 1
    \$\begingroup\$ @Reinderien - Oops, sorry. I had an & missing in the signature of insert(), so the vector was passed by copy. I had also written waypoint.back() instead of waypoints.back() in process_steams(). Works now and produces the correct results. Things happen if you write without ever compiling it. \$\endgroup\$
    – Rainer P.
    Sep 6, 2022 at 8:41
  • \$\begingroup\$ Thanks, it works. For the 1,000,000-rock dataset it's about 230% slower. \$\endgroup\$
    – Reinderien
    Sep 6, 2022 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.