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