git

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

commit 6b128d811ae4505bc4651ffd5cf3dc7f05d19618
parent e4d9b34a90b5b15bee9607bc3bf81c6044ccc655
Author: Luís Ferreira <[email protected]>
Date:   Wed,  1 Dec 2021 19:37:57 +0000

posts: Add 'Zettelkasten #2: Solution for Advent of Code 2021, Day 1'

Signed-off-by: Luís Ferreira <[email protected]>

Diffstat:
Acontent/posts/zet-2-aoc-2021-01.md | 137+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 137 insertions(+), 0 deletions(-)

diff --git a/content/posts/zet-2-aoc-2021-01.md b/content/posts/zet-2-aoc-2021-01.md @@ -0,0 +1,137 @@ +--- +title: 'Zettelkasten #2: Solution for Advent of Code 2021, Day 1' +date: '2021-12-01T18:03:00+01:00' +tags: ['zettelkasten', 'zet', 'dlang', 'aoc', 'aoc2021', 'adventofcode'] +description: "This post describes, in detail, my solution for the 1st puzzle +of the Advent of Code 2021." +--- + +## The challenge + +> As the submarine drops below the surface of the ocean, it automatically +> performs a sonar sweep of the nearby sea floor. On a small screen, the sonar +> sweep report (your puzzle input) appears: each line is a measurement of the +> sea floor depth as the sweep looks further and further away from the +> submarine. +> +> [...] +> +> The first order of business is to figure out how quickly the depth increases, +> just so you know what you're dealing with - you never know if the keys will +> get carried into deeper water by an ocean current or a fish or something. +> +> To do this, count the number of times a depth measurement increases from the +> previous measurement. (There is no measurement before the first measurement.) +> +> [...] + +You can read the challenge more in depth, +[here](https://adventofcode.com/2021/day/1). + +## Part 1 + +The idea here is to create duplicate version of the values array but shifted, +to zip and compare those two value groups afterwards: + +```d +auto a = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]; // initial array +[0, 199, 200, 208, 210, 200, 207, 240, 269, 260] // shifted by one + +zip(a, 0 ~ a[0 .. $ - 1]) // zipped ranges +``` + +But we now trim the first value of each zipped group. To do this efficiently, +without any reallocation, we can offset on of the arrays by one and slice the +other one with the right length: + +```d +auto a = [ 199, 200, 208, 210, 200, 207, 240, 269, 260, 263]; // initial array +a[1 .. $] // array slice with an offset +a[0 .. $ - 1] // slice without the last element + +zip(a[1 .. $], a[0 .. $ - 1]) // zipped ranges wo/ the 1st element +``` + +Finally we can calculate the difference between the zipped values by mapping +them: + +```d +auto z = zip(a[1 .. $], a[0 .. $ - 1]); +auto diff = z.map!"a[0] - a[1]"; // mapped difference + +diff.writeln; // [1, 8, 2, -10, 7, 33, 29, -9, 3] +``` + +Now that have an array with the calculated differences, we just need to count +the positive values: + +```d +auto diff = z.map!"a[0] - a[1]"; // mapped difference +auto p = diff.count!"a > 0"; // count positives + +p.writeln; // 7 +``` + +### Full solution + +```d +[stdin.byLine().map!(to!long).array] // input + .map!(r => zip(r[1 .. $], r[0 .. $-1])) // zip w/ shifted range + .front.map!(z => z[0] - z[1]) // calculate diffs + .count!"a > 0".writeln; // count positives +``` + +## Part 2 + +> Considering every single measurement isn't as useful as you expected: there's +> just too much noise in the data. Instead, consider sums of a +> three-measurement sliding window. +> +> [...] +> +> Your goal now is to count the number of times the sum of measurements in this +> sliding window increases from the previous sum. + +The second part is slightly different, as we need to group the values in groups +of three. Taking the same principle of the first part, we can shift and offset +the initial array to create the groups: + +```d +auto g = zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $]); // zip three slices +``` + +Now we just sum the values of each group, by mapping them and sum the expanded +version of the group: + +```d +auto g = zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $]); // zip three slices +auto s = g.map!(e => sum([e.expand])); // sum the values + +s.writeln; // [607, 618, 618, 617, 647, 716, 769, 792] +``` + +With those values summed up, we replicate the same exact thing from the first +part. + +### Full solution + +```d +[[stdin.byLine().map!(to!long).array] // input + .map!(r => zip(r[0 .. $ - 2], r[1 .. $ - 1], r[2 .. $])) // group values + .front.map!(e => sum([e.expand])).array] // sum each group + .map!(r => zip(r[1 .. $], r[0 .. $-1])) // zip w/ shifted range + .front.map!"a[0] - a[1]" // calculate diffs + .count!"a > 0".writeln; // count positives +``` + +### Clever solution + +Thanks to `u/Jlobblet` [on +Reddit](https://www.reddit.com/r/adventofcode/comments/r66vow/comment/hmtwtbw/), +this is also a possible solution in D: + +```d +auto data = stdin.byLine().map!(to!long).array; +StoppingPolicy.shortest.zip(data, data[3..$]) // change 3 to 1 for part one + .count!"a[1] > a[0]".writeln; +```