Mercurial > hg > aoc

annotate 2017/day21/problem @ 34:049fb8e56025

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add problem statements and inputs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 09 Jan 2018 21:51:44 -0500
parents
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 21: Fractal Art ---
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 You find a program trying to generate some art. It uses a strange
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
4 process that involves repeatedly enhancing the detail of an image
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
5 through a set of rules.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
6
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
7 The image consists of a two-dimensional square grid of pixels that are
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
8 either on (#) or off (.). The program always begins with this pattern:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10 .#.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 ..#
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 ###
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14 Because the pattern is both 3 pixels wide and 3 pixels tall, it is
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15 said to have a size of 3.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 Then, the program repeats the following process:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
19 If the size is evenly divisible by 2, break the pixels up into 2x2
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20 squares, and convert each 2x2 square into a 3x3 square by
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
21 following the corresponding enhancement rule.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
22
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
23 Otherwise, the size is evenly divisible by 3; break the pixels up
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
24 into 3x3 squares, and convert each 3x3 square into a 4x4 square by
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
25 following the corresponding enhancement rule.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
26
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
27
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 Because each square of pixels is replaced by a larger one, the image
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 gains pixels and so its size increases.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31 The artist's book of enhancement rules is nearby (your puzzle input);
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 however, it seems to be missing rules. The artist explains that
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33 sometimes, one must rotate or flip the input pattern to find a match.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 (Never rotate or flip the output pattern, though.) Each pattern is
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35 written concisely: rows are listed as single units, ordered top-down,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36 and separated by slashes. For example, the following rules correspond
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 to the adjacent patterns:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38
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 .#
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
41
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 .#./..#/### = ..#
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
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 #..#/..../#..#/.##. = ....
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 .##.
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 When searching for a rule to use, rotate and flip the pattern as
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
52 necessary. For example, all of the following patterns match the same
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
53 rule:
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 .#. .#. #.. ###
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 ### ### ##. .#.
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 Suppose the book contained the following two rules:
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 ../.# => ##./#../...
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
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
64 As before, the program begins with this pattern:
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 ..#
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
68 ###
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
69
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
70 The size of the grid (3) is not divisible by 2, but it is divisible by
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
71 3. It divides evenly into a single square; the square matches the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
72 second rule, which produces:
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 #..#
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 ....
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
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
79 The size of this enhanced grid (4) is evenly divisible by 2, so that
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
80 rule is used. It divides evenly into four squares:
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 #.|.#
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 --+--
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 #.|.#
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 Each of these squares matches the same rule (../.# => ##./#../...),
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
89 three of which require some flipping and rotation to line up with the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
90 rule. The output for the rule is the same in all four cases:
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 ##.|##.
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 ...|...
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 ##.|##.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
97 #..|#..
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
98 ...|...
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 Finally, the squares are joined into a new grid:
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 ##.##.
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 ......
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 #..#..
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
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
109 Thus, after 2 iterations, the grid contains 12 pixels that are on.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
110
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
111 How many pixels stay on after 5 iterations?
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
112
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
113 Your puzzle answer was 176.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
114
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
115 --- Part Two ---
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 How many pixels stay on after 18 iterations?
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 Your puzzle answer was 2368161.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
120
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
121 Both parts of this puzzle are complete! They provide two gold stars: **