git

My personal website source code
Log | Files | Refs | Submodules | README | LICENSE

zet-2-aoc-2021-01.md (4523B)


      1 ---
      2 title: 'Zettelkasten #2: Solution in D for Advent of Code 2021, Day 1'
      3 date: '2021-12-01T18:03:00+01:00'
      4 tags: ['zettelkasten', 'zet', 'dlang', 'aoc', 'aoc2021', 'adventofcode']
      5 description: "This post describes, in detail, my solution in the D programming
      6 language for the 1st puzzle of the Advent of Code 2021."
      7 ---
      8 
      9 ## The challenge
     10 
     11 > As the submarine drops below the surface of the ocean, it automatically
     12 > performs a sonar sweep of the nearby sea floor. On a small screen, the sonar
     13 > sweep report (your puzzle input) appears: each line is a measurement of the
     14 > sea floor depth as the sweep looks further and further away from the
     15 > submarine.
     16 >
     17 > [...]
     18 >
     19 > The first order of business is to figure out how quickly the depth increases,
     20 > just so you know what you're dealing with - you never know if the keys will
     21 > get carried into deeper water by an ocean current or a fish or something.
     22 >
     23 > To do this, count the number of times a depth measurement increases from the
     24 > previous measurement. (There is no measurement before the first measurement.)
     25 >
     26 > [...]
     27 
     28 You can read the challenge more in depth,
     29 [here](https://adventofcode.com/2021/day/1).
     30 
     31 ## Part 1
     32 
     33 The idea here is to create duplicate version of the values array but shifted,
     34 to zip and compare those two value groups afterwards:
     35 
     36 ```d
     37 auto a = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]; // initial array
     38 [0, 199, 200, 208, 210, 200, 207, 240, 269, 260] // shifted by one
     39 
     40 zip(a, 0 ~ a[0 .. $ - 1]) // zipped ranges
     41 ```
     42 
     43 But we now trim the first value of each zipped group. To do this efficiently,
     44 without any reallocation, we can offset on of the arrays by one and slice the
     45 other one with the right length:
     46 
     47 ```d
     48 auto a = [ 199, 200, 208, 210, 200, 207, 240, 269, 260, 263]; // initial array
     49 a[1 .. $] // array slice with an offset
     50 a[0 .. $ - 1] // slice without the last element
     51 
     52 zip(a[1 .. $], a[0 .. $ - 1]) // zipped ranges wo/ the 1st element
     53 ```
     54 
     55 Finally we can calculate the difference between the zipped values by mapping
     56 them:
     57 
     58 ```d
     59 auto z = zip(a[1 .. $], a[0 .. $ - 1]);
     60 auto diff = z.map!"a[0] - a[1]"; // mapped difference
     61 
     62 diff.writeln; // [1, 8, 2, -10, 7, 33, 29, -9, 3]
     63 ```
     64 
     65 Now that have an array with the calculated differences, we just need to count
     66 the positive values:
     67 
     68 ```d
     69 auto diff = z.map!"a[0] - a[1]"; // mapped difference
     70 auto p = diff.count!"a > 0"; // count positives
     71 
     72 p.writeln; // 7
     73 ```
     74 
     75 ### Full solution
     76 
     77 ```d
     78 [stdin.byLine().map!(to!long).array]        // input
     79     .map!(r => zip(r[1 .. $], r[0 .. $-1])) // zip w/ shifted range
     80     .front.map!(z => z[0] - z[1])           // calculate diffs
     81     .count!"a > 0".writeln;                 // count positives
     82 ```
     83 
     84 ## Part 2
     85 
     86 > Considering every single measurement isn't as useful as you expected: there's
     87 > just too much noise in the data. Instead, consider sums of a
     88 > three-measurement sliding window.
     89 >
     90 > [...]
     91 >
     92 > Your goal now is to count the number of times the sum of measurements in this
     93 > sliding window increases from the previous sum.
     94 
     95 The second part is slightly different, as we need to group the values in groups
     96 of three. Taking the same principle of the first part, we can shift and offset
     97 the initial array to create the groups:
     98 
     99 ```d
    100 auto g = zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $]); // zip three slices
    101 ```
    102 
    103 Now we just sum the values of each group, by mapping them and sum the expanded
    104 version of the group:
    105 
    106 ```d
    107 auto g = zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $]); // zip three slices
    108 auto s = g.map!(e => sum([e.expand])); // sum the values
    109 
    110 s.writeln; // [607, 618, 618, 617, 647, 716, 769, 792]
    111 ```
    112 
    113 With those values summed up, we replicate the same exact thing from the first
    114 part.
    115 
    116 ### Full solution
    117 
    118 ```d
    119 [[stdin.byLine().map!(to!long).array]                        // input
    120     .map!(r => zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $])) // group values
    121     .front.map!(e => sum([e.expand])).array]                 // sum each group
    122     .map!(r => zip(r[1 .. $], r[0 .. $-1]))                  // zip w/ shifted range
    123     .front.map!"a[0] - a[1]"                                 // calculate diffs
    124     .count!"a > 0".writeln;                                  // count positives
    125 ```
    126 
    127 ### Clever solution
    128 
    129 Thanks to `u/Jlobblet` [on
    130 Reddit](https://www.reddit.com/r/adventofcode/comments/r66vow/comment/hmtwtbw/),
    131 this is also a possible solution in D:
    132 
    133 ```d
    134 auto data = stdin.byLine().map!(to!long).array;
    135 StoppingPolicy.shortest.zip(data, data[3..$]) // change 3 to 1 for part one
    136     .count!"a[1] > a[0]".writeln;
    137 ```