[m-users.] Efficient circular lists in pure Mercury?

[Julian Fondren]

On 2019-06-26 14:45, Mark Brown wrote:
> 
> Since you know the size of the problem in advance there's no need to
> go for a dynamic data structure. You could just use a circular buffer.

This boils down to my original solution with a large enough initial
array. A few checks could be removed but they're not that significant in
cost. Since deletions are relatively rare it might be enough to have
next/previous skip over gaps in the buffer, but the constant insertions
would mean moving lots of data without some kind of trick, such as my
fake pointers.

This kind of thinking is a big part of why Advent of Code is fun,
though. You skip unneeded steps for part1, or do something that's "good
enough" for part1, and then part2 is revealed and you might have some
radical redesigning to do. Or part2 is revealed and you already have the
answer, or have no work beyond re-running your program.

Some categories of the escalation are:

"Do that again, but a lot more."
   - part1: give me the factorial of 5.
   - part2: give me the factorial of 5,000.

"Simulate this. OK, now *really* simulate it."
   - part1: a simulation and a question that doesn't actually require the
     simulation (you might do some math instead), or that doesn't require
     all of the simulation
   - part2: those missing parts are now required

"Run this really long simulation and tell me something about. Oh and
also tell me something else."
   - part1: you implement a solution, run it, get the answer, and your
     program exits.
   - part2: you just killed the process that you could've gotten the
     answer from. You monster.

"Make me a boat. By which I meant a space-boat."
   - part1: you're only required to enqueue and dequeue some data, so you
     use a linked list
   - part2: you now *also* need fast random-access to the data.