Mercurial > hg > aoc

comparison 2017/day12/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
comparison
equal deleted inserted replaced
33:bc652fa0a645 34:049fb8e56025
1 --- Day 12: Digital Plumber ---
2
3 Walking along the memory banks of the stream, you find a small village
4 that is experiencing a little confusion: some programs can't
5 communicate with each other.
6
7 Programs in this village communicate using a fixed system of pipes.
8 Messages are passed between programs using these pipes, but most
9 programs aren't connected to each other directly. Instead, programs
10 pass messages between each other until the message reaches the
11 intended recipient.
12
13 For some reason, though, some of these messages aren't ever reaching
14 their intended recipient, and the programs suspect that some pipes are
15 missing. They would like you to investigate.
16
17 You walk through the village and record the ID of each program and the
18 IDs with which it can communicate directly (your puzzle input). Each
19 program has one or more programs with which it can communicate, and
20 these pipes are bidirectional; if 8 says it can communicate with 11,
21 then 11 will say it can communicate with 8.
22
23 You need to figure out how many programs are in the group that
24 contains program ID 0.
25
26 For example, suppose you go door-to-door like a travelling salesman
27 and record the following list:
28
29 0 <-> 2
30 1 <-> 1
31 2 <-> 0, 3, 4
32 3 <-> 2, 4
33 4 <-> 2, 3, 6
34 5 <-> 6
35 6 <-> 4, 5
36
37 In this example, the following programs are in the group that contains
38 program ID 0:
39
40 Program 0 by definition.
41
42 Program 2, directly connected to program 0.
43
44 Program 3 via program 2.
45
46 Program 4 via program 2.
47
48 Program 5 via programs 6, then 4, then 2.
49
50 Program 6 via programs 4, then 2.
51
52
53 Therefore, a total of 6 programs are in this group; all but program 1,
54 which has a pipe that connects it to itself.
55
56 How many programs are in the group that contains program ID 0?
57
58 Your puzzle answer was 141.
59
60 --- Part Two ---
61
62 There are more programs than just the ones in the group containing
63 program ID 0. The rest of them have no way of reaching that group, and
64 still might have no way of reaching each other.
65
66 A group is a collection of programs that can all communicate via pipes
67 either directly or indirectly. The programs you identified just a
68 moment ago are all part of the same group. Now, they would like you to
69 determine the total number of groups.
70
71 In the example above, there were 2 groups: one consisting of programs
72 0,2,3,4,5,6, and the other consisting solely of program 1.
73
74 How many groups are there in total?
75
76 Your puzzle answer was 171.
77
78 Both parts of this puzzle are complete! They provide two gold stars: **