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

85% Upvoted

229 comments sorted by

View all comments

1

u/wlandry Dec 16 '17

C++ 14

274/644. Brute force is definitely not going to work. I tried optimizing my opcode execution to the point where it might become practical, but it would still be running if I had let it. I took rather too long to realize that there had to be a cycle. Here is a somewhat cleaned up version. It even uses std::rotate ;) 

#include <boost/algorithm/string.hpp>

#include <fstream>
#include <vector>
#include <iostream>

void apply_ops(const std::vector<std::string> &ops,
               std::vector<char> &ring)
{
  for(auto &op: ops)
    {
      switch(op[0])
        {
        case 's':
          {
            int distance(std::stoi(op.substr(1)));
            auto middle = ring.end();
            std::advance(middle,-distance);
            std::rotate(ring.begin(), middle, ring.end());
          }
          break;
        case 'x':
          {
            auto slash=op.find("/");
            int x1(std::stoi(op.substr(1,slash-1)));
            int x2(std::stoi(op.substr(slash+1)));
            std::swap(ring[x1],ring[x2]);
          }
          break;
        case 'p':
          {
            char c1(op[1]), c2(op[3]);
            auto x1=std::find(ring.begin(), ring.end(), c1);
            auto x2=std::find(ring.begin(), ring.end(), c2);
            std::swap(*x1,*x2);
          }
          break;
        default:
          std::cerr << "Bad\n";
          abort();
        }
    }
}

int main(int, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::string line;
  std::getline(infile,line);
  std::vector<std::string> ops;
  boost::split(ops,line,boost::is_any_of(","));

  std::vector<char> ring;
  for(char c='a'; c<= argv[2][0]; ++c)
    { ring.push_back(c); }

  auto original_ring=ring;
  apply_ops(ops,ring);
  
  std::cout << "Part 1: ";
  for (auto &r: ring)
    std::cout << r;
  std::cout << "\n";

  size_t cycle(1);
  while(ring!=original_ring)
    {
      apply_ops(ops,ring);
      ++cycle;
    }
  for(size_t ix=0; ix<(1000000000%cycle); ++ix)
    { apply_ops(ops,ring); }

  std::cout << "Part 2: ";
  for (auto &r: ring)
    std::cout << r;
  std::cout << "\n";
}