Advent of Code 2017, Day 15: Dueling Generators
Day 15: Dueling Generators
After the complexity of Day 14, today’s challenge is a nice break both in terms of cognitive load and code to be written. We need to write some number generators. The difficulty only comes in the physical memory constraints of our machine. Snippet from the challenge text is shown below:
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. 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. To get a significant sample, the judge would like to consider 40 million pairs.
So, we need to iterate 40 million times, comparing the outputs of Generator A and Generator B. Let’s crack on.
Solving Part 1
We are given the first 5 outputs from the pair of generators, so we can check that we are on the right path. Let’s take Generator A as the first example.
We need to multiply 65 by 16807 and calculate the remainder after dividing by 2147483647. We learnt on Day 2 that we can use mod to calculate the remainder, so translating this into Q code:
q)mod[16807 * 65;2147483647]
1092455
Turning that into a lambda:
q){ mod[16807 * x;2147483647] } 65
1092455
We can check that feeding in the result generates the next number in the sequence:
q){ mod[16807 * x;2147483647] } 65
1092455
q){ mod[16807 * x;2147483647] } 1092455
1181022009
q){ mod[16807 * x;2147483647] } 1181022009
245556042
q){ mod[16807 * x;2147483647] } 245556042
1744312007
q){ mod[16807 * x;2147483647] } 1744312007
1352636452
That’s Generator A sorted, now for Generator B:
q)mod[48271 * 8921;2147483647]
430625591
q){ mod[48271 * x;2147483647] } 8921
430625591
We can do better than this though. See what happens if we multiply two 2-item lists:
q)16807 48271 * 65 8921
1092455 430625591
… and similarly if we mod the result by 2147483647
q)mod[16807 48271 * 65 8921;2147483647]
1092455 430625591
Wrapping this in a lambda:
q){ mod[16807 48271 * x;2147483647] } 65 8921
1092455 430625591
Tip: We can use the scan adverb to perform cause this function to iterate 5 times:
q){ mod[16807 48271 * x;2147483647] }\[5;65 8921]
65 8921
1092455 430625591
1181022009 1233683848
245556042 1431495498
1744312007 137874439
1352636452 285222916
So, now we know how to generate numbers to compare, we need to check the lowest 16 bits of each number.
Whilst we can play around with bit manipulation (casting via 0b vs, taking the last 16 bits, compare them etc), a much simpler alternative is to perform the modulo operation against 65536 (2^16). This effectively ignores any bits higher than the first 16. Here’s an example to demonstrate:
q)0b vs 1233683848
0000000000000000000000000000000001001001100010001000010110001000b
q)-16#0b vs 1233683848
1000010110001000b
q)-16#0b vs 1233683848
1000010110001000b
q)0b sv (48#0b),-16#0b vs 1233683848 / new in 4.0, otherwise it tries to parse as a short
34184
q)1233683848 mod 65536
34184
To check equality of two numbers we can use ~ or =:
q)5 = 10
0b
q)5 ~ 10
0b
We saw on Day 1, we can use . to feed a list of arguments into a function which helps us to generalise things:
q){ x = y } . 5 10
0b
q)(=) . 5 10
0b
q)(~) . 5 10
0b
We therefore have almost all we need to get the first star: we have a way of generating numbers from generators A and B, and a way to compare the lowest 16 bits.
q){ mod[16807 48271 * x;2147483647] } 65 8921 / generate next numbers
1092455 430625591
q){ mod[;65536] mod[16807 48271 * x;2147483647] } 65 8921 / mod 65536 to get lowest 16 bits
43879 54071
q){ (=) . mod[;65536] mod[16807 48271 * x;2147483647] } 65 8921 / check for equality
0b
… The problem we have just created is that we cannot feed this result back into the function to generate the next 2 numbers to compare. We need to keep track of the numbers AND the result of their equality.
If you are using the 64bit flavour of KDB, and have enough memory, you can simply generate the list of all 40 million numbers and then check the equality via something like this:
/ will result in 'wsfull on 32bit
sum {x~y}.'mod[;65536] { mod[16807 48271 * x;2147483647] }\[40000000;65 8921]
… but this uses close to 8GB memory on my machine, which will therefore blow through the memory limits for the 32bit version, so we need a less memory intensive approach. For those of you thinking ‘why not break it into 4 batches’, feel free to consider that a homework task.
A gut instinct may be to reach for a do or a while loop, that way we can keep track of the number of matches, as well as the newly generated numbers:
i:65 8921 / initial generator values
m:0 / matches
do[40000000; / 40 million iterations
m+:(=) . mod[;65536] i:mod[16807 48271 * i;2147483647]
]
BUT… loops are boring, let’s try and solve in a more Q-like manner. We can change our generator function to return the result of the comparison and the generated numbers as a 2-item list:
q){ ( (~). mod[;65536] mod[16807 48271 * x;2147483647] ; mod[16807 48271 * x;2147483647] ) } 65 8921
0b / first item in the list, 'false'
1092455 430625591 / second item in the list, the new results
There is some duplication, so lets simplify down by saving the result of the generators as r
q){ ( (~). mod[;65536] r; r:mod[16807 48271 * x;2147483647] ) } / keeping similar projected style
q){ ( (~). mod[r;65536]; r:mod[16807 48271 * x;2147483647] ) } / using bracket notation
q){ ( (~). r mod 65536; r:mod[16807 48271 * x;2147483647] ) } / using infix notation
Now we know whether the results matched, and what the next values should be, but we cannot feed the output back in as input, as our function is only expecting to receive the numbers to be fed into the generators. We need to update our lambda so that it will support a 2-item list as input.
We can do this by replacing the x for last x (i.e. the last item in the list), or x 1 to index into the 2nd item of the list:
q){ ( (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) } (0b;1092455 430625591)
0b
1181022009 1233683848
Let’s add a scan (\) and run it 10 times:
q){ ( (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) }\[10;(0b;1092455 430625591)]
0b 1092455 430625591
0b 1181022009 1233683848
1b 245556042 1431495498 / the lowest 16 bits match in both 245556042 and 1431495498
0b 1744312007 137874439
0b 1352636452 285222916
0b 498961622 477717319
0b 124339419 213303963
0b 271026602 1358994255
0b 331284527 828718196
0b 1621432265 1878146447
0b 1992081072 1837501385
We need to accumulate the matches, we can do this by adding the previous result (the first element of our input list):
q){ (first[x] + (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) }\[10;(0b;1092455 430625591)]
0b 1092455 430625591
0i 1181022009 1233683848
1i 245556042 1431495498
1i 1744312007 137874439
1i 1352636452 285222916
1i 498961622 477717319
1i 124339419 213303963
1i 271026602 1358994255
1i 331284527 828718196
1i 1621432265 1878146447
1i 1992081072 1837501385
If we swap the scan (\)for an over (/) KDB will only return the final result:
q){ (first[x] + (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) }/[10;(0;1092455 430625591)]
1
1992081072 1837501385
If, instead of 10 iterations, we perform all 40 million, the accumulator will match the example, 588. Note that this takes a considerable amount of time - a little over a minute on my machine:
q){ (first[x] + (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) }/[40000000;(0;1092455 430625591)]
588
1534943907 395988311
We need to feed in our own puzzle input and re-run the 40 million iterations. Lets read0 our input file:
q)read0 `:input/15.txt
"Generator A starts with 783"
"Generator B starts with 325"
We can use vs to split each on " ":
q)" "vs'read0 `:input/15.txt
"Generator" ,"A" "starts" "with" "783"
"Generator" ,"B" "starts" "with" "325"
.. then take the last of each line:
q)last each " "vs'read0 `:input/15.txt
"783"
"325"
Finally using big-J casting to longs:
q)"J"$last each " "vs'read0 `:input/15.txt
783 325
So, putting that all together yields today’s first star:
q){ (first[x] + (~). r mod 65536; r:mod[16807 48271 * last x;2147483647] ) }/[40000000;(0;"J"$last each " "vs'read0 `:input/15.txt)]
650 / we only care about the 'first' result
1422403664 377111125 / and can ignore the 'next' numbers coming out of the generators
Solving Part 2
Part 2 is only a slight twist on Part 1 - and whilst we won’t be re-using the function from earlier, we will be re-using much of the same logic as before.
Challenge text below with the key parts highlighted:
[The generators] 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. This change makes the generators much slower, and the judge is getting impatient; it is now only willing to consider 5 million pairs.
Therefore we need to generate 5 million values for Generator A and 5 million values for Generator B, and compare each pair of values. We can do this by creating a list of values for Generator A, and a list of values for Generator B, and compare them.
Whilst for Part 1, we were generating pairs of values in a single function, for Part 2 we will break the generation into two separate functions, one for Generator A, one for Generator B.
Generator A uses 16807 as it’s ‘factor’, and the example starting value for Generator A is 65.
q){ mod[x * 16807;2147483647] } 65
1092455
We need to determine whether the latest result of Generator A is divisible by 4, and if it is we can add it to a list called A.
As we saw way back on Day 2, we can use the mod operator to get the remainder of the division of two numbers.
q)1092455 mod 4
3
q)0=1092455 mod 4
0b
The mod of 1092455 and 4 is not zero, therefore 1092455 is not divisible by 4. We can use this basic logic to decide whether or not to add each result to list A. First lets define our global variable A and initialise it as an empty list:
q)A:()
To add to a list we can use the append syntax ,::
q)A,:1
q)A,:2
q)A,:3
q)A
1 2 3
q)count A
3
A is a simple list and we can join another simple list, e.g. 4 5, to it:
q)A,:4 5
q)A
1 2 3 4 5
q)count A
5
In pseudocode what we want to do is:
f:{
if (newly generated value) modulo 4 is zero
add to list A
else
do nothing
return newly generated value
}
We can translate this to Q as:
f:{
n:mod[x * 16807;2147483647]; / save newly generated value as 'n'
if[0 = n mod 4; / is the new result divisible by 4?
A,:n / if so, append to list A
];
/ no need for an 'else'
n / return newly generated value
}
…or shrinking down to a 1-liner:
q)f:{ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }
We want to run this function until A contains 5 million entries. Back on Day 3 we saw the converge pattern that runs a function until a condition no longer holds true:
q){ x + 1 }/[{ x < 10 };] 3 / call the function until x is no longer less than 10
10
q){ x + 1 }\[{ x < 10 };] 3 / same but return intermediate steps
3 4 5 6 7 8 9 10
In our case, we want to iterate while there are fewer than 5 million entries in A, or to put it another way, the count of A is less-than 5 million:
q)f:{ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }/[{ (count A) < 5000000 };]
q)f:{ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }/[{ 5000000 > count A };] / no brackets
Let’s swap out the 5 million for just 5, run the function and compare its output to the expected output:
q)A:() / reset A back to an empty list
q){ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }/[{ (count A) < 5 };65]
740335192
q)A
1352636452 1992081072 530830436 1980017072 740335192
These match up to the examples for Generator A in the Challenge text:
--Gen. A-- --Gen. B--
1352636452 1233683848
1992081072 862516352
530830436 1159784568
1980017072 1616057672
740335192 412269392
OK! Let’s reset A, and run for 5 million:
q){ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }/[{ (count A) < 5000000 };65]
648634980
q)count A
5000000
q)A
1352636452 1992081072 530830436 1980017072 740335192 2099633200 1083904896 1239932660 366906132 260934108 1604199484 2079041784 1086548036 112881888 1767310380 1723250404 1582998620 854985672..
Now for Generator B, let’s create the empty list B to store the values in:
q)B:()
We can re-use our function, just changing a few of the values:
- the
factorfrom16807to48271, - the divisor from
4to8, and (most importantly) - the list to append values to from
AtoB
q){ n:mod[x * 48271;2147483647]; if[0 = n mod 8;B,:n]; n }/[{ 5000000 > count B };]
Feeding in the starting value for Generator B will kick off the generator. Note that this generator takes a fair while longer to run that the first.
We now have the two lists and need to compare the lowest 16 bits from each. We saw from Part 1 that taking a number modulo 65536 is equivalent to taking the lowest 16 bits, therefore we can apply this modulo to both A and B, and check equality with =:
q)mod[A;65536]
38948 48816 54372 43440 40536 56368 4992 57076 35604 35292 9276 43256 26692 28896 1068 46820 42076 3016 29588 1524 40904 20808 2916 26584 50800 37768 752 2728 46300 41524 22892 60792 29736..
q)mod[B;65536]
34184 62592 59512 5448 47952 55944 28912 31808 45816 13496 38760 15560 18512 60168 41312 40328 49376 36888 42760 30456 15904 41080 60480 43176 9800 10040 42680 59632 43448 25112 38336..
q)mod[A;65536]=mod[B;65536]
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000..
We can use sum to sum up all the ‘truthy’ cases (the matches):
q)sum mod[A;65536]=mod[B;65536]
309i
This matches the example, so the only thing left is to reset the lists A and B and to feed your puzzle input values in and collect your second star:
q)i:"J"$last each " "vs'read0 `:input/15.txt / read in our input, save as 'i'
q)A:B:() / shortcut way to set both A and B to empty list
q){ n:mod[x * 16807;2147483647]; if[0 = n mod 4;A,:n]; n }/[{ (count A) < 5000000 };] first i
875661760
q){ n:mod[x * 48271;2147483647]; if[0 = n mod 8;B,:n]; n }/[{ (count B) < 5000000 };] last i
415075424
q)sum mod[A;65536]=mod[B;65536]
336i
Complete Solution To Day 15
My full solution for Day 15 is below. There are a few tweaks, such as in-lining the generated value into the if-statement clause, but, for the most part, it matches this post.
Advent of Code 2017, Day 14: Disk DefragmentationNext: Advent of Code 2017, Day 16: Permutation Promenade