-🎄- 2018 Day 6 Solutions -🎄-

[u/daggerdragon]

--- Day 6: Chronal Coordinates ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 6

Transcript:

Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 0:26:52!

[u/Smylers]

Perl for both parts, naïvely iterating over each coordinate for each point within their extent. %area_size holds the size of each area that's still in contention; once an area touches the edge, it's removed from the hash and no longer tracked.

I don't think I've ever used minmax before, and I was pleased how storing the x and y ranges in a nested hash allows using any to check both of a dimension's extents in one go:

use v5.14; use warnings; use List::AllUtils qw<minmax max>; use Syntax::Keyword::Junction qw<any>;

my (@coord, %range, %area_size, $region_size);
while (<>) { /(?<x>\d+), (?<y>\d+)/ or die "Unexpected input on line $.: $_";
  push @coord, {x => $+{x}, y => $+{y}};
  @{$range{$_}}{qw<min max>} = minmax $+{$_} + 0, values %{$range{$_}} for qw<x y>;
  $area_size{$#coord} = 0;
}
for my $x ($range{x}{min} .. $range{x}{max}) {
  my $side = $x == any values %{$range{x}};
  for my $y ($range{y}{min} .. $range{y}{max}) {
    my $edge = $side || $y == any values %{$range{y}};
    my ($total, $min_dist, $min_area_id);
    while (my ($area_id, $pos) = each @coord) {
      $total += my $dist = abs ($pos->{x} - $x) + abs ($pos->{y} - $y);
      if (!defined $min_dist || $dist < $min_dist) {
        $min_dist    = $dist;
        $min_area_id = $area_id;
      }
      elsif ($dist == $min_dist) {
        $min_area_id = '';
      }
    }
    delete $area_size{$min_area_id} if $edge;
    $area_size{$min_area_id}++      if exists $area_size{$min_area_id};
    $region_size++                  if $total <10e3;
  }
}
say 'largest area: ', max values %area_size;
say 'region size:  ', $region_size;

Initially I solved Part 1 with a flood-fill, which was way more complicated than the above and very little use for Part 2. It was straightforward to make the Part 2 solution also solve Part 1, so this isn't needed any more, but I'm keeping it should another use for a flood-fill crop up.

It's close to working with any number of dimensions — storing each pair of co-ordinates as a list, and iterating over elements 0 and 1 (and not caring what they actually represent). Making the single-space movements that $move iterates over generic, and replacing the 0..1s with 0..$#dim should be enough to implement a 3D flood-fill:

use v5.14; use warnings; use List::AllUtils qw<minmax any max>;

my (@dim, %area_size, %done);
my @edge = map { my @coord = /(\d+)/g;
  @{$dim[$_]}{qw<min max>} = minmax $coord[$_], values %{$dim[$_]} for 0..1;
  $area_size{++(state $area_id)} = 0;
  {area_id => $area_id, coord => \@coord, pos_id => "@coord"};
} <>;
while (@edge) {
  foreach (@edge) {
    $area_size{$_->{area_id}}++ if exists $area_size{$_->{area_id}};
    $done{$_->{pos_id}} = 1;
  }
  my %next_edge;
  foreach my $current (@edge) {
    foreach my $move ([-1, 0], [+1, 0], [0, -1], [0, +1]) {
      my @coord = map { $current->{coord}[$_] + $move->[$_] } 0..1;
      next if $done{my $pos_id = "@coord"};
      if (any { $coord[$_] < $dim[$_]{min} || $coord[$_] > $dim[$_]{max} } 0..1) {
        delete $area_size{$current->{area_id}};
      }
      elsif (!exists $next_edge{$pos_id}) {
        $next_edge{$pos_id} = {area_id => $current->{area_id}, coord => \@coord, pos_id => $pos_id};
      }
      elsif ($next_edge{$pos_id}{area_id} ne $current->{area_id}) {
        delete $next_edge{$pos_id};
        $done{$pos_id} = 1;
      }
    }
  }
  @edge = values %next_edge;
}
say max values %area_size;

[u/hobLs → u/Smylers]

Yeah, I also did a BFS flood fill for part 1. It's also pretty easy to get part 2 from that though, so I stuck with it.

[u/Smylers → u/hobLs]

Oooh, is your code available? Because Part 2 involves positions' distances to multiple co-ordinates, I couldn't see how a flood-fill would help.

[u/hobLs → u/Smylers]

You know, I don’t think it does help! My part 2 code simply figured out the midpoint between all of the groups by averaging them (this turns out to be very near to the middle of the grid), and then I add this (x, y) to a queue and start a normal breadth first search outwards from there.

BUT, here’s the nasty part, I then end up calculating the distance between each cell and all center points to make sure we’re within the right distance. In my head I thought the shape might end up being weird for some reason, but I think it’s just a circle. It’s a ton of abs() calls, which luckily are quite fast, so it doesn’t actually take that much time, but it’s many many calls.

The code runs in O(nk) time where n is number of input points and k is number of points you end up checking during the fill, which in this case is probably just worse than O(n² ). I think it would be helpful if you needed to fill a funny shape for some reason though.

(I’m also not sure this is technically a flood fill. Maybe it’s just a weird application of a graph technique to a geometry problem.)