This year I decided to have fun and solve some advent puzzles. To keep myself motivated I will write everyday solutions and ways of thinking to solve them. Also, I am old so it won’t be some fancy language but plain old Java. (it’s surprising but there are not that many people actually using it to solve any puzzle challenges).
For those who don’t know it’s https://adventofcode.com/ that will give new challenges every day.
Day 11, Let’s start:
On day 11 we need to travel in the galaxy to find our desired hot springs.
We have map and we need to find distances between every two galaxies.
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies. However, there's a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory.
Due to something involving gravitational effects, only some space expands. In fact, the result is that any rows or columns that contain no galaxies should all actually be twice as big.
From the look of it. We need to expand our input to double every empty row and column. Afterward, we just go through all the points and find the distance to every other point (simple abs(x1-x2) + abs(y1-y2) should be enough by the looks of it. Also would probably save columns into some boolean array to check if it's empty or not.
A bit ugly but quick and does its job.
Part 2:
It seems researcher messed up and we should not double the empty galaxies but:
The galaxies are much older (and thus much farther apart) than the researcher initially estimated.
Now, instead of the expansion you did before, make each empty row or column one million times larger. That is, each empty row should be replaced with 1000000 empty rows, and each empty column should be replaced with 1000000 empty columns.
So my approach for the column was actually better than changing the input and I need to do the same for rows. Let’s try it out.
We added this part when creating a map and corresponding code to calculate the distance. The only thing that was tucked in me for a few minutes is that we need to add not 100000 columns but one less… This is obvious from the problem statement but it’s easy to miss.
Keep coding and have one.
— — — — — — —
The code can be found at https://github.com/Mumuksia/codingame/tree/master/app/src/main/java/advent_23
