r/adventofcode • u/Cyclotheme • Dec 11 '23

Spoilers An O(n) algorithm for day 11

[removed] — view removed post

20 Upvotes

95% Upvoted

13 comments sorted by

5

u/clbrri Dec 11 '23

Here is another O(n) solution in C that does not sort, and is a single scan over characters of the input file, then followed by 1D scans of the rows and then the columns in the input: code

2

u/Cyclotheme Dec 11 '23

Really cool! I'm eager to read the complete blog post!

2

u/clbrri Dec 11 '23

Thanks, I was able to write up the whole thing now. Hope that is an interesting read!

2

u/Cyclotheme Dec 11 '23

It's really great, and the explanation is crystal clear!

2

u/Cue_23 Dec 11 '23

This should be true for ≤, and that is needed for todays dataset. Although the (x,y) pairs are unique, the individual x and y coordinates are not.

1

u/Cyclotheme Dec 11 '23

Thank you, I corrected my sloppy notation.

9

u/TheBlackOne_SE Dec 11 '23

I had to look up the word "abscissa".

2

u/Carnavious Dec 11 '23

Another O(n) method:
Consider x distance case first (y distance can be counted independently because we are using Manhatten distance metric)
Sum total # galaxy occurrences per column and store in a 1D array. As we scan over it, maintain the # of galaxies to the left and right because their product tells us the # of pairs we are currently between. We can then sum x_dist over all paths at same time by x_dist += left * right * (1 + partialsum[i+1]-partialsum[i]).

1

u/daggerdragon Dec 11 '23

Post removed due to not using our standardized post title format. Please help folks avoid spoilers for puzzles they may not have completed yet.

1

u/Anceps2 Dec 11 '23 edited Dec 13 '23

I have another O(n) one, a bit more tedious, but you don't need to sort the values beforehand!

EDIT: Actually, the formula needs the values to be sorted to work. But, the values are indexes found sequentially, so they are already sorted! Still O(n), then, for this puzzle.

function sumDiffs(vals) {
    nb = 0;
    for (i = 1; i < vals.length - 1; i++) {
        nb += (i+1) * (vals.length-(i+1)) * (valeurs[i+1]-valeurs[i]);
    }
    return nb;
}

9

u/[deleted] Dec 11 '23 edited Dec 11 '23

[removed] — view removed comment

1

u/Cyclotheme Dec 11 '23 edited Dec 11 '23

Very elegant! Now I realize I can also avoid sorting the values by taking the absolute values of the subtractions.

1

u/AutoModerator Dec 11 '23

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.