Mercurial > hg > aoc

annotate 2017/day07/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 7: Recursive Circus ---
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 Wandering further through the circuits of the computer, you come upon
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
4 a tower of programs that have gotten themselves into a bit of trouble.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
5 A recursive algorithm has gotten out of hand, and now they're balanced
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
6 precariously in a large tower.
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 One program at the bottom supports the entire tower. It's holding a
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9 large disc, and on the disc are balanced several more sub-towers. At
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10 the bottom of these sub-towers, standing on the bottom disc, are other
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 programs, each holding their own disc, and so on. At the very tops of
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 these sub-sub-sub-...-towers, many programs stand simply keeping the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 disc below them balanced but with no disc of their own.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15 You offer to help, but first you need to understand the structure of
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 these towers. You ask each program to yell out their name, their
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 weight, and (if they're holding a disc) the names of the programs
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18 immediately above them balancing on that disc. You write this
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
19 information down (your puzzle input). Unfortunately, in their panic,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20 they don't do this in an orderly fashion; by the time you're done,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
21 you're not sure which program gave which information.
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 For example, if your list is the following:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
24
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
25 pbga (66)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
26 xhth (57)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
27 ebii (61)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 havc (66)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 ktlj (57)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30 fwft (72) -> ktlj, cntj, xhth
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31 qoyq (66)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 padx (45) -> pbga, havc, qoyq
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33 tknk (41) -> ugml, padx, fwft
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 jptl (61)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35 ugml (68) -> gyxo, ebii, jptl
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36 gyxo (61)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 cntj (57)
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 ...then you would be able to recreate the structure of the towers that
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40 looks like this:
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 gyxo
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 ugml - ebii
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 | jptl
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 | pbga
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 tknk --- padx - havc
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
51 \ \
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
52 | qoyq
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
53 |
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
54 | ktlj
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 fwft - cntj
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 xhth
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
59
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
60 In this example, tknk is at the bottom of the tower (the bottom
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
61 program), and is holding up ugml, padx, and fwft. Those programs are,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
62 in turn, holding up other programs; in this example, none of those
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
63 programs are holding up any other programs, and are all the tops of
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
64 their own towers. (The actual tower balancing in front of you is much
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
65 larger.)
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 Before you're ready to help them, you need to make sure your
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
68 information is correct. What is the name of the bottom program?
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 Your puzzle answer was xegshds.
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 --- Part Two ---
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 The programs explain the situation: they can't get down. Rather, they
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
75 could get down, if they weren't expending all of their energy trying
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
76 to keep the tower balanced. Apparently, one program has the wrong
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
77 weight, and until it's fixed, they're stuck here.
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 For any program holding a disc, each program standing on that disc
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
80 forms a sub-tower. Each of those sub-towers are supposed to be the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
81 same weight, or the disc itself isn't balanced. The weight of a tower
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
82 is the sum of the weights of the programs in that tower.
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 In the example above, this means that for ugml's disc to be balanced,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
85 gyxo, ebii, and jptl must all have the same weight, and they do: 61.
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 However, for tknk to be balanced, each of the programs standing on its
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
88 disc and all programs above it must each match. This means that the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
89 following sums must all be the same:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
90
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
91 ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
92 padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
93 fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243
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 As you can see, tknk's disc is unbalanced: ugml's stack is heavier
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
96 than the other two. Even though the nodes above ugml are balanced,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
97 ugml itself is too heavy: it needs to be 8 units lighter for its stack
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
98 to weigh 243 and keep the towers balanced. If this change were made,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
99 its weight would be 60.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
100
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
101 Given that exactly one program is the wrong weight, what would its
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
102 weight need to be to balance the entire tower?
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 Your puzzle answer was 299.
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 Both parts of this puzzle are complete! They provide two gold stars: **