Day 9

Author

Julia Romanowska

The input

Sequences of numbers.

root = dirname(@__FILE__);
input_file = joinpath(root, "..", "..", "DATA", "2023", "input_day09.txt");
#input_file = joinpath(root, "..", "..", "DATA", "2023", "example_input_day09.txt");
input_data = read(open(input_file, "r"), String);

input_data = split(input_data, "\n") |>
    x -> split.(x, " ");
input_data = broadcast(x -> parse.(Int64, x), input_data[1:(end - 1)])

200-element Vector{Vector{Int64}}:
 [8, 7, 3, 3, 21, 91, 297, 830, 2098, 4940  …  23745, 49682, 102071, 207392, 418543, 839856, 1672689, 3294947, 6393907, 12179007]
 [14, 16, 21, 48, 126, 306, 696, 1534, 3320, 7031  …  28549, 54126, 98307, 171187, 286281, 460690, 714762, 1070999, 1551934, 2176694]
 [16, 25, 28, 16, -15, -58, -95, -93, 27, 484  …  5395, 13786, 31983, 68678, 138244, 263370, 478515, 834334, 1403242, 2286295]
 [11, 14, 21, 40, 76, 125, 170, 186, 176, 285  …  4181, 13601, 38634, 99880, 241509, 555257, 1225456, 2610109, 5381286, 10759714]
 [14, 22, 47, 116, 268, 548, 997, 1638, 2458, 3386  …  4832, 4664, 3160, -511, -7454, -19098, -37250, -64153, -102548, -155740]
 [16, 17, 29, 64, 133, 246, 412, 639, 934, 1303  …  2282, 2899, 3604, 4398, 5281, 6252, 7309, 8449, 9668, 10961]
 [7, 17, 44, 98, 194, 359, 639, 1106, 1865, 3061  …  7586, 11468, 16907, 24353, 34338, 47483, 64505, 86224, 113570, 147590]
 [23, 34, 41, 50, 76, 155, 375, 943, 2318, 5456  …  26126, 53285, 104101, 195476, 353979, 620137, 1054142, 1743299, 2811586, 4431746]
 [9, 19, 33, 48, 60, 64, 54, 23, -37, -135  …  -486, -762, -1122, -1580, -2151, -2851, -3697, -4707, -5900, -7296]
 [12, 15, 21, 49, 138, 352, 778, 1528, 2774, 4870  …  16072, 31448, 63860, 131720, 271603, 555820, 1128761, 2284679, 4637247, 9488786]
 [15, 34, 61, 103, 183, 355, 725, 1476, 2893, 5379  …  15646, 24421, 35778, 48745, 60485, 64947, 50896, -867, -121319, -358325]
 [11, 13, 20, 35, 61, 101, 158, 235, 335, 461  …  803, 1025, 1285, 1586, 1931, 2323, 2765, 3260, 3811, 4421]
 [0, -2, -5, -17, -38, -48, -1, 167, 503, 959  …  680, -2193, -9841, -26210, -57218, -111414, -200940, -343079, -562875, -897600]
 ⋮
 [2, 4, 9, 29, 91, 243, 572, 1253, 2658, 5564  …  23355, 46127, 88207, 162972, 290975, 502778, 842556, 1372601, 2178865, 3377691]
 [19, 28, 43, 83, 186, 425, 932, 1938, 3857, 7477  …  27727, 53828, 104630, 201866, 383348, 712223, 1290098, 2275087, 3905963, 6533710]
 [10, 8, 4, 14, 77, 263, 688, 1540, 3115, 5867  …  18275, 31653, 56195, 104783, 207024, 428953, 912587, 1952373, 4138229, 8616090]
 [21, 29, 44, 83, 185, 422, 910, 1828, 3470, 6393  …  22362, 44018, 89188, 182562, 370687, 737235, 1426389, 2677512, 4875117, 8619151]
 [21, 31, 47, 88, 193, 432, 925, 1892, 3767, 7411  …  27741, 51929, 93998, 163636, 273125, 436329, 666183, 969881, 1340718, 1745257]
 [15, 13, 2, -11, 7, 129, 482, 1261, 2743, 5301  …  15701, 24895, 37897, 55770, 79757, 111295, 152029, 203826, 268789, 349271]
 [-8, -11, -14, -17, -20, -23, -26, -29, -32, -35  …  -41, -44, -47, -50, -53, -56, -59, -62, -65, -68]
 [18, 28, 36, 48, 72, 122, 228, 449, 886, 1692  …  5298, 8652, 13434, 19892, 28155, 38138, 49420, 61092, 71572, 78384]
 [14, 23, 47, 104, 221, 446, 873, 1686, 3232, 6142  …  21353, 39008, 70604, 127566, 232240, 429598, 810693, 1557495, 3024738, 5883107]
 [16, 29, 52, 81, 108, 121, 105, 56, 45, 420  …  8809, 27076, 72420, 174990, 390905, 820690, 1641111, 3163610, 5947757, 11028712]
 [21, 29, 40, 58, 84, 112, 134, 159, 245, 535  …  2841, 5664, 10389, 18477, 34425, 71752, 166672, 405377, 971947, 2221091]
 [-6, -14, -27, -33, -7, 89, 306, 708, 1372, 2388  …  5901, 8643, 12227, 16808, 22554, 29646, 38278, 48657, 61003, 75549]

Part 1

The problem and solution

Gather all the last differences and extrapolate another number in each sequence.

next_num_in_seq = Int64[];
for cur_seq in input_data
    last_differences = Int64[];

    cur_diff = diff(cur_seq);
    while !all(cur_diff .== 0)
        push!(last_differences, cur_diff[end]);
        cur_diff = diff(cur_diff);
    end

    push!(last_differences, cur_seq[end]);
    next_diff = 0;
    for i in last_differences
        next_diff += i;
    end
    push!(next_num_in_seq, next_diff);
end

The sum of the extrapolated values is: 1789635132.

Part 2

The problem and solution

Gather all the first differences and extrapolate previous number in each sequence.

prev_num_in_seq = Int64[];
for cur_seq in input_data
    first_differences = Int64[];

    cur_diff = diff(cur_seq);
    while !all(cur_diff .== 0)
        push!(first_differences, cur_diff[begin]);
        cur_diff = diff(cur_diff);
    end

    first_differences = first_differences[end:-1:1];
    push!(first_differences, cur_seq[begin]);
    prev_diff = 0;
    for i in first_differences
        prev_diff = i - prev_diff;
    end
    push!(prev_num_in_seq, prev_diff);
end

The sum of the extrapolated values is: 913.