63 lines
1.6 KiB
D
63 lines
1.6 KiB
D
|
import std;
|
||
|
|
|
||
|
|
import mir.combinatorics;
|
||
|
|
|
||
|
|
void main()
|
||
|
|
{
|
||
|
|
File("input", "r").byLine.map!(to!long).array.breakXMASEncryption(25).writeln;
|
||
|
|
}
|
||
|
|
|
||
|
|
auto findFirstNumberNotSumOf2PreviousNumbers(long[] numbers, size_t windowSize)
|
||
|
|
in(numbers.length > windowSize)
|
||
|
|
{
|
||
|
|
return numbers.slide(windowSize + 1)
|
||
|
|
.map!(window => tuple(window[0 .. $ - 1].combinations(2).map!sum, window[windowSize]))
|
||
|
|
.find!(pair => !pair[0].canFind(pair[1]))
|
||
|
|
.front[1];
|
||
|
|
}
|
||
|
|
|
||
|
|
unittest
|
||
|
|
{
|
||
|
|
long[] input = [
|
||
|
|
35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299,
|
||
|
|
277, 309, 576
|
||
|
|
];
|
||
|
|
|
||
|
|
assert(input.findFirstNumberNotSumOf2PreviousNumbers(5) == 127);
|
||
|
|
}
|
||
|
|
|
||
|
|
auto findContiguousSubrangeWhichSumsTo(long[] input, long number)
|
||
|
|
{
|
||
|
|
return iota(2, input.length + 1).map!(i => input.slide(i))
|
||
|
|
.joiner
|
||
|
|
.find!(it => it.sum == number)
|
||
|
|
.front;
|
||
|
|
}
|
||
|
|
|
||
|
|
unittest
|
||
|
|
{
|
||
|
|
long[] input = [
|
||
|
|
35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299,
|
||
|
|
277, 309, 576
|
||
|
|
];
|
||
|
|
|
||
|
|
assert(input.findContiguousSubrangeWhichSumsTo(127) == [15, 25, 47, 40]);
|
||
|
|
}
|
||
|
|
|
||
|
|
auto breakXMASEncryption(long[] input, size_t windowSize)
|
||
|
|
{
|
||
|
|
auto invalidNumber = input.findFirstNumberNotSumOf2PreviousNumbers(windowSize);
|
||
|
|
auto contiguousSubrange = input.findContiguousSubrangeWhichSumsTo(invalidNumber);
|
||
|
|
return contiguousSubrange.minElement + contiguousSubrange.maxElement;
|
||
|
|
}
|
||
|
|
|
||
|
|
unittest
|
||
|
|
{
|
||
|
|
long[] input = [
|
||
|
|
35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299,
|
||
|
|
277, 309, 576
|
||
|
|
];
|
||
|
|
|
||
|
|
assert(input.breakXMASEncryption(5) == 62);
|
||
|
|
}
|