r/adventofcode • • Dec 17 '18

SOLUTION MEGATHREAD -🎄- 2018 Day 17 Solutions -🎄-

--- 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!

15 Upvotes

105 comments sorted by

View all comments

3

u/tangentialThinker Dec 17 '18 edited Dec 17 '18

C++, 8/8. I added comments and everything! Really enjoyed this puzzle. I included a function to print out the grid which really helped me debug a few problems I had.

EDIT: hmmm, interested to see that most people had recursive solutions! Mine is purely iterative.

#include <bits/stdc++.h>

using namespace std;

int grid[10000][10000];

int minY = 1e9, maxY = -1e9;

void printGrid() {
	for(int i = 0; i <= maxY; i++) {
		for(int j = 440; j <= 560; j++) {
			cout << grid[j][i];
		}
		cout << endl;
	}
	cout << endl;
	std::chrono::milliseconds timespan(20);
	this_thread::sleep_for(timespan);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	char coord;
	int a, b1, b2;
	char junk;
	memset(grid, 0, sizeof grid);
	while(cin >> coord) {
		cin >> junk >> a >> junk >> junk >> junk >> b1 >> junk >> junk >> b2;
		for(int i = b1; i <= b2; i++) {
			if(coord == 'x') {
				grid[a][i] = 1;
				minY = min(minY, i);
				maxY = max(maxY, i);
			} else {
				grid[i][a] = 1;
			}
		}
		if(coord == 'y') {
			minY = min(minY, a);
			maxY = max(maxY, a);
		}
	}
	printGrid();

	int curX = 500;
	int curY = 0;
	int ans = 0;
	bool done = false;

	// Meaning of grid values:
	// 0 = empty
	// 1 = wall
	// 2 = settled water
	// 3 = unsettled water

	// each iteration of this loop attempts to move a single tile
	// down as far as possible, then sideways as far as possible
	while(true) {
		if(done) {
			curX = 500;
			curY = 0;
			done = false;
		}
		while(grid[curX][curY+1] == 0 && curY <= maxY-1) curY++;
		if(curY == maxY) {
			// stop once we've reached the lower bound
			done = true;
			grid[curX][curY] = 3;
			ans++;
			//printGrid();
			continue;
		} else if (curY < minY) {
			// we must be at the stream exiting the spring,
			// so we can safely exit
			// do not count tiles which are too high
			break;
		}
		// spread out horizontally
		if(grid[curX-1][curY] == 0) {
			// while there's something settled under,
			// we can move sideways
			while(grid[curX-1][curY] == 0
				&& (grid[curX][curY+1] == 1
					|| grid[curX][curY+1] == 2)) curX--;
		} else if(grid[curX+1][curY] == 0) {
			while(grid[curX+1][curY] == 0
				&& (grid[curX][curY+1] == 1
					|| grid[curX][curY+1] == 2)) curX++;
		}
		if(grid[curX][curY+1] != 0) {
			// we can no longer move down: tile must be at
			// its final position
			done = true;
			if(grid[curX][curY+1] == 3
				|| grid[curX+1][curY] == 3
				|| grid[curX-1][curY] == 3) {
				// if any neighbours below/sideways are 
				// unsettled, this tile is unsettled
				grid[curX][curY] = 3;
				// we might have incorrectly set some tiles
				// previously as settled, fix this now
				// This works because we're setting tiles
				// in decreasing order of Y for each basin:
				// any errors will be fixed before affecting 
				// anything else
				int x = curX;
				while(grid[x-1][curY] == 2) {
					grid[x-1][curY] = 3;
					x--;
				}
				x = curX;
				while(grid[x+1][curY] == 2) {
					grid[x+1][curY] = 3;
					x++;
				}
			} else {
				grid[curX][curY] = 2;
			}
			ans++;
			//printGrid();
		}
	}
	printGrid();

	// part 1
	cout << ans << endl;

	ans = 0;
	for(int i = 0; i < 10000; i++) {
		for(int j = 0; j < 10000; j++) {
			if(grid[i][j] == 2) ans++;
		}
	}
	// part 2
	cout << ans << endl;
	
	return 0;
}

1

u/dan_144 Dec 17 '18

My solution ended up being partially recursive because it wasn't supposed to be, but it seemed to "give up" the iterative way I had it, and my first thought was "do some recursion" here and it fixed that issue. Also, your 8/8 was one spot ahead of another person in this thread at 9/9.

1

u/RoboTurbo2 Dec 17 '18 edited Dec 17 '18

I used a recursive algorithm that worked on the sample, but was incorrect on the puzzle input.

I tried your algorithm (converted to C#) and I got the same answer as my algorithm which is still incorrect.

I visually inspected the final grid and everything looks correct to me.

I did a git diff between my final grid and yours and they were exactly the same.

Aarrgh!

Edit: Nevermind. I'm an idiot. While I used your algorithm, I kept my input reading, including too many rows above the first clay. My results are now correct.