-
Notifications
You must be signed in to change notification settings - Fork 0
/
day15.rb
185 lines (170 loc) · 5.79 KB
/
day15.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
# --- Day 15: Dueling Generators ---
#
# Here, you encounter a pair of dueling generators. The generators, called generator A and
# generator B, are trying to agree on a sequence of numbers. However, one of them is
# malfunctioning, and so the sequences don't always match.
#
# As they do this, a judge waits for each of them to generate its next value, compares the lowest
# 16 bits of both values, and keeps track of the number of times those parts of the values match.
#
# The generators both work on the same principle. To create its next value, a generator will take
# the previous value it produced, multiply it by a factor (generator A uses 16807; generator B
# uses 48271), and then keep the remainder of dividing that resulting product by 2147483647. That
# final remainder is the value it produces next.
#
# To calculate each generator's first value, it instead uses a specific starting value as its
# "previous value" (as listed in your puzzle input).
#
# For example, suppose that for starting values, generator A uses 65, while generator B uses
# 8921. Then, the first five pairs of generated values are:
#
# --Gen. A-- --Gen. B--
# 1092455 430625591
# 1181022009 1233683848
# 245556042 1431495498
# 1744312007 137874439
# 1352636452 285222916
#
# In binary, these pairs are (with generator A's value first in each pair):
#
# 00000000000100001010101101100111
# 00011001101010101101001100110111
#
# 01000110011001001111011100111001
# 01001001100010001000010110001000
#
# 00001110101000101110001101001010
# 01010101010100101110001101001010
#
# 01100111111110000001011011000111
# 00001000001101111100110000000111
#
# 01010000100111111001100000100100
# 00010001000000000010100000000100
#
# Here, you can see that the lowest (here, rightmost) 16 bits of the third value match:
# 1110001101001010. Because of this one match, after processing these five pairs, the judge would
# have added only 1 to its total.
#
# To get a significant sample, the judge would like to consider 40 million pairs. (In the example
# above, the judge would eventually find a total of 588 pairs that match in their lowest 16 bits.)
#
# After 40 million pairs, what is the judge's final count?
require_relative 'input'
day = __FILE__[/\d+/].to_i(10)
input = Input.for_day(day, 2017)
puts "solving day #{day} from input:\n#{input}"
class Generator
def initialize(name:, seed:, multiples_of: nil)
@name = name
@factor = { 'A' => 16807,
'B' => 48271,
}[name]
@mod = 2147483647
@value = seed
@multiples_of = multiples_of
end
def next1
@value = (@value * @factor) % @mod
end
def next2
loop do
this = self.next1
return this if (this % @multiples_of).zero?
end
end
end
if $DEBUG
a = Generator.new(name: 'A', seed: 65)
b = Generator.new(name: 'B', seed: 8921)
else
a = Generator.new(name: 'A', seed: 516)
b = Generator.new(name: 'B', seed: 190)
end
matches = 0
BITS16 = 0xFFFF
40_000_000.times do |round|
aval = a.next1
bval = b.next1
if ((aval ^ bval) & BITS16).zero?
matches += 1
end
end
puts "Part1:", matches
# --- Part Two ---
#
# In the interest of trying to align a little better, the generators get more picky about the
# numbers they actually give to the judge.
#
# They still generate values in the same way, but now they only hand a value to the judge when it
# meets their criteria:
#
# Generator A looks for values that are multiples of 4.
# Generator B looks for values that are multiples of 8.
#
# Each generator functions completely independently: they both go through values entirely on their
# own, only occasionally handing an acceptable value to the judge, and otherwise working through
# the same sequence of values as before until they find one.
#
# The judge still waits for each generator to provide it with a value before comparing them (using
# the same comparison method as before). It keeps track of the order it receives values; the first
# values from each generator are compared, then the second values from each generator, then the
# third values, and so on.
#
# Using the example starting values given above, the generators now produce the following first five values each:
#
# --Gen. A-- --Gen. B--
# 1352636452 1233683848
# 1992081072 862516352
# 530830436 1159784568
# 1980017072 1616057672
# 740335192 412269392
#
# These values have the following corresponding binary values:
#
# 01010000100111111001100000100100
# 01001001100010001000010110001000
#
# 01110110101111001011111010110000
# 00110011011010001111010010000000
#
# 00011111101000111101010001100100
# 01000101001000001110100001111000
#
# 01110110000001001010100110110000
# 01100000010100110001010101001000
#
# 00101100001000001001111001011000
# 00011000100100101011101101010000
#
# Unfortunately, even though this change makes more bits similar on average, none of these values'
# lowest 16 bits match. Now, it's not until the 1056th pair that the judge finds the first match:
#
# --Gen. A-- --Gen. B--
# 1023762912 896885216
#
# 00111101000001010110000111100000
# 00110101011101010110000111100000
#
# This change makes the generators much slower, and the judge is getting impatient; it is now only
# willing to consider 5 million pairs. (Using the values from the example above, after five
# million pairs, the judge would eventually find a total of 309 pairs that match in their lowest
# 16 bits.)
#
# After 5 million pairs, but using this new generator logic, what is the judge's final count?
if $DEBUG
a = Generator.new(name: 'A', seed: 65, multiples_of: 4)
b = Generator.new(name: 'B', seed: 8921, multiples_of: 8)
else
a = Generator.new(name: 'A', seed: 516, multiples_of: 4)
b = Generator.new(name: 'B', seed: 190, multiples_of: 8)
end
matches = 0
5_000_000.times do |round|
aval = a.next2
bval = b.next2
if ((aval ^ bval) & BITS16).zero?
matches += 1
end
end
puts "Part2:", matches