71 lines
2.0 KiB
D
71 lines
2.0 KiB
D
|
import std.stdio;
|
||
|
|
import std.algorithm;
|
||
|
|
import std.array;
|
||
|
|
import std.string;
|
||
|
|
import std.conv;
|
||
|
|
|
||
|
|
bool isLinear(long[] numbers) {
|
||
|
|
if (numbers.length < 2) return true;
|
||
|
|
const long diff = numbers[1] - numbers[0];
|
||
|
|
for (int i = 1; i + 1 < numbers.length; i++) {
|
||
|
|
if (numbers[i] - numbers[i-1] != diff) return false;
|
||
|
|
}
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
long[] computeNextOrder(long[] numbers) {
|
||
|
|
if (numbers.length < 2) return [];
|
||
|
|
long[] diffs = new long[](numbers.length - 1);
|
||
|
|
for (int i = 1; i < numbers.length; i++) {
|
||
|
|
diffs[i-1] = numbers[i] - numbers[i-1];
|
||
|
|
}
|
||
|
|
return diffs;
|
||
|
|
}
|
||
|
|
|
||
|
|
long extrapolateHistory(long[] numbers) {
|
||
|
|
long[] lastValues = [numbers[$-1]];
|
||
|
|
long[] currentSequence = numbers.dup;
|
||
|
|
while (!isLinear(currentSequence)) {
|
||
|
|
currentSequence = computeNextOrder(currentSequence);
|
||
|
|
lastValues ~= currentSequence[$-1];
|
||
|
|
}
|
||
|
|
const long linearDiff = currentSequence[$-1] - currentSequence[$-2];
|
||
|
|
long nextValue = lastValues[$-1] + linearDiff;
|
||
|
|
while (lastValues.length > 1) {
|
||
|
|
lastValues = lastValues[0..$-1];
|
||
|
|
nextValue = lastValues[$-1] + nextValue;
|
||
|
|
}
|
||
|
|
return nextValue;
|
||
|
|
}
|
||
|
|
|
||
|
|
long extrapolateHistoryBack(long[] numbers) {
|
||
|
|
long[] lastValues = [numbers[0]];
|
||
|
|
long[] currentSequence = numbers.dup;
|
||
|
|
while (!isLinear(currentSequence)) {
|
||
|
|
currentSequence = computeNextOrder(currentSequence);
|
||
|
|
lastValues ~= currentSequence[0];
|
||
|
|
}
|
||
|
|
const long linearDiff = currentSequence[$-1] - currentSequence[$-2];
|
||
|
|
long nextValue = lastValues[$-1] - linearDiff;
|
||
|
|
while (lastValues.length > 1) {
|
||
|
|
lastValues = lastValues[0..$-1];
|
||
|
|
nextValue = lastValues[$-1] - nextValue;
|
||
|
|
}
|
||
|
|
return nextValue;
|
||
|
|
}
|
||
|
|
|
||
|
|
void part1() {
|
||
|
|
File("input.txt").byLineCopy.map!(s => s.strip.split.map!(to!long).array)
|
||
|
|
.map!extrapolateHistory.sum.writeln;
|
||
|
|
}
|
||
|
|
|
||
|
|
void part2() {
|
||
|
|
File("input.txt").byLineCopy.map!(s => s.strip.split.map!(to!long).array)
|
||
|
|
.map!extrapolateHistoryBack.sum.writeln;
|
||
|
|
}
|
||
|
|
|
||
|
|
void main() {
|
||
|
|
part1();
|
||
|
|
part2();
|
||
|
|
}
|