Virgile Andreani on Nostr: I really enjoy all of the potential optimizations that today's problem lends itself ...
I really enjoy all of the potential optimizations that today's problem lends itself to! One can compute all pair distances without even enumerating the pairs, one can also decouple x and y. I wonder what the optimal complexity might be. I think I am currently at O(n log n) with n = number of galaxies, but I have the feeling I could refactor my code in O(n) (which would be optimal, because it's bounded by the size of the input), if I am not mistaken…
#AdventOfCode
Published at
2023-12-11 19:35:28Event JSON
{
"id": "32571f57468d3507fcc7074b0e15b0181ed39c01e2b808e6c3682552159de659",
"pubkey": "c70415d7a6fde7822bd86787a510fac4be9605d76fd8ea8f1238449843f82ef1",
"created_at": 1702323328,
"kind": 1,
"tags": [
[
"t",
"adventofcode"
],
[
"content-warning",
"Advent of Code Day 11 spoiler"
],
[
"proxy",
"https://fosstodon.org/users/Armavica/statuses/111563461666812621",
"activitypub"
]
],
"content": "I really enjoy all of the potential optimizations that today's problem lends itself to! One can compute all pair distances without even enumerating the pairs, one can also decouple x and y. I wonder what the optimal complexity might be. I think I am currently at O(n log n) with n = number of galaxies, but I have the feeling I could refactor my code in O(n) (which would be optimal, because it's bounded by the size of the input), if I am not mistaken…\n\n#AdventOfCode",
"sig": "7b5cb51a642f731becca1de8861ecdfb65fa6e79365e97f2f08cea91adc0e44408ac9f191e9bf6898cab6fb28c6c2dfdbaef888afa8217d915b8db8c0ff4964a"
}
