Advent of Code 2018 Day 25
Task: Solve for X where...
Part 1
X = the number of constellations formed by the fixed points in spacetime
Example input
0,0,0,0
3,0,0,0
0,3,0,0
0,0,3,0
0,0,0,3
0,0,0,6
9,0,0,0
12,0,0,0
It represents:
- A list of fixed points in spacetime
- A set of four-dimensional coordinates
Part 1
- Understanding the rules
- Analyzing example 1
- Analyzing example 2
- Analyzing example 3
- Analyzing example 4
- Re-analyzing example 3
- Concerned about performance already
- Writing a surprisingly working algorithm!
Understanding the rules
Two conditions determine whether two fixed points share a constellation:
- Their manhattan distance apart is no more than 3 (a.k.a. less than or equal to 3)
- They can form a chain of points, each a manhattan distance no more than 3 from the last, between the two of them
Rule two is interesting. Said another way:
If a point is close enough to a constellation, it "joins" that constellation
Analyzing example 1
Here again is the list of fixed points:
0,0,0,0
3,0,0,0
0,3,0,0
0,0,3,0
0,0,0,3
0,0,0,6
9,0,0,0
12,0,0,0
As stated in the instructions:
The first six points form a single constellation: 0,0,0,0 is exactly distance 3 from the next four, and the point at 0,0,0,6 is connected to the others by being 3 away from 0,0,0,3, which is already in the constellation
It seems like these are the points of reference and rules being passed for the first six points:
0,0,0,0 Source: forms constellation A
3,0,0,0 Passes Rule 1 compared to Source
0,3,0,0 Passes Rule 1 compared to Source
0,0,3,0 Passes Rule 1 compared to Source
0,0,0,3 Passes Rule 1 compared to Source
0,0,0,6 Passes Rule 2 compared to prior fixed point
9,0,0,0 Fails both rules compared to all prior points: forms constellation B
12,0,0,0 Passes Rule 1 compared to prior fixed point
It seems deceptively simple to think my list of fixed points will be in some sort of order.
Analyzing example 2
Here is the list of fixed points:
-1,2,2,0
0,0,2,-2
0,0,0,-2
-1,2,0,0
-2,-2,-2,2
3,0,2,-1
-1,3,2,2
-1,0,-1,0
0,2,1,-2
3,0,0,0
Trying to manually identify constellations:
1. -1,2,2,0 Passes Rule 1 compared to fourth point: B
2. 0,0,2,-2 Passes Rule 1 compared to third point: A
3. 0,0,0,-2 Passes Rule 1 compared to second point: A
4. -1,2,0,0 Passes Rule 1 compared to first point: B
5. -2,-2,-2,2 Fails both rules compared to all prior points: D
6. 3,0,2,-1 Passes Rule 1 compared to tenth point: C
7. -1,3,2,2 Passes Rule 1 compared to first point: B
8. -1,0,-1,0 Passes Rule 1 compared to fourth point: B
9. 0,2,1,-2 Passes Rule 1 compared to third point: A
10. 3,0,0,0 Passes Rule 1 compared to sixth point: C
I identified four constellations, which is the correct answer.
The best way I could describe my algorithm:
For each fixed point X
For each fixed point Y
As long as X is not Y (I'm not comparing a point to itself):
Do both points pass Rule 1?
Add them both to a new constellation if X is not already in one
Otherwise, add to the constellation that X is already in
Else - No points pass Rule 1 when comparing X and Y
Add X to a new constellation
That needs a lot more specificity and clarity before I attempt to write it.
Analyzing example 3
Here is the list of fixed points:
1,-1,0,1
2,0,-1,0
3,2,-1,0
0,0,3,1
0,0,-1,-1
2,3,-2,0
-2,2,0,0
2,-2,0,-1
1,-1,0,-1
3,2,0,2
Trying to manually identify constellations:
1. 1,-1,0,1 Passes Rule 1 compared to point 9: A
2. 2,0,-1,0 Passes Rule 1 compared to point 3: B
3. 3,2,-1,0 Passes Rule 1 compared to point 2: B
4. 0,0,3,1 Fails both rules compared to all prior points: D
5. 0,0,-1,-1 Passes Rule 1 compared to point 9: A
6. 2,3,-2,0 Passes Rule 1 compared to point 3: B
7. -2,2,0,0 Fails both rules compared to all prior points: C
8. 2,-2,0,-1 Passes Rule 1 compared to point 9: A
9. 1,-1,0,-1 Passes Rule 1 compared to point 1: A
10. 3,2,0,2 Passes Rule 1 compared to point 3: B
That's four. The correct answer is three. What am I missing?
When I arrange into groups:
2. 2,0,-1,0 Passes Rule 1 compared to point 3: B
3. 3,2,-1,0 Passes Rule 1 compared to point 2: B
6. 2,3,-2,0 Passes Rule 1 compared to point 3: B
10. 3,2,0,2 Passes Rule 1 compared to point 3: B
1. 1,-1,0,1 Passes Rule 1 compared to point 9: A
5. 0,0,-1,-1 Passes Rule 1 compared to point 9: A
8. 2,-2,0,-1 Passes Rule 1 compared to point 9: A
9. 1,-1,0,-1 Passes Rule 1 compared to point 1: A
4. 0,0,3,1 Fails both rules compared to all prior points: D
7. -2,2,0,0 Fails both rules compared to all prior points: C
I notice one Rule 2 passing:
2. 2,0,-1,0 B
3. 3,2,-1,0
6. 2,3,-2,0
10. 3,2,0,2
1. 1,-1,0,1 A
5. 0,0,-1,-1 Passes Rule 2 compared to point 2: Was A, joins B
8. 2,-2,0,-1 A
9. 1,-1,0,-1 A
4. 0,0,3,1 Fails both rules compared to all prior points: D
7. -2,2,0,0 Fails both rules compared to all prior points: C
That causes A and B to form a single constellation:
2. 2,0,-1,0 Passes Rule 1 compared to point 3: B
3. 3,2,-1,0 Passes Rule 1 compared to point 2: B
6. 2,3,-2,0 Passes Rule 1 compared to point 3: B
10. 3,2,0,2 Passes Rule 1 compared to point 3: B
1. 1,-1,0,1 Comes with 5 to join B
5. 0,0,-1,-1 Passes Rule 2 compared to point 2: B
8. 2,-2,0,-1 Comes with 5 to join B
9. 1,-1,0,-1 Comes with 5 to join B
4. 0,0,3,1 Fails both rules compared to all prior points: D
7. -2,2,0,0 Fails both rules compared to all prior points: C
And now I have three constellations!
There was a faster way, though, right?
1. 1,-1,0,1 Passes Rule 1 compared to point 9: B
2. 2,0,-1,0 Passes Rule 1 compared to point 3: B
3. 3,2,-1,0 Passes Rule 1 compared to point 2: B
4. 0,0,3,1 Fails both rules compared to all prior points: D
5. 0,0,-1,-1 Passes Rule 1 compared to points 2 AND 9: B
6. 2,3,-2,0 Passes Rule 1 compared to point 3: B
7. -2,2,0,0 Fails both rules compared to all prior points: C
8. 2,-2,0,-1 Passes Rule 1 compared to point 9: B
9. 1,-1,0,-1 Passes Rule 1 compared to point 1: B
10. 3,2,0,2 Passes Rule 1 compared to point 3: B
I'm perplexed as to how I would do that algorithmically.
How about that last example?
Analyzing example 4
Here is the list of fixed points:
1,-1,-1,-2
-2,-2,0,1
0,2,1,3
-2,3,-2,1
0,2,3,-2
-1,-1,1,-2
0,-2,-1,0
-2,2,3,-1
1,2,2,0
-1,-2,0,-2
Trying to manually identify constellations:
1. 1,-1,-1,-2 Fails both rules: A
2. -2,-2,0,1 Fails both rules: B
3. 0,2,1,3 Fails both rules: C
4. -2,3,-2,1 Fails both rules: D
5. 0,2,3,-2 Passes Rule 1 compared to point 8: E
6. -1,-1,1,-2 Passes Rule 1 compared to point 10: F
7. 0,-2,-1,0 Fails both rules: G
8. -2,2,3,-1 Passes Rule 1 compared to point 5: E
9. 1,2,2,0 Fails both rules: H
10. -1,-2,0,-2 Passes Rule 1 compared to point 5: F
I identified eight constellations. That's the correct answer.
I feel like I know what I'm doing mentally to generate the correct answer, but describing it algorithmically still feels difficult.
I need to redo example 3.
Re-analyzing example 3
Trying to manually identify constellations correctly in one pass:
1. 1,-1,0,1 Passes Rule 1 compared to point 9: A
2. 2,0,-1,0 Passes Rule 1 compared to point 3: A
3. 3,2,-1,0 Passes Rule 1 compared to point 2: A
4. 0,0,3,1 Fails both rules compared to all prior points: D
5. 0,0,-1,-1 Passes Rule 1 compared to points 2 and 9: A
6. 2,3,-2,0 Passes Rule 1 compared to point 3: A
7. -2,2,0,0 Fails both rules compared to all prior points: C
8. 2,-2,0,-1 Passes Rule 1 compared to point 9: A
9. 1,-1,0,-1 Passes Rule 1 compared to point 1: A
10. 3,2,0,2 Passes Rule 1 compared to point 3: A
When a point passes Rule 1 with respect to two points that are in different constellations, it must collapse one into the other.
Concerned about performance already
- I intend my algorithm to check N^2 points: 10 points? 100 checks, 10 for each point.
- 100 is no problem
- But my input has 1084 points
- 1084^2 = over 1 million
- That's a lot of checks
- Plus, in each check, there is going to be some work
So, my algorithm may not only generate the wrong answer, but it may do it very slowly.
I don't feel great about this.
But I gotta try!
Writing a surprisingly working algorithm!
Before I started writing it
- I'm willing to try writing one, even though I bet I'll miss some important caveat found only in my puzzle input
While writing it
- Easy part: parse the input into an array of arrays, each one containing four integer values
- I need a dictionary to store points as keys and their associated constellation, which can just be numbers 0 and greater
- Do I need to compare all points to one another, or can I move in one direction?
For example, must I do this?
0,0,0,0 0,0,0,0 0,0,0,0 0,0,0,0
3,0,0,0 3,0,0,0 3,0,0,0 3,0,0,0
0,3,0,0 0,3,0,0 0,3,0,0 0,3,0,0
Or this?
0,0,0,0 0,0,0,0
3,0,0,0 3,0,0,0
0,3,0,0 0,3,0,0
Thankfully - performance-wise - the second approach worked.
- Fairly easy: calculating the manhattan distance of each point compared to the source leverages built-in functions like
Math.abs()andreduce()
For example:
-2,-2,-2,2
3,0,2,-1
-2 -2 -2 2
- 3 - 0 - 2 - -1
----------------
5 -2 -4 3
----------------
5 + 2 + 4 + 3
----------------
14
- My algorithm worked on examples 1 and 2 without needing to calculate a shared constellation, which made things seem deceptively simple
- Example 3 was the kicker: I had to re-factor and expand the logic of my algorithm to ensure that points previously assigned to one constellation that later had a bridging point would get re-assigned to that other constellation
- This took a lot of trial-and-error, and learning how to properly use Math.min() with an array
- Thankfully, I only needed two branches: do one series of steps if there are no 'groups', and do another if there are
- The overly greedy step is where I iterate through every key in my dictionary in attempts to re-assign points to their potentially new constellation
A written description of the full, working algorithm
Parse the input:
Split the input at each newline character into a list of strings
Split each string at each comma character into a list of stringified numbers
Coerce each string into an integer
Prepare the accumulating values:
- Set c as an empty object - this will store each stringified fixed point and the constellation it is part of
- Set counter to 0 - this will store the next constellation to be formed if a fixed point is outside of the range of any other known constellations
The main loop:
For each fixed point A, except the last one in the list
Set matches as an empty array
Set source as the stringified representation of point A
For each fixed point B, starting with the point after A and never back-checking
Check for a passing Rule 1 by performing the following operations:
Calculate the sum of the absolute value of the differences of both integers in the same locations for point A and B
If the sum is less than or equal to 3
Add to matches a stringified representation of B's fixed points
By now, matches will contain each point B that is within a manhattan distance of 3 to point A
Store in groups an array containing the result of the following operations:
Start by adding source
Then add each point in matches
Then replace each stringified point with the constellation assigned to it's key in the object, c, if any. If none exists, it will be replaced by undefined.
Then, filter that list of values to remove any that are undefined, leaving only integers 0 or greater.
If groups is empty, I have identified a fixed point that currently does not fit in any existing constellations. I must create a constellation for it and each of the points that pass Rule 1 compared to it:
Create a key for it in c using counter as the value
Create keys for each of the matches, also using counter as the value
Increment counter by one
Else, if groups contains at least one non-negative number:
Set num as the smallest number in groups
Set (or update) the value associated with point A's key in c to num
Do the same for each of the matches: setting their associated value as num
For each key-value pair in c:
If the value is one of the integers in groups:
Reassign the value as num
Counting the number of constellations:
Extract the list of all non-zero integer values in c
Create a set of only the unique values
Return the size of the set
After writing it, running it, and generating the correct answer
I was surprised for a several reasons:
- I did NOT expect it to generate a correct answer for my input, as I was certain the examples were hiding some important edge case found in my puzzle input
- I did NOT expect it to run as fast as it does - milliseconds instead of seconds. I guess it helps that I don't check every point in each iteration of the main loop. It probably doesn't help that I do check every key in the dictionary.
I honestly anticipated running it, generating an answer that was wrong, and giving up because this algorithm was my best attempt at solving it.
I'm so delighted it worked!
Part 2
- Day 25's never have a puzzle for Part 2
- Part 2 is supposed to instantly award solvers their 50th gold star
- However, this year's text blurb references Day 21
- And Day 21 references Days 16 and 19
- Thus, it looks like I'll have another batch of must-complete-in-chronological-order puzzles this year. Joy.
I did it!!
- I solved Part 1!
- I carefully analyzed each example and the processes by which I arrived at the correct answers manually...thereby helping me devise a strategy for writing the same process as an algorithm
Bummer:
- No simulator. It wasn't going to be fun to watch, in my opinion.
- No GIFs. As much as I wanted to visually depict my algorithm, I'm ready to move on to Day 24 at this point.
Top comments (0)