Production code

Elegant

The user's solved the kata already.

I do not believe the description has an error. I have recently solved the Kata with respect to ignoring ranks 2 or more levels lower than the users rating.

Im currently able to pass around 70 tests, with A*. I am keeping track of open nodes with a list. I find children nodes of the parent, add the children to the open node list, and prioritize which child to visit next. I think a better data structure may help to pass the additional tests though as the list seems like a bad option. Can anyone recommend a data structure? Was thinking maybe a singly linked list or binary heap? Any advice on what the best option might be?

Interesting solution. Shows that I need to have bigger tests. This is in no way optimal.

After revisiting the problem, it was much easier. Thanks for the advice! I unfortunately did not come up with an elegant way of determining whether a set of nodes existed on a line with no solution.

Note that you're looking for the shortest possible number of steps. Sure, you can revisit nodes, but if coin is going A to B to A to B a million times, will that sequence of moves likely be the minimum? Look for ways to limit your search space by leveraging this.

Wasn't expecting the coins to be allowed to revisit nodes. Makes this significantly harder. Not sure how to even approach the problem.

I ended up rewriting everything into a BFS approach and was able to solve without too much trouble. I am gonna work on the DFS approach some more though. Really I should probably rewrite the whole DFS approach, but I think Im gonna try to patch the original until it works.

As far the dfs trying every path in the above map. It doesnt allow for that as it starts overwriting the open spaces in the top right square with walls as it recurses.

I think the main trouble might be that I have my player object who keeps track of visited nodes with a list. Im gonna try keeping track of visited nodes with a singly linked list to avoid costly insertion time. If that doesnt work, then maybe Ill just rewrite it again utilizing things I learned from the BFS. Thanks for the reply and advice!

If I understand your approach, in a maze like this you may try every single path inside the top-right square before going back? Maybe even backtracking paths.

# ######
# #    #
# #    #
# #    #
# #    #
# ####^#
#      #
########

An improvement I could propose that comes from A-star algorithm without rewriting all yu've done entirel would be to attribute a "shortest distance to the start" score to nodes instead of some kind of recursive "who visited who" (I'm not sure I quite understand the visited part of your code though), then you only visit a node if its shortest registered distance to the start is bigger than its distance to the start in your path.

Of course that'd just be a patch, I think BFS approaches, from floodfill to A-star to Djikstra are always better than depth first when correctly implemented.

Can you confirm that aliens move before turrets fire? If you look at the diagram drawn for the 11th round, it would seem the diagram indicates otherwise. Their is a spawned enemy at pos 0, 0. It is my understanding that all enemies on the board move, and if that is the case I would think the enemy spawned at 0, 0 would move 1 step forward before the turrets fired. But the diagram seems to show the turrets firing with no enemy movement.

I simply can not decypher the order in which a round proceeds. Is it spawn, move, fire. Or spawn fire move. Or as far as I can tell it could be any combination of those 3. Also unsure whether the new spawn moves the round it is spawned or if spawning counts as movement. Instructions seem ambiguous.

My game loop tests the map to see if any aliens can move

All aliens on the map can and will move forward 1 step. Depending on how you structure your data, it may make more sense to first spawn, then move.
Also, since aliens move before turrets fire, if an alien penetrates the base, it is effectively off the map.

Im passing roughly half of the tests. Very difficult to debug so far. Numerous off by 1 or 2 results. Is there some obscure mechanic I may be overlooking?

My game loop tests the map to see if any aliens can move, and if they can it steps them forward by 1. Then I check to see if a new alien needs to be spawned, and if so I place it onto the origin of the path. And finally I fire turrets. I assume that is the correct order?

Also, if an enemy pentrates the base, do turrets in range still get a chance to attack? This would represent a real time map as opposed to strictly turn based movement. It seems like if this is the case, it might fix a couple errors with my algorithm.

Furthermore is it correct to assume aliens take a step forward during a wave with 0?