For sure. And to your point, Day 12 was finally where I felt like using Fortran was a handicap. I made my simple little array-based tree structure, but I had trouble translating a “textbook” pathfinding algorithm to work correctly on it. It made me feel pretty stupid.
Day 12 was just a redux of 2021 Day 15, and I reused most of my code. It is easily handled in Fortran - no tree structure required, just three arrays, and MINLOC with mask makes it simple.
1 Like
Day 13 was fun since instead of trying to write a parser for the input, I just used JSON-Fortran (all it needed was an outer [] and some commas to be valid JSON).
But would have it been possible, to read it line by line and pass every line separately to the parser? In my Python version, I did exactly that, and each line itself was valid JSON… (I unfortunately decided to write my own parser for the Fortran version. It was kind of fun, but took way longer as I would have wished for…)
1 Like
I’ve done days 1 to 9, using fpm and stdlib. It’s the first time I used fpm to leverage other fortran packages, and it felt quite convenient. The places I used stdlib were:
1 Like
For day 11 I used a queue template from flibs, slightly modified, to store the items held by each monkey and their order.
I’m not very experienced with such data structures. One issue I had was that, as each queue was repeatedly filled and emptied, its data was stored at increasingly large indices of the queue’s internal data array. If left unchecked, this would eventually cause the queue to run out of space, followed by all sorts of unexpected behaviour.
To work around this I simply deleted and re-created the queues when emptied, if they were close to running out of space.
Anyway, the experience makes me want to learn more about data structures.
For day12 I implemented the shortest path search including use of a priority queue from the kdtree2 library. The idea was to roughly follow the description of Dijkstra’s algorithm in wikipedia (although my code may be far from that!).
Other than the one in kdtree2, I’m not aware of other priority queue implementations in fortran. Any suggestions? @nshaffer @aradi @sblionel
You’re making it more complicated than it needs to be. You don’t need a queue of any kind, just three 2D arrays, one for the tree heights, one for the path lengths, and one to record whether a tree has been visited. Use MINLOC with a mask of the visited array to select the next unvisited candidate, then compute path cost from there to surrounding unvisited trees. AOC12_1.f90
I’ve never run across the term “priority queue” before, but reviewing the definition, this looks as if it could be implemented by a linked list where items are inserted in priority order, whatever that happens to be.
1 Like
It can also be implemented in an array using a heap. I’ve used them many times.
1 Like
I implemented it without minloc by putting all fields, which will be visited in the next step into an array. As the max. number of such fields is well defined (the size of the simulation field), I just used a pre-allocated array for that.
1 Like
I found a Fortran implementation of a heap, which indeed seems equivalent to priority queue. This one assumes the nodes are double precision arrays. But it looks easy to change that.
In principle, the reason to use this kind of datastructure instead of minloc in day 12 is that it will be more efficient for sufficiently large arrays (per search point the time scales with log (# search sites), vs size(array) for minloc). I doubt this problem is large enough for that to matter – but a bit of fun to try it out.
Got Day 7 done. The breakthrough for me was realizing I didn’t need to know the filenames or the hierarchy at all. It looks like I ended up with a very similar solution.