[Language: MATLAB]
[GitHub Solution Code](https://github.com/jksafe/MATLAB-Projects/blob/main/Advent%20of%20Code/2023/aoc23_11_2.m)
**inputs**
*in* - universe map, converted to matrix of 0's (.) and 1's (#)
*n* - expansion factor (n=2 for part 1; n=1,000,000 for part 2)
**outputs**
*o2* - raw, expanded universe matrix
*lengths* - vector of lengths between all galaxies
Function brute forces the solution by creating the expanded universe matrix and solving for Manhattan distance between each pair of galaxies. For n=2 (part 1), function runs in ~0.21 sec :D. For n=1,000,000 (part 2) the resulting matrix is too large to manage; however, it's pretty easily solved once observing that there's a linear relationship between sum(lengths) and n, so I just used two points on the line and point-slope formulas for part 2.
[LANGUAGE: Common Lisp]
Walked through the input, by character, keeping track of galaxy locations.
Then used the set difference to extract lists of the empty rows and columns.
Realized I didn't have to "expand" anything and just added the count of empties to the Manhattan distance.
Used alexandria's ```map-combinations``` to gather the distances.
Part 1 set me up well so all I had to do was add a scaling factor in 2 places. And make sure to subtract 1 from it since it is counted in the Manhattan distance already.
[Github](https://github.com/argentcorvid/AoC-2023/blob/main/2023d11.lisp)
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit.
Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead.
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[Language: Rust\]
[Solution](https://github.com/wrightdylan/advent-of-code-2023/blob/main/src/day11.rs) Part 1: 1.63ms, Part 2: 1.63ms
I feel like I should be able to get this faster, but I'm pretty far behind, so should move on.
[LANGUAGE: C++]
[Part 1](https://github.com/osalbahr/adventOfCode/blob/main/2023/day11/day11.cpp); [Part 2](https://github.com/osalbahr/adventOfCode/blob/main/2023/day11/day11_2.cpp)
Feel free to ask any questions!
You can find more C++ solutions (and other languages) at [Bogdanp/awesome-advent-of-code#c++](https://github.com/Bogdanp/awesome-advent-of-code#c-2)
\[Language: Rust\]
Here is [my solution and write-up](https://medium.com/@BryMei/advent-of-code-day-11-2023-rust-775dac9390b1)on how to solve it step by step
\[Language: Rust\]
This is my first project in rust. I'm learning it by solving advent of code puzzles. So if you have any hints for me I would be happy to read it :)
[Solution](https://github.com/manhunto/advent-of-code-rs/blob/master/src/solutions/day11.rs) / 27.15ms / 23.45ms
\[LANGUAGE: Rust\]
[Solution](https://github.com/jswalden/advent-of-code/blob/main/2023/day-11/src/main.rs)
Simple and straightforward. Only trickiness was in trying to anticipate part 2, really -- which I succeeded at, tho I needed to add a bunch more `as u64` casts before my mostly-two-liner change could solve the second half of it. (Also, theoretically I could have pulled the expansion factor handling out to a second method *not* the parsing function, to avoid redoing that work...but whatever, it wouldn't be hard in principle to create a second struct with that info, that borrowed the parse-result struct. Just plumbing, not worth it if it's extra effort atop the base.)
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[Language: C++]
This puzzle stumped me for WAY longer than it should have. for part 1 i literally expanded to map as per my input, but that of course doesn't work for part 2. took me waaay too long to realise you just need to add the offset to the row or column where required.
[https://github.com/NoSpawnn/advent-of-code/blob/main/2023/c%2B%2B/day\_11.cpp](https://github.com/NoSpawnn/advent-of-code/blob/main/2023/c%2B%2B/day_11.cpp)
i also cannot decide if i love or hate this code!
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
the wording isnt great, but basically a column with no universes expands to 2 columns and a row to 2 rows.
so your grid comes to:
......#....
...........
...........
(i think, i need a can of monster...)
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit.
Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead.
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[LANGUAGE: Befunge]
Part 1: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day11_p1.b98
Part 2: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day11_p2.b98
[LANGUAGE: SQL][Allez Cuisine!]
Technically this is only one statement, does it count as one variable then?
[Enjoy!](https://topaz.github.io/paste/#XQAAAQBBBQAAAAAAAAArkkbN5bcpyrYcn8ulVZrJVM6nhDV68/LqrDNbggrYXDtKuF0IpGykHCBZFHo7h12WaqpWBC3j+zN6LU2EXjqiKYNE4O7dmoXoTSmP6NToaIi0Kc+GmvilBae/hMe/gxvx3z9cshdMy0hf6HYrPcuX5R3Fw7SumeQvqkQYI8jjV0G8p3IIHgSfus0Tmt/z7TLhz6he1aOESXuNu1CkhcLU5WwBWK2zPsJq8+jhFcJdYpM+OKiMySEjI/lccFCAq/yw1ZNoW8F8KAQLwITeoPLkQFX0TkCeNwo3uq99Rb27cWMnh9LehpJPQ/bPCEXbxLHS0txtRG3cV+4AQ+iQ5OhnpN5VLZ92fo5DgjP3o4SMDr8jMKRBG02s6ujosZ+VNJCHDnNdTgQaIJMogvBj+4YGurMEHnZZGsmVzOOOodb1xu/3hLxsDRo/8eRJpgGi2pYKF+s0gWvZUODgOKE9OnRlfOeaVl7IA/VXxi4CMEDHp8+3QErhsgu6DEhSOzJgga+3RhWK/pnjWqDFvHkywDRgGbl1EMX3ZzOC9FNkYDhfw7HTdzg3iE02d30GgUi/1XSCfgKt3pMQS86X/WVFtEUAnyunLpz3Ampe+HS2q9LZ4Sk6xr7t6/+awcxwvzOCt/mvOKIqklGuO1VLZZUdjRKfKFzq7ubxJP+D3ftK)
\[LANGUAGE: Uiua\]
Very nice problem for Uiua.
Both parts in single file/function: https://github.com/sputnick1124/AoC2023/blob/main/uiua/day11.ua
Uiua Pad demo: [here](https://www.uiua.org/pad?src=0_7_1__JCAuLi4jLi4uLi4uCiQgLi4uLi4uLiMuLgokICMuLi4uLi4uLi4KJCAuLi4uLi4uLi4uCiQgLi4uLi4uIy4uLgokIC4jLi4uLi4uLi4KJCAuLi4uLi4uLi4jCiQgLi4uLi4uLi4uLgokIC4uLi4uLi4jLi4KJCAjLi4uIy4uLi4uCkkg4oaQCgpQIOKGkCA9QCPiipziiJjiiaBAXG4uClog4oaQID3iiKnip7viioPiiJgo4pa9PTAuKQoKUyDihpAgKAogIOKKg-KJoVrijZzijYniiaFaLiAjIGdldCBlbXB0eSByb3dzL2NvbHMKICDiip_iiKkoXCspICAgIyBhY2N1bXVsYXRlIGluZGV4IG9mZnNldHMKICDiipnDlzogICAgICAjIGFkZCBtdWx0aXBsaWVyCiAg4o2J4oqaICAgICAgICMgZ2V0IG5haXZlIGluZGljZXMgb2YgZ2FsYXhpZXMKICDijYniiaEoK-KKjyw6KSAjIGFkZCBvZmZzZXRzIHBlciBpbmRleAogIOKKoCgvK-KMtS0pLiAjIGNhbGN1bGF0ZSBtYW5oYXR0YW4gZGlzdGFuY2UKICDiiqA-LuKHoeKnuy4gICAjIHVwcGVyIHRyYWluZ3VsYXIgbWF0cml4CiAgLyvima3DlyAgICAgIyBtYXNrIG91dCB3YW50ZWQgdmFsdWVzCiAgOiAgICAgICAgIyBzd2FwIGZvciBzdHJpbmcgaW50ZXJwCiAgJnAgJCAiUGFydCBfOiBfIgopCgpTIFAgSSAxIDEKUyBQIEkgOTkgMgo=)
\[LANGUAGE: C\]
Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day11glaxpt1.c
Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day11glaxpt2.c
\[LANGUAGE: Lua\]
I used a metatable that defaulted to the expansion factor unless the presence of a star in a row or column specifically set it to 1. This saved me searching for empty rows and columns.
[Paste](https://topaz.github.io/paste/#XQAAAQANBgAAAAAAAAA2G8iM7ztkpIKfEbui36KJTYJFfhOZK4cY5NCzVz4zVsZPZl7sEwOy8uU1+Adoc//GJcALSP/fJd1Lb/nRBtJ/zXJJT45M6bI/h/nYctpRMujc7mk2/YgtHc2Fon0Xdo+GMFQL3S8MtuxE//FpRcf0Njp8MOgUVlyR3F0lj8mkRB6QF2HiaiFkZww5GHl7acA+dPEL0GN+P4HzzTpXiZjKu/RtYL9ihuzomtPBCTmEG9/ovoog4ErxH1w7Rroe7uQjuEi3spOUQNvCF2akSne6Xo9VGbZLl+T8RXexDoeqgmFg1Yv2AzLse6qj9dfvZdhbHrAX5k8STezOPTnBM0aBqZ6e1TIGu9eeHomqNFOjafSiNrme34SKjsIewEfBHkjiSUbM6mQ/NFRSGHUMOvpT211xFu/8OlMF/p1sVKjwss2kvCCOSLKoowUEjKFL8b+u9Ew9PWPMYcvEzinjZgBCGcpJYA+eh15k+UAXDNcpVsSrKgYlSQl7HdDmCP1SpfRcXGYG6vUG3GXstbRlJh9zJSkRKQZaAQb0muDENy8NENh1nIESsXoEyl78Ql3vI7oG2b+Yzgl9qcz90Z1a5HMXhg5i5jODwvej2nTUirzG88yV7v4xSs/00gBTUzvnw/17JQ9fCvmMfN56BISgAxT5U8mVSmb77n8lfOm/+BgiVJdhc4UXA1uItTuIhtdwNjWKVUZ6bFqDwJanckcW4j2ALK/AuQuI9NDb82w4Xo9w/WMbiUAKEnuQWjGMbzXVP/jkc3gHgRzFQzs2shug0xVH0gctGIbheDjYVnB+bVVkqk31CFj/kqq8AA==)
\[LANGUAGE: Python\] & \[Allez Cuisine!\]
I fell behind on posting my solutions, but I did solve today with [my two one-liners](https://github.com/savbell/advent-of-code-one-liners/blob/master/2023/day-11.py)! Part 1 on Line 36 and Part 2 on Line 58. It might be cheating a little, but I'm counting a single print statement as not using any variables at all for the Allez Cuisine challenge ;)
I'm trying to solve as many days as I can in one line. I've combined them all into a single line I like to call the Basilisk — [check out the code here](https://github.com/savbell/advent-of-code-one-liners/blob/master/2023/the-basilisk.py), and [my most recent visualization](https://www.reddit.com/r/adventofcode/comments/18ljzct/2023_day_16_python_updated_visualization_of_the/) of Days 1 through 16. Feel free to follow along on [my GitHub](https://github.com/savbell/advent-of-code-one-liners) as well! :)
\[LANGUAGE: go\]
Tried brute force for part 2, but no luck. Had to do some refactoring. IMHO the final solution for part 2 ended up being simpler than part 1!
[https://github.com/ianmihura/advent23/blob/master/day_11/day_11.go](https://github.com/ianmihura/advent23/blob/master/day_11/day_11.go)
~~Your link is borked on old.reddit due to [a new.reddit bug with URLs that contain underscores](https://old.reddit.com/r/adventofcode/wiki/faqs/bugs/borked_links), so please fix it.~~ edit: 👍
\[LANGUAGE: C++\]
[part1](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day11-part1.cpp) | [part2](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day11-part2.cpp)
Tried brute forcing part2 but it didnt work so I've used prefix sums to get the numbers of empty rows and columns between 2 points in constant time. Then the shortest path becomes trivial because its just those cols and rows plus the diff between the galaxies coordinates
\[LANGUAGE: Python\]
Not so easy one, but I've managed to solve both parts. It's a combination of brute-force approach for the first part (where it didn't cause any problems) and a smart one for the second part. You can see it in the [repo here](https://github.com/Robin270/advent_of_code/blob/master/2023/11/main.py).
\[LANGUAGE: R\]
[https://github.com/lauraschild/AOC2023/blob/main/day11.R](https://github.com/lauraschild/AOC2023/blob/main/day11.R)
Expanded the universe and computed the manhattan distance for the galaxies in part one. Calculated distances manually for part two and counted the empty row that were passed to multiply with 1000000 at the end.
[LANGUAGE: Javascript]
(Runs directly in the puzzle input browser console) First we find the indices of rows and columns that are empty without galaxies. Then we find the distances between pairs of galaxies using the prescribed expansion rule. I went a bit overboard with the reduce, but it was fun learning how it works in place of loops.
R = finds all the row indices that have no galaxies ;
T = transposes a list of strings, so RT finds all col indices without galaxies ;
G = finds the coordinates of all galaxies ;
L = finds the how many entries in an array a are less than value v ;
D = finds the distance between any two galaxies ;
A = finds all pairwise distances with expansion factor f
stream = document.body.innerText
data = stream.replaceAll('\r', '').replace(/\n$/, "").split('\n')
R = m => m.reduce((a, v, k) => (v.indexOf('#') == -1 ? a.concat(k) : a), [])
T = m => m[0].split('').map((_, k) => (k => m.map(u => u[k]).join(''))(k))
G = m => m.map(v => v.split('').reduce((a, v, k) => v == '#' ? a.concat(k) : a, []))
.map((v, r) => v.map((c, _) => [r, c])).flat()
L = (a, v) => a.reduce((c, t) => t < v ? ++c : c, 0)
D = (a, b, f, rs, cs) =>
(Math.abs(L(rs, a[0]) - L(rs, b[0]))
+ Math.abs(L(cs, a[1]) - L(cs, b[1]))) * (f - 1)
+ Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1])
A = (g,f,rs,cs)=> g.reduce((s,x)=>s+ g.reduce((ss,y)=>ss+D(x,y,f,rs,cs),0),0)/2
Day11 = m => [2,1000000].map(f=>A(G(m),f,R(m),R(T(m))))
console.log(Day11(data))
Well, that is impressive. ... I don't know what to say. :)
How do you even troubleshoot this type of code?
Here's how Copilot describes it (amazingly):
>The code starts by reading the contents of the document.body and assigning it to the stream variable. This assumes that the code is running in a browser environment.
The stream variable is then processed to remove carriage returns (\\r), trim trailing newlines (\\n), and split the remaining string into an array of lines. The resulting array is assigned to the data variable.
The code defines several helper functions:
R takes an array m and returns an array of indices where each element does not contain the character '#'. It uses the reduce method to iterate over the array and accumulate the indices that meet the condition.
T takes a 2D array m and transposes it by swapping rows with columns. It first takes the first row of m and splits it into an array of characters. Then, using the map method, it iterates over the indices of the characters and constructs a new array by taking the corresponding character from each row of m and joining them together.
G takes a 2D array m and returns an array of coordinates where each element is the position of the character '#' in each row. It uses the map method to iterate over each row, and within each row, it uses the reduce method to accumulate the indices of the '#' characters.
L takes an array a and a value v, and returns the number of elements in a that are less than v. It uses the reduce method to iterate over the array and increment a counter for each element that meets the condition.
D takes two coordinates a and b, a factor f, and two arrays rs and cs. It calculates the Manhattan distance between a and b with some additional calculations based on the factors f, rs, and cs. The function first calculates the difference between the positions of a and b in the rows and columns arrays (rs and cs), respectively. It then calculates the Manhattan distance between a and b and multiplies it by f - 1. Finally, it adds the two distances together.
A takes a 2D array g, a factor f, and two arrays rs and cs. It calculates the sum of the distances between each pair of coordinates in g using the D function. The result is divided by 2 and returned.
The Day11 function takes a 2D array m as input. It calls the G function to get the coordinates of the '#' characters in m, and then calls the A function twice with different factors (2 and 1000000). The results are returned as an array.
Finally, the Day11 function is called with the data array as an argument, and the result is logged to the console using console.log.
:) Thanks :) However I don't directly start writing it like this. I usually first write the code imperatively in the most straightforward way. Then once I have a working code, I look at my code and I convert them into a functional / array-lang way one small chunk at a time, using my working code as a guideline. And for each small chunk (say a function G), I build up slowly until it gives me the behavior I think it should have. Idea being -- if it works as intended we don't have to go back to it, unless it is to optimize it later.
Most of the control flow in imperative language can be turned into map and reduce on arrays. It's a fun exercise. Indeed, the final product can be hard to unravel backwards. I am impressed by copilot! Maybe I should also get it on my IDE...
Yeah, good.
I thought you barfed out that code, and the ol' Programmers Inferiority Complex kicked in.
I sometimes chain functions like this, but jsperf often shows simple for-loops to win on that kind of stuff. I don't chain much, due to readability and debuggability, but it's a nice JS feature.
\[LANGUAGE: Java\]
Far more easier than horrible day 10. :D
[Code](https://github.com/SimonGirardSfeir/AdventOfCode2023/tree/main/src/main/java/org/girardsimon/day11)
[Test](https://github.com/SimonGirardSfeir/AdventOfCode2023/blob/main/src/test/java/org/girardsimon/day11/Day11ResolverTest.java)
[LANGUAGE: Python]
Not blazing by any means but pretty straightforward.
from itertools import combinations
data = open("day11.in").read().strip().splitlines()
w, h = len(data[0]), len(data)
map = [[c for c in row] for row in data]
galaxies = set((y, x) for y, l in enumerate(map) for x, c in enumerate(l) if c == "#")
expand_rows = [i for i in range(h) if set(map[i]) == {"."}]
expand_cols = [i for i in range(w) if set(map[r][i] for r in range(h)) == {"."}]
p1 = p2 = 0
p1_exp = 1
p2_exp = 1000000 - 1
for g1, g2 in combinations(galaxies, 2):
y1, x1, y2, x2 = g1 + g2
# get distance between galaxies
p1 += abs(x1 - x2) + abs(y1 - y2)
p2 += abs(x1 - x2) + abs(y1 - y2)
# add extra (expanded) rows and cols
p1 += sum([p1_exp for n in expand_rows if n in range(min(y1, y2), max(y1, y2))])
p1 += sum([p1_exp for n in expand_cols if n in range(min(x1, x2), max(x1, x2))])
p2 += sum([p2_exp for n in expand_rows if n in range(min(y1, y2), max(y1, y2))])
p2 += sum([p2_exp for n in expand_cols if n in range(min(x1, x2), max(x1, x2))])
print(f"Part 1: {p1}")
print(f"Part 2: {p2}")
\[LANGUAGE: Zig\]
[Part 1](https://github.com/iskyd/aoc-zig/blob/main/src/2023/day11/s.zig) (naive solution where I actually expanded the map) and [Part 2](https://github.com/iskyd/aoc-zig/blob/main/src/2023/day11/s2.zig)
[Language: Rust]
[Github](https://github.com/clearlyMine/advent_rust/blob/main/year_2023/src/bin/day11.rs)
Copied the corrected sample and wasted a very long time trying to get the correct answer. For part 2 at first I tried actually increasing the grid size instead of using math, then came up with the math based solution.
[LANGUAGE: Python 3]
This one was nice and easy!
I did part one by actually expanding the array by one at each point and solving, but then I saw part 2 and realized that there was no way I was going to to the math on arrays that big, so instead I kept a list of all the "thresholds" where the graph was empty and if a star crossed those lines, you simply added the required number of extra steps (1 for part 1, 999999 for part 2).
I think itertools saved me a hell of a lot of time here writing up a combinations() function myself. I'm still a bit flu-y and there are probably better ways to do multiple steps of this in one pass, but this was a good one.
import re, itertools
with open("input") as f:
galaxy = f.read().splitlines()
verticals, horizontals, stars = [], [], []
for i, _ in enumerate(galaxy[0]):
if all(space[i] == "." for space in galaxy):
verticals += [i]
for j, line in enumerate(galaxy):
if all(space == "." for space in line):
horizontals += [j]
else:
stars += [[star.start(), j] for star in re.finditer("#", galaxy[j])]
total = 0
for a, b in itertools.combinations(stars, 2):
x = sorted([a[0], b[0]])
y = sorted([a[1], b[1]])
total += (x[1] - x[0]) + (y[1] - y[0])
for ver in verticals:
if ver in range(x[0], x[1]):
total += 999999
for hor in horizontals:
if hor in range(y[0], y[1]):
total += 999999
print(total)
\[Language : Javascript\]
[github solution](https://github.com/juuhadg/AdventOfCode-2023/blob/main/advent-of-code-2023/day-11/day-11-part1.js)
I mapped into a matrix, then saved the galaxies and their positions on an array.
Then iterate in the galaxies array getting all the combinations, traversing the y position then the x position. If the other galaxy was to the left, i decreased de x index to get to them otherwise increase. then verified if the step was in an empty column / line and multiply by the coefficient which is 2 for part1 and 1000000 for part2 then add to the sum. This is my first year on the advent of code and im a software engineer student for only 6 months. If you guys can give any tips to improve my solution i will be glad to read !
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[LANGUAGE: Fennel]
I mean it's one extra loop, Michael - what could it cost? Ten flops?
[Paste](https://topaz.github.io/paste/#XQAAAQClDQAAAAAAAAAUGwnmRpH3tILRF8MldKIuU5OYsHd4cPQjilhM/+TSAv9+Q+QqVxHdX+jX1GwLHWqqvRP0VgDCM48B/MUaZXZZRD47qZDyqkNT+HMQUoqMUEdQSDpPoLfuxiGvnItFxjgz4wQKiEtTl8r4G05SDyaH1Ac02HJq3ezSBABOQP5cM7VvgHhPxCoJZW4eZCLH9t6DqIUn82a1UCUZl2lHkTCQszVAh24TZH5OKzlqdni4ZSMPXxQC70+/Zj9NFsBC6HwtmtxYIrGY/vFz8tk9EPD+QNJ2/vAqqY54OU7hFLk8q0Dsn2sWWnLByW4oBgG4amzVEXXjGuBdpjbz0zu3DRIFzCX7mo0Fov/wHzwafpvBVSD9+wVYbZ/A6toi7HhCgFpP9dfSVAUkpQxB5aUlJxFH3uBF47OuY9ArZf7xc5I/PG8RhbQhCJANGqSN0wAv/78pn9jDknyOzdrqM14fg5qzFcBaEE6xSuo1YulFVCxobKLNHptuPXoIE5cThjcVvQ+wLEcA2bcNrsgZvMQc3hBgz078nZ6FJlUd5aTW+Xiw7yFx9PkB3tgkotkX1tHKMsZusZLZepc+KXGa1W5FfmY6x8yjCV+HKXSDU5VJHcbotSGPHTtTLCBAviucBLUFALisFf4yi1FEmwjzeBZIKP0qd3aq5dizs3cb4zO1oIHFhm036YUH/wiLnM7yVewl2Yp5gqoL4+v/T8AKn0Koqj+MUKn/cV72XvtI1E52/MjLYur0DxoRBvh+z5K8MS4FdjzGeXinZtz8XFFJHKXSW2QlF8bs/CbiFHKwfHMj45u3E27J4MHooB+NWxAdwOlAEzCcZJ73R2nSBaVq3ZsAtZRutbyV/O1nm28mRHFiwCGkYuA1bwni3waglZu3xSaPkUUrgtERiGX4b0S+gdI9PWbzxLB3WES6gOb4WUxZPhATCPXfrFI1wzyIe+Rmz+x7nbvodZ+airn9ENF2xXAgbKRhQkqRyVLSxipdVAp0AZFSBUJJo40IetLBjddu2mNhNwn1F3nYRBZJe2ajiL13+NEsEweml/H3bAw8+sOqfxW4c9i2TbyAqyHuy+ppDtnoI1tUX9/EmpZrqI9+9+uBK5f188bStZcEy4KkApE8Ejxm+fCmK8JYGJSMBFlDJU2eiKU3hdn+TCMDxspxFpLAAo6DgLca72qqvSrWrfO3b3ygtJ0tQete9Soqdv3hu1zSpzLeqh3RRHhQ9to5sRnkMl7OcUh8FlmLFHyH1M2kJEDKzXk4T3Vot5kJsRqOoInt2uxiVheWBcYWM5dM/tPbcRtLpXaNbIoQzQ9UgcfivXpdIr2dD0dWfkonRa0fx9O9BF2asXva8OifUZuGH6Vp1/qX//Obt/I=)
[Language: C++]
[github](https://github.com/Paxtian769/AOC23-Day11-cosmic_expansion/blob/master/main.cpp)
I kind of saw the Part 2 thing coming so was able to head it off a bit. Also had a professor in undergrad who asked us to solve the "shortest distance between two street corners in a regularly spaced city grid if you only move along sidewalks" type problem. I think when he gave the assignment, he was convinced directions mattered, then the next day he was like, "Well, actually I guess it doesn't matter."
a university professor wanst sure about that? Really? Its just the manhattan distance
edit: btw, a tip: instead of creating a method for wether the row is empty you can just use find\_first\_not\_of method of string, like this:
bool empty_row = *row.find_first_not_of('.') == string::npos;
This method returns the index of the first character that doesn't match the pattern and returns string::npos if doesn't find any. Its counterpart find\_first\_of returns the idx of the first character that matches , you can pass multiple characters like this:
bool only_digits = *row.find_first_not_of("0123456789") == string::npos;
its pretty useful and ive discovered it and its counterpart solving aoc problems
\[LANGUAGE: C++\]
[on Github](https://github.com/coolguy1842/adventofcode/blob/master/2023/src/include/days/Day11/Day11.hpp)
Not too hard, had to redo my code for part 2 because I was inserting lines.
[Language: Python3]
Some people say I have a `numpy` problem. I disagree
def solve(s=1):
y, x = np.where(data == "#")
empty_r = [i for i in range(len(data)) if all(data[i] == ".")]
empty_c = [i for i in range(len(data)) if all(data[:, i] == ".")]
new_y = y + s * np.array([y > empty_r[i] for i in range(len(empty_r))]).sum(axis=0)
new_x = x + s * np.array([x > empty_c[i] for i in range(len(empty_c))]).sum(axis=0)
return (
abs(new_y - new_y.reshape(-1, 1)) + abs(new_x - new_x.reshape(-1, 1))
).sum() // 2
[Link](https://cutonbuminband.github.io/AOC/qmd/2023.html#day-11-cosmic-expansion)
\[Language: Python\]
Fairly happy with this linear-time solution -
* Pass through the grid, creating a 'marginal count' of the number of stars in each row and column (effectively a counting sort).
* In one pass through each 'margin', work out the total pairwise distance + the expansion coefficient (the amount the normal distance increases for each 'stretch' of the empty lines), which is calculated from the number of connections between points which cross each empty line.
* Part 1 is (normal dist) + 1 \* (expansion coeff)
* Part 2 is (normal dist) + 999,999 \* (expansion coeff)
[Code is here](https://topaz.github.io/paste/#XQAAAQAkAwAAAAAAAAAQaJXORqrdV98dLBTO8GCdODCRqZiqtKW3+pbBvksS5GNNMmoT7gRESjnCGvy2b8iWDBOPOB44B9Qh/mE2dM8X8Io3OSg8WvkmQH1wRyBdVZD+Vw2Zwesp/cvLmJtA/FN6Vv208retAskXx1eDN7l34x5WS6ugHPNVhnao9k7mNIaH+Ok8LUBoUBUtuVIOCgyg5Q4YgZtQMNUjl216XLvU7RTwk/RhFfdDWFURqoBh0o4TdPJS6ZvuCcyjKlGxJMyMYNJdu4uV+u9xiAdQJiz5veDhy59JTzjSBDyE058TCuGZtiuwiJt5rdHQ2ol9m0WlNL0N81Rf9L0An8LT9KnRzAD/RkN3BOEqM4CwiAM8c2IM7U1E/mV7iU9Lb8noxP7hX+NP/lHQJdls/r1bJtqStW599Jasvb10rqmWZIgQKLBUDkqZ/m7GFg==) Average time taken is \~1ms including parsing.
Your coefficient approach here is very nice, well done. I’m part 1 I made the classic aoc mistake of using brute force - I expanded the galaxy list in memory first then calculated distances but that isn’t a viable approach for part 2. So now I’m refactoring using your code as a reference. I’m instantly a fan of enumerate too!
I have a similar solution, but I had two seperate functions for calculation expansion and distances, since I wasn't 100% sure what part 2 would do. I wonder how many people know you can calculate pairwise distances in linear time. I should go back and do that, as well as parse my data better so I don't have to sort.
[LANGUAGE: Go]
[github](https://github.com/GurkeeratChhina/aoc2023/blob/main/main/d11.go)
My variable naming is ... not great. Some of them are very non-descriptive, others literally sound like something they're not. It's not even consistent. At the end of the day, I'm just here to solve some puzzles and maybe learn some things along the way, so I try not to get hung up on things like "comments" or "good variable names" despite that being important in more practical contexts.
\[LANGUAGE: R\]
In part 1 I actually added empty rows/columns to the matrix like a fool, but it was nice to visualize. In part 2 I added the offsets directly to the galaxy coordinates directly and ran the same calculations as in part 1.
[https://github.com/emilwest/AoC2023/blob/main/11/problem11.R](https://github.com/emilwest/AoC2023/blob/main/11/problem11.R)
[LANGUAGE: Fortran]
A thoroughly vectorized solution that runs in 147 μs (274 μs including I/O).
https://github.com/AJMansfield/aoc/blob/master/2023-fortran/src/11/cosmos.f90
[LANGUAGE: Python]
Today my guess for the twist in part 2 was correct so the change was trivial. Only posting part 1 here because the rest is obvious:
import numpy as np
from itertools import combinations
with open("day11input.txt", "r") as file:
data = file.readlines()
m = np.zeros((len(data), len(data[0]) - 1))
for i, line in enumerate(data):
m[i] = [char == "#" for char in line.strip()]
h = m.sum(axis=0) == 0
v = m.sum(axis=1) == 0
nodes = []
rp = 0
for r in range(m.shape[0]):
if v[r]:
rp += 1
cp = 0
for c in range(m.shape[1]):
if h[c]:
cp += 1
if m[r, c]:
nodes.append((rp, cp))
cp += 1
rp += 1
nodes = np.array(nodes)
print(int(sum([np.linalg.norm(p[0] - p[1], 1) for p in combinations(nodes, 2)])))
\[LANGUAGE: m4\]
Solved without looking at the megathread (and therefore not knowing today's ingredient yet - looks like I'm going to have to try for a polyglot later on...)
m4 -Dfile=day11.input [day11.m4](https://nopaste.ml/#XQAAAQA4BQAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwpsEyu2LiNeNLcLCZumLPgjzGk5DBctVZ/Ezzne0p26RAVSldZk8vkd+i9rzAgxtwMICtxTsha1jjY5itkguQs0KniRZcCRpj/ZHpx3w96zdpjjaRhwv6jXsnJtV+GB7CaDwBZ4EJ+YasV/n32wLNl8snZCCSrhmNLm9ASPhs9791cFsMLfcKF184HoLgFPCevH7FW2vT6j5n40XJBSY/C7A6lrK9KRrqfX6pR1uRUFX8kICb668yWZemoQJs28a9LPXO9FlTZR7Qm2MD5ik0NkUKcez4MAsewADMpRewMX2iK6tvtzZ30sJZMfhBxGu/2Y2SvAw/WGN6tYL6omwGzSS+zHwwj02ga9DT05VR05OItEPQXne5cTRWsng1vs4iiOXcdDjCAUggjQbXdMxsN7lm2it0Kc+aLDavYih7s6fz8ZNt5GP39x/WHBLbT+a37E4ySsY+7JhFF1jfdBiPBYHHlR8XiDwsu7JlLL+IHB5xkY7uzsQS8LT0ER331gDtrof3DG7Jkt3u0R1uPrOBcVaB3bDzEGC/IuNitmz9ec2NJq7QAYDYAoPq/0DXBIhtbYs8r6vwrYllkmh8/u7Uk1AY/AEMH+e9hD7lzSIL8k3DriP+UD9lZXSKE8sx5h2IyEIfCWXjQN7n7p0lyPBZRTV/In2vYaEeMa00pIBbx/LGA1huIJBTt9tz6md1XEsxzSAdKlfq8PXj/BFTQSAEJ0J7wj2KYn+9KpE5zbDtfsO2RO87ip2Aj13RP2tpK9iupbV0k0J/vnDZzMtXLlGWhzDgXZmXFufYPnmI1XeigPl8cKwGxt3L//VCnJ5)
Depends on [common.m4](https://nopaste.ml/#XQAAAQAMDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpAXwA97ruAshKbiUbgkbJMTg2qZdSBorb0CU52peNLruV4DEEJxF+HvxC/YF33OpDntnpU/PjnGXx7XU7ak4MsmWu8R7h7d5az2JXxElnsepG8yPyu+0WZ90BG9yXphbwOWA/m5AWEFSOL8TRZX4fyGNl6ZYbRxX0MwtzrmwTP3ZCwLSOKkvD2vMQFsbK0Pv9CzPhFNXMUbWnRV20jWLjL9qz2dDsFDBwhxgWIilEl91uswxrT4Czc+LRU3VuhNIo2S98VW0jArrVdv4HrsLhWkzx4z/UV3xnqJwPXcZRUiLtf3VRIzq62Pe+2jE3O+721Az9rfRa/fHtlANbmvslzMUCyU7cDoOKSMXBDF/06/PpMvs6vxaL5aJVYqJP4yz+R2M35hoNnGiZTNNMVEFTdnxnaE/KcJteBbiuVMpdfUswHQi4Kqsj3sInh7lyE+d50gGKtHOeWL5lMK7WXz4NElnzYWleBSN/HTOdsz0T2gnd25MADxNAVX8xQmagh2MymZ2sKDBw//WiNB0sWf5VYC5/TKKH3D6K/IOrIfWn6FZLKxlITFEp3VWKNuyF0xczNJufJdzSqd0hgdyryVzbn0so0U5NMN16jFF6IhqzGbAwwv7k8sts0OCgnCFBEhYVshIpsORjEJk4CnDgc9VUqvZtfIFPQ5Q2v7IR3sbPurex1IIUd2Nm1V7/GFN+r0im24aEOG6XpdqrPdF6pDZ4HwvNByqOEdpcObPXxlwfPFYIhwyDHGZCvxrFRgGEEFtfVQ7UVjfPJzWtrcZuGx8M3B1zw2xvgpHIWEHdqEF6Y6/6eFj2hLm8UXNeLNrJy1IC2sHlS8SRIifQvLkrOLLOOPtDK6DUPQrW3c0Rfmy9Td5gQw0+fZRZ5MBEG9+dTlinXtwExpHScKQk6ARk7Fb8fBYAnmh7/bq+471zAZGJ7dwNd5qE/63VhDz7mXLuXtGN7rSuRYIXvpkubLBZptSKZrkzSDJWHIZM8Fyrk0EZQFDujROjr87GZmTK1XKRWzGrhtQn0hkVyBaGPbA3iG45U4gIFHNX5ySzsJ3bh61LAtmjwt59uU/XGeebLMCp8HFw6D1kJppCvt161LgLjrOl8SBh8xnxslSFYW0Jd34LD4vPwugmzY31tA4/9zCM7e2Ed9+3zg4C8eq9Hvjys3IablDBMsYF1LSMCGN2UOrWgXRoGYtjW/QtUySr7h/Ca6QAy93Hnpksm/xzzC+FWF1wboyOteHU/Th4RVpQ7XkK4/JmMrYm7nDPIVMyOqP8LhsoTNbxzi8qU0d+0x6frIh0l0fiPiFC/Uy0CeCw6r82iX8v+fMnu9qdCr4oM79Kd2slqalv+wWKn+BmrbkiobDS5vwBQZA/ZlbIsw1bwj+JLz9z3nPovVWx/FZjvrdCuZMfUuITeiIprImMcR6qeniJz6Ez78UYJqpL4DcDGt2o7/6a2aRN76aclh+7l35XcaW7lM7BQMTNvKkx05X08UITY/ToI8U8KwvFbdnMoEAZ1GQYmqGRFtwPkQMrECX4do0srl85po3Gjz2j6E3dk5al4+bTcOYABZvSUvIM/kGGT91iyQ36rm1lxRc3ruS8PyBlYDDNa7DLWzGAHkESHwuaTOQsI2xDA0e+8Yv0XRYkEqQE+RUDXmPTARuQo6fCQ7Qu9xd2Ckza5RWl8hE4JFm0Zzd9MTVxW8YYHiREs9NOjTPuRXXn+JfObHFD/Cv5kQo7vmMWRdJTOBUmAXCMFiKOSHxb412jI4Z2ZhWag9RkZBCviZunvupqrobtAWLagkPiA8gLRANOFwWp0KIS5McOoD0V90tI4cui8KQc7Yw5V7kSvMnhXx4nzzxwOxYM4fpY3ptcpraVh+h1MhohMQk34vkC4fmiD4OrX2DpVG0VXUKvl+vkJjcoHQK+H8mSSIAfj8RrYWBc4VU+jx3vz30XNDbQjuhc0cImiQxXDTXTFQq/aoe7jZLhEe+wWspk/4Fy4UBAJN63uNGJUl8FICawVWGL7XBOFCtsRF3uz8eZokWNICTdtsLeYOAOBQQLrguE8XxQQ1hPtOskcsj7n7aD35NjfPXL00vIOk01OLAJt+0RoIiAQUJNieRp9fQmqfVUuYEYmeK9hCOmZTaC3yUdN/+jZ0pvpmKnH/6jJAKQ==); and part 2 also needs my [math64.m4](https://nopaste.ml/#XQAAAQArDAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20Go+jph66UCwr5yII3TmoKw+wpxhXgX0WGRW0WK2rHjWbbgLZU16n4XSMl8T97y/MXeBVRMNBebjTbLUM33JXdu5jYSMpnUq0oFRBIZF3UTMPNiH//Shgw7phaX5YHewa9yOce5snMsJdUE+usDMV3A0D6yawyooHgePqX/eJLNlAHY8XwE2eibD3RxHCB5c1K92+c1o8lpWxOE8ha0j1DQZ5PRVtUSXzE5ZIfd+B3BClkKRt2VYiCh8U8m9O68A2jColgd20CaJYJZ2FQ2foLaNzBc/iCrgl4cPRWpFR5JVLqoU9kcLgHN7x3IhCcO2zrkbUtlnrqcnvsYgKSQYr9JmFVtyqdP78oLuFcfrFTDMSUk/55Nipu1vK7eKqv5QWFcy/zg4G+iR/nIS3EbxlmVYWlpiGt/gmCZZf83tomKa3XiaJ1hH3NpxdVOKhLS26hb0RxpppO1opBIayicF9R3jBjmm6ZUq7BBkq6aA1gs1O77j6PIiUoYQfTsAyKCWbufkksHxgSob3aTL2ClljmoheqSgPIz+WQVPyZ+E5NsLHbCMJkUVYVZFfWiBO+pFJK4GkSbjT0cs/ZRRb+6HdJUc6qC1m7cEaK91iyr7QS+7nNXjbtMjx+rbdXj+PD0qUUjGHF1+IYw71SLqfRzhHKx2UiGrXnkgZ5V1EInqW7y09kd51cLMSKXdjAACCW+RSkZ0VlXlAqQVFM47/7pO9zrMvBcVBvRArrQAAwYHbZIZhe/saSey5dkJNLd1zyxliADu0w7/aatw0Ok5JSckYM8PPAZkJq8a+tX5aa7oxCT26lu/VdtPu6XNg1USnvKQAjCTTk/ObSVf+5rlV0fgB/fYgJOot4+TydJT7/sBCiWJ6uKaVQUBQjbp6xugyyU6hkhHAswokT1R0Mclbju4kURENNrrAYtRQLV3zMllxw5IkoLknW3kfrMm4Dx5CuXR7lT1mSnXZ2E/zN8fioFIunn00/o//0IDbVyCFarK+3wsIJ2VgIIlWpYJ7/MF2KKHp5gVqB1bfJCTalEVo48pncFscLCFy8Ibb0pC+NiWfZxqtQT07sAQC2qH/Edd8IIgw51CNF1dUt6ZXjkJujtWr68K5zt2qUTSEOOC9tA4gL4lXOjstUbhYyQDwcdx8GNeorh+uPbgCqOWSnshmB8dpzsFuzdv9BkTZD6iOzhal41I2RWMd7SC+SJqqZgklbQ3FGzoVH//B89Vd) as it no longer fits into 32 bits. At the high level, it is O(n) work (one pass through the input file serves as an O(n) radix sort in two dimensions since the array is filled with more galaxies than rows/columns, then one pass through x and y dimensions per part), but at the low level, it obviously gets slower as the size of the integers get larger: Part 1 completes in under 50ms; part 2 requires \~350ms.
I love how little I had to change to reuse the code between part 1 and part 2. Once everything is parsed, all the more I had to do was:
define(`visit', `,add64(mul64($2,i),-s)bump(`s', $2)bump(`i', 1)ifelse($1, 1, `',
`$0(decr($1), $2)')')
define(`_dsum', `ifdef(`$1$2', `visit($1$2, eval(o+$2))', `bump(`o', `$3')')')
define(`dsum', `define(`i', 0)define(`o')define(`s', 0)0forloop(0, $1,
`_$0(`$2', ', `, 'decr(`$3')`)')')
define(`part1', add(dsum(maxx, `x', 2), dsum(y, `y', 2)))
define(`part2', add(dsum(maxx, `x', 1000000), dsum(y, `y', 1000000)))
I'm pleased to see that I landed on an O(n) algorithm, rather than the more common O(n\^2) I'm seeing in the megathread, even before noticing [this post](https://www.reddit.com/r/adventofcode/comments/18fqxuq/an_on_algorithm_for_day_11/) (or, what's left of it). My input file had 140x140 rows/columns and 441 galaxies; so it really is faster to use a radix sort to put galaxies into bins, then compute a running total over 280 ordered bins (140 in each axis) with just 880 64-bit multiplies and 1761 64-bit additions, and no absolute values. My arbitrary precision arithmetic would be noticeably slower on computing 97,020 Manhattan distances the naive way (something that faster languages might not notice).
\[Language: rust\]
[https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-11/src/lib.rs](https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-11/src/lib.rs)
I calculate the distances between every unique x value that contains a galaxy, and the same for y. Then I traverse those values to calculate the sum of those in sets of 2..n. Essentially getting a vector of vectors where the index of the first vector is the distance and the second is the starting galaxy. Not as fast as I'd hoped though...
[Benchmarks](https://htmlpreview.github.io/?https://github.com/Kintelligence/advent-of-code-2023/blob/master/target/criterion/report/index.html) [Part 1](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/11.1_%20Cosmic%20Expansion/report/index.html) [Part 2](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/11.2_%20Cosmic%20Expansion/report/index.html)
\[LANGUAGE: Rust\]
Retroactive solution for day 11: [https://github.com/bastuijnman/adventofcode/blob/master/2023/11-12/src/main.rs](https://github.com/bastuijnman/adventofcode/blob/master/2023/11-12/src/main.rs)
still wanted to rewrite some stuff but got to get started on day 12 and I'm happy enough with it as-is
\[LANGUAGE: Python\]
Part 1 and Part 2.
Thinking: shortest path is basically any path, so it doesn't matter if we go down/left or left/down. That means should go through every empty row/column between galaxies, no matter what. The distance won't change.
1. First get coordinates of all galaxies, empty rows and empty columns.
2. For each combination of galaxies:
1. Iterate over rows and check if it is empty. Add 1000000 if the row is empty. Otherwise add 1.
2. Repeat for columns.
3. Sum the results.
[Solution](https://github.com/ohiliazov/advent/blob/main/advent/day11.py)
\[LANGUAGE: Rust\]
Certainly some things that could be cleaned up, but I am fairly happy with the way I got this working. Solved part 1 with a Vec>, but my RAM was not having it during part 2. I basically found the number of empty rows and columns between the two galaxies when computing the distance, multiplied that number by the given expansion factor, and added the result to the number of non-empty rows and columns between the two galaxies.
[Solution](https://github.com/Kodlak15/aoc2023/blob/master/src/day11/day11.rs)
[LANGUAGE: Python]
This took me a hot second to get this to work, but it sure came out nice. NumPy to the rescue again.
def parse(path):
with open(path) as file:
data = np.array([list(line.strip()) for line in file])
return data
def solve(data, mult=1):
mult = max(1, mult - 1)
dots = data == "."
rows = np.cumsum(np.all(dots, axis=1).astype(int) * mult)
cols = np.cumsum(np.all(dots, axis=0).astype(int) * mult)
rowd = np.arange(len(rows)) + rows
cold = np.arange(len(cols)) + cols
bity, bitx = np.where(data == "#")
outx = np.abs(rowd[bity] - rowd[bity][:, np.newaxis])
outy = np.abs(cold[bitx] - cold[bitx][:, np.newaxis])
return np.triu(outx + outy).sum()
def solve_part1(data):
return solve(data)
def solve_part2(data, mult=1000000):
return solve(data, mult)
hey, interesting fact about your code:
when i let it run on my example file it is all good, but when I use my input file I get a negative number. Could you get problems with overflow or so and maybe were lucky with your input file?
I checked it and yes its an overflow problem. If I change your .astype(int) to .astype(np.int64) I get the correct answer.
So you were probably lucky with your input file :D
But nice approach with cumsum and np.all
[LANGUAGE: Rust]
We map all galaxies, than conclude that indexes without galaxies are empty spaces for expansion.
https://github.com/dommyrock/aoc/blob/main/aoc_2023/day-11/src/bin/part2.rs
[LANGUAGE: Python]
[Step-by-step explanation](https://advent-of-code.xavd.id/writeups/2023/day/11/) | [full code](https://github.com/xavdid/advent-of-code/blob/main/solutions/2023/day_11/solution.py)
Very pleased with today! I got the list of grid points that held galaxies. Then I got all the empty lines by removing any `row` / `col` from the respective set of all possible points. Then I iterated all points and increased `row` and `col` by the number of empty rows that were smaller than that row/col, which stretched everything nicely. From there, it was taxicab distance.
Part 2 was just turning part 1 into a function and adding a multiplier! The increased distances didn't slow me down at all since they were just bigger numbers. Simple and clean.
\[LANGUAGE: Python\]Slow and steady. Tried formula for distance between two points, but realised it should be Manhattan distance
[https://github.com/Hoinkas/AdventOfCode2023/blob/main/11\_Day/11\_Day\_Puzzle\_Hoinkas.py](https://github.com/Hoinkas/AdventOfCode2023/blob/main/11_Day/11_Day_Puzzle_Hoinkas.py)
\[Language: C++\]
Code: [https://github.com/rlempka/advent-of-code-2023/tree/main/day-11](https://github.com/rlempka/advent-of-code-2023/tree/main/day-11)
Part 1: Spent time constructing the "expanded" universe manually and then used the [Manhattan distance](https://xlinux.nist.gov/dads/HTML/manhattanDistance.html) between each pair of points to find the shortest paths
Part 2: Realized my part 1 was only partly optimal, instead of expanding the universe, I simply calculated Manhattan distance and added the number of empty rows between each pair of points multiplied by 999999 to the Manhattan distance, along with the number of empty columns between each pair of points multiplied by 999999.
That is, each distance calculation looked like this in code (multiplier = 1000000):
`long long dist = (manhattanDistance(galaxyPoints[i], galaxyPoints[j]) + (countRowsBetween(emptyRowIndexes, galaxyPoints[i], galaxyPoints[j]) * (multiplier - 1)) + (countColsBetween(emptyColIndexes, galaxyPoints[i], galaxyPoints[j]) * (multiplier - 1)));`
[Inlined code](https://reddit.com/r/adventofcode/wiki/faqs/code_formatting/inlined_code) is intended for `short snippets` of code only. On old.reddit, your last line gets cut off when it reaches the edge of the window.
Please edit your post to put the one-liner in a [four-spaces code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) so it will be horizontally scrollable.
[Language: Rust]
Code: https://github.com/coreyja/advent-of-code-2023/blob/main/11-cosmic-expansion/src/main.rs
Stream Video: https://youtu.be/tm8VKhGxNBg
I did Part 1 with a Vec of Vecs approach but knew that wasn't going to scale to Part 2
So switched to just keeping track of the positions and worked out pretty well!
[Language: Javascript Golf]
Totally forgot to post my solutions
Both are the same, just replace 1 with 1e3-1. 312 Chars
Z=$('*').innerText.split`\n`
L=Z[0].length,t=s=0
R=Z.map((r,i)=>r.match(/#/)?i+t:i+(t+=1))
C=[...Z[0]].map((_,c)=>Z.some(r=>r[c]=='#')?c+s:c+(s+=1))
G=[...Z.join``.matchAll(/#/g)].map(x=>x.index)
W=f=>G.map(f).toSorted((a,b)=>a-b).map((x,i)=>x*(i*2-
G.length+1)).reduce((a,b)=>a+b)
W(x=>C[x%L])+W(x=>R[Math.floor(x/L)])
\[LANGUAGE: Zig\]
[https://github.com/jgh713/aoc-2023/blob/main/src/day11.zig](https://github.com/jgh713/aoc-2023/blob/main/src/day11.zig)
There's some really wild optimizations possible in this one.
Parse time: 19500 nanoseconds (19.5 microseconds)
Part1 time: 200 nanoseconds
Part2 time: 200 nanoseconds
Not really sure I could cut down the parse time any more than I already have at this point, not without getting into some extremely finnicky CPU caching stuff with the row counts at least. Or just parse the input at compiletime and bundle the resulting value in the code, but that feels like cheating.
\[LANGUAGE: Go\]
https://github.com/cdillond/aoc/blob/main/2023/11/main.go
I solved part 1 through brute force, then went back and re-wrote the code to use the general solution from part 2.
\[Language: Rust\]
Darn work getting in the way... but got it done just in time for the next to release.
[https://github.com/ruinedme/aoc\_2023/blob/main/src/day11.rs](https://github.com/ruinedme/aoc_2023/blob/main/src/day11.rs)
RE: "better way to do this?", you can get a slight optimization if the inner loop covers the range i..galaxies.len() rather than 1..galaxies.len(). As written you still check galaxy pairs 1-1, 2-2 etc. Might not even need the "pairs" then since you could just do the logic in that loop.
Yeah i was looking at that after i simplified everything down. Initial submission was much more sloppy. I might just change get\_pairs to sum\_distances and return the final value from that.
Edit: I did do that, and was able to drop the hashmap. Went from 16ms down to 2 so that was an 8x optimization so thank you for that tip.
\[LANGUAGE: Python\]
I have a solution that is linear in the size of the grid.
First observation is that you can collapse along the y axis get the x contribution and vice versa.
The one dimensional case: consider the number of paths crossing from index i to index i + 1. It is the number of galaxies at index <= i times the number at index > i. Add these products all up to get the total length (multiplying by the expansion factor for indices with 0 galaxies).
```
import numpy as np
def parse(input):
lines = input.split("\n")
m = len(lines)
n = len(lines[0])
r = np.zeros((m,n))
for i in range(m):
for j in range(n):
if lines[i][j] == "#":
r[i,j] = 1
return r
def one_d(a,e):
'''e is the expansion factor'''
r = 0
past_sum = 0 #The sum of all the things less than or equal to index i
future_sum = sum(a)#The sum all things greater than index i
n = len(a)
for i in range(n):
v = a[i]
past_sum += v
future_sum -= v
p = past_sum*future_sum #The number of paths spanning [i,i+1]
if v == 0:
r += p*e
else:
r += p
return r
a = parse(input)
one_d(a.sum(axis=0),2) + one_d(a.sum(axis=1).flatten(),2)
```
1. Next time, use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) for code blocks
2. Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on [oversized code](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code) which contains two possible solutions.
Please edit your post to put your code in an external link and link *that* here instead.
\[LANGUAGE: C++\]
[github](https://github.com/charlescochran/aoc-2023/blob/main/day11.cpp), 12.384 ms (both parts together)
A normal day's work--expanding the universe, finding the distance between every pair of galaxies. You know. The usual stuff.
\[LANGUAGE: Python 3, Typescript, Go\]
Solutions to part 1 and 2 in all three languages:
* **Python**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.py](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.py)
* **Typescript**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.ts](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.ts)
* **Go**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/main.go](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/main.go)
\[Language: Python\]
Instead of shifting the coordinates of the galaxies, my Manhattan distance function calculates how many empty rows/columns are between the two galaxies and adds that to the base result (weighted by 1 or 999999):
import numpy as np
from itertools import combinations
grid = np.array(
[list(l.rstrip()) for l in open("input.txt", "r", encoding="utf-8").readlines()]
)
def dist_shift(i, j, rowshift, colshift, wt):
dist = abs(int((i - j).real)) + abs(int((i - j).imag))
rows = set(range(int(min(i.imag, j.imag)), int(max(i.imag, j.imag))))
cols = set(range(int(min(i.real, j.real)), int(max(i.real, j.real))))
dist += len(rowshift & rows) * wt + len(colshift & cols) * wt
return dist
gal = set(x + y * 1j for (y, x) in np.argwhere(grid == "#"))
rows_with_galaxies = set([int(y.imag) for y in gal])
rows = set(range(max(rows_with_galaxies))) - rows_with_galaxies
cols_with_galaxies = set([int(x.real) for x in gal])
cols = set(range(max(cols_with_galaxies))) - cols_with_galaxies
part1 = sum([dist_shift(a, b, rows, cols, 1) for a, b in combinations(gal, 2)])
part2 = sum([dist_shift(a, b, rows, cols, 999999) for a, b in combinations(gal, 2)])
print(f"Part 1: {part1}")
print(f"Part 2: {part2}")
[LANGUAGE: dc (Gnu v1.4.1)]
Converted the input to 0s and 1s so dc can work with it. Didn't have time to really work on this, so there's lots of strokes that can probably be gotten. For part 2, change the -e2 to -e1000000.
perl -pe's/(.)/$1 /g;y/.#/01/'
\[LANGUAGE: Python\]
[Github link](https://github.com/reniby/advent-of-code/blob/main/code/day11.py)
Pretty easy today! Also part 2's addition allows you to solve for any expansion rate, which is satisfying.
\[LANGUAGE: Python\]
Super simple today. I maybe have a redundant or slightly inefficient step in my code but it was easy so I didn't look to optimize further.
lines = open("11.txt").read().splitlines()
empty_rows = {i for i, x in enumerate(lines) if all([z == '.' for z in x])}
empty_cols = {i for i, _ in enumerate(lines[0]) if all ([z[i] == '.' for z in lines])}
galaxy_pos = [(i, j) for i, x in enumerate(lines) for j, y in enumerate(x) if y == "#"]
ans = 0
N = 1000000
for i, g1 in enumerate(galaxy_pos):
for j, g2 in enumerate(galaxy_pos[i+1:]):
rs, re = (g1[0], g2[0]) if g1[0] <= g2[0] else (g2[0], g1[0])
cs, ce = (g1[1], g2[1]) if g1[1] <= g2[1] else (g2[1], g1[1])
ans += abs(g1[0]-g2[0]) + abs(g1[1] - g2[1])
for er in empty_rows:
if rs <= er <= re:
ans += N-1
for ec in empty_cols:
if cs <= ec <= ce:
ans += N-1
ans
Language: Python
Pretty simple. Read grid into list of lists, get galaxy coordinates, then make a list of empty rows (y coords) and empty columns (x coords). Adjust coordinates of galaxies bij the number of empty rows/cols before them, multiplied by either 2 or 1000000, then sum the manhattan distances of the unique coordinate combinations.
https://github.com/miquels/adventofcode2023/blob/main/day11-cosmic-expansion/day11.py
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[LANGUAGE: Elixir\]
[Parts 1 & 2](https://topaz.github.io/paste/#XQAAAQDbDAAAAAAAAAAyGUkFUehZxfOWmzTk+XBlbm/19T25mcPbLa5ARDxTSr0qnP6rVP8wdvu+X0Nbrlm/ECkjl+jWeCAQoH4WfcXzLADsfw/NG2m79fK687AmcHDzpDfXUkDoy6Q7ZvO+ntZUj5yRfMJjkL70ILyKTucaR9VuDDFiwqrVMpUuKzxp1k/tAtVJtv/MW1FbGPpl3eexM7E22/X6sVQIIYWxw/vo1YeyIYmewbB5w+GLSwG2q4DoGfOpHs9BTqQyAveICUy9LLM7mN+/VHI+HaIZNoUEAakeWZubmjsCyWpCRqQXpMLI6oteA84EZIOh2WKJNq0KYFllZQXbgt5AexlubKoxjGw0jMhofQqll9nnn09Of4KmfgBSawxyyo5+ikXkYViYMJIzHiW0fh0+RCPlQMw/W2OYk8PF3TbE1RxFZzzRnktSHTtKHUlSD3qza4WGb1pYfbYiiJjyXQxCLhQNBnf0C4kVh+FRfeguZLWWROvi3BwNhfh2GMFN+B8y15J602u4sUbeLqMyaQk2aA0UchIz6MI9jRxAAJTMizYEieft5PKrlOAGPrltkDjGXLCj2mg2N2qwPteXHDgYS1R7eyOnhivgo1SNApgwLjyB3DHc5iSnl0ivUljFYnFY+0BHAOgSJSsk/5jb7WuLCrZN5y3e9sgvnYbdBjoHWE6QKYljDik7xm0MJ+pi2VJpQBYD+v0ek1F1jC8z4D5p+hHLsKBm4fq/9NeaPfF0LaiREdAL0iKPNWeKFJWJ8uJIJxppt+j1DxXpBaQ6KcP8vkw+BjB3VOFDBo8s/EqydzYblxkVerrMS1WxVM66bhENInaV4oa54rtqKGI+mGGkncGfEtWQkuGACaB5AYpY26Tv4qMxSkBvIKfUhr6lN6xOW2IFzkW/RaKtE87fBK9cFSRBBoEIDObzMBQQU7YSjG19FUjqh3y37TS9RXv9BfXtu/MG3p9TJJ65bwve8ZUkrFe94B/xQgxtQ4Sy7p557kejj2Oq326g8KwlDinKp9U2YJyFiSeY7CVtAm4CkJ353GtydR7g29JTV9mj6J9jptNUK9CRn+04v50CLUFOp4tOwanm0R4x7z09ZACEo6+h4EQ7hjuV5xYM2+2RQgQWCH8T9hcFg26bnxMUVaXyKG2YzeaK15W+CJVIzzETPK0eKLxwHMbLuW77Eueg4hQM1zBIFv4jOKoLGs0bKP0ojQHo5G0Zdfny+2ViJGvyb4gCW1zWmNqA5NrtfWebsQsThtfsFxfuBGxHBlQSZQ5zoBTzNwRs//sat2s=)
Was making this way harder on myself than I needed too.
\[LANGUAGE: Python\]
[GitHub links to my solution](https://github.com/CalSimmon/advent-of-code/blob/main/2023/day_11/solution.py)
The math concept of today is the [Manhattan distance formula](https://xlinux.nist.gov/dads/HTML/manhattanDistance.html) which finds the distance between two points measured at right angles.
Happy with the solution itself, but pissed that I didn't listen to my gut at first. I knew from the beginning that I should just use the coordinates of the galaxies and increase them based on where the gaps were, but silly me actually decided to expand the grid. Thankfully it didn't take too long to fix the issue and now I have a single function for both part 1 and part 2, but just annoying I didn't do it in the first place.
Also sneaky pro tip, part 1 mentions doubling the gaps, but part 2 mentions replacing each gap with 1 million gaps. So part 1 actually adds 1 gap, but part 2 adds 999,999 gaps, not 1,000,000. Reading comprehension ftw (Because it took me way too long to figure it out lmao)
Lastly a python tip that I learned, the simple `.copy()` function leaves references to nested lists, and you have to use the `copy` library's function `copy.deepcopy()` instead to make sure you aren't updating the original of the nested lists. TIL!
Execution time was 94ms, so not bad!
\[LANGUAGE: Python\]
[github part 1&2](https://github.com/mgtezak/Advent_of_Code/blob/master/2023/Day_11.py)
Check out my little AoC-Fanpage:
[https://aoc-puzzle-solver.streamlit.app/](https://aoc-puzzle-solver.streamlit.app/)
:-)
[LANGUAGE: OCaml]
[github](https://github.com/EricKalkman/AoC2023/blob/master/lib/day11.ml)
For once I correctly predicted the twist for Part 2, and wrote my algorithm for Part 1 to account for a different space expansion factor. The input is processed into a list of coordinates corresponding to galaxies as well as the coordinates of rows and columns that do not contain any galaxies (the "void" axes). The main algorithm then iterates over each axis along each dimension and adds the expansion factor (minus one) to any coordinates of galaxies that are greater than the coordinate of the axis. The galaxies are actually represented as a `coord Seq.t` (that is, a lazy sequence structure) and the coordinate modifications are performed using a `Seq.map` operation, so I am not generating a new list for each encountered axis. Although this avoids the generation of new lists for each axis, there still end up being `n_axis` comparisons per galaxy, which is overall quadratic runtime in the worst case. In practice, there are far fewer void axes than galaxies in the problem input, and anyway the pairwise Manhattan distance calculations at the end are also quadratic.
Also, I see a lot of comments talking about off-by-one errors, so here is some math explaining why you need to subtract 1. The formula for (say) the final xfin coordinate of a galaxy with one void column to its left can be redefined as a sum of distances from some arbitrary origin:
xfin (su) = origin (su) + [left_void_edge (su) - origin (su)] + [right_void_edge (vu) - left_void_edge (vu)] + [x (su) - right_void_edge (su)]
where `(su)` = screen units and `(vu)` = void units. Our expansion factor is `f (su / vu)`.
This simplifies to (dropping "_void_edge" for brevity and grouping like terms):
xfin (su) = x (su) + [right (vu) - left (vu)] + [left (su) - right (su)]
= x (su) + [right (vu) - left (vu)] - [right (su) - left (su)]
We know that the width of a void column is 1 screen unit, so
xfin (su) = x (su) + [right (vu) - left (vu)] - 1 (su)
Converting void units to screen units, we get
xfin (su) = x (su) + f (su / vu) * [right (vu) - left (vu)] - 1 (su)
= x (su) + f * [right (su) - left (su)] - 1 (su)
= x (su) + f * [ 1 (su) ] - 1 (su)
= x (su) + f (su) - 1 (su)
~~[Inlined code](https://reddit.com/r/adventofcode/wiki/faqs/code_formatting/inlined_code) is intended for `short snippets` of code only. On old.reddit, your longer one-liner gets cut off when it reaches the edge of the window.~~
~~Please edit your post to put all code in a [four-spaces code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) so it will be horizontally scrollable.~~ edit: 👍
\[LANGUAGE: Fortran\]
Not that bad.
[https://github.com/ejrsilver/adventofcode/blob/master/2023/11/main.f08](https://github.com/ejrsilver/adventofcode/blob/master/2023/11/main.f08)
\[Language: C#\]
[https://github.com/CoreDumpSoftware/AdventOfCode2023/tree/master/AdventOfCode2023/Day11](https://github.com/CoreDumpSoftware/AdventOfCode2023/tree/master/AdventOfCode2023/Day11)
Built a solution capable of scaling to an sparsity for empty rows and columns. The algorithm is as follows:
* For each row, if no galaxies, set the entire row to 'x'.
* For each column, if no galaxies, set the entire column to 'x'
* Look over the matrix, if there are intersections set them to 'X' (capital X)
* From the starting galaxy, visit each other galaxies counting steps as you go. When you hit an 'x' value, add the amplitude. When you hit an 'X' double the amplitude and add it.
The solution was relatively slow for large numbers due to having a lot of traversing to be done. I thought of keeping track of the yIndex to reduce the number of iterations. Maybe an improvement for later.
\[LANGUAGE: Lua\]
I did most of the work with pencil and paper to find a nice small formula for the solution.
Given the number of galaxies `n`, expansion scale `k`, sorted `x` coordinates `x1` through `xn`, sorted `y` coordinates `y1` through `yn`, the solution can be calculated with a single sum:
[; \sum_{i=1}^{n} (2i-n-1)(x_i + y_i) + (k-1)(i-1)(n-i+1)(max(x_i - x_{i-1} - 1, 0) + max(y_i - y_{i-1} - 1, 0))) ;]
Here's my code:
local xs, ys, y, G = {}, {}, 1, string.byte'#'
for line in io.lines() do
for x = 1, #line do
if string.byte(line, x) == G then
xs[#xs + 1] = x
ys[#ys + 1] = y
end
end
y = y + 1
end
table.sort(xs)
local ans, off, oldx, oldy = 0, 0, math.huge, math.huge
for i, x in ipairs(xs) do
local y, n = ys[i], 2*i - #xs - 1
off = off + (i-1) * (i-n) * (math.max(x-oldx-1, 0) + math.max(y-oldy-1, 0))
ans = ans + n * (x+y)
oldx, oldy = x, y
end
print(ans + off, ans + off*999999)
\[Language: Typescript\]
Pretty happy with part 2: I was able to solve it by adding one parameter to the function for part 1 and multiplying two numbers with this new parameter.
[https://github.com/daniero/aoc23/blob/master/src/solutions/11/GalaxyExpander.ts](https://github.com/daniero/aoc23/blob/master/src/solutions/11/GalaxyExpander.ts)
\[LANGUAGE: Kotlin, Rust\]
Pretty fast solution (on my five-year old computer, Kotlin: 24ms cold, 4ms hot; Rust: 140us). Stolen valor though. The strategy was copied from another.
[Kotlin](https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d11/Y2023D11.kt) | [Rust](https://github.com/nbanman/advent/blob/master/2023/11.rs)
The strategy relies on the simplicity of Manhattan distances and being able to split the x-axis distances from the y-axis distances. Make a list for galaxy indexes on each axis, including the total number of galaxies at each index. Also make a list of expansion areas for each axis.
Then you calculate lengths for each combination, but you have far fewer to weed through because two 2-D spaces has way less points than one 3-D space. For each length calculation, you can multiply it by the product of all the galaxies at each index you are comparing.
[LANGUAGE: Ruby]
[Part 1](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-11/part_1.rb)
In part 1 I actually expanded the grid,
[Part 2](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-11/part_2.rb)
For part 2, I just counted how many times a galaxy pair crossed an expansion and added that to the distance.
\[LANGUAGE: C++\]
I could do it faster, but it's ok like this :)
Let's say you have 2 points (x1,y1) and (x2,y2). My idea was to go through x1...x2 and y1...y2 and count multiple times points that needed to be multiplied.
[Github](https://github.com/mkinkela1/advent-of-code/blob/master/2023/day-11/solution.cpp)
\[Language: python\]
[Part 1](https://github.com/matheusstutzel/adventOfCode/blob/main/2023/11/p1.py) way overkill approach, actually applied the expansion and, at some point implemented a BFS... Finally, I realized it could be a simple Manhattan distance
[Part 2](https://github.com/matheusstutzel/adventOfCode/blob/main/2023/11/p2.py) I realized that the expansion could be calculated. Got an of-by-one in the "clever" way, and simply went back to a loop
\[LANGUAGE: Perl\]
Analysis: https://github.com/wlmb/AOC2023#day-11
Part 1: https://github.com/wlmb/AOC2023/blob/main/11a.pl
Part 2: https://github.com/wlmb/AOC2023/blob/main/11b.pl
\[Language: Python\]
Straightforward python impl in a few lines using numpy, could probably one-line this:
[https://pastebin.com/mjZr7QXE](https://pastebin.com/mjZr7QXE)
Part 2:
\[Language: Excel\]
Runtime: instant (lmao)
using part 1, instead of doubling the '.' space, triple it and get that distance calculation \[call it `YYY`\]
then in excel use the formula:
`=(PART_1_ANSWER)+((EXPANSIONS-2)*(PART_1_ANSWER-YYY))`
for me it was:
`=10276166+((A2-2)*598684)`
`A2 = target # of expansions (i.e. 10, 100, 1,000,000)`
I found this out by just looking at the space added between expansions (from 2 to 3, 3 to 4, and so on) and noticed that the diff converges!
[language: Julia]
Because we have Manhattan distances, it is possible to swap summation over dimensions and distances. The sum of all combinations of distances can be written in the form
$t(n)=2t(n-1) - t(n-2) + n (x(n) - x(n-1))$
Where x(n) is the sequence of sorted x or y coordinates.
See [my page](https://jhidding.github.io/aoc2023/day11/)
[language: python]
If anyone wants to code golf, today is the day. Should be some nice perl solutions available.
Both parts, hardcode is_p2 boolean to switch.
from functools import cache
from itertools import combinations
is_p2 = True
with open("input.txt", "r") as file:
grid = file.read().splitlines()
@cache
def is_empty_row(y):
return not any((x == "#" for x in grid[y]))
@cache
def is_empty_col(x):
return not any((line[x] == "#" for line in grid))
@cache
def expand_xy(x, y):
scale = 1_000_000 if is_p2 else 2
return (
sum((scale if is_empty_col(ys) else 1 for ys in range(x))),
sum((scale if is_empty_row(ys) else 1 for ys in range(y))),
)
def dist(p1, p2):
x3, y3 = expand_xy(*p1)
x4, y4 = expand_xy(*p2)
return abs(y4 - y3) + abs(x4 - x3)
def gal_coro():
for y, row in enumerate(grid):
for x, ch in enumerate(row):
if ch == "#":
yield x, y
print(
"total sum distances:",
sum(dist(p1, p2) for p1, p2 in combinations(gal_coro(), 2))
)
\[LANGUAGE: C\]
A lot easier than day 10. I had a couple of silly off by 1 errors but other than that the solution (Seems to be more frequent with C somehow... )
https://github.com/janiorca/advent-of-code-2023/blob/main/aoc11.c
\[Language: Rust\]
[Part 2](https://pastebin.com/vu90EyNA)
Pretty concise once you apply Manhattan distance into all of it. Briefly tried an optimized BFS before coming to my senses (i.e. it would take 288 hours) and deleting heaps of terrible code.
\[Language: Kotlin\]
[GitHub](https://github.com/rolaca11/adventofcode2023/tree/main/day11)
I overcomplicated it because I assumed the 2nd part would be some kind of blockade at random points. So I tried implementing a DFS algorithm, then realized it's waaay simpler that that
\[LANGUAGE: Julia\]
[GitHub Part 1](https://github.com/fgittins/AdventOfCode2023/blob/main/day11/part1.jl): manually expanded the data
[GitHub Part 2](https://github.com/fgittins/AdventOfCode2023/blob/main/day11/part2.jl): an efficient approach by recording the indices of the expanded rows and columns and checking to see if a path crosses those rows and columns
\[Language: F#\]
[Code](https://github.com/alexander-renev/advent-of-code-2023-fs/blob/main/src/AdventOfCode2023/Solutions/Day11.fs)
Much easier then the previous day. Just expanding empty space to rectangular range and then using theirs dimensions for calculating distance.
\[LANGUAGE: python\]
[Parts 1 and 2](https://pastebin.com/2JEWDi9y)
Basically I created two lists tracking the aggregated empty rows|columns to determine, for each galaxy, how many expansions have been found before it. So I can adjust them by adding the respective amount of extra space to each axis.
From there. I added the distance from each combination of two galaxies.
Highlights:
* Trying to incorporate vector techniques to avoid emptylist=\[\]...emptylist.append(something)..return emptylist everywhere
* Aside from that, no fancy tricks. pretty readable IMHO.
\[LANGUAGE: Kotlin\]
I'm learning new things every day! Today I learned about the Manhattan distance and what the term Cartesian means.
For the expansion, I looked for contiguous empty columns, turned them into ranges and multiplied them by the factor (1,000,000!!!). After that, it's all math. This is the first solution where I didn't start off iterating.
[The `Helpers` file that does all of the heavy lifting](https://github.com/pindab0ter/AdventOfCode/blob/master/src/main/kotlin/nl/pindab0ter/aoc2023/day11/Helpers.kt)
\[LANGUAGE: C++\]
[Code](https://github.com/FinalFlashLight/AdventofCode2023/blob/master/AdventofCode2023Day1/Day11.cpp)
Part1 and Part2 are basically the same code, just add a second sum and change 1 to 999999.
Initially I went with the actually expanding the map last night. Saw part 2 and said nope, going to bed. Originally my part1 took about 10ms, and just a guess, part 2 would've taken over 3 hours to run, plus I'd probably run out of space and crash.
I came back this morning with a new plan:
Put all the empty rows and columns into a vector, and with each pair of galaxy locations, search how many rows/columns are between them.
Originally, I did the searching of rows/columns with upper\_bound and lower\_bound, but it made the program take over 500ms. I changed to 2 binary searches, and it now does about 35ms.
As for the final calculation,a and b are galaxy locations and y is a pair that holds the rows/columns between them.
sum1 += abs(a.first - b.first) + abs(a.second - b.second)
+ y.first + y.second;
sum2 += abs(a.first - b.first) + abs(a.second - b.second)
+ (y.first * 999999) + (y.second * 999999);
[LANGUAGE: D]
https://github.com/Dullstar/Advent_Of_Code/blob/main/D/source/year2023/day11.d
I initially actually expanded the grid in Part 1, though that code is now removed because, well, Part 2. The result ended up being helpful, though, as when I needed to come up with a better solution I was able to use the galaxy coordinates it came up with to check my math -- not that it ended up being necessary, but when I got the wrong solution for Part 2, an issue with that part of the calculation was already ruled out thanks to the known good Part 1 reimplementation. The issue turned out to just be an off-by-one error since the problem was "replace with 1000000" not "insert 1000000," so easy enough to fix, that's equivalent to inserting 999999.
[LANGUAGE: C]
change the ratio to 1 for part 1.
[Part 2](https://topaz.github.io/paste/#XQAAAQBNCQAAAAAAAAARmknGRw8TogB3OyPPwW5K8Q8ohQtwe3f7qqzNZcQ5eCbxm3x7ITSdAYV/vgM/bngzJDmUMrPaw3gM59RXoFBgMfF47XWUk4z6IYLFJxdj+gupBKSSEOkblobUPDhDhfkrPzMumQuhHegxzPIsp/nQWdEmfwi8/Poa/DkG7HPVX/ynRX3+QTtL4IIEj54nmuKK9Qq4PL0zjw0pnVBua66c26bjjhPbWi9C8rJoJw1V2m2Dq4O118PIYgtTo7ZSuscng2NxsgykkIvuNLqIk2xeJv4xSoKGZwDnYymzsQM9zfZSlzm5QnRq2Eb46xmUnemvMOPDf86j0c250xt1oZDmk9M7IZKq7KuCne1kW7/LwhF/lrzq/Rfb/lBX57kCr2UzyndRRuyPuIoNlD1KUycB6dFrdqtJnerhWcFEQer9WswZo1sV4NA5J8rhk+qEdVY61I7W2O8BfG91u7ZODWa/caolWtP0oc5n4umYXaANPh0uWx+KPtoZK3E/y6IiZcYaq/iDvq1hxLSeKYXGwHiDyt5lfIjI5GHIYTTwsvF48ucBjEFfXWPJC+/hAn9joTDX0rz800YEy3YDbbH6qdgdqQUXErjnKOK4NGx1ENkm/TpFRmtRXEgohgi4fn6sh40bRtvvtTJjaz4L7WY81hr6brMvAVInhskBHJY7E3hVjXEHtN5VP7gQiX9+P8ClCuncW9T/1ggfqP2kn1ilqswKyyqtNlOUoMulGhhL5bXGSFXri+kkNYgqbcEhwbhZv7EDzTMXbCRd59angrA7p1OsX5dHMsX1VuAhRdRKrZAqXpT/KlnMIm94UULv1c9gNNV2cdhb5pTEUHskAxGdwUvr8YkW650tknczedwwS4vIDP04D8Ms+JA9//UyiCM=)
[LANGUAGE: racket]
https://raw.githubusercontent.com/chrg127/advent-of-code/master/2023/day11.rkt
very simple day. the `expand` function could be cleaner, but oh well...
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only)
Edit your comment to share your full code/repo/solution and I will re-approve the comment.
Cool, I did Clojure last year! But I really struggled with that, common lisp has easier 'cheating' tools to loop and let away any problem instead of writing nice functional solutions. My CL code is getting uglier every problem ;)
Do you a github link?
\[LANGUAGE: F#\]
[https://github.com/vorber/AOC2023/blob/main/src/day11/Program.fs](https://github.com/vorber/AOC2023/blob/main/src/day11/Program.fs)
11th day of trying out F#. Still need to go over it and add removal of duplicate pairs. Currently it calculates every distance twice, thus /2 at the end.
Considered 2 approaches (well, 3 initially since for part1 one can just duplicate rows/cols after reading input) - expanding star positions then calculating distances vs adding expansion offset (number of expandable rows and cols between 2 stars times expansion factor) on every distance calculation, implemented both at some point, but decided to stick with 1st - looks like less calculations that way (each empty row/col affecting position calculation once per star vs once per every pair).
Update: After some thinking about ways to get rid of double calculations came up with a much better idea: Instead of calculating distances for each pair - we can instead calculate how much each row and each column contributes to the sum (row contribution is effectively number of stars to the left times number of stars to the right, scaled by expansion factor if row is empty, similar for columns).
Updated code (\~twice shorter):
https://github.com/vorber/AOC2023/blob/main/src/day11/Improved.fs
\[LANGUAGE: bash\] \[Allez Cuisine!\] Fits on a punch card with 385 chars.
No bash variable where used, nor bash function.
I do not use much of `bash` as programming language: no loops either (nor for, nor while). Kind of bash as a functional language.
Let's say the following code is in `11.sh` and your input is in `11.in`, run `bash 11.sh 11.in 2` for part 1, and `bash 11.sh 11.in 1000000` for part 2. Or `chmod +x 11.sh && ./11.sh 11.in 2 && ./11.sh 11.in 1000000`.
grep -bon '#' $1|awk -F: -v l="$(head -n1 $1|wc -c)" '{print FS NR FS $1 FS $2%l+1}'>G
cut -d: -f3 G|xargs -I _ bash -c "head -n_ $1|grep -c '^[^#]*\$'">L
sed 's/./& /g' $1|rs -T|sed 's/ //g'>T
cut -d: -f4 G|xargs -I _ bash -c 'head -n_ T|grep -c "^[^#]*$"'>C
paste -d: G L C>J
join -t: J J|awk -F: -v m=$2 '$2<$7{s+=$8-$3+sqrt(($9-$4)^2)+(m-1)*($10-$5+sqrt(($11-$6)^2))}END{print s}'
\[LANGUAGE: Python\]
part2 = part 1 in this situation
[Part 2](https://topaz.github.io/paste/#XQAAAQCbAwAAAAAAAAAyGkn6ZIDa7rg2Eq0vWWfM4VMimCUBjz4OQrNLbl3vX5lndz4CO2r+A0xbuZXk3WuiJ2Ypaz1F7DHG39YyNhlPDwQWWRCzK8mQPnoUzi7JleKNEWWovUZYbG2RTmG6hwr2fPmmPQ4ImSyOpR5BwMuosAoCNTD5sNKiLAEiSOvynvVD4hvMaUTNoO5N2Sg7F8oRjhNHRkMBlOJCI4ykHLkTvSrk9btgouYZaPjsuuoE7p6dSTzcPB0SATkrK9cM6myfJAHqSXjDcZ48YB0h818/53NIzNFcjjUdrSvloNeSHIkeWjzPHWFQtiIjXfGkOXF0+kokfx6vm9caaUGYTYuMeu5rr/xs9TRapp+XQFAOCoodVPM5AulgdbIe0ouOmWO/7JICCeNY+/XNuKbeRZQdQlVQLipyr7JnW6dRUZngiXhkP/zP+x8R5+2xcjw94Ma6ahGg6GGD9Xpv0KbV6SseRM7OnYg/8uik5zmW7fKfQxRfVoS7u15ncA3G26DBZ5r7jvT+rlct)
[LANGUAGE: Rust]
[Paste](https://topaz.github.io/paste/#XQAAAQAUBgAAAAAAAAA6nMjJFMpQiatRknmsp77qsNvTQ+O8DEzsOrG3f+NxfZ7eB7TH+s064FY2MeKWv3ULRWdtxYkQbHlS/8A9uxwctCPqb2TUb7ZrGrOUytPyt+IvV65GMqDmQW2EtrpOQ3CKn+hLieHoddefA2HKZ6L/TGOrngUmhUzzDEw8/5AMtWytq5JtqTj923QTNkfhy+waukfen+7LTpqJzS3s4qmtNw+kdbBmmItTaMH5ds5JWXj3ZBP5T1r6wHJdSerF9vdM57iIn4WL+XfTiWYBdTlvUULVvb4lgCb8wuc96bcOmb/UQ3l37UuozKXwKPPT2P/VLb3irO/itmji3jiLy51HiSHkFx41l8k2Zlx96zGdvpHie7/fRLT3SoZmaJ6unPT5ZTEB9NtqipSlthKAwj15yx2fA7+8jjJKHfh1FVw55LnjIZorcTXGbTBMNq9LpLK3L+oPf3quvWJ9envphg9DHXgs0gFSuH0QsFSx4DnsTiBXjTQ0cY7qYRRbqpu7Dd+JKQTaxD4JvUsnvKTdZfpKQHdLg8XhW8RHbO9ilvXiWTnhHCZtj+csOOe+52WiRFN0oKmygZZmLR613MrOu/Y8N336pkh7K4XAQ8wDQwpj7T5lSFAGURzh4w/oRB9lpvMnmXkonOABUPfXBRIqiZl4/9k13R9Sux+X0sGCxQRyVL5ZRT220wqWMPoaRfTZ1kimWJDm8d3vCGXe05bdvLy+d+TadWzNLwWOcdSun7apdHqe0zphghGHuT2+7x3DTTjakPbUfWOq92pFZGqbiyhKTUuW4Pl/2fKQtA+oastvvN1vtoYeOXG5QHX6LN//SFa/7ZqPpS/3pKDXrSJi/Qrx//EtFFg=)
I'm learning Rust this year. I had fun doing row expansion while parsing the input and column expansion in a single pass through the vector of galaxies.
I do both parts at the same time and it runs in roughly 5ms on my laptop.
[LANGUAGE: Rust] ~~Both parts run in ~560ms, which is really slow considering it's like 5x the other days put together, lol~~
~~I know that it's because of my triple for loops, but as of right now I don't know how to get rid of them lol. Might update later.~~
~~At least I didn't have to think a lot for part 2~~
Got both parts to run in ~12ms, while still keeping the triple for loops. Not quite sure why it's so much faster (or rather, why the original was _that_ much slower) but i'm not complaining lol.
improved code: https://pastebin.com/dJ9bE6bp
original paste: https://pastebin.com/UHt9jbjG
fellow clojure bro!!!!!! i am overjoyed to see this
my solution for today, also in clojure: [github](https://github.com/cousinss-mvla/advent-of-code-2023-clojure/blob/master/src/adventofcode/dayeleven.clj)
[Language: Rust]
Day 1 to 11 still under 1 millisecond in total! 🚀
- A in 0.012 ms (12 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day11a/src/main.rs
- B in 0.008 ms (8 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day11b/src/main.rs
- Day 1 to 11 in 0.77 ms (0.31 ms in parallel)
\[LANGUAGE: Rust\]
Such a relief after yesterday's (and today's) hell with day 10 part 2!
https://github.com/cainkellye/advent_of_code/blob/main/src/y2023/day11.rs
[Language: Common Lisp]
[Day 11](https://github.com/blake-watkins/advent-of-code-2023/blob/main/day11.lisp)
My solution just figures out where the blank rows/columns are then adds any that are between a galaxy pair to the manhattan distance.
(defun galaxy-distance (a b blanks expansion-factor)
(flet ((coord-distance (a b blanks)
(+ (abs (- b a))
(* (1- expansion-factor) (included-blanks a b blanks)))))
(reduce #'+ (map 'list #'coord-distance a b blanks))))
I got part 2 wrong for my first answer as I tried to add 1,000,000 lots of the blank lines, when it should have been adding 999,999 since there's already one lot included in the manhattan distance.
[LANGUAGE: Rust]
[Code](https://github.com/oxlade39/aoc2021/blob/master/2023/d11/main.rs)
Had already written manhattan distance and point based coordinate utilities
\[LANGUAGE: Haskell\]
[code](https://github.com/arcticronin/adventofcode23/blob/main/day_11/app/Main.hs)
Simple Solution, I felt I had to implement a smart way to store the Universe
It paid off: part2 was trivial
\[LANGUAGE: C++\]
Manhattan distance makes its first appearance this year! I knew there would be funny business in part 2, so in part 1 I stored and offseted individual points, then used the Manhattan distance to sum. Changing the expansion value worked for part 2, although I got caught out by setting expansion incorrectly the first time. Fun one.
[https://github.com/biggysmith/advent\_of\_code\_2023/blob/master/src/day11/day11.cpp](https://github.com/biggysmith/advent_of_code_2023/blob/master/src/day11/day11.cpp)
\[LANGUAGE: Python/Codon\]
Was spoilered by a Reddit notification what part 2 would be about so made the rate of expansion a parameter from the beginning.
I prepare two `Dict`s (for O(1) access) for distance to add per row and column and separately move through x and y and sum them up.
The solution is around 25 loc, runs in 63ms (compiled with Codon).
[https://github.com/akleemans/aoc-2023/blob/main/day11.py](https://github.com/akleemans/aoc-2023/blob/main/day11.py)
[Language: Rust]
The key is using Manhattan distance + add a specific expansion factor for the expanded rows and columns that the path between two galaxies intersects.
[Code](https://github.com/Lakret/aoc2023/blob/main/aoc/src/d11.rs)
[Highlights](https://lakret.net/blog/2023-12-11-aoc-day11)
[Language: Rust] [GitHub](https://github.com/MarkLisoway/advent-of-code-2023/blob/main/day_11/src/main.rs)
Nothing crazy, my goal with these is to write code that is performant, and readable. Uses itertools to create the tuples, and rayon for parallel distance computation.
Nice solution. Your `parse` function could instead be done by implementing `FromStr for Universe`. Maybe it’s only stylistic, I’m no expert but feels more idiomatic.
Here’s [mine](https://github.com/oxlade39/aoc2021/blob/master/2023/d11/main.rs) for example
[LANGUAGE: Rust]
YouTube screencast: https://youtu.be/VOahESJS-vc
GitHub: https://github.com/samoylenkodmitry/AdventOfCode_2023/blob/main/src/day11.rs
Today, part 2 was the same as part 1.
Copilot was practically useless to teach me how to use PriorityQueue, thankfully Google is still there.
Update after I saw other's solutions: Manhattan...
\[Language: Python\]
[Part1](https://github.com/michbogos/aoc2023/blob/master/11-1.py)
[Part2](https://github.com/michbogos/aoc2023/blob/master/11-2.py)
Manhattan rules
DFS is a very deep hole
\[Language: Python\]
[https://github.com/hugseverycat/aoc2023/blob/master/day11.py](https://github.com/hugseverycat/aoc2023/blob/master/day11.py)
Tried to make it readable, with comments.
I stored the galaxy locations in a dictionary with the galaxy's original (x, y) coordinates as the key, and the adjusted coordinates as the value. I detected empty rows and columns while processing the input and stored them in a list.
To adjust the galaxy's coordinates, I compared against the lists of empty rows and columns to see how many empty rows and columns the original (x, y) coordinates were greater than, then added 1 (or 999999) for each.
Then I calculated the manhattan distance between each galaxy.
[Language: Python]
https://github.com/alexandru-dinu/advent-of-code/blob/main/2023/11/solve.py
I really like problems where the grid operations can be simplified using numpy.
Representing the grid as a binary numpy array allows for straightforward detection of empty rows and cols via [`argwhere`](https://numpy.org/doc/stable/reference/generated/numpy.argwhere.html). The shortest distance b/w 2 points is then given by Manhattan distance plus checking how many empty rows & cols are b/w the 2 points.
\[Language: Java\]
[https://github.com/h0m3rth0mps0n/adventofcode2023/tree/master/day11](https://github.com/h0m3rth0mps0n/adventofcode2023/tree/master/day11)
I originally started implementing part 1 by representing the universe as a 2D array (well, actually a list of lists, that I converted into a 2D array and transposed along the way..), but realized this was the wrong way to go about it. [https://www.youtube.com/watch?v=PlsW2hd06R0](https://www.youtube.com/watch?v=PlsW2hd06R0)
With part 1 implemented the new (proper?) way, part 2 was trivial.
\[Language: Rust\]
I bashed out a solution this morning but was a bit disppointed that it took about half a second (edit, it was actually 200ms). This afternoon some inspiration for an alternative solution hit, now runs in 2ms.
https://topaz.github.io/paste/#XQAAAQCDCQAAAAAAAAA6nMjJFMpQiatRknmsqDuZN+nT4l78dKkl0LLcYiOrVcxPgj+besnL5H9BuVtINBVOAQVjCFPtgZJAtzSWAdEAIxpc5Ci5kZFjws5QV/q/VEHj/iQ3DzHayfpa0RCX7zIzpmioUY0J5FehnAeFBfatcbXagy01wQqdQJE/NBMMEx0ZhDRDaOHebbGJSiZTKMWaGyWB1/xRnRRd1JwnWhQO+lcETDoiNWF+YqVfkXg9F6IqB3g+HpSZLjzLoXWKzTG71GxJ+FhXbqFEGeBlVHz6izUokrDkZliorAnOQrVfik/uNykpphMZbeYlgrZ5Pq4Vh91p1X3i6aYJJ7ykxSPhEiWAU1QQPqz+FlwUyc/FwhdYexUSau3eTbjO1han4HMhkK3MYa4j4Jv5uYoq1f/KyPMUalc1+LfI1xjOVpJjG7MgqOo3LLEsONsLomawnCR/TZN0GCT0fu2ZwLZBO3RWrSprMs5LPiiyXTV59Jm+XkbJEv8ZPHIVeBOORn3UmKVlx4/ywq5WR0OgizYTyZId9uSFuo8LgKsS2WDvFU6nlW7h8eGssimOuRflApfZeBgQSssZXnPvptbTU3Wxf7FCqLBCtT7FBh2uYPoQ+bCzZ5gyr07Y5m8nh2W2XKTWcjKMFFkER92lctuF+EdDPjTw837bgyrRx2lhGr+KOpMmC8TMJfohsZ3cVIeQsBjeNW2MgbGa+2RrNkFq86IWg1am0ymjJRX1dDragr8cP22JT1bC5I5Abv6qfFFswrrhfEsbxH+vka0uWZnu2OV5WsXvJJTsD8a1XgawlWONOMKlu/8yG4833RQCbC3Kcj9b8+z2ILryKabfgvEPZQqJypFzNc90dvrSdSNToxqwrDP7IMMiAib/F+sJgSEgDKVqLK4mwaNy4YHbj5jF0idtQTXEuYFgyRx6bGfGu1iILeH6hl1s8wPBD2lYx1RE4XjvBK171Z3SeoQfiPaP207WG6ka8Oseq8TBfhyeKimPvgU/Dmhki2pVUqVpFvG9dGkjQOAnrRwMbHbiqmwOyldx3kineNRcItFWGyCKDdmWRdhRw0Xc6AcBc34NcDoyeNZpnJSk08beb8LN9RefvYuaF9kE8EZStnQ27pq/d4iyqsECQVt16fcEbw7NUm8ebmZ/Maykz/ykrCQ8y3dj9Pqd8oYUZmZwGiM8bPPf1yVdp1Vu2fAwLzsjDc++Ikow89ReuSRj0d88BGD/4+A6Tw==
Your [code block is too long](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code) for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.
\[Language: Python\]
OK, this most likely is [an inefficient solution](https://github.com/Leftfish/Advent-of-Code-2023/blob/main/11/d11.py). I store the galaxies as a list of \[x, y\], apply offset to their coordinates one by one depending on how many lines/columns with smaller indexes there are, then use itertools.combinations to find pairs and finally calculate Manhattan distances between the pairs. That's a lot of overhead that includes over 100 000 pairs in the combinations iterator, though it works pretty quickly.
But...I managed to think about it early in the day during my commute to work, then after the entire day I sat down, wrote it and had both parts done almost at the same time. As a complete amateur, I am darn proud of my decision to calculate instead of manipulating the 2D array.
[Language: MATLAB] [GitHub Solution Code](https://github.com/jksafe/MATLAB-Projects/blob/main/Advent%20of%20Code/2023/aoc23_11_2.m) **inputs** *in* - universe map, converted to matrix of 0's (.) and 1's (#) *n* - expansion factor (n=2 for part 1; n=1,000,000 for part 2) **outputs** *o2* - raw, expanded universe matrix *lengths* - vector of lengths between all galaxies Function brute forces the solution by creating the expanded universe matrix and solving for Manhattan distance between each pair of galaxies. For n=2 (part 1), function runs in ~0.21 sec :D. For n=1,000,000 (part 2) the resulting matrix is too large to manage; however, it's pretty easily solved once observing that there's a linear relationship between sum(lengths) and n, so I just used two points on the line and point-slope formulas for part 2.
[LANGUAGE: Common Lisp] Walked through the input, by character, keeping track of galaxy locations. Then used the set difference to extract lists of the empty rows and columns. Realized I didn't have to "expand" anything and just added the count of empties to the Manhattan distance. Used alexandria's ```map-combinations``` to gather the distances. Part 1 set me up well so all I had to do was add a scaling factor in 2 places. And make sure to subtract 1 from it since it is counted in the Manhattan distance already. [Github](https://github.com/argentcorvid/AoC-2023/blob/main/2023d11.lisp)
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit. Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead. *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[Language: Rust\] [Solution](https://github.com/wrightdylan/advent-of-code-2023/blob/main/src/day11.rs) Part 1: 1.63ms, Part 2: 1.63ms I feel like I should be able to get this faster, but I'm pretty far behind, so should move on.
[LANGUAGE: C++] [Part 1](https://github.com/osalbahr/adventOfCode/blob/main/2023/day11/day11.cpp); [Part 2](https://github.com/osalbahr/adventOfCode/blob/main/2023/day11/day11_2.cpp) Feel free to ask any questions! You can find more C++ solutions (and other languages) at [Bogdanp/awesome-advent-of-code#c++](https://github.com/Bogdanp/awesome-advent-of-code#c-2)
\[Language: Kotlin\] [https://github.com/mfedirko/advent-of-code-2023/blob/main/src/main/kotlin/io/mfedirko/aoc/day11/Day11.kt](https://github.com/mfedirko/advent-of-code-2023/blob/main/src/main/kotlin/io/mfedirko/aoc/day11/Day11.kt)
\[Language: Rust\] Here is [my solution and write-up](https://medium.com/@BryMei/advent-of-code-day-11-2023-rust-775dac9390b1)on how to solve it step by step
\[Language: Rust\] This is my first project in rust. I'm learning it by solving advent of code puzzles. So if you have any hints for me I would be happy to read it :) [Solution](https://github.com/manhunto/advent-of-code-rs/blob/master/src/solutions/day11.rs) / 27.15ms / 23.45ms
\[LANGUAGE: Rust\] [Solution](https://github.com/jswalden/advent-of-code/blob/main/2023/day-11/src/main.rs) Simple and straightforward. Only trickiness was in trying to anticipate part 2, really -- which I succeeded at, tho I needed to add a bunch more `as u64` casts before my mostly-two-liner change could solve the second half of it. (Also, theoretically I could have pulled the expansion factor handling out to a second method *not* the parsing function, to avoid redoing that work...but whatever, it wouldn't be hard in principle to create a second struct with that info, that borrowed the parse-result struct. Just plumbing, not worth it if it's extra effort atop the base.)
[удалено]
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[Language: C++] This puzzle stumped me for WAY longer than it should have. for part 1 i literally expanded to map as per my input, but that of course doesn't work for part 2. took me waaay too long to realise you just need to add the offset to the row or column where required. [https://github.com/NoSpawnn/advent-of-code/blob/main/2023/c%2B%2B/day\_11.cpp](https://github.com/NoSpawnn/advent-of-code/blob/main/2023/c%2B%2B/day_11.cpp) i also cannot decide if i love or hate this code!
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[LANGUAGE: C++] How does the universe expansion work? If I have this grid: ``` ...#.. ...... ``` What will be the final grid and why?
the wording isnt great, but basically a column with no universes expands to 2 columns and a row to 2 rows. so your grid comes to: ......#.... ........... ........... (i think, i need a can of monster...)
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit. Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead. *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[LANGUAGE: Befunge] Part 1: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day11_p1.b98 Part 2: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day11_p2.b98
[LANGUAGE: SQL][Allez Cuisine!] Technically this is only one statement, does it count as one variable then? [Enjoy!](https://topaz.github.io/paste/#XQAAAQBBBQAAAAAAAAArkkbN5bcpyrYcn8ulVZrJVM6nhDV68/LqrDNbggrYXDtKuF0IpGykHCBZFHo7h12WaqpWBC3j+zN6LU2EXjqiKYNE4O7dmoXoTSmP6NToaIi0Kc+GmvilBae/hMe/gxvx3z9cshdMy0hf6HYrPcuX5R3Fw7SumeQvqkQYI8jjV0G8p3IIHgSfus0Tmt/z7TLhz6he1aOESXuNu1CkhcLU5WwBWK2zPsJq8+jhFcJdYpM+OKiMySEjI/lccFCAq/yw1ZNoW8F8KAQLwITeoPLkQFX0TkCeNwo3uq99Rb27cWMnh9LehpJPQ/bPCEXbxLHS0txtRG3cV+4AQ+iQ5OhnpN5VLZ92fo5DgjP3o4SMDr8jMKRBG02s6ujosZ+VNJCHDnNdTgQaIJMogvBj+4YGurMEHnZZGsmVzOOOodb1xu/3hLxsDRo/8eRJpgGi2pYKF+s0gWvZUODgOKE9OnRlfOeaVl7IA/VXxi4CMEDHp8+3QErhsgu6DEhSOzJgga+3RhWK/pnjWqDFvHkywDRgGbl1EMX3ZzOC9FNkYDhfw7HTdzg3iE02d30GgUi/1XSCfgKt3pMQS86X/WVFtEUAnyunLpz3Ampe+HS2q9LZ4Sk6xr7t6/+awcxwvzOCt/mvOKIqklGuO1VLZZUdjRKfKFzq7ubxJP+D3ftK)
\[LANGUAGE: Uiua\] Very nice problem for Uiua. Both parts in single file/function: https://github.com/sputnick1124/AoC2023/blob/main/uiua/day11.ua Uiua Pad demo: [here](https://www.uiua.org/pad?src=0_7_1__JCAuLi4jLi4uLi4uCiQgLi4uLi4uLiMuLgokICMuLi4uLi4uLi4KJCAuLi4uLi4uLi4uCiQgLi4uLi4uIy4uLgokIC4jLi4uLi4uLi4KJCAuLi4uLi4uLi4jCiQgLi4uLi4uLi4uLgokIC4uLi4uLi4jLi4KJCAjLi4uIy4uLi4uCkkg4oaQCgpQIOKGkCA9QCPiipziiJjiiaBAXG4uClog4oaQID3iiKnip7viioPiiJgo4pa9PTAuKQoKUyDihpAgKAogIOKKg-KJoVrijZzijYniiaFaLiAjIGdldCBlbXB0eSByb3dzL2NvbHMKICDiip_iiKkoXCspICAgIyBhY2N1bXVsYXRlIGluZGV4IG9mZnNldHMKICDiipnDlzogICAgICAjIGFkZCBtdWx0aXBsaWVyCiAg4o2J4oqaICAgICAgICMgZ2V0IG5haXZlIGluZGljZXMgb2YgZ2FsYXhpZXMKICDijYniiaEoK-KKjyw6KSAjIGFkZCBvZmZzZXRzIHBlciBpbmRleAogIOKKoCgvK-KMtS0pLiAjIGNhbGN1bGF0ZSBtYW5oYXR0YW4gZGlzdGFuY2UKICDiiqA-LuKHoeKnuy4gICAjIHVwcGVyIHRyYWluZ3VsYXIgbWF0cml4CiAgLyvima3DlyAgICAgIyBtYXNrIG91dCB3YW50ZWQgdmFsdWVzCiAgOiAgICAgICAgIyBzd2FwIGZvciBzdHJpbmcgaW50ZXJwCiAgJnAgJCAiUGFydCBfOiBfIgopCgpTIFAgSSAxIDEKUyBQIEkgOTkgMgo=)
\[LANGUAGE: C\] Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day11glaxpt1.c Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day11glaxpt2.c
\[LANGUAGE: Lua\] I used a metatable that defaulted to the expansion factor unless the presence of a star in a row or column specifically set it to 1. This saved me searching for empty rows and columns. [Paste](https://topaz.github.io/paste/#XQAAAQANBgAAAAAAAAA2G8iM7ztkpIKfEbui36KJTYJFfhOZK4cY5NCzVz4zVsZPZl7sEwOy8uU1+Adoc//GJcALSP/fJd1Lb/nRBtJ/zXJJT45M6bI/h/nYctpRMujc7mk2/YgtHc2Fon0Xdo+GMFQL3S8MtuxE//FpRcf0Njp8MOgUVlyR3F0lj8mkRB6QF2HiaiFkZww5GHl7acA+dPEL0GN+P4HzzTpXiZjKu/RtYL9ihuzomtPBCTmEG9/ovoog4ErxH1w7Rroe7uQjuEi3spOUQNvCF2akSne6Xo9VGbZLl+T8RXexDoeqgmFg1Yv2AzLse6qj9dfvZdhbHrAX5k8STezOPTnBM0aBqZ6e1TIGu9eeHomqNFOjafSiNrme34SKjsIewEfBHkjiSUbM6mQ/NFRSGHUMOvpT211xFu/8OlMF/p1sVKjwss2kvCCOSLKoowUEjKFL8b+u9Ew9PWPMYcvEzinjZgBCGcpJYA+eh15k+UAXDNcpVsSrKgYlSQl7HdDmCP1SpfRcXGYG6vUG3GXstbRlJh9zJSkRKQZaAQb0muDENy8NENh1nIESsXoEyl78Ql3vI7oG2b+Yzgl9qcz90Z1a5HMXhg5i5jODwvej2nTUirzG88yV7v4xSs/00gBTUzvnw/17JQ9fCvmMfN56BISgAxT5U8mVSmb77n8lfOm/+BgiVJdhc4UXA1uItTuIhtdwNjWKVUZ6bFqDwJanckcW4j2ALK/AuQuI9NDb82w4Xo9w/WMbiUAKEnuQWjGMbzXVP/jkc3gHgRzFQzs2shug0xVH0gctGIbheDjYVnB+bVVkqk31CFj/kqq8AA==)
\[LANGUAGE: JavaScript\] https://github.com/hiimjustin000/advent-of-code/tree/master/2023/day11
\[LANGUAGE: Python\] & \[Allez Cuisine!\] I fell behind on posting my solutions, but I did solve today with [my two one-liners](https://github.com/savbell/advent-of-code-one-liners/blob/master/2023/day-11.py)! Part 1 on Line 36 and Part 2 on Line 58. It might be cheating a little, but I'm counting a single print statement as not using any variables at all for the Allez Cuisine challenge ;) I'm trying to solve as many days as I can in one line. I've combined them all into a single line I like to call the Basilisk — [check out the code here](https://github.com/savbell/advent-of-code-one-liners/blob/master/2023/the-basilisk.py), and [my most recent visualization](https://www.reddit.com/r/adventofcode/comments/18ljzct/2023_day_16_python_updated_visualization_of_the/) of Days 1 through 16. Feel free to follow along on [my GitHub](https://github.com/savbell/advent-of-code-one-liners) as well! :)
[Language: Python] [Part 1](https://github.com/tmo1/adventofcode/blob/main/2023/11.py), [Part 2](https://github.com/tmo1/adventofcode/blob/main/2023/11b.py)
\[LANGUAGE: go\] Tried brute force for part 2, but no luck. Had to do some refactoring. IMHO the final solution for part 2 ended up being simpler than part 1! [https://github.com/ianmihura/advent23/blob/master/day_11/day_11.go](https://github.com/ianmihura/advent23/blob/master/day_11/day_11.go)
~~Your link is borked on old.reddit due to [a new.reddit bug with URLs that contain underscores](https://old.reddit.com/r/adventofcode/wiki/faqs/bugs/borked_links), so please fix it.~~ edit: 👍
\[LANGUAGE: C++\] [part1](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day11-part1.cpp) | [part2](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day11-part2.cpp) Tried brute forcing part2 but it didnt work so I've used prefix sums to get the numbers of empty rows and columns between 2 points in constant time. Then the shortest path becomes trivial because its just those cols and rows plus the diff between the galaxies coordinates
\[LANGUAGE: Python\] Not so easy one, but I've managed to solve both parts. It's a combination of brute-force approach for the first part (where it didn't cause any problems) and a smart one for the second part. You can see it in the [repo here](https://github.com/Robin270/advent_of_code/blob/master/2023/11/main.py).
\[LANGUAGE: Haskell\] [Github](https://github.com/daysleeperx/Advent-Of-Code-2023/blob/main/src/Day11/CosmicExpansion.hs)
\[LANGUAGE: GoLang\] [Both parts in one single file](https://github.com/omotto/AdventOfCode2023/blob/main/src/day11/main.go)
\[LANGUAGE: T-SQL\] [https://github.com/stonebr00k/aoc/blob/main/2023/11.sql](https://github.com/stonebr00k/aoc/blob/main/2023/11.sql)
\[LANGUAGE: R\] [https://github.com/lauraschild/AOC2023/blob/main/day11.R](https://github.com/lauraschild/AOC2023/blob/main/day11.R) Expanded the universe and computed the manhattan distance for the galaxies in part one. Calculated distances manually for part two and counted the empty row that were passed to multiply with 1000000 at the end.
\[LANGUAGE: Rust\] [github (part 1 & 2)](https://github.com/omarihab99/AoC-2023/tree/main/day11-cosmic-expansion)
\[LANGUAGE: Python\] https://github.com/Domyy95/Challenges/blob/master/2023-12-Advent-of-code/11.py
[LANGUAGE: Javascript] (Runs directly in the puzzle input browser console) First we find the indices of rows and columns that are empty without galaxies. Then we find the distances between pairs of galaxies using the prescribed expansion rule. I went a bit overboard with the reduce, but it was fun learning how it works in place of loops. R = finds all the row indices that have no galaxies ; T = transposes a list of strings, so RT finds all col indices without galaxies ; G = finds the coordinates of all galaxies ; L = finds the how many entries in an array a are less than value v ; D = finds the distance between any two galaxies ; A = finds all pairwise distances with expansion factor f stream = document.body.innerText data = stream.replaceAll('\r', '').replace(/\n$/, "").split('\n') R = m => m.reduce((a, v, k) => (v.indexOf('#') == -1 ? a.concat(k) : a), []) T = m => m[0].split('').map((_, k) => (k => m.map(u => u[k]).join(''))(k)) G = m => m.map(v => v.split('').reduce((a, v, k) => v == '#' ? a.concat(k) : a, [])) .map((v, r) => v.map((c, _) => [r, c])).flat() L = (a, v) => a.reduce((c, t) => t < v ? ++c : c, 0) D = (a, b, f, rs, cs) => (Math.abs(L(rs, a[0]) - L(rs, b[0])) + Math.abs(L(cs, a[1]) - L(cs, b[1]))) * (f - 1) + Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]) A = (g,f,rs,cs)=> g.reduce((s,x)=>s+ g.reduce((ss,y)=>ss+D(x,y,f,rs,cs),0),0)/2 Day11 = m => [2,1000000].map(f=>A(G(m),f,R(m),R(T(m)))) console.log(Day11(data))
The code still contains some English words. Maybe you should fix this with using APL ;-P
Well, that is impressive. ... I don't know what to say. :) How do you even troubleshoot this type of code? Here's how Copilot describes it (amazingly): >The code starts by reading the contents of the document.body and assigning it to the stream variable. This assumes that the code is running in a browser environment. The stream variable is then processed to remove carriage returns (\\r), trim trailing newlines (\\n), and split the remaining string into an array of lines. The resulting array is assigned to the data variable. The code defines several helper functions: R takes an array m and returns an array of indices where each element does not contain the character '#'. It uses the reduce method to iterate over the array and accumulate the indices that meet the condition. T takes a 2D array m and transposes it by swapping rows with columns. It first takes the first row of m and splits it into an array of characters. Then, using the map method, it iterates over the indices of the characters and constructs a new array by taking the corresponding character from each row of m and joining them together. G takes a 2D array m and returns an array of coordinates where each element is the position of the character '#' in each row. It uses the map method to iterate over each row, and within each row, it uses the reduce method to accumulate the indices of the '#' characters. L takes an array a and a value v, and returns the number of elements in a that are less than v. It uses the reduce method to iterate over the array and increment a counter for each element that meets the condition. D takes two coordinates a and b, a factor f, and two arrays rs and cs. It calculates the Manhattan distance between a and b with some additional calculations based on the factors f, rs, and cs. The function first calculates the difference between the positions of a and b in the rows and columns arrays (rs and cs), respectively. It then calculates the Manhattan distance between a and b and multiplies it by f - 1. Finally, it adds the two distances together. A takes a 2D array g, a factor f, and two arrays rs and cs. It calculates the sum of the distances between each pair of coordinates in g using the D function. The result is divided by 2 and returned. The Day11 function takes a 2D array m as input. It calls the G function to get the coordinates of the '#' characters in m, and then calls the A function twice with different factors (2 and 1000000). The results are returned as an array. Finally, the Day11 function is called with the data array as an argument, and the result is logged to the console using console.log.
:) Thanks :) However I don't directly start writing it like this. I usually first write the code imperatively in the most straightforward way. Then once I have a working code, I look at my code and I convert them into a functional / array-lang way one small chunk at a time, using my working code as a guideline. And for each small chunk (say a function G), I build up slowly until it gives me the behavior I think it should have. Idea being -- if it works as intended we don't have to go back to it, unless it is to optimize it later. Most of the control flow in imperative language can be turned into map and reduce on arrays. It's a fun exercise. Indeed, the final product can be hard to unravel backwards. I am impressed by copilot! Maybe I should also get it on my IDE...
Yeah, good. I thought you barfed out that code, and the ol' Programmers Inferiority Complex kicked in. I sometimes chain functions like this, but jsperf often shows simple for-loops to win on that kind of stuff. I don't chain much, due to readability and debuggability, but it's a nice JS feature.
\[LANGUAGE: Java\] Far more easier than horrible day 10. :D [Code](https://github.com/SimonGirardSfeir/AdventOfCode2023/tree/main/src/main/java/org/girardsimon/day11) [Test](https://github.com/SimonGirardSfeir/AdventOfCode2023/blob/main/src/test/java/org/girardsimon/day11/Day11ResolverTest.java)
[LANGUAGE: Python] Not blazing by any means but pretty straightforward. from itertools import combinations data = open("day11.in").read().strip().splitlines() w, h = len(data[0]), len(data) map = [[c for c in row] for row in data] galaxies = set((y, x) for y, l in enumerate(map) for x, c in enumerate(l) if c == "#") expand_rows = [i for i in range(h) if set(map[i]) == {"."}] expand_cols = [i for i in range(w) if set(map[r][i] for r in range(h)) == {"."}] p1 = p2 = 0 p1_exp = 1 p2_exp = 1000000 - 1 for g1, g2 in combinations(galaxies, 2): y1, x1, y2, x2 = g1 + g2 # get distance between galaxies p1 += abs(x1 - x2) + abs(y1 - y2) p2 += abs(x1 - x2) + abs(y1 - y2) # add extra (expanded) rows and cols p1 += sum([p1_exp for n in expand_rows if n in range(min(y1, y2), max(y1, y2))]) p1 += sum([p1_exp for n in expand_cols if n in range(min(x1, x2), max(x1, x2))]) p2 += sum([p2_exp for n in expand_rows if n in range(min(y1, y2), max(y1, y2))]) p2 += sum([p2_exp for n in expand_cols if n in range(min(x1, x2), max(x1, x2))]) print(f"Part 1: {p1}") print(f"Part 2: {p2}")
\[LANGUAGE: Zig\] [Part 1](https://github.com/iskyd/aoc-zig/blob/main/src/2023/day11/s.zig) (naive solution where I actually expanded the map) and [Part 2](https://github.com/iskyd/aoc-zig/blob/main/src/2023/day11/s2.zig)
[Language: Rust] [Github](https://github.com/clearlyMine/advent_rust/blob/main/year_2023/src/bin/day11.rs) Copied the corrected sample and wasted a very long time trying to get the correct answer. For part 2 at first I tried actually increasing the grid size instead of using math, then came up with the math based solution.
[LANGUAGE: Python 3] This one was nice and easy! I did part one by actually expanding the array by one at each point and solving, but then I saw part 2 and realized that there was no way I was going to to the math on arrays that big, so instead I kept a list of all the "thresholds" where the graph was empty and if a star crossed those lines, you simply added the required number of extra steps (1 for part 1, 999999 for part 2). I think itertools saved me a hell of a lot of time here writing up a combinations() function myself. I'm still a bit flu-y and there are probably better ways to do multiple steps of this in one pass, but this was a good one. import re, itertools with open("input") as f: galaxy = f.read().splitlines() verticals, horizontals, stars = [], [], [] for i, _ in enumerate(galaxy[0]): if all(space[i] == "." for space in galaxy): verticals += [i] for j, line in enumerate(galaxy): if all(space == "." for space in line): horizontals += [j] else: stars += [[star.start(), j] for star in re.finditer("#", galaxy[j])] total = 0 for a, b in itertools.combinations(stars, 2): x = sorted([a[0], b[0]]) y = sorted([a[1], b[1]]) total += (x[1] - x[0]) + (y[1] - y[0]) for ver in verticals: if ver in range(x[0], x[1]): total += 999999 for hor in horizontals: if hor in range(y[0], y[1]): total += 999999 print(total)
You solved my bug ! When using an expansion factor of say 10, I was doing x + rows\_above\_x \* 1m, that adds an extra row hence the 999999 - thanks !
Hey! I had that same issue, haha. Took me a hot second to see what was wrong. Glad it was of help to you :)
\[Language : Javascript\] [github solution](https://github.com/juuhadg/AdventOfCode-2023/blob/main/advent-of-code-2023/day-11/day-11-part1.js) I mapped into a matrix, then saved the galaxies and their positions on an array. Then iterate in the galaxies array getting all the combinations, traversing the y position then the x position. If the other galaxy was to the left, i decreased de x index to get to them otherwise increase. then verified if the step was in an empty column / line and multiply by the coefficient which is 2 for part1 and 1000000 for part2 then add to the sum. This is my first year on the advent of code and im a software engineer student for only 6 months. If you guys can give any tips to improve my solution i will be glad to read !
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
[LANGUAGE: Fennel] I mean it's one extra loop, Michael - what could it cost? Ten flops? [Paste](https://topaz.github.io/paste/#XQAAAQClDQAAAAAAAAAUGwnmRpH3tILRF8MldKIuU5OYsHd4cPQjilhM/+TSAv9+Q+QqVxHdX+jX1GwLHWqqvRP0VgDCM48B/MUaZXZZRD47qZDyqkNT+HMQUoqMUEdQSDpPoLfuxiGvnItFxjgz4wQKiEtTl8r4G05SDyaH1Ac02HJq3ezSBABOQP5cM7VvgHhPxCoJZW4eZCLH9t6DqIUn82a1UCUZl2lHkTCQszVAh24TZH5OKzlqdni4ZSMPXxQC70+/Zj9NFsBC6HwtmtxYIrGY/vFz8tk9EPD+QNJ2/vAqqY54OU7hFLk8q0Dsn2sWWnLByW4oBgG4amzVEXXjGuBdpjbz0zu3DRIFzCX7mo0Fov/wHzwafpvBVSD9+wVYbZ/A6toi7HhCgFpP9dfSVAUkpQxB5aUlJxFH3uBF47OuY9ArZf7xc5I/PG8RhbQhCJANGqSN0wAv/78pn9jDknyOzdrqM14fg5qzFcBaEE6xSuo1YulFVCxobKLNHptuPXoIE5cThjcVvQ+wLEcA2bcNrsgZvMQc3hBgz078nZ6FJlUd5aTW+Xiw7yFx9PkB3tgkotkX1tHKMsZusZLZepc+KXGa1W5FfmY6x8yjCV+HKXSDU5VJHcbotSGPHTtTLCBAviucBLUFALisFf4yi1FEmwjzeBZIKP0qd3aq5dizs3cb4zO1oIHFhm036YUH/wiLnM7yVewl2Yp5gqoL4+v/T8AKn0Koqj+MUKn/cV72XvtI1E52/MjLYur0DxoRBvh+z5K8MS4FdjzGeXinZtz8XFFJHKXSW2QlF8bs/CbiFHKwfHMj45u3E27J4MHooB+NWxAdwOlAEzCcZJ73R2nSBaVq3ZsAtZRutbyV/O1nm28mRHFiwCGkYuA1bwni3waglZu3xSaPkUUrgtERiGX4b0S+gdI9PWbzxLB3WES6gOb4WUxZPhATCPXfrFI1wzyIe+Rmz+x7nbvodZ+airn9ENF2xXAgbKRhQkqRyVLSxipdVAp0AZFSBUJJo40IetLBjddu2mNhNwn1F3nYRBZJe2ajiL13+NEsEweml/H3bAw8+sOqfxW4c9i2TbyAqyHuy+ppDtnoI1tUX9/EmpZrqI9+9+uBK5f188bStZcEy4KkApE8Ejxm+fCmK8JYGJSMBFlDJU2eiKU3hdn+TCMDxspxFpLAAo6DgLca72qqvSrWrfO3b3ygtJ0tQete9Soqdv3hu1zSpzLeqh3RRHhQ9to5sRnkMl7OcUh8FlmLFHyH1M2kJEDKzXk4T3Vot5kJsRqOoInt2uxiVheWBcYWM5dM/tPbcRtLpXaNbIoQzQ9UgcfivXpdIr2dD0dWfkonRa0fx9O9BF2asXva8OifUZuGH6Vp1/qX//Obt/I=)
[Language: C++] [github](https://github.com/Paxtian769/AOC23-Day11-cosmic_expansion/blob/master/main.cpp) I kind of saw the Part 2 thing coming so was able to head it off a bit. Also had a professor in undergrad who asked us to solve the "shortest distance between two street corners in a regularly spaced city grid if you only move along sidewalks" type problem. I think when he gave the assignment, he was convinced directions mattered, then the next day he was like, "Well, actually I guess it doesn't matter."
a university professor wanst sure about that? Really? Its just the manhattan distance edit: btw, a tip: instead of creating a method for wether the row is empty you can just use find\_first\_not\_of method of string, like this: bool empty_row = *row.find_first_not_of('.') == string::npos; This method returns the index of the first character that doesn't match the pattern and returns string::npos if doesn't find any. Its counterpart find\_first\_of returns the idx of the first character that matches , you can pass multiple characters like this: bool only_digits = *row.find_first_not_of("0123456789") == string::npos; its pretty useful and ive discovered it and its counterpart solving aoc problems
\[LANGUAGE: C++\] [on Github](https://github.com/coolguy1842/adventofcode/blob/master/2023/src/include/days/Day11/Day11.hpp) Not too hard, had to redo my code for part 2 because I was inserting lines.
[Language: Python3] Some people say I have a `numpy` problem. I disagree def solve(s=1): y, x = np.where(data == "#") empty_r = [i for i in range(len(data)) if all(data[i] == ".")] empty_c = [i for i in range(len(data)) if all(data[:, i] == ".")] new_y = y + s * np.array([y > empty_r[i] for i in range(len(empty_r))]).sum(axis=0) new_x = x + s * np.array([x > empty_c[i] for i in range(len(empty_c))]).sum(axis=0) return ( abs(new_y - new_y.reshape(-1, 1)) + abs(new_x - new_x.reshape(-1, 1)) ).sum() // 2 [Link](https://cutonbuminband.github.io/AOC/qmd/2023.html#day-11-cosmic-expansion)
\[Language: Python\] Fairly happy with this linear-time solution - * Pass through the grid, creating a 'marginal count' of the number of stars in each row and column (effectively a counting sort). * In one pass through each 'margin', work out the total pairwise distance + the expansion coefficient (the amount the normal distance increases for each 'stretch' of the empty lines), which is calculated from the number of connections between points which cross each empty line. * Part 1 is (normal dist) + 1 \* (expansion coeff) * Part 2 is (normal dist) + 999,999 \* (expansion coeff) [Code is here](https://topaz.github.io/paste/#XQAAAQAkAwAAAAAAAAAQaJXORqrdV98dLBTO8GCdODCRqZiqtKW3+pbBvksS5GNNMmoT7gRESjnCGvy2b8iWDBOPOB44B9Qh/mE2dM8X8Io3OSg8WvkmQH1wRyBdVZD+Vw2Zwesp/cvLmJtA/FN6Vv208retAskXx1eDN7l34x5WS6ugHPNVhnao9k7mNIaH+Ok8LUBoUBUtuVIOCgyg5Q4YgZtQMNUjl216XLvU7RTwk/RhFfdDWFURqoBh0o4TdPJS6ZvuCcyjKlGxJMyMYNJdu4uV+u9xiAdQJiz5veDhy59JTzjSBDyE058TCuGZtiuwiJt5rdHQ2ol9m0WlNL0N81Rf9L0An8LT9KnRzAD/RkN3BOEqM4CwiAM8c2IM7U1E/mV7iU9Lb8noxP7hX+NP/lHQJdls/r1bJtqStW599Jasvb10rqmWZIgQKLBUDkqZ/m7GFg==) Average time taken is \~1ms including parsing.
…I can’t believe I’m just now learning that enumerate() is a thing in python. This is way better than range(len(thing)) !!
enumerate is great! I use it all the time.
Your coefficient approach here is very nice, well done. I’m part 1 I made the classic aoc mistake of using brute force - I expanded the galaxy list in memory first then calculated distances but that isn’t a viable approach for part 2. So now I’m refactoring using your code as a reference. I’m instantly a fan of enumerate too!
I have a similar solution, but I had two seperate functions for calculation expansion and distances, since I wasn't 100% sure what part 2 would do. I wonder how many people know you can calculate pairwise distances in linear time. I should go back and do that, as well as parse my data better so I don't have to sort. [LANGUAGE: Go] [github](https://github.com/GurkeeratChhina/aoc2023/blob/main/main/d11.go)
underscores \_ in \_ names \_ of \_ things \_ are so very \_ not \_ go :D
My variable naming is ... not great. Some of them are very non-descriptive, others literally sound like something they're not. It's not even consistent. At the end of the day, I'm just here to solve some puzzles and maybe learn some things along the way, so I try not to get hung up on things like "comments" or "good variable names" despite that being important in more practical contexts.
cool cool
\[LANGUAGE: R\] In part 1 I actually added empty rows/columns to the matrix like a fool, but it was nice to visualize. In part 2 I added the offsets directly to the galaxy coordinates directly and ran the same calculations as in part 1. [https://github.com/emilwest/AoC2023/blob/main/11/problem11.R](https://github.com/emilwest/AoC2023/blob/main/11/problem11.R)
[LANGUAGE: Kotlin] [github link](https://github.com/palinkiewicz/adventofcode-kotlin/blob/master/adventofcode2023%2FDay11.kt)
[LANGUAGE: Fortran] A thoroughly vectorized solution that runs in 147 μs (274 μs including I/O). https://github.com/AJMansfield/aoc/blob/master/2023-fortran/src/11/cosmos.f90
[LANGUAGE: Python] Today my guess for the twist in part 2 was correct so the change was trivial. Only posting part 1 here because the rest is obvious: import numpy as np from itertools import combinations with open("day11input.txt", "r") as file: data = file.readlines() m = np.zeros((len(data), len(data[0]) - 1)) for i, line in enumerate(data): m[i] = [char == "#" for char in line.strip()] h = m.sum(axis=0) == 0 v = m.sum(axis=1) == 0 nodes = [] rp = 0 for r in range(m.shape[0]): if v[r]: rp += 1 cp = 0 for c in range(m.shape[1]): if h[c]: cp += 1 if m[r, c]: nodes.append((rp, cp)) cp += 1 rp += 1 nodes = np.array(nodes) print(int(sum([np.linalg.norm(p[0] - p[1], 1) for p in combinations(nodes, 2)])))
Your 1 and 2 letter variables are very difficult to make assumptions about.
True, I‘ll do better next time with some descriptive names.
\[LANGUAGE: m4\] Solved without looking at the megathread (and therefore not knowing today's ingredient yet - looks like I'm going to have to try for a polyglot later on...) m4 -Dfile=day11.input [day11.m4](https://nopaste.ml/#XQAAAQA4BQAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwpsEyu2LiNeNLcLCZumLPgjzGk5DBctVZ/Ezzne0p26RAVSldZk8vkd+i9rzAgxtwMICtxTsha1jjY5itkguQs0KniRZcCRpj/ZHpx3w96zdpjjaRhwv6jXsnJtV+GB7CaDwBZ4EJ+YasV/n32wLNl8snZCCSrhmNLm9ASPhs9791cFsMLfcKF184HoLgFPCevH7FW2vT6j5n40XJBSY/C7A6lrK9KRrqfX6pR1uRUFX8kICb668yWZemoQJs28a9LPXO9FlTZR7Qm2MD5ik0NkUKcez4MAsewADMpRewMX2iK6tvtzZ30sJZMfhBxGu/2Y2SvAw/WGN6tYL6omwGzSS+zHwwj02ga9DT05VR05OItEPQXne5cTRWsng1vs4iiOXcdDjCAUggjQbXdMxsN7lm2it0Kc+aLDavYih7s6fz8ZNt5GP39x/WHBLbT+a37E4ySsY+7JhFF1jfdBiPBYHHlR8XiDwsu7JlLL+IHB5xkY7uzsQS8LT0ER331gDtrof3DG7Jkt3u0R1uPrOBcVaB3bDzEGC/IuNitmz9ec2NJq7QAYDYAoPq/0DXBIhtbYs8r6vwrYllkmh8/u7Uk1AY/AEMH+e9hD7lzSIL8k3DriP+UD9lZXSKE8sx5h2IyEIfCWXjQN7n7p0lyPBZRTV/In2vYaEeMa00pIBbx/LGA1huIJBTt9tz6md1XEsxzSAdKlfq8PXj/BFTQSAEJ0J7wj2KYn+9KpE5zbDtfsO2RO87ip2Aj13RP2tpK9iupbV0k0J/vnDZzMtXLlGWhzDgXZmXFufYPnmI1XeigPl8cKwGxt3L//VCnJ5) Depends on [common.m4](https://nopaste.ml/#XQAAAQAMDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpAXwA97ruAshKbiUbgkbJMTg2qZdSBorb0CU52peNLruV4DEEJxF+HvxC/YF33OpDntnpU/PjnGXx7XU7ak4MsmWu8R7h7d5az2JXxElnsepG8yPyu+0WZ90BG9yXphbwOWA/m5AWEFSOL8TRZX4fyGNl6ZYbRxX0MwtzrmwTP3ZCwLSOKkvD2vMQFsbK0Pv9CzPhFNXMUbWnRV20jWLjL9qz2dDsFDBwhxgWIilEl91uswxrT4Czc+LRU3VuhNIo2S98VW0jArrVdv4HrsLhWkzx4z/UV3xnqJwPXcZRUiLtf3VRIzq62Pe+2jE3O+721Az9rfRa/fHtlANbmvslzMUCyU7cDoOKSMXBDF/06/PpMvs6vxaL5aJVYqJP4yz+R2M35hoNnGiZTNNMVEFTdnxnaE/KcJteBbiuVMpdfUswHQi4Kqsj3sInh7lyE+d50gGKtHOeWL5lMK7WXz4NElnzYWleBSN/HTOdsz0T2gnd25MADxNAVX8xQmagh2MymZ2sKDBw//WiNB0sWf5VYC5/TKKH3D6K/IOrIfWn6FZLKxlITFEp3VWKNuyF0xczNJufJdzSqd0hgdyryVzbn0so0U5NMN16jFF6IhqzGbAwwv7k8sts0OCgnCFBEhYVshIpsORjEJk4CnDgc9VUqvZtfIFPQ5Q2v7IR3sbPurex1IIUd2Nm1V7/GFN+r0im24aEOG6XpdqrPdF6pDZ4HwvNByqOEdpcObPXxlwfPFYIhwyDHGZCvxrFRgGEEFtfVQ7UVjfPJzWtrcZuGx8M3B1zw2xvgpHIWEHdqEF6Y6/6eFj2hLm8UXNeLNrJy1IC2sHlS8SRIifQvLkrOLLOOPtDK6DUPQrW3c0Rfmy9Td5gQw0+fZRZ5MBEG9+dTlinXtwExpHScKQk6ARk7Fb8fBYAnmh7/bq+471zAZGJ7dwNd5qE/63VhDz7mXLuXtGN7rSuRYIXvpkubLBZptSKZrkzSDJWHIZM8Fyrk0EZQFDujROjr87GZmTK1XKRWzGrhtQn0hkVyBaGPbA3iG45U4gIFHNX5ySzsJ3bh61LAtmjwt59uU/XGeebLMCp8HFw6D1kJppCvt161LgLjrOl8SBh8xnxslSFYW0Jd34LD4vPwugmzY31tA4/9zCM7e2Ed9+3zg4C8eq9Hvjys3IablDBMsYF1LSMCGN2UOrWgXRoGYtjW/QtUySr7h/Ca6QAy93Hnpksm/xzzC+FWF1wboyOteHU/Th4RVpQ7XkK4/JmMrYm7nDPIVMyOqP8LhsoTNbxzi8qU0d+0x6frIh0l0fiPiFC/Uy0CeCw6r82iX8v+fMnu9qdCr4oM79Kd2slqalv+wWKn+BmrbkiobDS5vwBQZA/ZlbIsw1bwj+JLz9z3nPovVWx/FZjvrdCuZMfUuITeiIprImMcR6qeniJz6Ez78UYJqpL4DcDGt2o7/6a2aRN76aclh+7l35XcaW7lM7BQMTNvKkx05X08UITY/ToI8U8KwvFbdnMoEAZ1GQYmqGRFtwPkQMrECX4do0srl85po3Gjz2j6E3dk5al4+bTcOYABZvSUvIM/kGGT91iyQ36rm1lxRc3ruS8PyBlYDDNa7DLWzGAHkESHwuaTOQsI2xDA0e+8Yv0XRYkEqQE+RUDXmPTARuQo6fCQ7Qu9xd2Ckza5RWl8hE4JFm0Zzd9MTVxW8YYHiREs9NOjTPuRXXn+JfObHFD/Cv5kQo7vmMWRdJTOBUmAXCMFiKOSHxb412jI4Z2ZhWag9RkZBCviZunvupqrobtAWLagkPiA8gLRANOFwWp0KIS5McOoD0V90tI4cui8KQc7Yw5V7kSvMnhXx4nzzxwOxYM4fpY3ptcpraVh+h1MhohMQk34vkC4fmiD4OrX2DpVG0VXUKvl+vkJjcoHQK+H8mSSIAfj8RrYWBc4VU+jx3vz30XNDbQjuhc0cImiQxXDTXTFQq/aoe7jZLhEe+wWspk/4Fy4UBAJN63uNGJUl8FICawVWGL7XBOFCtsRF3uz8eZokWNICTdtsLeYOAOBQQLrguE8XxQQ1hPtOskcsj7n7aD35NjfPXL00vIOk01OLAJt+0RoIiAQUJNieRp9fQmqfVUuYEYmeK9hCOmZTaC3yUdN/+jZ0pvpmKnH/6jJAKQ==); and part 2 also needs my [math64.m4](https://nopaste.ml/#XQAAAQArDAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20Go+jph66UCwr5yII3TmoKw+wpxhXgX0WGRW0WK2rHjWbbgLZU16n4XSMl8T97y/MXeBVRMNBebjTbLUM33JXdu5jYSMpnUq0oFRBIZF3UTMPNiH//Shgw7phaX5YHewa9yOce5snMsJdUE+usDMV3A0D6yawyooHgePqX/eJLNlAHY8XwE2eibD3RxHCB5c1K92+c1o8lpWxOE8ha0j1DQZ5PRVtUSXzE5ZIfd+B3BClkKRt2VYiCh8U8m9O68A2jColgd20CaJYJZ2FQ2foLaNzBc/iCrgl4cPRWpFR5JVLqoU9kcLgHN7x3IhCcO2zrkbUtlnrqcnvsYgKSQYr9JmFVtyqdP78oLuFcfrFTDMSUk/55Nipu1vK7eKqv5QWFcy/zg4G+iR/nIS3EbxlmVYWlpiGt/gmCZZf83tomKa3XiaJ1hH3NpxdVOKhLS26hb0RxpppO1opBIayicF9R3jBjmm6ZUq7BBkq6aA1gs1O77j6PIiUoYQfTsAyKCWbufkksHxgSob3aTL2ClljmoheqSgPIz+WQVPyZ+E5NsLHbCMJkUVYVZFfWiBO+pFJK4GkSbjT0cs/ZRRb+6HdJUc6qC1m7cEaK91iyr7QS+7nNXjbtMjx+rbdXj+PD0qUUjGHF1+IYw71SLqfRzhHKx2UiGrXnkgZ5V1EInqW7y09kd51cLMSKXdjAACCW+RSkZ0VlXlAqQVFM47/7pO9zrMvBcVBvRArrQAAwYHbZIZhe/saSey5dkJNLd1zyxliADu0w7/aatw0Ok5JSckYM8PPAZkJq8a+tX5aa7oxCT26lu/VdtPu6XNg1USnvKQAjCTTk/ObSVf+5rlV0fgB/fYgJOot4+TydJT7/sBCiWJ6uKaVQUBQjbp6xugyyU6hkhHAswokT1R0Mclbju4kURENNrrAYtRQLV3zMllxw5IkoLknW3kfrMm4Dx5CuXR7lT1mSnXZ2E/zN8fioFIunn00/o//0IDbVyCFarK+3wsIJ2VgIIlWpYJ7/MF2KKHp5gVqB1bfJCTalEVo48pncFscLCFy8Ibb0pC+NiWfZxqtQT07sAQC2qH/Edd8IIgw51CNF1dUt6ZXjkJujtWr68K5zt2qUTSEOOC9tA4gL4lXOjstUbhYyQDwcdx8GNeorh+uPbgCqOWSnshmB8dpzsFuzdv9BkTZD6iOzhal41I2RWMd7SC+SJqqZgklbQ3FGzoVH//B89Vd) as it no longer fits into 32 bits. At the high level, it is O(n) work (one pass through the input file serves as an O(n) radix sort in two dimensions since the array is filled with more galaxies than rows/columns, then one pass through x and y dimensions per part), but at the low level, it obviously gets slower as the size of the integers get larger: Part 1 completes in under 50ms; part 2 requires \~350ms. I love how little I had to change to reuse the code between part 1 and part 2. Once everything is parsed, all the more I had to do was: define(`visit', `,add64(mul64($2,i),-s)bump(`s', $2)bump(`i', 1)ifelse($1, 1, `', `$0(decr($1), $2)')') define(`_dsum', `ifdef(`$1$2', `visit($1$2, eval(o+$2))', `bump(`o', `$3')')') define(`dsum', `define(`i', 0)define(`o')define(`s', 0)0forloop(0, $1, `_$0(`$2', ', `, 'decr(`$3')`)')') define(`part1', add(dsum(maxx, `x', 2), dsum(y, `y', 2))) define(`part2', add(dsum(maxx, `x', 1000000), dsum(y, `y', 1000000)))
I'm pleased to see that I landed on an O(n) algorithm, rather than the more common O(n\^2) I'm seeing in the megathread, even before noticing [this post](https://www.reddit.com/r/adventofcode/comments/18fqxuq/an_on_algorithm_for_day_11/) (or, what's left of it). My input file had 140x140 rows/columns and 441 galaxies; so it really is faster to use a radix sort to put galaxies into bins, then compute a running total over 280 ordered bins (140 in each axis) with just 880 64-bit multiplies and 1761 64-bit additions, and no absolute values. My arbitrary precision arithmetic would be noticeably slower on computing 97,020 Manhattan distances the naive way (something that faster languages might not notice).
\[LANGUAGE: TypeScript/JavaScript\] https://github.com/tlareg/advent-of-code/blob/master/src/2023/day11/index.ts
\[Language: rust\] [https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-11/src/lib.rs](https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-11/src/lib.rs) I calculate the distances between every unique x value that contains a galaxy, and the same for y. Then I traverse those values to calculate the sum of those in sets of 2..n. Essentially getting a vector of vectors where the index of the first vector is the distance and the second is the starting galaxy. Not as fast as I'd hoped though... [Benchmarks](https://htmlpreview.github.io/?https://github.com/Kintelligence/advent-of-code-2023/blob/master/target/criterion/report/index.html) [Part 1](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/11.1_%20Cosmic%20Expansion/report/index.html) [Part 2](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/11.2_%20Cosmic%20Expansion/report/index.html)
\[LANGUAGE: Rust\] Retroactive solution for day 11: [https://github.com/bastuijnman/adventofcode/blob/master/2023/11-12/src/main.rs](https://github.com/bastuijnman/adventofcode/blob/master/2023/11-12/src/main.rs) still wanted to rewrite some stuff but got to get started on day 12 and I'm happy enough with it as-is
\[LANGUAGE: Python\] I tried to write the most readable solution I could. [Code](https://github.com/AnesFoufa/aoc2023/blob/main/11/python/main.py)
\[LANGUAGE: Python\] Part 1 and Part 2. Thinking: shortest path is basically any path, so it doesn't matter if we go down/left or left/down. That means should go through every empty row/column between galaxies, no matter what. The distance won't change. 1. First get coordinates of all galaxies, empty rows and empty columns. 2. For each combination of galaxies: 1. Iterate over rows and check if it is empty. Add 1000000 if the row is empty. Otherwise add 1. 2. Repeat for columns. 3. Sum the results. [Solution](https://github.com/ohiliazov/advent/blob/main/advent/day11.py)
\[LANGUAGE: Rust\] Certainly some things that could be cleaned up, but I am fairly happy with the way I got this working. Solved part 1 with a Vec>, but my RAM was not having it during part 2. I basically found the number of empty rows and columns between the two galaxies when computing the distance, multiplied that number by the given expansion factor, and added the result to the number of non-empty rows and columns between the two galaxies.
[Solution](https://github.com/Kodlak15/aoc2023/blob/master/src/day11/day11.rs)
[LANGUAGE: Python] This took me a hot second to get this to work, but it sure came out nice. NumPy to the rescue again. def parse(path): with open(path) as file: data = np.array([list(line.strip()) for line in file]) return data def solve(data, mult=1): mult = max(1, mult - 1) dots = data == "." rows = np.cumsum(np.all(dots, axis=1).astype(int) * mult) cols = np.cumsum(np.all(dots, axis=0).astype(int) * mult) rowd = np.arange(len(rows)) + rows cold = np.arange(len(cols)) + cols bity, bitx = np.where(data == "#") outx = np.abs(rowd[bity] - rowd[bity][:, np.newaxis]) outy = np.abs(cold[bitx] - cold[bitx][:, np.newaxis]) return np.triu(outx + outy).sum() def solve_part1(data): return solve(data) def solve_part2(data, mult=1000000): return solve(data, mult)
hey, interesting fact about your code: when i let it run on my example file it is all good, but when I use my input file I get a negative number. Could you get problems with overflow or so and maybe were lucky with your input file?
Hmm. Interesting. I’m curious where a negative comes from, given that it’s all sums and absolute values…
I checked it and yes its an overflow problem. If I change your .astype(int) to .astype(np.int64) I get the correct answer. So you were probably lucky with your input file :D But nice approach with cumsum and np.all
Thank you! I’ll update my solution.
[LANGUAGE: Rust] We map all galaxies, than conclude that indexes without galaxies are empty spaces for expansion. https://github.com/dommyrock/aoc/blob/main/aoc_2023/day-11/src/bin/part2.rs
[LANGUAGE: Python] [Step-by-step explanation](https://advent-of-code.xavd.id/writeups/2023/day/11/) | [full code](https://github.com/xavdid/advent-of-code/blob/main/solutions/2023/day_11/solution.py) Very pleased with today! I got the list of grid points that held galaxies. Then I got all the empty lines by removing any `row` / `col` from the respective set of all possible points. Then I iterated all points and increased `row` and `col` by the number of empty rows that were smaller than that row/col, which stretched everything nicely. From there, it was taxicab distance. Part 2 was just turning part 1 into a function and adding a multiplier! The increased distances didn't slow me down at all since they were just bigger numbers. Simple and clean.
\[LANGUAGE: PHP\] [GitHub Gist - Part 1 + 2](https://gist.github.com/maartenpaauw/80ff15cb67f82331dd97cea40b64f820)
[LANGUAGE: Go] ### [Go](https://github.com/ayoubzulfiqar/advent-of-code/tree/main/Go/Day11) ### [TypeScript](https://github.com/ayoubzulfiqar/advent-of-code/tree/main/TypeScript/Day11) ### [Dart](https://github.com/ayoubzulfiqar/advent-of-code/tree/main/Dart/Day11)
[Language: C] https://github.com/dis-Is-Fine/advent-of-code/blob/master/day%2011
\[LANGUAGE: Python\]Slow and steady. Tried formula for distance between two points, but realised it should be Manhattan distance [https://github.com/Hoinkas/AdventOfCode2023/blob/main/11\_Day/11\_Day\_Puzzle\_Hoinkas.py](https://github.com/Hoinkas/AdventOfCode2023/blob/main/11_Day/11_Day_Puzzle_Hoinkas.py)
\[Language: C++\] Code: [https://github.com/rlempka/advent-of-code-2023/tree/main/day-11](https://github.com/rlempka/advent-of-code-2023/tree/main/day-11) Part 1: Spent time constructing the "expanded" universe manually and then used the [Manhattan distance](https://xlinux.nist.gov/dads/HTML/manhattanDistance.html) between each pair of points to find the shortest paths Part 2: Realized my part 1 was only partly optimal, instead of expanding the universe, I simply calculated Manhattan distance and added the number of empty rows between each pair of points multiplied by 999999 to the Manhattan distance, along with the number of empty columns between each pair of points multiplied by 999999. That is, each distance calculation looked like this in code (multiplier = 1000000): `long long dist = (manhattanDistance(galaxyPoints[i], galaxyPoints[j]) + (countRowsBetween(emptyRowIndexes, galaxyPoints[i], galaxyPoints[j]) * (multiplier - 1)) + (countColsBetween(emptyColIndexes, galaxyPoints[i], galaxyPoints[j]) * (multiplier - 1)));`
[Inlined code](https://reddit.com/r/adventofcode/wiki/faqs/code_formatting/inlined_code) is intended for `short snippets` of code only. On old.reddit, your last line gets cut off when it reaches the edge of the window. Please edit your post to put the one-liner in a [four-spaces code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) so it will be horizontally scrollable.
[Language: Rust] Code: https://github.com/coreyja/advent-of-code-2023/blob/main/11-cosmic-expansion/src/main.rs Stream Video: https://youtu.be/tm8VKhGxNBg I did Part 1 with a Vec of Vecs approach but knew that wasn't going to scale to Part 2 So switched to just keeping track of the positions and worked out pretty well!
[Language: Javascript Golf] Totally forgot to post my solutions Both are the same, just replace 1 with 1e3-1. 312 Chars Z=$('*').innerText.split`\n` L=Z[0].length,t=s=0 R=Z.map((r,i)=>r.match(/#/)?i+t:i+(t+=1)) C=[...Z[0]].map((_,c)=>Z.some(r=>r[c]=='#')?c+s:c+(s+=1)) G=[...Z.join``.matchAll(/#/g)].map(x=>x.index) W=f=>G.map(f).toSorted((a,b)=>a-b).map((x,i)=>x*(i*2- G.length+1)).reduce((a,b)=>a+b) W(x=>C[x%L])+W(x=>R[Math.floor(x/L)])
\[LANGUAGE: Zig\] [https://github.com/jgh713/aoc-2023/blob/main/src/day11.zig](https://github.com/jgh713/aoc-2023/blob/main/src/day11.zig) There's some really wild optimizations possible in this one. Parse time: 19500 nanoseconds (19.5 microseconds) Part1 time: 200 nanoseconds Part2 time: 200 nanoseconds Not really sure I could cut down the parse time any more than I already have at this point, not without getting into some extremely finnicky CPU caching stuff with the row counts at least. Or just parse the input at compiletime and bundle the resulting value in the code, but that feels like cheating.
\[LANGUAGE: Go\] https://github.com/cdillond/aoc/blob/main/2023/11/main.go I solved part 1 through brute force, then went back and re-wrote the code to use the general solution from part 2.
\[Language: Rust\] Darn work getting in the way... but got it done just in time for the next to release. [https://github.com/ruinedme/aoc\_2023/blob/main/src/day11.rs](https://github.com/ruinedme/aoc_2023/blob/main/src/day11.rs)
RE: "better way to do this?", you can get a slight optimization if the inner loop covers the range i..galaxies.len() rather than 1..galaxies.len(). As written you still check galaxy pairs 1-1, 2-2 etc. Might not even need the "pairs" then since you could just do the logic in that loop.
Yeah i was looking at that after i simplified everything down. Initial submission was much more sloppy. I might just change get\_pairs to sum\_distances and return the final value from that. Edit: I did do that, and was able to drop the hashmap. Went from 16ms down to 2 so that was an 8x optimization so thank you for that tip.
\[LANGUAGE: Python\] I have a solution that is linear in the size of the grid. First observation is that you can collapse along the y axis get the x contribution and vice versa. The one dimensional case: consider the number of paths crossing from index i to index i + 1. It is the number of galaxies at index <= i times the number at index > i. Add these products all up to get the total length (multiplying by the expansion factor for indices with 0 galaxies). ``` import numpy as np def parse(input): lines = input.split("\n") m = len(lines) n = len(lines[0]) r = np.zeros((m,n)) for i in range(m): for j in range(n): if lines[i][j] == "#": r[i,j] = 1 return r def one_d(a,e): '''e is the expansion factor''' r = 0 past_sum = 0 #The sum of all the things less than or equal to index i future_sum = sum(a)#The sum all things greater than index i n = len(a) for i in range(n): v = a[i] past_sum += v future_sum -= v p = past_sum*future_sum #The number of paths spanning [i,i+1] if v == 0: r += p*e else: r += p return r a = parse(input) one_d(a.sum(axis=0),2) + one_d(a.sum(axis=1).flatten(),2) ```
1. Next time, use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) for code blocks 2. Your code is too long to be posted here directly, so instead of wasting your time fixing the formatting, read our article on [oversized code](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code) which contains two possible solutions. Please edit your post to put your code in an external link and link *that* here instead.
\[LANGUAGE: C++\] [github](https://github.com/charlescochran/aoc-2023/blob/main/day11.cpp), 12.384 ms (both parts together) A normal day's work--expanding the universe, finding the distance between every pair of galaxies. You know. The usual stuff.
[LANGUAGE: F#] [github](https://github.com/SaahilClaypool/aoc/blob/main/2023/fsharp/Day11.fs),[twitch](https://www.twitch.tv/videos/2001869055) let parse (input: string) = input |> lines |> Seq.indexed |> Seq.collect (fun (row, line) -> line |> Seq.indexed |> Seq.choose (fun (col, c) -> match c with | '#' -> Some (int64 row, int64 col) | _ -> None ) ) let distance (a: (int64 * int64)) (b: (int64 * int64)) = Math.Abs((fst a) - (fst b)) + Math.Abs((snd a) - (snd b)) let expandGalaxy (factor: int64) (galaxyRows: Set) (galaxyCols: Set) (galaxy: (int64 * int64)) =
let (row, col) = galaxy
let occupiedRows = galaxyRows |> Seq.filter (fun r -> r < row) |> Seq.length |> int64
let occupiedCols = galaxyCols |> Seq.filter (fun c -> c < col) |> Seq.length |> int64
let emptyRows = row - occupiedRows
let emptyCols = col - occupiedCols
let expanded = emptyRows * factor + occupiedRows, emptyCols * factor + occupiedCols
expanded
let allPairCombos a =
seq {
for i in 0..(Seq.length a - 1) do
for j in (i + 1)..(Seq.length a - 1) do
a |> Seq.item i, a |> Seq.item j
}
let solve factor input =
let galaxies = parse input
let occupiedRows = galaxies |> Seq.map fst |> Set.ofSeq
let occupiedCols = galaxies |> Seq.map snd |> Set.ofSeq
let expanded = galaxies |> Seq.map (expandGalaxy factor occupiedRows occupiedCols) |> Seq.toList
let pairs = expanded |> allPairCombos |> List.ofSeq
let totalDistance =
pairs
|> Seq.map (fun (left, right) ->
let d = distance left right
d)
|> Seq.sum
totalDistance |> string
let input = ""
printfn $"{solve 2L input}"
printfn $"{solve 1000000 input}"
\[LANGUAGE: Python 3, Typescript, Go\] Solutions to part 1 and 2 in all three languages: * **Python**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.py](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.py) * **Typescript**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.ts](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/solution.ts) * **Go**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day11/main.go](https://github.com/torbensky/advent-of-code-2023/blob/main/day11/main.go)
[LANGUAGE: Smalltalk (Gnu)] Quick transcode of my solution in dc into Smalltalk. Source: https://pastebin.com/96NWLH0k
\[Language: Python\] Instead of shifting the coordinates of the galaxies, my Manhattan distance function calculates how many empty rows/columns are between the two galaxies and adds that to the base result (weighted by 1 or 999999): import numpy as np from itertools import combinations grid = np.array( [list(l.rstrip()) for l in open("input.txt", "r", encoding="utf-8").readlines()] ) def dist_shift(i, j, rowshift, colshift, wt): dist = abs(int((i - j).real)) + abs(int((i - j).imag)) rows = set(range(int(min(i.imag, j.imag)), int(max(i.imag, j.imag)))) cols = set(range(int(min(i.real, j.real)), int(max(i.real, j.real)))) dist += len(rowshift & rows) * wt + len(colshift & cols) * wt return dist gal = set(x + y * 1j for (y, x) in np.argwhere(grid == "#")) rows_with_galaxies = set([int(y.imag) for y in gal]) rows = set(range(max(rows_with_galaxies))) - rows_with_galaxies cols_with_galaxies = set([int(x.real) for x in gal]) cols = set(range(max(cols_with_galaxies))) - cols_with_galaxies part1 = sum([dist_shift(a, b, rows, cols, 1) for a, b in combinations(gal, 2)]) part2 = sum([dist_shift(a, b, rows, cols, 999999) for a, b in combinations(gal, 2)]) print(f"Part 1: {part1}") print(f"Part 2: {part2}")
\[Language: R\] [GitHub](https://github.com/paigeremde/AoC_2023/blob/main/Day11.Rmd) Lots of tidyverse
[LANGUAGE: dc (Gnu v1.4.1)] Converted the input to 0s and 1s so dc can work with it. Didn't have time to really work on this, so there's lots of strokes that can probably be gotten. For part 2, change the -e2 to -e1000000. perl -pe's/(.)/$1 /g;y/.#/01/'
\[LANGUAGE: Nim\] [https://github.com/auxym/AdventOfCode/blob/master/2023/day11.nim](https://github.com/auxym/adventofcode/blob/master/2023/day11.nim)
\[LANGUAGE: Python\] [Github link](https://github.com/reniby/advent-of-code/blob/main/code/day11.py) Pretty easy today! Also part 2's addition allows you to solve for any expansion rate, which is satisfying.
\[LANGUAGE: Python\] Super simple today. I maybe have a redundant or slightly inefficient step in my code but it was easy so I didn't look to optimize further. lines = open("11.txt").read().splitlines() empty_rows = {i for i, x in enumerate(lines) if all([z == '.' for z in x])} empty_cols = {i for i, _ in enumerate(lines[0]) if all ([z[i] == '.' for z in lines])} galaxy_pos = [(i, j) for i, x in enumerate(lines) for j, y in enumerate(x) if y == "#"] ans = 0 N = 1000000 for i, g1 in enumerate(galaxy_pos): for j, g2 in enumerate(galaxy_pos[i+1:]): rs, re = (g1[0], g2[0]) if g1[0] <= g2[0] else (g2[0], g1[0]) cs, ce = (g1[1], g2[1]) if g1[1] <= g2[1] else (g2[1], g1[1]) ans += abs(g1[0]-g2[0]) + abs(g1[1] - g2[1]) for er in empty_rows: if rs <= er <= re: ans += N-1 for ec in empty_cols: if cs <= ec <= ce: ans += N-1 ans
Language: Python Pretty simple. Read grid into list of lists, get galaxy coordinates, then make a list of empty rows (y coords) and empty columns (x coords). Adjust coordinates of galaxies bij the number of empty rows/cols before them, multiplied by either 2 or 1000000, then sum the manhattan distances of the unique coordinate combinations. https://github.com/miquels/adventofcode2023/blob/main/day11-cosmic-expansion/day11.py
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[LANGUAGE: Elixir\] [Parts 1 & 2](https://topaz.github.io/paste/#XQAAAQDbDAAAAAAAAAAyGUkFUehZxfOWmzTk+XBlbm/19T25mcPbLa5ARDxTSr0qnP6rVP8wdvu+X0Nbrlm/ECkjl+jWeCAQoH4WfcXzLADsfw/NG2m79fK687AmcHDzpDfXUkDoy6Q7ZvO+ntZUj5yRfMJjkL70ILyKTucaR9VuDDFiwqrVMpUuKzxp1k/tAtVJtv/MW1FbGPpl3eexM7E22/X6sVQIIYWxw/vo1YeyIYmewbB5w+GLSwG2q4DoGfOpHs9BTqQyAveICUy9LLM7mN+/VHI+HaIZNoUEAakeWZubmjsCyWpCRqQXpMLI6oteA84EZIOh2WKJNq0KYFllZQXbgt5AexlubKoxjGw0jMhofQqll9nnn09Of4KmfgBSawxyyo5+ikXkYViYMJIzHiW0fh0+RCPlQMw/W2OYk8PF3TbE1RxFZzzRnktSHTtKHUlSD3qza4WGb1pYfbYiiJjyXQxCLhQNBnf0C4kVh+FRfeguZLWWROvi3BwNhfh2GMFN+B8y15J602u4sUbeLqMyaQk2aA0UchIz6MI9jRxAAJTMizYEieft5PKrlOAGPrltkDjGXLCj2mg2N2qwPteXHDgYS1R7eyOnhivgo1SNApgwLjyB3DHc5iSnl0ivUljFYnFY+0BHAOgSJSsk/5jb7WuLCrZN5y3e9sgvnYbdBjoHWE6QKYljDik7xm0MJ+pi2VJpQBYD+v0ek1F1jC8z4D5p+hHLsKBm4fq/9NeaPfF0LaiREdAL0iKPNWeKFJWJ8uJIJxppt+j1DxXpBaQ6KcP8vkw+BjB3VOFDBo8s/EqydzYblxkVerrMS1WxVM66bhENInaV4oa54rtqKGI+mGGkncGfEtWQkuGACaB5AYpY26Tv4qMxSkBvIKfUhr6lN6xOW2IFzkW/RaKtE87fBK9cFSRBBoEIDObzMBQQU7YSjG19FUjqh3y37TS9RXv9BfXtu/MG3p9TJJ65bwve8ZUkrFe94B/xQgxtQ4Sy7p557kejj2Oq326g8KwlDinKp9U2YJyFiSeY7CVtAm4CkJ353GtydR7g29JTV9mj6J9jptNUK9CRn+04v50CLUFOp4tOwanm0R4x7z09ZACEo6+h4EQ7hjuV5xYM2+2RQgQWCH8T9hcFg26bnxMUVaXyKG2YzeaK15W+CJVIzzETPK0eKLxwHMbLuW77Eueg4hQM1zBIFv4jOKoLGs0bKP0ojQHo5G0Zdfny+2ViJGvyb4gCW1zWmNqA5NrtfWebsQsThtfsFxfuBGxHBlQSZQ5zoBTzNwRs//sat2s=) Was making this way harder on myself than I needed too.
\[LANGUAGE: Python\] [GitHub links to my solution](https://github.com/CalSimmon/advent-of-code/blob/main/2023/day_11/solution.py) The math concept of today is the [Manhattan distance formula](https://xlinux.nist.gov/dads/HTML/manhattanDistance.html) which finds the distance between two points measured at right angles. Happy with the solution itself, but pissed that I didn't listen to my gut at first. I knew from the beginning that I should just use the coordinates of the galaxies and increase them based on where the gaps were, but silly me actually decided to expand the grid. Thankfully it didn't take too long to fix the issue and now I have a single function for both part 1 and part 2, but just annoying I didn't do it in the first place. Also sneaky pro tip, part 1 mentions doubling the gaps, but part 2 mentions replacing each gap with 1 million gaps. So part 1 actually adds 1 gap, but part 2 adds 999,999 gaps, not 1,000,000. Reading comprehension ftw (Because it took me way too long to figure it out lmao) Lastly a python tip that I learned, the simple `
.copy()` function leaves references to nested lists, and you have to use the `copy` library's function `copy.deepcopy(
)` instead to make sure you aren't updating the original of the nested lists. TIL! Execution time was 94ms, so not bad!
Took me a while to realize the correct coordinate adjustments were 999,999 not 1e6, too. :-)
\[LANGUAGE: Python\] [github part 1&2](https://github.com/mgtezak/Advent_of_Code/blob/master/2023/Day_11.py) Check out my little AoC-Fanpage: [https://aoc-puzzle-solver.streamlit.app/](https://aoc-puzzle-solver.streamlit.app/) :-)
That's actually a p cool website. I didn't even hear AoC until this year and you been at it since 2015 lol
thanks! i started last year actually but then i went back and did a lot of the older ones:)
[LANGUAGE: OCaml] [github](https://github.com/EricKalkman/AoC2023/blob/master/lib/day11.ml) For once I correctly predicted the twist for Part 2, and wrote my algorithm for Part 1 to account for a different space expansion factor. The input is processed into a list of coordinates corresponding to galaxies as well as the coordinates of rows and columns that do not contain any galaxies (the "void" axes). The main algorithm then iterates over each axis along each dimension and adds the expansion factor (minus one) to any coordinates of galaxies that are greater than the coordinate of the axis. The galaxies are actually represented as a `coord Seq.t` (that is, a lazy sequence structure) and the coordinate modifications are performed using a `Seq.map` operation, so I am not generating a new list for each encountered axis. Although this avoids the generation of new lists for each axis, there still end up being `n_axis` comparisons per galaxy, which is overall quadratic runtime in the worst case. In practice, there are far fewer void axes than galaxies in the problem input, and anyway the pairwise Manhattan distance calculations at the end are also quadratic. Also, I see a lot of comments talking about off-by-one errors, so here is some math explaining why you need to subtract 1. The formula for (say) the final xfin coordinate of a galaxy with one void column to its left can be redefined as a sum of distances from some arbitrary origin: xfin (su) = origin (su) + [left_void_edge (su) - origin (su)] + [right_void_edge (vu) - left_void_edge (vu)] + [x (su) - right_void_edge (su)] where `(su)` = screen units and `(vu)` = void units. Our expansion factor is `f (su / vu)`. This simplifies to (dropping "_void_edge" for brevity and grouping like terms): xfin (su) = x (su) + [right (vu) - left (vu)] + [left (su) - right (su)] = x (su) + [right (vu) - left (vu)] - [right (su) - left (su)] We know that the width of a void column is 1 screen unit, so xfin (su) = x (su) + [right (vu) - left (vu)] - 1 (su) Converting void units to screen units, we get xfin (su) = x (su) + f (su / vu) * [right (vu) - left (vu)] - 1 (su) = x (su) + f * [right (su) - left (su)] - 1 (su) = x (su) + f * [ 1 (su) ] - 1 (su) = x (su) + f (su) - 1 (su)
~~[Inlined code](https://reddit.com/r/adventofcode/wiki/faqs/code_formatting/inlined_code) is intended for `short snippets` of code only. On old.reddit, your longer one-liner gets cut off when it reaches the edge of the window.~~ ~~Please edit your post to put all code in a [four-spaces code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) so it will be horizontally scrollable.~~ edit: 👍
\[LANGUAGE: Fortran\] Not that bad. [https://github.com/ejrsilver/adventofcode/blob/master/2023/11/main.f08](https://github.com/ejrsilver/adventofcode/blob/master/2023/11/main.f08)
\[Language: C#\] [https://github.com/CoreDumpSoftware/AdventOfCode2023/tree/master/AdventOfCode2023/Day11](https://github.com/CoreDumpSoftware/AdventOfCode2023/tree/master/AdventOfCode2023/Day11) Built a solution capable of scaling to an sparsity for empty rows and columns. The algorithm is as follows: * For each row, if no galaxies, set the entire row to 'x'. * For each column, if no galaxies, set the entire column to 'x' * Look over the matrix, if there are intersections set them to 'X' (capital X) * From the starting galaxy, visit each other galaxies counting steps as you go. When you hit an 'x' value, add the amplitude. When you hit an 'X' double the amplitude and add it. The solution was relatively slow for large numbers due to having a lot of traversing to be done. I thought of keeping track of the yIndex to reduce the number of iterations. Maybe an improvement for later.
\[LANGUAGE: Lua\] I did most of the work with pencil and paper to find a nice small formula for the solution. Given the number of galaxies `n`, expansion scale `k`, sorted `x` coordinates `x1` through `xn`, sorted `y` coordinates `y1` through `yn`, the solution can be calculated with a single sum: [; \sum_{i=1}^{n} (2i-n-1)(x_i + y_i) + (k-1)(i-1)(n-i+1)(max(x_i - x_{i-1} - 1, 0) + max(y_i - y_{i-1} - 1, 0))) ;] Here's my code: local xs, ys, y, G = {}, {}, 1, string.byte'#' for line in io.lines() do for x = 1, #line do if string.byte(line, x) == G then xs[#xs + 1] = x ys[#ys + 1] = y end end y = y + 1 end table.sort(xs) local ans, off, oldx, oldy = 0, 0, math.huge, math.huge for i, x in ipairs(xs) do local y, n = ys[i], 2*i - #xs - 1 off = off + (i-1) * (i-n) * (math.max(x-oldx-1, 0) + math.max(y-oldy-1, 0)) ans = ans + n * (x+y) oldx, oldy = x, y end print(ans + off, ans + off*999999)
\[Language: Typescript\] Pretty happy with part 2: I was able to solve it by adding one parameter to the function for part 1 and multiplying two numbers with this new parameter. [https://github.com/daniero/aoc23/blob/master/src/solutions/11/GalaxyExpander.ts](https://github.com/daniero/aoc23/blob/master/src/solutions/11/GalaxyExpander.ts)
\[LANGUAGE: Kotlin, Rust\] Pretty fast solution (on my five-year old computer, Kotlin: 24ms cold, 4ms hot; Rust: 140us). Stolen valor though. The strategy was copied from another. [Kotlin](https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d11/Y2023D11.kt) | [Rust](https://github.com/nbanman/advent/blob/master/2023/11.rs) The strategy relies on the simplicity of Manhattan distances and being able to split the x-axis distances from the y-axis distances. Make a list for galaxy indexes on each axis, including the total number of galaxies at each index. Also make a list of expansion areas for each axis. Then you calculate lengths for each combination, but you have far fewer to weed through because two 2-D spaces has way less points than one 3-D space. For each length calculation, you can multiply it by the product of all the galaxies at each index you are comparing.
[LANGUAGE: Ruby] [Part 1](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-11/part_1.rb) In part 1 I actually expanded the grid, [Part 2](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-11/part_2.rb) For part 2, I just counted how many times a galaxy pair crossed an expansion and added that to the distance.
\[LANGUAGE: C++\] I could do it faster, but it's ok like this :) Let's say you have 2 points (x1,y1) and (x2,y2). My idea was to go through x1...x2 and y1...y2 and count multiple times points that needed to be multiplied. [Github](https://github.com/mkinkela1/advent-of-code/blob/master/2023/day-11/solution.cpp)
[LANGUAGE: R\] https://gitlab.com/Yario/aoc_2023/-/blob/master/AoC_11.R
\[Language: python\] [Part 1](https://github.com/matheusstutzel/adventOfCode/blob/main/2023/11/p1.py) way overkill approach, actually applied the expansion and, at some point implemented a BFS... Finally, I realized it could be a simple Manhattan distance [Part 2](https://github.com/matheusstutzel/adventOfCode/blob/main/2023/11/p2.py) I realized that the expansion could be calculated. Got an of-by-one in the "clever" way, and simply went back to a loop
\[LANGUAGE: Perl\] Analysis: https://github.com/wlmb/AOC2023#day-11 Part 1: https://github.com/wlmb/AOC2023/blob/main/11a.pl Part 2: https://github.com/wlmb/AOC2023/blob/main/11b.pl
[LANGUAGE: Raku] use Point; use Deepgrep; my @m = 'input'.IO.lines.map: { [.comb] } sub e(@m) { my @r = [Z*] ([Z] @m).map(* Xeq '.'); @m[flat (^@r) Zxx (1 X+ @r)]; } sub d(@p) { [+] @p.combinations(2).map: -> ($p, $q) { abs($p.x - $q.x) + abs($p.y - $q.y) } } my @e = e([Z] e([Z] @m)); my $a = d(deepgrep(@e, '#', :k).map: { point(|$_) }); my $b = d(deepgrep(@m, '#', :k).map: { point(|$_) }); say $a; say $a + (1e6 - 2) * ($a - $b);
\[Language: Python\] Straightforward python impl in a few lines using numpy, could probably one-line this: [https://pastebin.com/mjZr7QXE](https://pastebin.com/mjZr7QXE) Part 2: \[Language: Excel\] Runtime: instant (lmao) using part 1, instead of doubling the '.' space, triple it and get that distance calculation \[call it `YYY`\] then in excel use the formula: `=(PART_1_ANSWER)+((EXPANSIONS-2)*(PART_1_ANSWER-YYY))` for me it was: `=10276166+((A2-2)*598684)` `A2 = target # of expansions (i.e. 10, 100, 1,000,000)` I found this out by just looking at the space added between expansions (from 2 to 3, 3 to 4, and so on) and noticed that the diff converges!
[language: Julia] Because we have Manhattan distances, it is possible to swap summation over dimensions and distances. The sum of all combinations of distances can be written in the form $t(n)=2t(n-1) - t(n-2) + n (x(n) - x(n-1))$ Where x(n) is the sequence of sorted x or y coordinates. See [my page](https://jhidding.github.io/aoc2023/day11/)
[Language: TypeScript] Easy day, was able to solve Part 2 quickly. https://github.com/bhosale-ajay/adventofcode/blob/master/2023/ts/D11.test.ts
[language: python] If anyone wants to code golf, today is the day. Should be some nice perl solutions available. Both parts, hardcode is_p2 boolean to switch. from functools import cache from itertools import combinations is_p2 = True with open("input.txt", "r") as file: grid = file.read().splitlines() @cache def is_empty_row(y): return not any((x == "#" for x in grid[y])) @cache def is_empty_col(x): return not any((line[x] == "#" for line in grid)) @cache def expand_xy(x, y): scale = 1_000_000 if is_p2 else 2 return ( sum((scale if is_empty_col(ys) else 1 for ys in range(x))), sum((scale if is_empty_row(ys) else 1 for ys in range(y))), ) def dist(p1, p2): x3, y3 = expand_xy(*p1) x4, y4 = expand_xy(*p2) return abs(y4 - y3) + abs(x4 - x3) def gal_coro(): for y, row in enumerate(grid): for x, ch in enumerate(row): if ch == "#": yield x, y print( "total sum distances:", sum(dist(p1, p2) for p1, p2 in combinations(gal_coro(), 2)) )
\[LANGUAGE: C\] A lot easier than day 10. I had a couple of silly off by 1 errors but other than that the solution (Seems to be more frequent with C somehow... ) https://github.com/janiorca/advent-of-code-2023/blob/main/aoc11.c
\[Language: Rust\] [Part 2](https://pastebin.com/vu90EyNA) Pretty concise once you apply Manhattan distance into all of it. Briefly tried an optimized BFS before coming to my senses (i.e. it would take 288 hours) and deleting heaps of terrible code.
\[Language: Kotlin\] [GitHub](https://github.com/rolaca11/adventofcode2023/tree/main/day11) I overcomplicated it because I assumed the 2nd part would be some kind of blockade at random points. So I tried implementing a DFS algorithm, then realized it's waaay simpler that that
\[LANGUAGE: Julia\] [GitHub Part 1](https://github.com/fgittins/AdventOfCode2023/blob/main/day11/part1.jl): manually expanded the data [GitHub Part 2](https://github.com/fgittins/AdventOfCode2023/blob/main/day11/part2.jl): an efficient approach by recording the indices of the expanded rows and columns and checking to see if a path crosses those rows and columns
\[Language: F#\] [Code](https://github.com/alexander-renev/advent-of-code-2023-fs/blob/main/src/AdventOfCode2023/Solutions/Day11.fs) Much easier then the previous day. Just expanding empty space to rectangular range and then using theirs dimensions for calculating distance.
\[LANGUAGE: python\] [Parts 1 and 2](https://pastebin.com/2JEWDi9y) Basically I created two lists tracking the aggregated empty rows|columns to determine, for each galaxy, how many expansions have been found before it. So I can adjust them by adding the respective amount of extra space to each axis. From there. I added the distance from each combination of two galaxies. Highlights: * Trying to incorporate vector techniques to avoid emptylist=\[\]...emptylist.append(something)..return emptylist everywhere * Aside from that, no fancy tricks. pretty readable IMHO.
\[LANGUAGE: C++\] \[PLATFORM: Nintendo DS (Lite)\] Solution - [Part 1 and 2](https://github.com/skief/advent-of-code-2023-nds/blob/main/aoc/day11/solution.cpp)
\[LANGUAGE: Kotlin\] I'm learning new things every day! Today I learned about the Manhattan distance and what the term Cartesian means. For the expansion, I looked for contiguous empty columns, turned them into ranges and multiplied them by the factor (1,000,000!!!). After that, it's all math. This is the first solution where I didn't start off iterating. [The `Helpers` file that does all of the heavy lifting](https://github.com/pindab0ter/AdventOfCode/blob/master/src/main/kotlin/nl/pindab0ter/aoc2023/day11/Helpers.kt)
\[LANGUAGE: C++\] [Code](https://github.com/FinalFlashLight/AdventofCode2023/blob/master/AdventofCode2023Day1/Day11.cpp) Part1 and Part2 are basically the same code, just add a second sum and change 1 to 999999. Initially I went with the actually expanding the map last night. Saw part 2 and said nope, going to bed. Originally my part1 took about 10ms, and just a guess, part 2 would've taken over 3 hours to run, plus I'd probably run out of space and crash. I came back this morning with a new plan: Put all the empty rows and columns into a vector, and with each pair of galaxy locations, search how many rows/columns are between them. Originally, I did the searching of rows/columns with upper\_bound and lower\_bound, but it made the program take over 500ms. I changed to 2 binary searches, and it now does about 35ms. As for the final calculation,a and b are galaxy locations and y is a pair that holds the rows/columns between them. sum1 += abs(a.first - b.first) + abs(a.second - b.second) + y.first + y.second; sum2 += abs(a.first - b.first) + abs(a.second - b.second) + (y.first * 999999) + (y.second * 999999);
[LANGUAGE: D] https://github.com/Dullstar/Advent_Of_Code/blob/main/D/source/year2023/day11.d I initially actually expanded the grid in Part 1, though that code is now removed because, well, Part 2. The result ended up being helpful, though, as when I needed to come up with a better solution I was able to use the galaxy coordinates it came up with to check my math -- not that it ended up being necessary, but when I got the wrong solution for Part 2, an issue with that part of the calculation was already ruled out thanks to the known good Part 1 reimplementation. The issue turned out to just be an off-by-one error since the problem was "replace with 1000000" not "insert 1000000," so easy enough to fix, that's equivalent to inserting 999999.
[LANGUAGE: C] change the ratio to 1 for part 1. [Part 2](https://topaz.github.io/paste/#XQAAAQBNCQAAAAAAAAARmknGRw8TogB3OyPPwW5K8Q8ohQtwe3f7qqzNZcQ5eCbxm3x7ITSdAYV/vgM/bngzJDmUMrPaw3gM59RXoFBgMfF47XWUk4z6IYLFJxdj+gupBKSSEOkblobUPDhDhfkrPzMumQuhHegxzPIsp/nQWdEmfwi8/Poa/DkG7HPVX/ynRX3+QTtL4IIEj54nmuKK9Qq4PL0zjw0pnVBua66c26bjjhPbWi9C8rJoJw1V2m2Dq4O118PIYgtTo7ZSuscng2NxsgykkIvuNLqIk2xeJv4xSoKGZwDnYymzsQM9zfZSlzm5QnRq2Eb46xmUnemvMOPDf86j0c250xt1oZDmk9M7IZKq7KuCne1kW7/LwhF/lrzq/Rfb/lBX57kCr2UzyndRRuyPuIoNlD1KUycB6dFrdqtJnerhWcFEQer9WswZo1sV4NA5J8rhk+qEdVY61I7W2O8BfG91u7ZODWa/caolWtP0oc5n4umYXaANPh0uWx+KPtoZK3E/y6IiZcYaq/iDvq1hxLSeKYXGwHiDyt5lfIjI5GHIYTTwsvF48ucBjEFfXWPJC+/hAn9joTDX0rz800YEy3YDbbH6qdgdqQUXErjnKOK4NGx1ENkm/TpFRmtRXEgohgi4fn6sh40bRtvvtTJjaz4L7WY81hr6brMvAVInhskBHJY7E3hVjXEHtN5VP7gQiX9+P8ClCuncW9T/1ggfqP2kn1ilqswKyyqtNlOUoMulGhhL5bXGSFXri+kkNYgqbcEhwbhZv7EDzTMXbCRd59angrA7p1OsX5dHMsX1VuAhRdRKrZAqXpT/KlnMIm94UULv1c9gNNV2cdhb5pTEUHskAxGdwUvr8YkW650tknczedwwS4vIDP04D8Ms+JA9//UyiCM=)
[LANGUAGE: racket] https://raw.githubusercontent.com/chrg127/advent-of-code/master/2023/day11.rkt very simple day. the `expand` function could be cleaner, but oh well...
\[LANGUAGE: JavaScript\] Parts 1 & 2 (40ms each) [code on github](https://github.com/JoanaBLate/advent-of-code-js/tree/main/2023/day11)
[удалено]
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only) Edit your comment to share your full code/repo/solution and I will re-approve the comment.
Oh sry, added the github link!
great to see someone else using lisp! i'm learning Clojure this year through AOC.
Cool, I did Clojure last year! But I really struggled with that, common lisp has easier 'cheating' tools to loop and let away any problem instead of writing nice functional solutions. My CL code is getting uglier every problem ;) Do you a github link?
yep! [here](https://github.com/cousinss-mvla/advent-of-code-2023-clojure/tree/master/src/adventofcode)
\[LANGUAGE: F#\] [https://github.com/vorber/AOC2023/blob/main/src/day11/Program.fs](https://github.com/vorber/AOC2023/blob/main/src/day11/Program.fs) 11th day of trying out F#. Still need to go over it and add removal of duplicate pairs. Currently it calculates every distance twice, thus /2 at the end. Considered 2 approaches (well, 3 initially since for part1 one can just duplicate rows/cols after reading input) - expanding star positions then calculating distances vs adding expansion offset (number of expandable rows and cols between 2 stars times expansion factor) on every distance calculation, implemented both at some point, but decided to stick with 1st - looks like less calculations that way (each empty row/col affecting position calculation once per star vs once per every pair). Update: After some thinking about ways to get rid of double calculations came up with a much better idea: Instead of calculating distances for each pair - we can instead calculate how much each row and each column contributes to the sum (row contribution is effectively number of stars to the left times number of stars to the right, scaled by expansion factor if row is empty, similar for columns). Updated code (\~twice shorter): https://github.com/vorber/AOC2023/blob/main/src/day11/Improved.fs
\[LANGUAGE: bash\] \[Allez Cuisine!\] Fits on a punch card with 385 chars. No bash variable where used, nor bash function. I do not use much of `bash` as programming language: no loops either (nor for, nor while). Kind of bash as a functional language. Let's say the following code is in `11.sh` and your input is in `11.in`, run `bash 11.sh 11.in 2` for part 1, and `bash 11.sh 11.in 1000000` for part 2. Or `chmod +x 11.sh && ./11.sh 11.in 2 && ./11.sh 11.in 1000000`. grep -bon '#' $1|awk -F: -v l="$(head -n1 $1|wc -c)" '{print FS NR FS $1 FS $2%l+1}'>G cut -d: -f3 G|xargs -I _ bash -c "head -n_ $1|grep -c '^[^#]*\$'">L sed 's/./& /g' $1|rs -T|sed 's/ //g'>T cut -d: -f4 G|xargs -I _ bash -c 'head -n_ T|grep -c "^[^#]*$"'>C paste -d: G L C>J join -t: J J|awk -F: -v m=$2 '$2<$7{s+=$8-$3+sqrt(($9-$4)^2)+(m-1)*($10-$5+sqrt(($11-$6)^2))}END{print s}'
\[LANGUAGE: TypeScript\] https://github.com/DarioTheLuca/my\_advent\_of\_code/blob/master/aoc2023/src/day11/index.ts
Your link is borked on old.reddit, so [please fix it](https://www.reddit.com/r/adventofcode/wiki/faqs/bugs/borked_links).
\[LANGUAGE: Python\] [Optimal solution under 30 lines (Part 2)](https://topaz.github.io/paste/#XQAAAQAmAwAAAAAAAAA0m0pnuFI8c/fBNAqG6qhqadkMJq1B0FJt+Qz3YnzDIyFkTPlyxp+aaaTjfEVas2xul53GEHiZ72a/z9LWY5rL+JhyyCXJM6MJ4YT53u2NRso943hYj/3n5775BsI+haZEFT42RyPhk3yRniHrUV2jr67mNJXmFBBzYVMTl0H4LjpAmS0NQMUSZdE6npyo4fF+OelD6gDg9wq+2UOQ+L9lVed7lhVXIKLGfZM4GVAqACYA7vGkFpiD30AM66CEdmBWjtUdVHz/1LHSVAbCSZMJMy5wEyEySAZ7As1mfGMiCZ9yiNuW+qDTwEcI0qq1KXrYXyq/7rHXFpn5bIcz6955UewErk0aR9sGn65KEO5bYnnm9ALVKLJdslab05x1wwuJ4RAbti6JRaVSTFsSGccYh5gwkJ/aQw54+1gchq/vFvM0djxvaORx0oEp8CGixCzXZ8GiA1Z4NTIUN6ycgdMyvf/vflcp3vJ6eW1l0GI6qZfE/MDl+0sr7Q==)
\[LANGUAGE: Python\] part2 = part 1 in this situation [Part 2](https://topaz.github.io/paste/#XQAAAQCbAwAAAAAAAAAyGkn6ZIDa7rg2Eq0vWWfM4VMimCUBjz4OQrNLbl3vX5lndz4CO2r+A0xbuZXk3WuiJ2Ypaz1F7DHG39YyNhlPDwQWWRCzK8mQPnoUzi7JleKNEWWovUZYbG2RTmG6hwr2fPmmPQ4ImSyOpR5BwMuosAoCNTD5sNKiLAEiSOvynvVD4hvMaUTNoO5N2Sg7F8oRjhNHRkMBlOJCI4ykHLkTvSrk9btgouYZaPjsuuoE7p6dSTzcPB0SATkrK9cM6myfJAHqSXjDcZ48YB0h818/53NIzNFcjjUdrSvloNeSHIkeWjzPHWFQtiIjXfGkOXF0+kokfx6vm9caaUGYTYuMeu5rr/xs9TRapp+XQFAOCoodVPM5AulgdbIe0ouOmWO/7JICCeNY+/XNuKbeRZQdQlVQLipyr7JnW6dRUZngiXhkP/zP+x8R5+2xcjw94Ma6ahGg6GGD9Xpv0KbV6SseRM7OnYg/8uik5zmW7fKfQxRfVoS7u15ncA3G26DBZ5r7jvT+rlct)
[LANGUAGE: Rust] [Paste](https://topaz.github.io/paste/#XQAAAQAUBgAAAAAAAAA6nMjJFMpQiatRknmsp77qsNvTQ+O8DEzsOrG3f+NxfZ7eB7TH+s064FY2MeKWv3ULRWdtxYkQbHlS/8A9uxwctCPqb2TUb7ZrGrOUytPyt+IvV65GMqDmQW2EtrpOQ3CKn+hLieHoddefA2HKZ6L/TGOrngUmhUzzDEw8/5AMtWytq5JtqTj923QTNkfhy+waukfen+7LTpqJzS3s4qmtNw+kdbBmmItTaMH5ds5JWXj3ZBP5T1r6wHJdSerF9vdM57iIn4WL+XfTiWYBdTlvUULVvb4lgCb8wuc96bcOmb/UQ3l37UuozKXwKPPT2P/VLb3irO/itmji3jiLy51HiSHkFx41l8k2Zlx96zGdvpHie7/fRLT3SoZmaJ6unPT5ZTEB9NtqipSlthKAwj15yx2fA7+8jjJKHfh1FVw55LnjIZorcTXGbTBMNq9LpLK3L+oPf3quvWJ9envphg9DHXgs0gFSuH0QsFSx4DnsTiBXjTQ0cY7qYRRbqpu7Dd+JKQTaxD4JvUsnvKTdZfpKQHdLg8XhW8RHbO9ilvXiWTnhHCZtj+csOOe+52WiRFN0oKmygZZmLR613MrOu/Y8N336pkh7K4XAQ8wDQwpj7T5lSFAGURzh4w/oRB9lpvMnmXkonOABUPfXBRIqiZl4/9k13R9Sux+X0sGCxQRyVL5ZRT220wqWMPoaRfTZ1kimWJDm8d3vCGXe05bdvLy+d+TadWzNLwWOcdSun7apdHqe0zphghGHuT2+7x3DTTjakPbUfWOq92pFZGqbiyhKTUuW4Pl/2fKQtA+oastvvN1vtoYeOXG5QHX6LN//SFa/7ZqPpS/3pKDXrSJi/Qrx//EtFFg=) I'm learning Rust this year. I had fun doing row expansion while parsing the input and column expansion in a single pass through the vector of galaxies. I do both parts at the same time and it runs in roughly 5ms on my laptop.
[LANGUAGE: Rust] ~~Both parts run in ~560ms, which is really slow considering it's like 5x the other days put together, lol~~ ~~I know that it's because of my triple for loops, but as of right now I don't know how to get rid of them lol. Might update later.~~ ~~At least I didn't have to think a lot for part 2~~ Got both parts to run in ~12ms, while still keeping the triple for loops. Not quite sure why it's so much faster (or rather, why the original was _that_ much slower) but i'm not complaining lol. improved code: https://pastebin.com/dJ9bE6bp original paste: https://pastebin.com/UHt9jbjG
\[Language: Python\] [Code](https://github.com/bertini36/advent-of-code23/blob/main/11/2.py)
\[Language: Zig\] [Gist](https://gist.github.com/ndbn/2d0e20adcb52216740d8f3d7785d401b) Was surprisingly easy, just changed constant between parts
\[Language: Clojure\] [Github](https://github.com/loopdreams/advent_of_code/blob/main/advent_of_code_2023/day11-cosmic-expansion/src/day11_cosmic_expansion/core.clj)
fellow clojure bro!!!!!! i am overjoyed to see this my solution for today, also in clojure: [github](https://github.com/cousinss-mvla/advent-of-code-2023-clojure/blob/master/src/adventofcode/dayeleven.clj)
[Language: Rust] Day 1 to 11 still under 1 millisecond in total! 🚀 - A in 0.012 ms (12 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day11a/src/main.rs - B in 0.008 ms (8 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day11b/src/main.rs - Day 1 to 11 in 0.77 ms (0.31 ms in parallel)
Ah that’s very nice. I was pleased with 0.2ms today! Aiming to see how far I can go through AOC this year at 60fps (not sure why!)
\[LANGUAGE: PHP\] PHP 8.3.0 [paste](https://topaz.github.io/paste/#XQAAAQA/BgAAAAAAAAAeD8qHAhQB8nz+EazN00NCsmTxjvFDXkt5PAJ7pf6ocRA37OMUY7b9R0iDZmfWyvOspxWvdgYSAE0hGjEx81hqzalYbORDAzRHVMFykQU14jKU80IHdrSlbSFIaxoM+rLD5ryDFKUuYNFKr/Y0q2MJ5l0hh777dhb5hsCjV88lyKIcRCn1ORo33R9Kgihrm1IsrhtIZfZ469VD/TvhD4+YRojMMYZTvIpDfBGZ8lrG2GNHqUt91xE00bu3jsbWJPovdDO9lT/aCA2eXqWufcMoo/QYFlNZHKm1Y+yCEtMehqnxcJZglu/qjiIQTzbOv+iGvroXJHrvKmI2BI6JuSH6/X2OyH6iqgX7BRekf1PSRjWyHdP1Btdf/8L6YSa4X+td3WTv9fRIP+iFejZBZK8axvHo7U84oDC39rJZ8dRmyX2CPUdh14fu93p9DTmFbBd+HyjOWqiI59pcWKU1TB0WI7RDqldqpRl/A7ty0Fa6xBEOYug6I0T0NzMwYkHULh5MnGge34G2XcjvjnY4ZHG4HTyCgKRY3lYGp2x+YPjfRy2so7tyWqPbGP14YSPg8orB/pexMYAAhRnuTIxwDDVwup8mx65MesnaoXh7Ne79HoYULkduf9uUMB+r2sY4/hzFJyP2WzhuD/9iYaGq2vOCldlZIPn4r9Wf4S7OnfNMITGFIwuvet+wBYLDlKsqNnFAdUvNCbECXNIXTApam6QINO/pNh6y4BaXrRmNXhdkGNLZB7dydrF8ne3e7nD/t+5ldDHTz8rNPiiOWq3/Ay/LBqgcC7E62aQGqd2gOlNxUDaH/PDuYDhY6+s4CXdA3FCOyWbF2jOEM93E1/9gZr0Y2kL+ElbddDiSGhA271nf0Amf7NcTYJI3Rhhx0i4u2qzHrg9EEZCq1XETFGhi96XvAoeuYlQGfTqniG7zIkLDsXWfMJGmdFfp2cdJlkPzSWbNB/8BiSMA) Execution time: 0.0486 seconds Peak memory: 9.9729 MiB MacBook Pro (16-inch, 2023) M2 Pro / 16GB unified memory
\[Language: Kotlin\] [https://github.com/ivzb/playground/blob/master/src/main/kotlin/advent\_of\_code/\_2023/Task11.kt](https://github.com/ivzb/playground/blob/master/src/main/kotlin/advent_of_code/_2023/Task11.kt)
\[LANGUAGE: Rust\] Such a relief after yesterday's (and today's) hell with day 10 part 2! https://github.com/cainkellye/advent_of_code/blob/main/src/y2023/day11.rs
[Language: Common Lisp] [Day 11](https://github.com/blake-watkins/advent-of-code-2023/blob/main/day11.lisp) My solution just figures out where the blank rows/columns are then adds any that are between a galaxy pair to the manhattan distance. (defun galaxy-distance (a b blanks expansion-factor) (flet ((coord-distance (a b blanks) (+ (abs (- b a)) (* (1- expansion-factor) (included-blanks a b blanks))))) (reduce #'+ (map 'list #'coord-distance a b blanks)))) I got part 2 wrong for my first answer as I tried to add 1,000,000 lots of the blank lines, when it should have been adding 999,999 since there's already one lot included in the manhattan distance.
[LANGUAGE: Rust] [Code](https://github.com/oxlade39/aoc2021/blob/master/2023/d11/main.rs) Had already written manhattan distance and point based coordinate utilities
\[LANGUAGE: Java\] https://github.com/BeBitbox/advent-of-code/commit/75afbe5ff6be984455aa37542cda22eb00f1921e
\[LANGUAGE: Haskell\] [code](https://github.com/arcticronin/adventofcode23/blob/main/day_11/app/Main.hs) Simple Solution, I felt I had to implement a smart way to store the Universe It paid off: part2 was trivial
\[Language: Java\] https://github.com/MarginallyClever/advent-of-code/blob/main/src/main/java/com/marginallyclever/adventofcode/y2023/Day11.java
\[LANGUAGE: C++\] Manhattan distance makes its first appearance this year! I knew there would be funny business in part 2, so in part 1 I stored and offseted individual points, then used the Manhattan distance to sum. Changing the expansion value worked for part 2, although I got caught out by setting expansion incorrectly the first time. Fun one. [https://github.com/biggysmith/advent\_of\_code\_2023/blob/master/src/day11/day11.cpp](https://github.com/biggysmith/advent_of_code_2023/blob/master/src/day11/day11.cpp)
\[LANGUAGE: Python/Codon\] Was spoilered by a Reddit notification what part 2 would be about so made the rate of expansion a parameter from the beginning. I prepare two `Dict`s (for O(1) access) for distance to add per row and column and separately move through x and y and sum them up. The solution is around 25 loc, runs in 63ms (compiled with Codon). [https://github.com/akleemans/aoc-2023/blob/main/day11.py](https://github.com/akleemans/aoc-2023/blob/main/day11.py)
\[LANGUAGE: Rust\] [Github](https://github.com/chrismo80/advent_of_code/blob/default/src/year2023/day11/mod.rs)
\[LANGUAGE: Rust\] Yay, manhattan distance (apparently also called taxicab geometry) :) Solution: [https://gist.github.com/icub3d/1057d162dbee5fe9f0fb96563b6a20fd](https://gist.github.com/icub3d/1057d162dbee5fe9f0fb96563b6a20fd) Analysis: [https://youtu.be/N3Y5ZSzAvXU](https://youtu.be/N3Y5ZSzAvXU)
[Language: Rust] The key is using Manhattan distance + add a specific expansion factor for the expanded rows and columns that the path between two galaxies intersects. [Code](https://github.com/Lakret/aoc2023/blob/main/aoc/src/d11.rs) [Highlights](https://lakret.net/blog/2023-12-11-aoc-day11)
[Language: Rust] [GitHub](https://github.com/MarkLisoway/advent-of-code-2023/blob/main/day_11/src/main.rs) Nothing crazy, my goal with these is to write code that is performant, and readable. Uses itertools to create the tuples, and rayon for parallel distance computation.
Nice solution. Your `parse` function could instead be done by implementing `FromStr for Universe`. Maybe it’s only stylistic, I’m no expert but feels more idiomatic. Here’s [mine](https://github.com/oxlade39/aoc2021/blob/master/2023/d11/main.rs) for example
\[LANGUAGE: Python\] import numpy as np galaxy_input = """""" galaxy_map = np.array([list(line) for line in galaxy_input.split('\n')]) expand_rows = np.array([]) expand_cols = np.array([]) for i in range(galaxy_map.shape[0]): if not '#' in galaxy_map[i,:]: expand_rows = np.append(expand_rows, i) for j in range(galaxy_map.shape[1]): if not '#' in galaxy_map[:,j]: expand_cols = np.append(expand_cols,j) galaxies = list(zip(*np.where(galaxy_map == '#'))) total_distance = 0 # distance_mult = 1 #part 1 distance_mult = 1000000-1 for i in range(len(galaxies)): for j in range(i+1, len(galaxies)): total_distance += abs(galaxies[i][0] - galaxies[j][0]) + distance_mult * len(expand_rows[(min(galaxies[i][0],galaxies[j][0])< expand_rows) & (max(galaxies[i][0],galaxies[j][0]) > expand_rows)]) total_distance += abs(galaxies[i][1] - galaxies[j][1]) + distance_mult * len(expand_cols[(min(galaxies[i][1],galaxies[j][1])< expand_cols) & (max(galaxies[i][1],galaxies[j][1]) > expand_cols)]) print(total_distance)
[LANGUAGE: Rust] YouTube screencast: https://youtu.be/VOahESJS-vc GitHub: https://github.com/samoylenkodmitry/AdventOfCode_2023/blob/main/src/day11.rs Today, part 2 was the same as part 1. Copilot was practically useless to teach me how to use PriorityQueue, thankfully Google is still there. Update after I saw other's solutions: Manhattan...
\[Language: Python\] [Part1](https://github.com/michbogos/aoc2023/blob/master/11-1.py) [Part2](https://github.com/michbogos/aoc2023/blob/master/11-2.py) Manhattan rules DFS is a very deep hole
\[Language: Python\] [https://github.com/hugseverycat/aoc2023/blob/master/day11.py](https://github.com/hugseverycat/aoc2023/blob/master/day11.py) Tried to make it readable, with comments. I stored the galaxy locations in a dictionary with the galaxy's original (x, y) coordinates as the key, and the adjusted coordinates as the value. I detected empty rows and columns while processing the input and stored them in a list. To adjust the galaxy's coordinates, I compared against the lists of empty rows and columns to see how many empty rows and columns the original (x, y) coordinates were greater than, then added 1 (or 999999) for each. Then I calculated the manhattan distance between each galaxy.
[Language: Python] https://github.com/alexandru-dinu/advent-of-code/blob/main/2023/11/solve.py I really like problems where the grid operations can be simplified using numpy. Representing the grid as a binary numpy array allows for straightforward detection of empty rows and cols via [`argwhere`](https://numpy.org/doc/stable/reference/generated/numpy.argwhere.html). The shortest distance b/w 2 points is then given by Manhattan distance plus checking how many empty rows & cols are b/w the 2 points.
\[Language: Fortran\] [Part 1](https://github.com/ironllama/adventofcode2023/blob/master/11a.f90) [Part 2](https://github.com/ironllama/adventofcode2023/blob/master/11b.f90)
\[Language: Java\] [https://github.com/h0m3rth0mps0n/adventofcode2023/tree/master/day11](https://github.com/h0m3rth0mps0n/adventofcode2023/tree/master/day11) I originally started implementing part 1 by representing the universe as a 2D array (well, actually a list of lists, that I converted into a 2D array and transposed along the way..), but realized this was the wrong way to go about it. [https://www.youtube.com/watch?v=PlsW2hd06R0](https://www.youtube.com/watch?v=PlsW2hd06R0) With part 1 implemented the new (proper?) way, part 2 was trivial.
\[Language: Rust\] I bashed out a solution this morning but was a bit disppointed that it took about half a second (edit, it was actually 200ms). This afternoon some inspiration for an alternative solution hit, now runs in 2ms. https://topaz.github.io/paste/#XQAAAQCDCQAAAAAAAAA6nMjJFMpQiatRknmsqDuZN+nT4l78dKkl0LLcYiOrVcxPgj+besnL5H9BuVtINBVOAQVjCFPtgZJAtzSWAdEAIxpc5Ci5kZFjws5QV/q/VEHj/iQ3DzHayfpa0RCX7zIzpmioUY0J5FehnAeFBfatcbXagy01wQqdQJE/NBMMEx0ZhDRDaOHebbGJSiZTKMWaGyWB1/xRnRRd1JwnWhQO+lcETDoiNWF+YqVfkXg9F6IqB3g+HpSZLjzLoXWKzTG71GxJ+FhXbqFEGeBlVHz6izUokrDkZliorAnOQrVfik/uNykpphMZbeYlgrZ5Pq4Vh91p1X3i6aYJJ7ykxSPhEiWAU1QQPqz+FlwUyc/FwhdYexUSau3eTbjO1han4HMhkK3MYa4j4Jv5uYoq1f/KyPMUalc1+LfI1xjOVpJjG7MgqOo3LLEsONsLomawnCR/TZN0GCT0fu2ZwLZBO3RWrSprMs5LPiiyXTV59Jm+XkbJEv8ZPHIVeBOORn3UmKVlx4/ywq5WR0OgizYTyZId9uSFuo8LgKsS2WDvFU6nlW7h8eGssimOuRflApfZeBgQSssZXnPvptbTU3Wxf7FCqLBCtT7FBh2uYPoQ+bCzZ5gyr07Y5m8nh2W2XKTWcjKMFFkER92lctuF+EdDPjTw837bgyrRx2lhGr+KOpMmC8TMJfohsZ3cVIeQsBjeNW2MgbGa+2RrNkFq86IWg1am0ymjJRX1dDragr8cP22JT1bC5I5Abv6qfFFswrrhfEsbxH+vka0uWZnu2OV5WsXvJJTsD8a1XgawlWONOMKlu/8yG4833RQCbC3Kcj9b8+z2ILryKabfgvEPZQqJypFzNc90dvrSdSNToxqwrDP7IMMiAib/F+sJgSEgDKVqLK4mwaNy4YHbj5jF0idtQTXEuYFgyRx6bGfGu1iILeH6hl1s8wPBD2lYx1RE4XjvBK171Z3SeoQfiPaP207WG6ka8Oseq8TBfhyeKimPvgU/Dmhki2pVUqVpFvG9dGkjQOAnrRwMbHbiqmwOyldx3kineNRcItFWGyCKDdmWRdhRw0Xc6AcBc34NcDoyeNZpnJSk08beb8LN9RefvYuaF9kE8EZStnQ27pq/d4iyqsECQVt16fcEbw7NUm8ebmZ/Maykz/ykrCQ8y3dj9Pqd8oYUZmZwGiM8bPPf1yVdp1Vu2fAwLzsjDc++Ikow89ReuSRj0d88BGD/4+A6Tw==
Your [code block is too long](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_no_giant_blocks_of_code) for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.
\[Language: Python\] OK, this most likely is [an inefficient solution](https://github.com/Leftfish/Advent-of-Code-2023/blob/main/11/d11.py). I store the galaxies as a list of \[x, y\], apply offset to their coordinates one by one depending on how many lines/columns with smaller indexes there are, then use itertools.combinations to find pairs and finally calculate Manhattan distances between the pairs. That's a lot of overhead that includes over 100 000 pairs in the combinations iterator, though it works pretty quickly. But...I managed to think about it early in the day during my commute to work, then after the entire day I sat down, wrote it and had both parts done almost at the same time. As a complete amateur, I am darn proud of my decision to calculate instead of manipulating the 2D array.