How do you simulate a problem where you have to check multiple points at once?

user_17944321 0
Viewed 34

I'm trying to implement a problem where there are "pairs" of points that you can teleport between when walking in the positive x direction, and you have to find the number of such permutations of "pairs" that can get you stuck in an infinite loop (i.e you keep teleporting back and forth). I'm trying to solve this problem by first generating all such pairs using recursion and then simulating for each point whether in your journey, you teleport back to a point that you've already been to (visited[point] = true). However, I'm having a lot of trouble implementing this because we have to process the point that the current wormhole connects to and the next point on the same y-coordinate together.

I use a map to store the pairs, and the points for each y-coordinate (using a set), and I've created a check() function to help me check.

bool check() {
    for (int i = 0; i < n; i++) {
        int done = 1;
        pair<int, int> curp = wormholes[i];
        map<pair<int, int>, bool> visited;
        for (int j = 0; j < n; i++) visited[wormholes[j]] = false;
        visited[wormholes[i]] = true;
        while (done < n) {
            curp = pairs[curp];
            if (visited[curp]) return true;
            visited[curp] = true;
            if (xpery[curp.s].find(curp.f) == xpery[curp.s].end()) return false;

            done += 1;
            
            curp = mp(*(++(xpery[curp.s].find(curp.f))), curp.s);
            if (visited[curp]) return true;
            visited[curp] = true;

            done += 1;
        }
    }
    return false;
}

I return true if you get stuck in an infinite loop and false if you don't, but I'm pretty sure this doesn't work. Is there a better way to implement this?

simulation c++
1 Answers

Not a full answer, You can store multiple wormholes per position like this. What you will have to do is to check if there are loops in the input. (Lookup something called topological sort in graph theory, if you can't sort there is a loop)

#include <cassert>
#include <iostream>
#include <vector>
#include <unordered_map>

// First start modeling things in your universe :)
// wormholes go from one coordinate to another, so we need Coordinates
// and then we need wormholes.

struct Coordinate
{
    std::size_t x;
    std::size_t y;
};

struct Wormhole
{
    Coordinate from;
    Coordinate to;
};

//-------------------------------------------------------------------------------------------------------------
// some output functions for coordinates and wormholes

std::ostream& operator<<(std::ostream& os, const Coordinate& pos)
{
    os << "(" << pos.x << ", " << pos.y << ")";
    return os;
}

std::ostream& operator<<(std::ostream& os, const Wormhole& wormhole)
{
    os << "Wormhole from : " << wormhole.from << ", to : " << wormhole.to;
    return os;
}

//-------------------------------------------------------------------------------------------------------------
// specialize hash for a Coordinate, so Coordinate can be used as a key in an unordered_map
template<>
struct std::hash<Coordinate>
{
    std::size_t operator()(const Coordinate& value) const noexcept
    {
        return (17 * value.x) + (13 * value.y);
    }
};

// also provide equality, operation also needed for unordered_map
bool operator==(const Coordinate& lhs, const Coordinate& rhs)
{
    return (lhs.x == rhs.x) && (rhs.y == rhs.y);
}

//-------------------------------------------------------------------------------------------------------------
// Now model your game map in a class

class Map
{
public:
    // Construct a map with width and height
    // the initializer list will be a list of wormholes for your map.
    Map(const std::size_t width, const std::size_t height, const std::initializer_list<Wormhole>& wormholes) :
        m_width{ width },
        m_height{ height }
    {
        // Loop over all input wormholes
        for (const auto& wormhole : wormholes)
        {
            // check if wormhole coordinates make sense on your map.
            assert((wormhole.from.x < width) && (wormhole.to.x < width) && (wormhole.from.y < height) && (wormhole.to.y < height));

            //For each start coordinate we will add a list of wormholes from that coordinate
            //operator [] will add a new vector if none is present at the current position.
            m_wormholes[wormhole.from].push_back(wormhole);
        }
    }

    const std::vector<Wormhole>& get_wormholes_at(const Coordinate& position)
    {
        assert((position.x < m_width) && (position.y < m_height));
        return m_wormholes.contains(position) ? m_wormholes.at(position) : m_no_wormholes;
    }

private:
    std::size_t m_width;
    std::size_t m_height;
    
    // a default empty list of wormholes so we 
    // can always return a list for each position on the map (even if it is an empty one)
    // this will reduce the number of ifs in your code a lot.
    std::vector<Wormhole> m_no_wormholes;

    // Use an unordered map to store wormhole information for each coordinate
    // that has at least one wormhole
    // a std::vector will hold a list of wormholes at each position
    std::unordered_map<Coordinate, std::vector<Wormhole>> m_wormholes;
};

//-------------------------------------------------------------------------------------------------------------

int main()
{
    // Create and initialize a map
    Map map{ 10,10,
    {
        {{1,1},{3,4}}, // wormhole from 1,1 to 3,4
        {{1,1},{4,5}},
        {{9,9},{1,1}}
    }};

    Coordinate position{ 1,1 };

    std::cout << "Wormholes at position : " << position << "\n";
    for (const auto& wormhole : map.get_wormholes_at(position))
    {
        std::cout << wormhole << "\n";
    }

    return 0;
}
user_166495500
Related