5
\$\begingroup\$

Follow up to this question: 10 Kinds of People Open Kattis Problem Time Limit Exceeded C++

Solves the puzzle linked in that question.

I use Dijkstra algorithm to find items.
The only twist is that each time I do a search I save the boundary list of the search in a Zone. On a subsequent search if my current "Zone" bumps into an existing Zone I merge the boundary lists and make the old zone point at the current zone.

The searched squares are stored directly on the map 0 or 1 mean original value while any value >= 100 means a zone number (subtract 100 to get the zone). You can then use this value in the zoneMap (if zones clide this keeps the mapping upto date) to get the zone it belongs to.

I tried A* but for a problem space this small it doubles the time as you need to keep an ordered list to know which item to search for next. You can see the remininest of the A* stuff in the Zone class as commented out parts to keep the boundary list sorted.

#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <functional>

struct Point: public std::pair<int, int>
{
    friend std::istream& operator>>(std::istream& str, Point& dst)
    {
        return str >> dst.first >> dst.second;
    }
    friend std::ostream& operator<<(std::ostream& str, Point const& src)
    {
        return str << "[" << src.first << "," << src.second << "] ";
    }
};

class Zone
{
    Point                       dst;
    char                        type;
    int                         id;
    std::vector<Point>          boundry;
    int distsq(Point const& p) const
    {
        int x = std::abs(p.first - dst.first);
        int y = std::abs(p.second - dst.second);
        return x * x + y * y;
    }
    bool order(Point const& lhs, Point const& rhs) const
    {
        return distsq(lhs) > distsq(rhs);
    }

    public:
        Zone(char type, int id, Point dst)
            : type(type)
            , id(id)
            , dst(dst)
        {}
        char getType() const {return type;}
        int  getId()   const {return id;}
        void updateDestination(Point const& d)
        {
            using namespace std::placeholders;
            dst = d;
            //std::make_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
        }
        bool empty() const          {return boundry.empty();}
        void push(Point const& p)
        {
            using namespace std::placeholders;
            boundry.emplace_back(p);
            //std::push_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
        }
        void pop()
        {
            using namespace std::placeholders;
            //std::pop_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
            boundry.pop_back();
        }
        Point top()                 {return boundry./*front*/back();}
        void addZoneBoundry(Zone const& src)
        {
            boundry.reserve(boundry.size() + src.boundry.size());
            using namespace std::placeholders;
            for (auto const& p: src.boundry) {
                boundry.emplace_back(p);
                //std::push_heap(std::begin(boundry), std::end(boundry), std::bind(&Zone::order, this, _1, _2));
            }
        }
};

class Maze
{
    std::vector<std::vector<int>>   maze;
    std::vector<Zone>               zoneInfo;
    std::map<int, int>              zoneMap;

    public:

    Maze()
    {
        zoneInfo.reserve(1000);
    }
    void clear()
    {
        maze.clear();
        zoneInfo.clear();
        zoneMap.clear();
    }

    std::istream& read(std::istream& str)
    {
        clear();

        int r;
        int c;
        str >> r >> c;
        str.ignore(-1, '\n');

        maze.resize(r);

        std::string line;
        for(int loopY = 0; loopY < r; ++loopY)
        {
            maze[loopY].resize(c);
            for(int loopX = 0; loopX < c; ++loopX)
            {
                char v;
                str >> v;
                maze[loopY][loopX] = v - '0';
            }
        }
        return str;
    }

    int const&  loc(Point const& point) const   {return maze[point.first - 1][point.second - 1];}
    int&        loc(Point const& point)         {return maze[point.first - 1][point.second - 1];}
    char type(Point const& point) const
    {
        int l = loc(point);
        if (l < 100) {
            return l + '0';
        }
        return zoneInfo[zone(point)].getType();
    }

    int zone(Point const& point) const
    {
        int l = loc(point);
        if (l < 100) {
            return -1;
        }
        auto find = zoneMap.find(l - 100);
        return find->second;
    }

    Zone& getCurrentZone(Point const& point, Point const& dst)
    {
        int l = loc(point);
        if (l >= 100) {
            l = zoneMap[l - 100];
            zoneInfo[l].updateDestination(dst);
            return zoneInfo[l];
        }
        zoneMap[zoneInfo.size()] = zoneInfo.size();
        zoneInfo.emplace_back(type(point), zoneInfo.size(), dst);

        Zone& cZ = zoneInfo.back();
        loc(point)      = cZ.getId() + 100;
        cZ.push(point);
        return cZ;
    }

