Support AoC 2022 Day 20

[Teo-ShaoWei]

Advent of Code 2022 Day 20.

This library proves to be really useful to represent the problem at a high level. Much of the calculations that my peers needed to do are already abstracted away by the underlying circular list 🎉

However, in exchange, I needed to wrestle with the underlying implementation to get my code to work. Here is a summary of some of the hurdles I faced:

1. circularlist has to take in a non-empty abstract vector (also #1). Since my algo needed to create the value and store the created node one-by-one, the code needed to turn to x1, rest = Iterators.peel(vec) etc for help.
2. Had to quickly derive what the source code is doing on 20th Dec itself, and last vs capacity took some double-take for me to understand.
3. The problem uses a positive number to shift forward, and a negative number to shift back. As the code uses :forward and :backward, we will need to perform if-conditionals to adapt the library to the problem. Also :forward and :backward takes time and carefulness to write in a speed run >_<
4. The problem needs to move a node around in the circular list. This is currently only doable via insert-shift-delete, but this is a destructive process, a new node will be created containing the same value as the old one but with different next and prev. Couple with the fact that jump! doesn't validates (to keep the code fast), the resulting error is an erratic behaviour of the circular list that is very hard to debug 😢

I will try to propose some PRs to hopefully improve on these issues, in the process of cleaning up my solution for AoC 2022 Day 20. As of now I can think of the following (to update as time goes?):

• [x] Update support from Julia v1.1 to Julia v1.6, which is the current LTS. This unlock the door to some niceties, e.g. isnothing.
• [x] Remove of List.capacity field.
• [x] Implement a method of shift!(CL::List, step::Int) that handles negative step. Extend this support to the existing shift! methods.
• [ ] Implement move!(CL::List, step::Int) that moves the current head step forward (or backward if step is negative). This abstraction remove the need to "insert node" for now, which is easy for user to accidentally shoot ourselves in the foot >_<
• [ ] Implement Base.findfirst(predicate::Function, CL::List) to return the first node found. Probably make sense as a node indexes the value for a circular list, and we get there using jump!.

I put these up here so we can discuss them first as the implementation goes on. I want to make sure that most users of this package remain well-served, and as much as possible respect the current convention of the package.

[Teo-ShaoWei]

I have done up most of the features in my dev branch, except for CircularList.List{T}() which no matter how will have trade-off... With what I've implemented, I'll be able to write a compact AoC 2022 Day 20 already 🎉

[tk3369]

Wow, this is a great list of improvements! 👍🏻 I have no problem with any of them.

[jakewilliami]

This looks great @Teo-ShaoWei! Another improvement of this library would be to allow any Integer type in the shift! argument (rather than just Int). Furthermore, I wonder (if you haven't already done it) if it's worth doing some modulo magic on the input of shift! as it's a circular list so if the shift amount that is given is greater than the length of the list, then we should not keep going around in circles for the input amount?

[Teo-ShaoWei]

Thanks for your input @jakewilliami 🙏

It's possible to try to generalize shifting of any Integer and to perform modulo within the library, but I didn't help to implement it into the library due to some push/pull factors.

For the pull factor: these have low overhead if managed by the client. For example, when I was solving AoC 2022 Day 20, I performed modulo myself before calling the library. I would also imagine that any problem can be solved using Int (which is 64-bit in most modern systems). If BigInt is required, since this library is O(n) we are likely not able to use this too.

For the push factor: Generalizing will introduce optimization concern. E.g. every round will perform a divrem or fldmod call. I might want to see more AoC problems to get a sense of whether the trade-off is something good...

So I went with the status quo 😂. That said if you are able to justify the 2 features are nett-useful, feel free to open a new issue on each of those. I can help to review the derivation and the code. Then we will all have a better code to use in future problems 💪

[jakewilliami]

That makes sense, thanks for explaining @Teo-ShaoWei! I don't suppose you could share with me your code for day 20 using CircularLists.jl? 😅 I'm curious how exactly you did the modulo before using shift!. Once again, great work on this!