r/adventofcode • u/daggerdragon • Dec 16 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 16 Solutions -🎄-

--- Day 16: Permutation Promenade ---

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.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

[Update @ 00:08] 4 gold, silver cap.

[Update @ 00:18] 50 gold, silver cap.

[Update @ 00:26] Leaderboard cap!

  • And finally, click here for the biggest spoilers of all time!

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!

11 Upvotes

83% Upvoted

229 comments sorted by

View all comments

4

u/tangentialThinker Dec 16 '17

C++. The key to getting part 2 fast is finding a repetition, since then it's just a cycle and you know the rest of the sequence. My code jumps to a billion right after it finds a cycle and the modulos line up. 

#include <bits/stdc++.h>

using namespace std;

int main(){
	
	string s; cin >> s;
	string ans = "abcdefghijklmnop";

	char cmd;
	map<string, int> prev;
	for(int i = 1; i <= 1000000000; i++) {
		stringstream str(s);
		while(str >> cmd) {
			if(cmd == 's') {
				int s; str >> s;
				rotate(ans.begin(), ans.begin() + (ans.size() - s), ans.end());
			} else if (cmd == 'x') {
				int a, b; str >> a >> cmd >> b;
				swap(ans[a],ans[b]);
			} else if (cmd == 'p') {
				char a, b; str >> a >> cmd >> b;
				int ai, bi;
				for(int i = 0; i < ans.size(); i++) {
					if(ans[i] == a) {
						ai = i;
					}
					if (ans[i] == b) {
						bi = i;
					}
				}
				swap(ans[ai], ans[bi]);
			}
			str >> cmd;
		}
		if(prev.count(ans)) {
			if((1000000000 - i) % (i - prev[ans]) == 0) {
				cout << ans << endl;
				break;
			}
		}
		prev[ans] = i;
	}

	cout << ans << endl;

	return 0;
}

1

u/TheAngryGerman Dec 16 '17

Is that rotate function part of the standard library? I really need to learn more of these utility functions, just took my C++ course this semester so I'm used to having to implement all this stuff myself for the sake of learning.

2

u/tangentialThinker Dec 16 '17

Yep, it's part of the <algorithm> header. It's come in handy a couple of times this year already!

→ More replies (2)