[Community Puzzle] Battle Tower

Puzzles
#21

Have you tried aurelags test case above?

#22

Yes, it does give the correct result for that (3) so I am at a loss. The problem is that it only stops working for very huge data sets so that I can’t properly visualize the network anymore, thats why I am looking for a simpler test case.
here is the code for the main routine

bool allSafe = false;
int counter = 0;
while(!allSafe)
{
    
    int biggest = 1;
    for(int i = 1; i <= N;i++)
    {
        if(cells[i].conCounter > cells[biggest].conCounter && cells[i].conCounter != 0)
        {
            biggest = i;
        }


    }
    
    cells[biggest].exit = true;
    
    listOfExits.push_back(biggest);
    
    //cerr << biggest << endl;
    cells[biggest].connectedToExit = true;
    cells[biggest].conCounter = 0;
    for(auto c : cells[biggest].connected )
    {
        cells[c].connectedToExit = true;
        cells[c].conCounter--;
    }
    allSafe = true;
    for(int i = 1; i <= N;i++)
    {
        if(!cells[i].connectedToExit)
        {
            allSafe= false;
            break;
        }
    }

  

}

then I just count the exits in a loop

#23

Try (answer should be 3):

7
1 1 2
2 2 1 3
3 3 2 4 5
4 2 3 6
5 2 3 7
6 1 4 
7 1 5

I thought the one above was this shape but it’s slightly different.

2 Likes
#24

okay yeah that breaks my solution thx, I’ll see where this will take me :slight_smile:

#25

Since the graph is undirected, connected and acyclic, it’s a free tree. That leads to a very simple divide-and-conquer…O(n) in both time and space.

Full disclosure: I discovered this after my initial “greedy” approach failed multiple test cases…which probably says more about me that it does about this problem. :^)

Greedy or not, it’s a nice problem!

#26

Not at all greedy but good problem :confused:

2 Likes
#27

I don’t understand how the Approximation method can work here. The algorithm requires both vertices of an edge to added to the solution set. So it’ll fail any situation like the simple case because it will return 2 instead of 1.

#28

I solved this long time ago so I might not remember correctly…
The preudocode on the wikipedia page is for a generic graph, but here we have a tree.
That means that in every iteration there must be at least 1 leaf node. So instead of selecting “arbitrary edge” we can select the edge connecting this leaf and its parent. Then it is enough to add only the parent to the solution set, not the leaf. After deleting all the edges of the parent we still have a (bit smaller) tree for the next iteration. Repeat until no edges remained.

#29

Ah, I did not see that we have a tree and the special case it presents. Thanks for the clarification that helps me understand the goal a lot better.