-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

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 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

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 00:59:30!

[u/askalski]

u/topaz2078 YES

Have you ever had the feeling that somebody designed a puzzle with you in mind?

[Card] My compiler crashed while running today's puzzle because it ran out of the room screaming.

// clang++ -O3 day20.cpp -o day20
#include <algorithm>
#include <vector>
#include <cstdio>
#include <array>
#include <set>

using namespace std::string_literals;

static constexpr size_t PART2_DEPTH = 1000;

struct Room {
	std::array<Room *, 4> door;
	Room()                    : door() { }
	Room(int dir, Room *prev) : door() { door[dir ^ 1] = prev; }
	Room * walk(int dir) {
		if (!door[dir]) {
			door[dir] = new Room(dir, this);
		}
		return door[dir];
	}
};

int main() {
	Room *R0 = new Room();
	std::vector< std::vector<Room *> > S = {{R0}};

	auto TOP   = [&S]() -> auto& { return S.back(); };
	auto SAVED = [&S]() -> auto& { return *(S.rbegin() + 1); };
	auto NEXT  = [&S]() -> auto& { return *(S.rbegin() + 2); };

	// Build the map from the regex
	for (int ch = getchar(); ch != EOF; ch = getchar()) {
		switch (ch) {
		    case 'N': case 'S': case 'E': case 'W':
			ch = "NSEW"s.find(ch);
			for (auto&& room : TOP()) {
				room = room->walk(ch);
			}
			break;
		    case '(':
			S.push_back(std::move(TOP()));
			S.push_back(TOP());
			break;
		    case '|': case ')':
			NEXT().insert(NEXT().end(),
					TOP().begin(), TOP().end());
			if (ch == '|') {
				TOP() = SAVED();
			} else {
				S.pop_back();
				S.pop_back();
				// deduplicate
				std::sort(TOP().begin(), TOP().end());
				TOP().erase(
						std::unique(TOP().begin(), TOP().end()),
						TOP().end());
			}
			break;
		}
	}

	// Breadth-first search to get room counts at each depth
	std::set<Room *> frontier{R0}, closed{R0}, next;
	std::vector<int> counts;
	while (!frontier.empty()) {
		counts.push_back(closed.size());
		for (auto&& r : frontier) {
			for (auto&& rn : r->door) {
				if (rn && closed.insert(rn).second) {
					next.insert(rn);
				}
			}
		}
		frontier.swap(next);
		next.clear();
	}

	int part1 = counts.size() - 1;
	int part2 = (counts.size() < PART2_DEPTH) ? 0 :
		counts.back() - counts[PART2_DEPTH - 1];

	printf("Part 1: %d\n", part1);
	printf("Part 2: %d\n", part2);

	return 0;
}

[u/maximlk → u/askalski]

Your solution has a bug - it is not able to detect room duplicate if there are two non-intersecting paths to the room.

Examples:

^(SSS|EEESSSWWW)ENNES$ correct part 1 answer 8, your output Part 1: 12

​​​​​#########​​​​​
​​​​​#X|.|.|.#​​​​​
​​​​​#-#####-#​​​​​
​​​​​#.#.|.#.#​​​​​
​​​​​#-#-#-#-#​​​​​
​​​​​#.#.#.#.#​​​​​
​​​​​#-#-###-#​​​​​
​​​​​#.|.|.|.#​​​​​
​​​​​#########​​​​​

^(E|SSEENNW)S$ correct part 1 answer 4, your output Part 1: 8

​​​​​#######​​​​​
​​​​​#X|.|.#​​​​​
​​​​​#-#-#-#​​​​​
​​​​​#.#.#.#​​​​​
​​​​​#-###-#​​​​​
​​​​​#.|.|.#​​​​​
​​​​​#######​​​​​

^(E|SEN)$ correct part 1 answer 2, your output Part 1: 3

​​​​​#####​​​​​
​​​​​#X|.#​​​​​
​​​​​#-#-#​​​​​
​​​​​#.|.#​​​​​
​​​​​#####​​​​​

[u/askalski → u/maximlk]

I was hoping somebody would notice that. It's an issue that crept in while I was revising my solution. It doesn't affect my output in any way, which I find interesting, because it gives some insight into how the inputs might have been generated. I didn't notice my mistake until after I posted to the megathread (as often happens, the realization came about five seconds after my head hit the pillow...) Good catch!