DEV Community

Cover image for Four-Dimensional Adventure
Robert Mion
Robert Mion

Posted on

Four-Dimensional Adventure

#adventofcode #algorithms #computerscience #programming

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A list of fixed points in spacetime
  • A set of four-dimensional coordinates

Part 1

  1. Understanding the rules
  2. Analyzing example 1
  3. Analyzing example 2
  4. Analyzing example 3
  5. Analyzing example 4
  6. Re-analyzing example 3
  7. Concerned about performance already
  8. Writing a surprisingly working algorithm!

Understanding the rules

Two conditions determine whether two fixed points share a constellation:

  1. Their manhattan distance apart is no more than 3 (a.k.a. less than or equal to 3)
  2. 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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() and reduce()

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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)

Read next

bishwapoudel profile image

Advanced Error Handling in Spring Boot Microservices

Bishwa Poudel -

dhanush9952 profile image

Java Inner Classes and Nested Classes

Dhanush -

dsfhigor profile image

WEB3 BetCandidate

Hígor da Silva Flores -

jagroop2001 profile image

20 TypeScript Tricks Every Developer Should Know 🚀

Jagroop Singh -