Hi there !
Warning, the following post contains hints to help solving this puzzle.
If Skynet is on a node without any connections to gateways, it cannot beat you this turn, so use this kind of turn (I will call them KIND1) wisely
If Skynet is on a node with exactly one connection to a gateway, you have no choice for this turn, you must severe this connection. (KIND2)
Notice that Skynet will beat you if it reaches any node with connections to 2 gateways (KIND3). This kind of situation must be avoided, so as soon as possible, you must try to severe one of those. Of course, ASAP = KIND1
The challenge in this puzzle is to determine which KIND3 nodes Skynet will reach the most fast and turn it into a KIND2 node before it happens. This must be repeated until there are only KIND2 nodes left. Then the rest is easy =)
So like other people here, got 100% but unsatisfied with my solution since I’m quite sure it can’t solve all cases.
Did someone understood how the custom tests are working ? I’d like to build one I can’t solve, and check if other people solutions are havings problems as well or not.
Custom test look like this (example for test 01) :
LOCKED
8 <— ok, number of nodes
159 361 <— ???
285 277 <— ???
285 450 <— ???
681 361 <— ???
780 216 <— ???
780 513 <— ???
540 450 <— ???
540 277 <— ???
13 <— ok, number of links
6 2 <— ok, a link…
7 3
6 3
5 3
3 4
7 1
2 0
0 1
0 3
1 3
2 3
7 4
6 5
0 <— ok, starting position for the agent
2 <— ok, number of gateways
4 <— ok, gateway id
5 <— ok, gateway id
I guess that the ??? lines (there are as much as nodes) implement the agent logic, to determine when you’re at a node N where the agent is going next, obviously depending on what links are remaining on the map, but I’v not been able to understand the logic. There are even some negative numbers (test 06).
Anybody ?
Edit: ok, looks like it’s actually just the coordinates for the UI
Too bad, won’t be able to push this nice problem further
All right, that was finally easy, I don’t know how the agent is implemented, but it handles very well this very simple custom test:
LOCKED
12
85 328
625 297
625 427
800 325
800 250
800 400
800 475
313 197
625 100
313 400
800 100
800 150
11
2 6
0 7
9 2
3 1
2 5
4 1
9 1
0 9
7 8
8 10
8 11
0
6
3
4
5
6
10
11
Facts:
This test is compliant with the rules
This test is “solvable”, it has a least one solution
This test is even easy ! Takes 10 seconds to solve on “paper”, it’s a very simple and obvious graph
And nows comes the fun part: out of the 24 Java published solutions, only 10 are able to solve it !!!
Yes, I did spent 10 minutes copy/pasting the Java solutions and evaluating them against my custom test.
It’s a bit disturbing to see 60% of the published Java solutions not able to solve this easy case, although they can solve quite complex ones such as IDE test 4/5/6. While I said earlier that I’m not satisfied with my own solution, at least it solves this test.
I don’t know about the other languages (I only have access to Java solutions since I only solved it using Java), but my guess is that we would have the same kind of ratios.
And I’m quite sure I could easily raise this ratio even further with a little more complex test.
So, open questions:
a) am I wrong somewhere on my facts ?
b) should this puzzle be “redesigned” ?
c) is your solution solving this test ?
I think this puzzle is not a good puzzle. The tests can be passed by implementing simple linear algorithm, but the problem is actually NP complete, so in order to solve it correctly an exponential algorithm is required.
Hello! The logic behind my solution is pretty simple:
I find the nearest node with two gateways’ links and severe one of the links.
If the one-gateway node is closer than two-gateways then I severe this one link.
This logic allows me to pass all tests except for the last one: https://www.codingame.com/replay/solo/128353757
I saw @derbov’s solution posted above but I still don’t understand how to determine the right link.
Finally solved it after some thinking. The logic is a little tricky. You need to tweak bfs a bit. This is the algorithm I followed:
If there’s an immediate gateway node adjacent to the current node, obviously you need to break it.
If not then you need to sever one of the links that lead to multiple gateways(urgent nodes).
Now the challenge is to write an evaluating function that determines which ‘urgent’ node you need to sever.
In my approach, my evaluation function considered the number of nodes that immediately lead to a gateway and the distance of the urgent node from Skynet. Do remember to not consider gateway nodes in the distance.
My algorithm is like yours but I have a problem with Complex mesh validator. My code pass all test cases but when I submit my code doesn’t work like I want.
This is the first link I want to sever ( based in the distance from agent to the nodes with multiple adyacent gateways and the adyacents gateways in the closest way nodes ), in test cases works fine, but in validators doesn’t work like I want:
The only thing that changes between the test and validator are nodes id I guess, and so your program may not compute links in the same order. And it may explain the difference in outputs.
I changed the inputs order and always the output is the correct “27 16”. I think my code is correct. I need the inputs of Complex mesh validator to debug my code. Does anyone have the Complex mesh validator inputs???
I saw now what was done for Indiana, and maybe instead of “redesigning” the hard version, Skynet should just have its very hard version as well, with same rules but harder use cases
Pessimistic N^3 does the job. In my case I use bfs from agent node at every step of the way to determine most threatening gateway link. With good conditions for enqueueing nodes this has complexity far below N^2. But still, worst case scenario is N^3. Also keep in mind I’m using ordinary 2D table with no degree sorting etc. I reckon you could improve overall pessimistic complexity to N^2 log N using better structures - with realistic results closer to N log N.
The thing you must keep in mind here is that super complex examples would mean that they are unsolvable (agent always wins). For example 2 or more equally demanding paths possible for agent, and enough time to start making proper cuts only on one of them.
and you start from node 0; basically, you have 1 node connected to two gateways which is really close and 1 node connected to 4 gateways which is really far. Since the far node will have a higher “rank” according to your definition, you’ll try to cover that node up and the bot will just escape through the close node.
So you rank all the nodes by the number of exit edges connected to them… So would you ignore the gate nodes? Or do those get ranked really well? How does that work?
Then you use Dijkstra… starting where? Starting at the agent? Starting at the gates?
Then you “summed the rank on the shortest path to gate nodes, ones that still has exit edge.” I’m so lost. What are you adding together? And for which nodes? All of them? Or just the ones connected to gates? Or just the nodes connected to 2 or more gates?
