Mercurial > hg > aoc

annotate 2017/day09/problem @ 35:1d99d733cf13 default tip @

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
day08: replace static foreach with workaround
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 16 Jan 2018 11:28:55 -0500
parents 049fb8e56025
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
34
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
1 --- Day 9: Stream Processing ---
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
2
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
3 A large stream blocks your path. According to the locals, it's not
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
4 safe to cross the stream at the moment because it's full of garbage.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
5 You look down at the stream; rather than water, you discover that it's
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
6 a stream of characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
7
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
8 You sit for a while and record part of the stream (your puzzle input).
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9 The characters represent groups - sequences that begin with { and end
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10 with }. Within a group, there are zero or more other things, separated
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 by commas: either another group or garbage. Since groups can contain
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 other groups, a } only closes the most-recently-opened unclosed group
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 - that is, they are nestable. Your puzzle input represents a single,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14 large group which itself contains many smaller ones.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 Sometimes, instead of a group, you will find garbage. Garbage begins
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 with < and ends with >. Between those angle brackets, almost any
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18 character can appear, including { and }. Within garbage, < has no
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
19 special meaning.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
21 In a futile attempt to clean up the garbage, some program has canceled
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
22 some of the characters within it using !: inside garbage, any
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
23 character that comes after ! should be ignored, including <, >, and
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
24 even another !.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
25
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
26 You don't see any characters that deviate from these rules. Outside
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
27 garbage, you only find well-formed groups, and garbage always
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 terminates according to the rules above.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30 Here are some self-contained pieces of garbage:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 <>, empty garbage.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 <random characters>, garbage containing random characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36 <<<<>, because the extra < are ignored.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38 <{!>}>, because the first > is canceled.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
39
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40 <!!>, because the second ! is canceled, allowing the > to
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
41 terminate the garbage.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
42
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
43 <!!!>>, because the second ! and the first > are canceled.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
44
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
45 <{o"i!a,<{i<a>, which ends at the first >.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
46
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
47 Here are some examples of whole streams and the number of groups they contain:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
48
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
49 {}, 1 group.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
50
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
51 {{{}}}, 3 groups.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
52
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
53 {{},{}}, also 3 groups.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
54
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
55 {{{},{},{{}}}}, 6 groups.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
56
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
57 {<{},{},{{}}>}, 1 group (which itself contains garbage).
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
58
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
59 {<a>,<a>,<a>,<a>}, 1 group.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
60
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
61 {{<a>},{<a>},{<a>},{<a>}}, 5 groups.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
62
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
63 {{<!>},{<!>},{<!>},{<a>}}, 2 groups (since all but the last > are
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
64 canceled).
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
65
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
66
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
67 Your goal is to find the total score for all groups in your input.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
68 Each group is assigned a score which is one more than the score of the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
69 group that immediately contains it. (The outermost group gets a score
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
70 of 1.)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
71
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
72 {}, score of 1.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
73
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
74 {{{}}}, score of 1 + 2 + 3 = 6.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
75
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
76 {{},{}}, score of 1 + 2 + 2 = 5.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
77
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
78 {{{},{},{{}}}}, score of 1 + 2 + 3 + 3 + 3 + 4 = 16.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
79
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
80 {<a>,<a>,<a>,<a>}, score of 1.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
81
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
82 {{<ab>},{<ab>},{<ab>},{<ab>}}, score of 1 + 2 + 2 + 2 + 2 = 9.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
83
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
84 {{<!!>},{<!!>},{<!!>},{<!!>}}, score of 1 + 2 + 2 + 2 + 2 = 9.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
85
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
86 {{<a!>},{<a!>},{<a!>},{<ab>}}, score of 1 + 2 = 3.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
87
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
88 What is the total score for all groups in your input?
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
89
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
90 Your puzzle answer was 12803.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
91
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
92 --- Part Two ---
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
93
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
94 Now, you're ready to remove the garbage.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
95
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
96 To prove you've removed it, you need to count all of the characters
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
97 within the garbage. The leading and trailing < and > don't count, nor
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
98 do any canceled characters or the ! doing the canceling.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
99
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
100 <>, 0 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
101
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
102 <random characters>, 17 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
103
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
104 <<<<>, 3 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
105
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
106 <{!>}>, 2 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
107
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
108 <!!>, 0 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
109
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
110 <!!!>>, 0 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
111
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
112 <{o"i!a,<{i<a>, 10 characters.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
113
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
114 How many non-canceled characters are within the garbage in your puzzle
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
115 input?
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
116
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
117 Your puzzle answer was 6425.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
118
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
119 Both parts of this puzzle are complete! They provide two gold stars: **