Advent of Code results (so far)

I tried my hand at Advent of Code this year and was able to get 45 stars.

A lot of my time has been learning about different techniques. As my background is business applications and not computer science, I found there is a lot I don’t know. But I know that and I know a little more than when I started.

I was not able to get day 15 completed. This requires using a search algorithm, which I was not familiar with. I tried to get my code to work properly but the units would not move correctly. I then decided as time permits that I would learn about Breadth First Search (BFS).  This is a technique for searching could be a tree or grid. I have watched videos on it and read several sites. Here is a good one on redblobgames.com.  So here is what I did to do BFS.

It is basically a flood fill that checks if it encounters the target (blue square). You can see it turn red.

Then I added an Exit Early.

This does what the name says and as soon as it finds the target it ends the search.

I then added code to keep track of where each step recorded where it came from. This allows the determination of a path.

So you can see that it has a fairly direct path. It is not optimal as it drops down and then come back up. The next thing for me to do is an A* search which will get the optimum path.

So, once I get a handle on this searching I will try to complete day 15. One of the other days also has a search involved but also with cost associated with each step. I will need to be able to get through day 15 before I tackle that one. Then the only one remaining will involve finding a point in space that is in range of the most number of other points.