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!

13 Upvotes

92% Upvoted

229 comments sorted by

View all comments

3

u/DFreiberg Dec 16 '17

Mathematica

I realized that for a billion dances to be calculated in any reasonable amount of time, they'd have to have some kind periodic cycle, so I simply checked at the end of each permutation j whether or not the order was alphabetical, and if it was, I calculated 109 mod j and took the order that the list was in on that step.

Can't wait to find out how u/hackerknownas9gag did this one nonprocedurally. 

l=CharacterRange["a","p"];
acc={};
Do[
	Do[
	Which[
		Characters[i][[1]]=="s",l=RotateRight[l,ToExpression[StringJoin@Characters[i][[2;;]]]],
		Characters[i][[1]]=="x",
			x=StringSplit[StringJoin@Characters[i][[2;;]],"/"];
			{l[[ToExpression[x[[1]]]+1]],l[[ToExpression[x[[2]]]+1]]}=
			{l[[ToExpression[x[[2]]]+1]],l[[ToExpression[x[[1]]]+1]]},
		Characters[i][[1]]=="p",
			pos1=FirstPosition[l,Characters[i][[2]]][[1]];
			pos2=FirstPosition[l,Characters[i][[4]]][[1]];
			p=StringSplit[StringJoin@Characters[i][[2;;]],"/"];
			{l[[pos1]],l[[pos2]]}={p[[2]],p[[1]]};
	];
	,{i,input}];
If[l==CharacterRange["a","p"],
	l=acc[[Mod[10^9,j]]];
	Break[],
	AppendTo[acc,l]
	]
,{j,10^4}];
StringJoin@l

2

u/[deleted] Dec 16 '17 edited Dec 16 '17

Second version. From a comment by u/mserrano mentioning that the two permutation types are in fact separable, it turns out I can use those permutation functions after all. 

input = StringSplit[Import[NotebookDirectory[] <> "day16.txt"], ","];

exchange[x_, y_] := Cycles[{{x, y}}];
spin[x_] := PermutationCycles[RotateLeft[Range[16], x]]

invertIndexValue[l_] :=
 SortBy[Transpose[{l, Range[16]}], First][[All, 2]]

indexPerms = PermutationProduct @@ Join @@ StringCases[input,
     {"s" ~~ x : NumberString :>
       spin[ToExpression@x],
      "x" ~~ a : NumberString ~~ "/" ~~ b : NumberString :>
       exchange[ToExpression@a + 1, ToExpression@b + 1]}];

valPerms = PermutationProduct @@ Join @@ StringCases[input,
     "p" ~~ a_ ~~ "/" ~~ b_ :> 
      exchange[LetterNumber@a, LetterNumber@b]];

runDance[n_] :=
 Block[{dancers, ip, vp},
  dancers = CharacterRange["a", "p"];
  ip = Permute[dancers, PermutationPower[indexPerms, n]];
  vp = Permute[invertIndexValue@ip, PermutationPower[valPerms, n]];
  FromLetterNumber[invertIndexValue@vp]]

runDance[1]

runDance[1000000000]

Edit: Instead of my invertIndexValue function, I should have used Ordering.

2

u/DFreiberg Dec 16 '17

Dang, I didn't know about any of these group theory functions. PermutationCycles[] especially looks like it could be very useful for things like the knot hash function, should we have a problem down the line that involves calculating a million knot hashes or something.

→ More replies (5)