    void tryAdding(Zone& cZ, Point const& next, int v, int h)
    {
        Point point = next;
        point.first  += v;
        point.second += h;

        if (point.first <= 0 || point.first > maze.size() ||
            point.second <= 0 || point.second > maze[0].size() ||
            type(point) != cZ.getType())
        {
            return;
        }

        int l = loc(point);
        if (l < 100)
        {
            loc(point) = cZ.getId() + 100;
            cZ.push(point);
        }
        else
        {
            int currentDest = zoneMap[l - 100];
            if (currentDest != cZ.getId())
            {
                for(auto& item: zoneMap) {
                    if (item.second == currentDest) {
                        item.second = cZ.getId();
                    }
                }
                cZ.addZoneBoundry(zoneInfo[currentDest]);
            }
        }
    }

    // Basically Dijkstra algorithm,
    // Returns '0' '1' if the src and dst are the same type and can be reached.
    // returns another letter for a failure to connect.
    char route(Point const& src, Point& dst)
    {
        // The zone contains the boundry list.
        // If the src already exists in a searched zone then
        // re-use the zone and boundary list so we don't have
        // to repeat any work.
        Zone& cZ = getCurrentZone(src, dst);

        // Different types immediately fails.
        if (type(dst) != cZ.getType()) {
            return 'F';
        }

        // If we know that both points are in the same zone.
        // We don't need to expand the boundary and simply return.
        if (zone(dst) == cZ.getId()) {
            return cZ.getType();
        }

        // Otherwise expand the boundary until both
        // points are in the zone or we can't expand anymore.
        while(!cZ.empty())
        {
            Point next = cZ.top();
            if (next == dst) {
                // next location is the destination we have
                // confirmed we can get from source to dest.
                return cZ.getType();
            }

            // Only remove next if we are going to expand.
            cZ.pop();

            tryAdding(cZ, next, -1, 0);
            tryAdding(cZ, next, +1, 0);
            tryAdding(cZ, next, 0, -1);
            tryAdding(cZ, next, 0, +1);


            // This extra check is needed because
            // zones may have been combined. Thus it checks
            // to see if the two points are now in the same zone
            // after combining zones.
            if (zone(dst) == cZ.getId()) {
                return cZ.getType();
            }
        }
        return 'F';
    }

    friend std::istream& operator>>(std::istream& str, Maze& dst)
    {
        return dst.read(str);
    }
};

int main()
{
    Maze        maze;
    std::cin >> maze;

    int count;
    std::cin >> count;
    Point src;
    Point dst;
    for(int loop = 0;loop < count; ++loop)
    {
        std::cin >> src >> dst;
        switch (maze.route(src, dst))
        {
            case '0': std::cout << "binary\n";break;
            case '1': std::cout << "decimal\n";break;
            default:
                      std::cout << "neither\n";
        }
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This doesn't seem to compile: zoneInfo[zone(point)].getType(); what's zone? \$\endgroup\$ – user673679 Sep 24 '20 at 19:14
  • 2
    \$\begingroup\$ @user673679: Opps. I must of accidentally deleted the method zone() while I was tidying up and adding comments. I have put it back. It now compiles. \$\endgroup\$ – Martin York Sep 25 '20 at 0:06
3
\$\begingroup\$

So from a small glance this looks good

I would have gone with a union-find structure but I think it is a neat idea to store in the map.

There are some things I would like to improve:

  1. You are missing [[nodiscard]] throughout, which I believe should be used nowadays.

  2. Formatting is a bit off for me. A few newlines here and there could help a lot with readability.

  3. Your manhatten distance function can be improved

    int distsq(Point const& p) const {
        int x = std::abs(p.first - dst.first);
        int y = std::abs(p.second - dst.second);
        return x * x + y * y;
    }
    

    First, both x and y could be const. Second, the names are too short. distance_x or whatever would be better Third, you do not need the call to std::abs as a negative sign would cancel each other out. Fourth, your Point structure is cheap so I would suggest to pass it by value. This comes with a grain of salt should one need to use other types later on.

    [[nodiscard]] int distsq(Point const p) const {
        const int distance_x = p.first - dst.first;
        const int distance_y = p.second - dst.second ;
        return distance_x * distance_x + distance_y * distance_y;
    }
    

Need to go, will return later

EDIT


I said I like the approach with the zone. However, I believe you might be better off storing the zone in the map itself.

According to the Problem statement the maximal size of the grid is 1000 x 1000. This means there are at max 1'000'000 possible zones.

Using an unsigned integer and encoding the map in the MSB you could then store the index of the zone in the 31 lower bits. So with each start you could use a new zone and merge them via a union-find data structure.

\$\endgroup\$
2
  • \$\begingroup\$ But there will only be a maximum of 1000 searches. A maximum of one zone is created on each search so we will have a maximum of 1000 zones. Though likely a lot less. \$\endgroup\$ – Martin York Sep 23 '20 at 22:59
  • \$\begingroup\$ @MartinYork Does that change the approach of using an unsigned integer and storing the zones it belings to in the lower bits? The number of possible zones would only affect the size of the integer, e.g. uint16_t or uint32_t \$\endgroup\$ – miscco Sep 27 '20 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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