10 Kinds of People

Question

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";
        }
    }
}

Answer 1

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.