Death First Search - Episode 1 - Puzzle discussion

The check for hardcoding doesn’t work that way. It’s just another set of testcases, like the testcases in the IDE.

You could hardcode an “algorithm” if you knew all the validation testcases. You would just solve the problem by hand for all testcases and have your algorithm read the input and output the right solution. That’s why the validation testcases have to be secret.

In this puzzle the difference between the IDE and validation testcases is the behaviour of the agent and the numbering of the nodes.

The different numbering of the nodes has some effect on your algorithm.

As chrm said, they don’t modify your code upon submission. They switch the node ids around and make the Skynet agent move slightly differently. This is completely fair since they tell you all the node ids up front and the Skynet behavior is not guaranteed anywhere in the problem description. If you made assumptions about node arrangements or agent behavior (intentional or otherwise) and those assumptions turned out to be incorrect, then that’s the problem you need to address.

1 Like

If all they did was switch the IDs around and then give the agent AI a more random path, then my code would work every time regardless. I stores all nodes and their relationships in a map as it is received. Their IDs at the end of the day aren’t really important as much as how they are linked together. They could be real names or even a combination of letters and numbers and it would still work.

The problem I am dealing with, is if I store the values from those two last submission test cases (ide test cases work flawlessly) as I receive them the code fails. If I use an algorithmic approach to change the ids and restore it to its original value when I output my intended link to break it works perfectly.

The biggest failure I noticed while watching replay was that the code did not break the link directly between the exit node and the agent when he was one move away from it. I had commented out the other code related to breaking random links and yet, in the submission test, the code failed by breaking links the AI wasn’t even at. It was working in complete disregard for what I had directly instructed it to do.

Now if this was a consistent problem I would blame my code through and through. But that fact that just by masking the IDs internally but maintaining their link relationships and the code then works, proves that it isn’t my code that is causing the issue.

I’m sorry mate, but there is more going on with this submission test then just changed node IDs and random agent pathing.

Now don’t get me wrong. I’m not that overly upset about it. I managed to pass all the tests, and that final hurdle made me think outside of the box. I considered they test may have been looking for the values of the ids stored in my code and assuming they were hard coded in. If and what it did at that point is anyone guess but my idea to overcome it was to just change it. And guess what - it worked. The only change I did was store the IDs with a different value then I received them, and at that point the code made the correct choices, despite no logical changes in the code.

Anyway, rant over, and despite the difficulties this site is awesome and I’m really enjoying the challenge.

There’s absolutely no way CG will modify your program or your memory management (pointers/refs etc), you do that yourself with what is clearly a bug in your code that triggers in some but not all cases.
Many people including myself have passed all the tests with no issue.

If you want to improve as you claimed, you should analyze your code again and understand where it’s going wrong, instead of fantasizing about some trickster test out there to troll you.

2 Likes

For some reason I can’t get the third achievements on this test, though I still have 52 links left at the end…

Does your code pass all the other validators?

I can only see that you got lucky,

If the agent moved as the following, it is impossible:

  1. Agent move to upper left node which has one link removed
  2. Agent moves one node lower left
  3. Agent moves to lower right
  4. Agent moves to the upper right and spins clockwise finishing all circle
  5. Agent moves lower left, spins clockwise finishing the lower circle
  6. Agent moves up to the left up circle and spins clockwise finishing the circle.
    I didn’t write your move because all of the above mentioned moves forces you to remove the link between the node and gate. So your strategy just got “lucky”

Man this was a blast from the past to find in my inbox.

Anyway yeah tracing the route you’re right on that one - it can be beaten that way. What I never did get around to doing was implementing an actual planning strategy that would play more intelligently than an if-else statement. Probably A* with some heuristic (Minimum Spanning Tree seems appropriate at a first glance)

The agent plays suboptimally, though, and in fairness a year ago the ‘lucky’ strategy was just repeating the test until a random first cut landed on a favourable space.

Yeah sorry man xD I only noticed later on that this was a damn necro-reply. Sorry about that :stuck_out_tongue:

Hi.

I believe that I have solved the Triple Star with 56 remaining links: https://www.codingame.com/replay/solo/91838472. However, I am not getting the “Ambush” achievement. I had previously submitted a solution that had fewer remaining links.

What am I missing?

Thanks.

The achievement description says “Finish the 4th test of the “Skynet: the virus” puzzle with 50 or more remaining links and get a 100% score.”
You must be missing the 100% score part.

After I submitted my updated solution, it says 100%.

Have you checked, maybe you have the achievement already?
I don’t remember exactly, if you need to save 50 links in IDE or in validator as well. If you have submitted a 100% solution, which also saves 50+ links in IDE, and it didn’t give you the achievement, then I see only 2 possibilities here:

  1. Your code fails to save links in validator. This may happen due to some sort of hardcoding in your algorithm, such as depending on numerical order of node ids.
  2. The achievement is bugged.
    Make sure it’s not the former, before blaming the latter.

The achievement is related to the last submission test, the IDE tests have no effect on it.

No need to feel foolish.
While what you say is true for this puzzle, it’s not necessarily true for more general variations. (There’s a special condition simplifying this one.)
So “thinking ahead” is not necessary for the first 2 achievements.

However, a slightly more advanced algorithm would be necessary for third.
Fortunately, the Agent AI doesn’t try to maximise its escape opportunities.
Otherwise it would be quite a bit more difficult to code a solution guaranteed to trap the agent within a minimum number moves.

(Note a brute-force solution might be feasible on the test and validation cases, but would very likely be too slow on more complex networks.)

You’re showing a replay of the test, not the validator.
Because the validator is slightly different, the Agent AI may have followed a different path resulting in more moves required.

I can also point out that your algorithm is not guaranteed to minimise the moves required to block the agent.
In fact, your first move gives the Agent (if it were so written) the opportunity to:

  • circle each wheel, one move from exit
  • leaving you only 1 choice to block
  • until you’ve closed each spoke 1-by-1
  • thus maximising the moves required for you to fully block the Agent

I see. Thank you for the clarification and the tips.

Can anyone tell me why these solutions are failing?



Edit: does the test fail if the agent visits the same node twice? If so, how do you prevent that?
Edit2: found it. Error in my pathfinding. (grr).

Did someone made a solution by trapping the agent and not cut all connections to the exits?

I did. I wrote a code to get the pair of edges blocking the path in the 2 biggest circles. I trapped skynet just in time!