diff 2017/day15/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
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/2017/day15/problem
@@ -0,0 +1,135 @@
+--- 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?
+
+Your puzzle answer was 626.
+
+--- 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?
+
+Your puzzle answer was 306.
+
+Both parts of this puzzle are complete! They provide two gold stars: **