Advents of Code (programming challenges)

[DavidM]

(12-25-2022 09:19 AM)pier4r Wrote:  Thus I can get the map state in a large matrix (102k), now I need to actually solve part1 and 2 (of Day 14).

I haven't yet started on day 14, but as a result of your posts I took a look at it to see how I might approach it.

The Input Data

Whenever I see x-y pairs in these problems, I think about storing the input data as complex numbers. As long as the numbers aren't primarily single-digit figures, the internal representation of complex numbers will usually save space over a list of 2 reals.

The number of pairs for each line varies, so to reduce the storage footprint I'd make each input line a sublist. They only need to be accessed in a sequential manner at the beginning when the map is being populated, so that would be a good candidate.

Given the above considerations, I'd start out by storing the input data as a "list of sublists" with the innermost sublists having complex numbers as the elements. If that ended up being too large, I'd consider having real/approximate numbers as the innermost elements, coded as XXXX.YYYY to "compress" the data. I don't think it's needed in this case, but that would be the fallback plan.


The Map Data

This is where things get more interesting. I would guess that the author intentionally chose to use x-y values in certain ranges to deliberately force participants to have to go through a translation step. You could create an array of "0..maxX+1, 0..maxY+1", but that would allocate a lot of space that would never be used (at least with the data they provided when I acquired it). That might simply be "annoyingly wasteful" on a computer that has lots of memory, but on a 50g that becomes severly limiting or potentially impossible depending on the actual max values.

By setting up the map with the top left corner as (minX-1, minY-1) and the bottom right corner as (maxX+1, maxY+1), you can significantly reduce the memory footprint needed.

I may actually take this a step further by storing the map as a string instead of an array. There's a limited range of values needed for each element of the map, and a string could easily accommodate them. So the map cell addresses would need two separate translations: once at the beginning of the program when the map is populated with rock structures, and then a conversion of x-y values to string offsets while processing the falling sand. A pain, perhaps, but converting the cell indices to a single offset is pretty easy.

Of course, I could change my mind entirely by the time I get to that problem. But that's what strikes me as a potential method that I would pursue for that one.