adventofcode2017/day16.cpp at master · zhatt/adventofcode2017 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
--- Day 16: Permutation Promenade ---

You come upon a very unusual sight; a group of programs here appear to be
dancing.

There are sixteen programs in total, named a through p. They start by
standing in a line: a stands in position 0, b stands in position 1, and so
on until p, which stands in position 15.

The programs' dance consists of a sequence of dance moves:

  - Spin, written sX, makes X programs move from the end to the front, but
    maintain their order otherwise. (For example, s3 on abcde produces
    cdeab).
  - Exchange, written xA/B, makes the programs at positions A and B swap
    places.
  - Partner, written pA/B, makes the programs named A and B swap places.

For example, with only five programs standing in a line (abcde), they could
do the following dance:

  - s1, a spin of size 1: eabcd.
  - x3/4, swapping the last two programs: eabdc.
 - pe/b, swapping programs e and b: baedc.

After finishing their dance, the programs end up in order baedc.

You watch the dance for a while and record their dance moves (your puzzle
input). In what order are the programs standing after their dance?

--- Part Two ---

Now that you're starting to get a feel for the dance moves, you turn your
attention to the dance as a whole.

Keeping the positions they ended up in from their previous dance, the
programs perform it again and again: including the first dance, a total of
one billion (1000000000) times.

In the example above, their second dance would begin with the order baedc,
and use the same dance moves:

  - s1, a spin of size 1: cbaed.
  - x3/4, swapping the last two programs: cbade.
  - pe/b, swapping programs e and b: ceadb.

In what order are the programs standing after their billion dances?
*/

#include <algorithm>
#include <cassert>
#include <deque>
#include <list>
#include <iostream>
#include <sstream>
#include <utility>

#include "main.h"

using namespace std;

int mainfunc( istream &is, ostream &os, Part part ) {

    string input;
    getline( is, input );
    assert( is );

    replace( input.begin(), input.end(), ',', ' ' );

    string move;
    deque<char> programs;
    for ( char c = 'a'; c <= 'p'; c++ ) {
        programs.push_back( c );
    }
    const deque<char> programsOrig( programs );

    unsigned numIterations = 1;
    if ( part == Part::PART2 ) numIterations = 1000000000;

    for ( unsigned iteration = 0; iteration < numIterations; iteration++ ) {
        istringstream parser( input );
        while ( parser >> move ) {
            if ( move[0] == 's' ) {
                // Spin
                istringstream s( move.substr(1) );

                unsigned count;
                s >> count;
                assert( s );

                for ( unsigned i = 0; i < count; i++ ) {
                    programs.push_front( programs.back() );
                    programs.pop_back();
                }

            } else if ( move[0] == 'x' ) {
                // Exchange
                istringstream s( move.substr(1) );
                unsigned pos1, pos2;

                s >> pos1;
                assert( pos1 < programs.size() );
                assert( s.peek() == '/' );
                s.ignore( 1 );
                s >> pos2;
                assert( pos2 < programs.size() );
                assert( s );

                swap( programs[pos1], programs[pos2] );

            } else if ( move[0] == 'p' ) {
                // Partner
                assert( move.size() == 4 );
                assert( move[2] == '/' );

                auto pos1 = find( programs.begin(), programs.end(), move[1] );
                assert( pos1 != programs.end() );
                auto pos2 = find( programs.begin(), programs.end(), move[3] );
                assert( pos2 != programs.end() );

                swap( *pos1, *pos2 );
            } else {
                assert( !"Unknown comand" );
            }
        }

        if ( programs == programsOrig ) {
            unsigned numIterationsInCycle = iteration + 1;
            while( iteration < numIterations ) iteration += numIterationsInCycle;
            iteration -= numIterationsInCycle;
        }
    }

    for( auto c: programs ) {
        os << c;
    }
    os << endl;

    return 0;
}