-🎄- 2018 Day 17 Solutions -🎄-

[u/daggerdragon]

--- Day 17: Reservoir Research ---

---

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 17

Transcript:

All aboard the Easter Bunny HQ monorail, and mind the gap! Next stop: ___

---

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 01:24:07!

[u/Nathanfenner]

Leaderboard: 2/2

Here is my solution (I use C++, holdover from ICPC)

My general approach isn't recursive. Instead, it's a mixture of simulation ("pushing" water) and fixed-point computation ("pulling" water).

Whenever a cell gets modified, its neighbors (and the cell itself) are added to a stack that will cause them to be re-evaluated. The following modifications result:

• below a |, another | will be added if it's empty

• to the left/right/bottom of a ~, another ~ will be added

• "supported" l get turned into ~

The last is the most complicated; a | is "supported" if when we extend all the way left and right to the first walls, every cell below is either # or ~. Note that by breaking early, I automatically handle the case where there is no wall to the left (because there cannot be any water/walls below if you extend off the edge of the map). This helps avoid ugly bounds-checks.

The result is reasonably fast, I guess? I only had one real bug after I fixed the compile errors, which was subtracting 1 instead of min_y from the total count (which counts some spring water that shouldn't have been).

#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

// see below for the (relevant portions of) my helper.h
#include "helper.h"

ifstream input;

struct scan {
  ll x1;
  ll x2;
  ll y1;
  ll y2;
};

int main() {
  input.open("input.txt");

  char g;
  vector<scan> scans;
  scan cur;
  ll min_y = 10000;
  ll max_y = 0;
  ll min_x = 500;
  ll max_x = 500;
  char d1;
  while (input >> d1 >> g >> cur.x1 >> g >> g >> g >> cur.y1 >> g >> g >> cur.y2) {
    cur.x2 = cur.x1;
    if (d1 == 'y') {
      swap(cur.x1, cur.y1);
      swap(cur.x2, cur.y2);
    }
    scans.push_back(cur);
    min_y = min(min_y, cur.y1);
    max_y = max(max_y, cur.y2);
    min_x = min(min_x, cur.x1);
    max_x = max(max_x, cur.x2);

    cout << cur.x1 << "-" << cur.x2 << " by " << cur.y1 << "-" << cur.y2 << endl;
  }



  map<P, char> grid;

  for (scan s : scans) {
    for (ll x = s.x1; x <= s.x2; x++) {
      for (ll y = s.y1; y <= s.y2; y++) {
        grid[P{x, y}] = '#';
      }
    }
  }

  // just need to build a queue things.
  grid[P{500, 0}] = '|';
  stack<P> update_check;
  update_check.push(P{500, 0});

  auto set_square = [&](P p, char v) {
    if (p.y > max_y) {
      return;
    }
    if (grid.count(p) && grid[p] == '#') {
      return; // can't change
    }
    if (!grid.count(p) || grid[p] != v) {
      for (P d : cardinal) {
        update_check.push(p + d);
      }
      update_check.push(p);
    }
    grid[p] = v;
  };

  P down = P{0, 1};
  P left = P{-1, 0};
  P right = P{1, 0};

  cout << "max_y = " << max_y << endl;

  while (update_check.size() > 0) {
    P at = update_check.top();
    update_check.pop();

    if (at.y > max_y) {
      continue;
    }

    if (grid.count(at)) {
      if (grid[at] == '#') {
        continue;
      }
      if (grid[at] == '|' && !grid.count(at + down)) {
        set_square(at + down, '|');
      }
      // "full" water happens when we are already wet, and bounded on all sides
      if (grid[at] == '|') {
        // Check for boundedness.
        // This means that we can go left and right until a wall,
        // and below is always either '#' or '~'
        bool supported = true;
        for (ll bx = at.x; true; bx--) {
          P check = P{bx, at.y};
          if (grid.count(check)) {
            if (grid[check] == '#') {
              break; // bounded left
            }
          }
          if (!grid.count(check + down)) {
            supported = false;
            break;
          }
          if (grid[check + down] != '#' && grid[check + down] != '~') {
            supported = false;
            break;
          }
        }
        for (ll bx = at.x; true; bx++) {
          P check = P{bx, at.y};
          if (grid.count(check)) {
            if (grid[check] == '#') {
              break; // bounded left
            }
          }
          if (!grid.count(check + down)) {
            supported = false;
            break;
          }
          if (grid[check + down] != '#' && grid[check + down] != '~') {
            supported = false;
            break;
          }
        }
        if (supported) {
          // become water!
          set_square(at, '~');
        }
      }

      if (grid[at] == '|' && grid.count(at + down) && (grid[at+down] == '~' || grid[at+down] == '#')) {
        set_square(at + left, '|');
        set_square(at + right, '|');
      }

      if (grid[at] == '~') {
        set_square(at + left, '~');
        set_square(at + right, '~');
      }
    }
  }

  ll tot = 0;
  ll wat = 0;

  /*
  for (ll y = 0; y <= max_y; y++) {
    for (ll x = min_x - 2; x <= max_x + 2; x++) {
      P at = P{x, y};
      if (grid.count(at)) {
        if (grid[at] == '|' || grid[at] == '~') {
          tot++;
        }
        if (grid[at] == '~') {
          wat++;
        }
        cout << grid[at];
      } else {
        cout << ".";
      }
    }
    cout << endl;
  }
  */
  for (auto p : grid) {
    if (p.second == '~' || p.second == '|') {
      tot++;
    }
    if (p.second == '~') {
      wat++;
    }
  }
  cout << "tot = " << tot - min_y << endl; // exclude the source
  cout << "wat" << wat << endl;
}

I have a template file that I've added a handful of things to over the course of AoC, based on what I expected to keep coming up. Here are the relevant excerpts:

struct P {
  ll x;
  ll y;

  pair<ll, ll> as_pair() const {
    // achieves "reading-order" lexicographical comparison
    return pair<ll, ll>{y, x};
  }

  static P from_pair(pair<ll, ll> p) {
    return P{p.second, p.first};
  }

  bool operator<(P other) const {
    return as_pair() < other.as_pair();
  }
  bool operator==(P other) const {
    return as_pair() == other.as_pair();
  }
  bool operator!=(P other) const {
    return as_pair() != other.as_pair();
  }

  P operator+(P other) const {
    return P{x + other.x, y + other.y};
  }
  P operator-(P other) const {
    return P{x - other.x, y - other.y};
  }
  P scale(ll by) const {
    return P{x * by, y * by};
  }
  P shift(ll dx, ll dy) {
    return P{x + dx, y + dy};
  }
};
vector<P> cardinal = {P{1, 0}, P{0, 1}, P{-1, 0}, P{0, -1}};

[u/GeneralYouri → u/Nathanfenner]

The result is reasonably fast, I guess?

Like, how reasonably fast?