[2018 Day 25] In Review (Four-Dimensional Adventure)

[u/musifter]

And it turns out that the reindeer medicine we need is the hot chocolate we were working on 1000 years in the future. We just need to open a portal to get it, using constellations of 4D fixed points.

And so we get a problem that's very much like Day 12 of 2017, where we were the number of disconnected subgraphs. Only this time, the input isn't a list of edges. But it's easy to make the graph from the points, so that's what I did. Then I just found the subgraphs on it (with recursion). I suppose I could have done a number of fancier things, like building and counting the constellations in one pass. But reduction to a simpler problem is a standard problem solving technique. It serves me well with twisty puzzles.

And so we come the end of another year. Personally I really liked this year and don't think of it as particularly hard... but I know some people do. But that's probably because a lot of problems were more up my alley, with lots of simulations. Simulations can have a lot of chaos making them hard to debug if you don't get things exactly right. Which I can certainly understand causing a lot of people to spend a lot of time on this year.

Since this was the first year I did live, I took a look at my personal leaderboard times (something I've rarely done). I see a lot of the days (especially early on) I was starting midday. Later on, I seem to have gone to starting at drop, and I got a bunch under 1000. I don't do these things for speed at all (none of the times are great... I don't rush, I take my time)... so that's mostly due to a lack of people doing AoC at the time. Still, in later years, there was typically a problem where I managed to get in the top 1000, not by being fast, but by knowing what to do and just doing it. I think that's probably why the best part 2 ranking I had was day 23 (breaking into the top 300). The scale of the puzzle is a bit overwhelming at first... but I immediately thought "quadtrees in 3D" and worked from there. I might not know all the competitive tricks (I tried one competition in University and decided it was not my thing), but sometimes I have relevant experience for a problem.

[u/e_blake]

This day has a nice speedup by switching from the naive O(n²) pairwise distance comparison of every point to instead an O(n) nearest neighbors check when you realize that the number of possible points fits in a 23⁴ region and there are only 128 possible neigbors per point.

[u/terje_wiig_mathisen → u/e_blake]

Base 23? In my input I only see single-digit numbers, so -9..9 would fit in 21 slots. Since the problem text doesn't specify any limits on (x,y,z,t) I parsed them all as i32. When I tried i8 instead the runtime was still the same, almost exactly 1 ms.

My clique logic was to handle them in input order, each 4D point has an added 'parent' index (usize) which initially starts as usize::MAX.

fn discrete_sets(inp:&str) -> usize
{
 let p = parser!(lines(x:i8 "," y:i8 "," z:i8 "," t:i8 =>   P4{x,y,z,t,set_number:usize::MAX}));
 let mut points = p.parse(&inp).unwrap();
 let mut sets = 0;
 for i in 0..points.len() {
  let mut parent = i;
  sets += 1;
  if points[i].set_number != usize::MAX {
   parent = flatten(&mut points,i);
   sets -= 1;
  }
  points[i].set_number = parent;

  for j in i+1..points.len() {
   if points[i].manhattan_dist4(&points[j]) <= 3 {
    if points[j].set_number == usize::MAX {
     points[j].set_number = parent;
    }
    else { // Merge two sets if they are disjunct
     let jparent = flatten(&mut points, j);
     if jparent != parent { // Pick the lowest/oldest set #!
      if jparent < parent {
       parent = flatten_to(&mut points, i, jparent);
      }
      else { //if jparent > parent {
       parent = flatten_to(&mut points, j, parent);
      }
      sets -= 1;
     }
    }
   }
  }
 }
 sets
}

[u/e_blake → u/terje_wiig_mathisen]

The inputs are [-8, 8] - but existence checks probe [-3, 3]. So base-23 lets me create a perfect hash for all points [-11, 11] without needing to do boundary checks along the way.

Your code is doing the naive O(n²) point pairing. My code does 128 hash lookups per point in an O(n) pass. https://github.com/maneatingape/advent-of-code-rust/pull/31 got a 4x speedup in Rust; my m4 code got closer to a 10x speedup (computing Manhattan distance is slower there)

[u/terje_wiig_mathisen → u/e_blake]

Thanks! There are just enough points that storing them in a 4D lookup tree makes sense,  simply sorting by x would on average reduce the work by a factor of about 3, right? I want to apply some form of bitmap processing, but directly checking all points within the Max Manhattan distance reduces the work factor by almost an order of magnitude (6x) since we got about 1500 points.

15001500/2 Vs 1500128

Otoh each hash lookup is at least one memory access while Manhattan is just 4 parallel sub+abs followed by a 3 adds for the sum reduce and the final comparison.

The latter looks like a simd candidate, possibly doing 8 of them in parallel inside a 32 byte avx register?

[u/e_blake → u/terje_wiig_mathisen]

With only 17 buckets per dimension, a radix sort with O(n) effort will beat a generic O(n log n) sort per dimension, but I'm less certain how complex a 4D lookup structure would be to make lookups of actual neighbors without any wasted lookups feasible, rather than just blindly probing all 128 possible neighbor addresses where many of the probes find nothing of interest. I also wonder if a scan line along one or two dimensions can reduce work needed along the remaining dimensions.

[u/DelightfulCodeWeasel → u/e_blake]

I did think about that this morning but running a quick back of envelope calculation you need to bucket by at least 3 dimensions to beat 128, so I think the hash will end up quicker. 

Are you doing a DSU merge per bucket and updating the parent pointers as you go? I think it'll be pretty hard to beat converting the position to an index, as you are doing, and a couple of pointer ops.

[u/e_blake → u/DelightfulCodeWeasel]

A DSU merge is important if the set is dynamically changing or you need a representative element of a set when given any member of the set. But for just counting the number of disjoint sets, you can go even simpler, by just using a todo queue of points transitively reachable from any arbitrary starting point that has not yet been seen in another point's set, and counting how many times you had to drain the todo queue.

[u/DelightfulCodeWeasel]

Looking back at some of the puzzles I feel like 2018 was the year that Eric really started to hit his stride with AoC puzzle making, and I get the feeling he really had some fun with them this year.

A regex that's actually a maze? Brilliant stuff.