Skynet Revolution - Episode 1 - Puzzle discussion

Well, we needn’t. We need to implement a smarter algorithm.

Again, you can.

I tried to solve the challenge using a variant of Dijkstra’s algorithm.
All the validation tests work fine. However, for the submission there seems to be an issue with the last one. There seems to be some kind of crash since the virus doesn’t move even once.
Hints?

[Fixed Dijkstra’s name]

an issue with how you handle indexes? The validator is the same in terms of structure of the network; only the indexes differ.

Is there a “bug” with the Triple Star test case ?
I have a timeout each pass, even if I print something just after getting the input.
FYI I use Python.

your code considers only one exit gateway so your bfs timeouts.

Hi, i passed all 4 test in IDE but in validator it shows that i failed the first test. Can someone tell me what i did wrong?

Hi. I solved the challenge, had 63 links left on test case 4 with a 100% score, yet I didn’t get the Gold achievement (50+ links left on test case 4 and 100% score). How can I reach the goal?

It says test case 4, but I’m pretty sure it means Validator 4. The Agent has another movement pattern on the Validators.
You can watch how it played out after you submit and look under the validators. It’s under Results -> My Report -> Details.
I have 45 links left on the test case and 57 links left on the validator and got the achievement.

1 Like

Thank you very much for the quick responce.
Now I see what is Validator (probably like all others :slight_smile: ).

I’m getting error as:

terminate called after throwing an instance of 'std::bad_alloc’
what(): std::bad_alloc

Cannot figure out why.

My code runs perfectly on my local IDE (CodeBlocks).
I even measured the time using chrono.

Algo:
just bfs and checking if the node I’m currently traversing has a gateway as its adjacent position or not.

Here is my code

    #include \<bits/stdc++.h\>

    using namespace std;

    class Graph
    {
        int v;
        list<int> *adj,gate;

        public:

            Graph(int v);
            void addEdge(int v, int w);
            void delEdge(int v, int w);
            void BFS(int s,int *node1, int *node2);
            void addGateway(int v);
    };

    Graph::Graph(int v){
        adj = new list<int> [v];
    }

    void Graph::addEdge(int v, int w){
        adj[v].push_back(w);
    }

    void Graph::delEdge(int v,int w){
        adj[v].remove(w);
    }

    void Graph::addGateway(int v){
        gate.push_back(v);
    }

    void Graph::BFS(int s, int *node1, int *node2){

        bool *visited = new bool[v];

        for(int i=0; i<v; i++)
            visited[i]=false;

        visited[s]=true;

        queue <int> q;
        q.push(s);

        while(!q.empty()){
            int po=q.front();
            q.pop();
            list <int> :: iterator it;

            for(it = adj[po].begin(); it != adj[po].end(); it++){
                if(!visited[*it]){
                    visited[*it]=true;
                   list<int> :: iterator itg;
                    for( itg = gate.begin(); itg!= gate.end(); itg++){

                            if(*itg == *it){
                                *node1 = po;
                                *node2 = *it;
                                return ;
                            }
                        }
                    q.push(*it);
                }
            }
        }

    }
    int main()
    {
        int N; // the total number of nodes in the level, including the gateways
        int L; // the number of links
        int E; // the number of exit gateways
        cin >> N >> L >> E; cin.ignore();
        Graph g(N);
        for (int i = 0; i < L; i++) {
            int N1; // N1 and N2 defines a link between these nodes
            int N2;
            cin >> N1 >> N2; cin.ignore();
            g.addEdge(N1,N2);

        }
        for (int i = 0; i < E; i++) {
            int EI; // the index of a gateway node
            cin >> EI; cin.ignore();
            g.addGateway(EI);
        }

        // game loop
        while (1) {
            int SI; // The index of the node on which the Skynet agent is positioned this turn
            cin >> SI; cin.ignore();
            int node1,node2;
            g.BFS(SI,&node1, &node2);
            g.delEdge(node1,node2);
            cout << node1<< " " << node2<< endl;
        }
    }

Help :cry:

Hi everyone,
How can I get the distance b/w gate and agent? I am using queue to implement BFS.

@Dhruv-Garg79 If you correctly observe the animation that is shown when you just see the puzzle story (before clicking “Solve it”) you will get your answer. Hence, you don’t need distance to solve this puzzle.

1 Like

@with_love_KD I was able to solve it using distance array but I think your solution is better.
I understood after watching animation as you mentioned.
If I only break link directly between virus and gate, It will work.

1 Like

Hello… i would not consider my code as hard coded at all!
It worked in the iDE perfectly fine but when i submitted, it only passed 1 of the validations.

May I find out why?

n, l, e = [int(i) for i in input().split()]

links = []

for i in range(l):

    n1, n2 = [int(j) for j in input().split()]

    links.append([n1,n2])

getaway = []

for i in range(e):

    getaway.append(int(input()))  

while True:

    si = int(input())  

    testcases = []

    a = 0

    for i in getaway:

        if sorted([i,si]) in links:

            print(' '.join(sorted([str(i),str(si)])))

            links.remove(sorted([i,si]))

            a = 1            

            break

    if a == 0:

        print(' '.join(sorted([str(i) for i in links[0]])))

        links.remove(links[0])

if I’m not mistaken, you’re only considering links where the gateway is the first node of the link.

Thank you for the reply!
If it is one step away from the gateway, that link will be cut,
else a random link connected to a gateway will be cut.

Is there anything wrong with the logic?

you’re only checking (i, si) not (si, i)

hmm i sorted it so there is only one permutation of it!

There seems to be a problem with the Scala template for this puzzle.
In the val assignments, I get ‘error: value not found’ for each letter (N, L E)

val Array(N, L, E) = readLine.split(" ").map(_.toInt)

Thanks for your input, it helped me too :slight_smile: