Mercurial > hg > aoc

comparison 2017/day15/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 15: Dueling Generators ---
2
3 Here, you encounter a pair of dueling generators. The generators,
4 called generator A and generator B, are trying to agree on a sequence
5 of numbers. However, one of them is malfunctioning, and so the
6 sequences don't always match.
7
8 As they do this, a judge waits for each of them to generate its next
9 value, compares the lowest 16 bits of both values, and keeps track of
10 the number of times those parts of the values match.
11
12 The generators both work on the same principle. To create its next
13 value, a generator will take the previous value it produced, multiply
14 it by a factor (generator A uses 16807; generator B uses 48271), and
15 then keep the remainder of dividing that resulting product by
16 2147483647. That final remainder is the value it produces next.
17
18 To calculate each generator's first value, it instead uses a specific
19 starting value as its "previous value" (as listed in your puzzle
20 input).
21
22 For example, suppose that for starting values, generator A uses 65,
23 while generator B uses 8921. Then, the first five pairs of generated
24 values are:
25
26 --Gen. A-- --Gen. B--
27 1092455 430625591
28 1181022009 1233683848
29 245556042 1431495498
30 1744312007 137874439
31 1352636452 285222916
32
33 In binary, these pairs are (with generator A's value first in each
34 pair):
35
36 00000000000100001010101101100111
37 00011001101010101101001100110111
38
39 01000110011001001111011100111001
40 01001001100010001000010110001000
41
42 00001110101000101110001101001010
43 01010101010100101110001101001010
44
45 01100111111110000001011011000111
46 00001000001101111100110000000111
47
48 01010000100111111001100000100100
49 00010001000000000010100000000100
50
51 Here, you can see that the lowest (here, rightmost) 16 bits of the
52 third value match: 1110001101001010. Because of this one match, after
53 processing these five pairs, the judge would have added only 1 to its
54 total.
55
56 To get a significant sample, the judge would like to consider 40
57 million pairs. (In the example above, the judge would eventually find
58 a total of 588 pairs that match in their lowest 16 bits.)
59
60 After 40 million pairs, what is the judge's final count?
61
62 Your puzzle answer was 626.
63
64 --- Part Two ---
65
66 In the interest of trying to align a little better, the generators get
67 more picky about the numbers they actually give to the judge.
68
69 They still generate values in the same way, but now they only hand a
70 value to the judge when it meets their criteria:
71
72 Generator A looks for values that are multiples of 4.
73
74 Generator B looks for values that are multiples of 8.
75
76 Each generator functions completely independently: they both go
77 through values entirely on their own, only occasionally handing an
78 acceptable value to the judge, and otherwise working through the same
79 sequence of values as before until they find one.
80
81 The judge still waits for each generator to provide it with a value
82 before comparing them (using the same comparison method as before). It
83 keeps track of the order it receives values; the first values from
84 each generator are compared, then the second values from each
85 generator, then the third values, and so on.
86
87 Using the example starting values given above, the generators now
88 produce the following first five values each:
89
90 --Gen. A-- --Gen. B--
91 1352636452 1233683848
92 1992081072 862516352
93 530830436 1159784568
94 1980017072 1616057672
95 740335192 412269392
96
97 These values have the following corresponding binary values:
98
99 01010000100111111001100000100100
100 01001001100010001000010110001000
101
102 01110110101111001011111010110000
103 00110011011010001111010010000000
104
105 00011111101000111101010001100100
106 01000101001000001110100001111000
107
108 01110110000001001010100110110000
109 01100000010100110001010101001000
110
111 00101100001000001001111001011000
112 00011000100100101011101101010000
113
114 Unfortunately, even though this change makes more bits similar on
115 average, none of these values' lowest 16 bits match. Now, it's not
116 until the 1056th pair that the judge finds the first match:
117
118 --Gen. A-- --Gen. B--
119 1023762912 896885216
120
121 00111101000001010110000111100000
122 00110101011101010110000111100000
123
124 This change makes the generators much slower, and the judge is getting
125 impatient; it is now only willing to consider 5 million pairs. (Using
126 the values from the example above, after five million pairs, the judge
127 would eventually find a total of 309 pairs that match in their lowest
128 16 bits.)
129
130 After 5 million pairs, but using this new generator logic, what is the
131 judge's final count?
132
133 Your puzzle answer was 306.
134
135 Both parts of this puzzle are complete! They provide two gold stars: **