summary refs log tree commit diff stats
path: root/2020/day-03
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2020-12-04 20:21:18 +0530
committerAndinus <andinus@nand.sh>2020-12-04 20:21:18 +0530
commit26abda4d486c2e9efc276d6b7e85f8ce5d009828 (patch)
tree988c0b3d980494761e7e4ec5f85f48d8a8fa316f /2020/day-03
parentf2da3d2696546d1b12e9eb6a30bab31fefbba4ee (diff)
downloadaoc-26abda4d486c2e9efc276d6b7e85f8ce5d009828.tar.gz
Add day-03 solution
Diffstat (limited to '2020/day-03')
-rw-r--r--2020/day-03/README.org162
-rwxr-xr-x2020/day-03/day-03.raku50
-rw-r--r--2020/day-03/input323
3 files changed, 535 insertions, 0 deletions
diff --git a/2020/day-03/README.org b/2020/day-03/README.org
new file mode 100644
index 0000000..77328b3
--- /dev/null
+++ b/2020/day-03/README.org
@@ -0,0 +1,162 @@
+#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org
+#+HTML_LINK_UP: ../../../writings/#aoc
+#+OPTIONS: toc:1
+#+EXPORT_FILE_NAME: index
+#+TITLE: Day 03 - Toboggan Trajectory
+
+* Puzzle
+- This puzzle is taken from: https://adventofcode.com/2020/day/3
+
+With the toboggan login problems resolved, you set off toward the
+airport. While travel by toboggan might be easy, it's certainly not
+safe: there's very minimal steering and the area is covered in trees.
+You'll need to see which angles will take you near the fewest trees.
+
+Due to the local geology, trees in this area only grow on exact integer
+coordinates in a grid. You make a map (your puzzle input) of the open
+squares (.) and trees (#) you can see. For example:
+#+BEGIN_SRC
+..##.......
+#...#...#..
+.#....#..#.
+..#.#...#.#
+.#...##..#.
+..#.##.....
+.#.#.#....#
+.#........#
+#.##...#...
+#...##....#
+.#..#...#.#
+#+END_SRC
+
+These aren't the only trees, though; due to something you read about
+once involving arboreal genetics and biome stability, the same pattern
+repeats to the right many times:
+#+BEGIN_SRC
+..##.........##.........##.........##.........##.........##.......  --->
+#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
+.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
+..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
+.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
+..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
+.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
+.#........#.#........#.#........#.#........#.#........#.#........#
+#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
+#...##....##...##....##...##....##...##....##...##....##...##....#
+.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->
+#+END_SRC
+
+You start on the open square (.) in the top-left corner and need to
+reach the bottom (below the bottom-most row on your map).
+
+The toboggan can only follow a few specific slopes (you opted for a
+cheaper model that prefers rational numbers); start by counting all the
+trees you would encounter for the slope right 3, down 1:
+
+From your starting position at the top-left, check the position that is
+right 3 and down 1. Then, check the position that is right 3 and down 1
+from there, and so on until you go past the bottom of the map.
+
+The locations you'd check in the above example are marked here with O
+where there was an open square and X where there was a tree:
+#+BEGIN_SRC
+..##.........##.........##.........##.........##.........##.......  --->
+#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
+.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
+..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
+.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
+..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##.....  --->
+.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
+.#........#.#........X.#........#.#........#.#........#.#........#
+#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
+#...##....##...##....##...#X....##...##....##...##....##...##....#
+.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.#  --->
+#+END_SRC
+
+In this example, traversing the map using this slope would cause you to
+encounter 7 trees.
+
+Starting at the top-left corner of your map and following a slope of
+right 3 and down 1, how many trees would you encounter?
+** Part 2
+Time to check the rest of the slopes - you need to minimize the
+probability of a sudden arboreal stop, after all.
+
+Determine the number of trees you would encounter if, for each of the
+following slopes, you start at the top-left corner and traverse the map
+all the way to the bottom:
+
+- Right 1, down 1.
+- Right 3, down 1. (This is the slope you already checked.)
+- Right 5, down 1.
+- Right 7, down 1.
+- Right 1, down 2.
+
+In the above example, these slopes would find 2, 7, 3, 4, and 2 tree(s)
+respectively; multiplied together, these produce the answer 336.
+
+What do you get if you multiply together the number of trees encountered
+on each of the listed slopes?
+* Solution
+=count-trees= is a subroutine that will count the number of trees we'll
+encounter, it needs =@input=, =$right=, =$down=.
+#+BEGIN_SRC raku
+sub count-trees (
+    @input,
+    Int $right,
+    Int $down
+) {
+    # Start at top left position.
+    my $x = 0;
+    my $y = 0;
+    my $trees = 0;
+
+    my $x-max = @input[0].elems - 1;
+    my $y-max = @input.elems - 1;
+
+    loop {
+        $trees++ if @input[$y][$x] eq '#';
+
+        $x += $right;
+        $y += $down;
+
+        # Cannot let $x become greater than $x-max because that'll produce
+        # error when we try to access @input with those positions. So, we
+        # wrap it around because the same map is repeated.
+        $x -= $x-max + 1 if $x > $x-max;
+
+        last if $y-max < $y;
+    }
+    return $trees;
+}
+#+END_SRC
+
+=$x-max= holds the last index of =@input= =x= coordinate & same for =$y-max=
+with =y= coordinate. The loop first checks if we've encountered a tree &
+increments =$trees= if true. Then =$x= & =$y= are incremented to new
+positions.
+
+Later we check if =$x= has become greater than =$-max=, if true then we just
+wrap =$x= around the map. The map is infinitely long in =x= axis, =$x-max + 1=
+is subtracted because that is the length of map in =x= axis after which it
+repeats infinitely. We stop when the we reach the bottom most corner of
+the map.
+
+For part 1 we simply pass (3, 1) for (=$right=, =$down=) values to
+subroutine =count-trees= & print the solution.
+#+BEGIN_SRC raku
+say "Part 1: ", count-trees(@input, 3, 1);
+#+END_SRC
+** Part 2
+For part 2 we calculate the number of trees for different sets of
+(=$right=, =$down=), multiply those numbers & print it.
+#+BEGIN_SRC raku
+my @trees = [{ right => 1, down => 1 },
+	     { right => 3, down => 1 },
+	     { right => 5, down => 1 },
+	     { right => 7, down => 1 },
+	     { right => 1, down => 2 },].map(
+    {count-trees(@input, $_<right>, $_<down>)}
+);
+say "Part 2: ", [*] @trees;
+#+END_SRC
diff --git a/2020/day-03/day-03.raku b/2020/day-03/day-03.raku
new file mode 100755
index 0000000..c8656ac
--- /dev/null
+++ b/2020/day-03/day-03.raku
@@ -0,0 +1,50 @@
+#!/usr/bin/env raku
+
+sub MAIN (
+    # Part to run.
+    Int $part where * == 1|2 = 1
+) {
+    my @input = "input".IO.lines>>.comb;
+
+    if $part == 1 {
+        say "Part 1: ", count-trees(@input, 3, 1);
+    } elsif $part == 2 {
+        my @trees = [{ right => 1, down => 1 },
+	 { right => 3, down => 1 },
+	 { right => 5, down => 1 },
+	 { right => 7, down => 1 },
+	 { right => 1, down => 2 },].map(
+            {count-trees(@input, $_<right>, $_<down>)}
+        );
+        say "Part 2: ", [*] @trees;
+    }
+}
+
+sub count-trees (
+    @input,
+    Int $right,
+    Int $down
+) {
+    # Start at top left position.
+    my $x = 0;
+    my $y = 0;
+    my $trees = 0;
+
+    my $x-max = @input[0].elems - 1;
+    my $y-max = @input.elems - 1;
+
+    loop {
+        $trees++ if @input[$y][$x] eq '#';
+
+        $x += $right;
+        $y += $down;
+
+        # Cannot let $x become greater than $x-max because that'll produce
+        # error when we try to access @input with those positions. So, we
+        # wrap it around because the same map is repeated.
+        $x -= $x-max + 1 if $x > $x-max;
+
+        last if $y-max < $y;
+    }
+    return $trees;
+}
diff --git a/2020/day-03/input b/2020/day-03/input
new file mode 100644
index 0000000..a8bdfa9
--- /dev/null
+++ b/2020/day-03/input
@@ -0,0 +1,323 @@
+......#...........#...#........
+.#.....#...##.......#.....##...
+......#.#....#.................
+..............#.#.......#......
+.....#.#...##...#.#..#..#..#..#
+.......##...#..#...........#...
+.......#.##.#...#.#.........#..
+..#...##............##......#.#
+.......#.......##......##.##.#.
+...#...#........#....#........#
+#............###.#......#.....#
+..#........#....#..#..........#
+..#..##....#......#..#......#..
+........#......#......#..#..#..
+..#...#....#..##.......#.#.....
+.....#.#......#..#....#.##.#..#
+......###.....#..#..........#..
+.#................#.#..........
+.........#..#...#......##......
+##...#....#...#.#...#.##..#....
+...##...#....#.........###.....
+.#.#....#.........##...........
+....#.#..#..#...........#......
+..#..#.#....#....#...#.........
+..........##.....#.##..........
+..#.#....#..##......#.#.....##.
+..#...#.##......#..........#...
+......#....#..#.....#.....#...#
+#.#...##.#.##.........#..#.....
+...#.#.#.........#.....#.#.#...
+..#.........#...............#..
+#..##.....#.........#....#.....
+...#....##..##...........##..#.
+......##.................#.#...
+##.......#....#.#.#.....#......
+....#.#...#.................##.
+#...#.........##.....#.........
+#....#.###..#.....##.#....#....
+#..#....#...#....#.#.#.........
+.......#...........#....#.....#
+#...#.............#........#...
+.......#.....#...#..#.........#
+.##.....##.....##.......#......
+....##...##.......#..#.#.....#.
+.##.........#......#........##.
+.......#...#...###.#..#........
+..#..###......##..##...........
+.#..#......##..#.#.........#...
+...#.......#........#...#.#....
+...#....#..#....#.....##.......
+............#......#..........#
+.#.......#......#.#....#..#.#..
+##.........#.#.#..........#....
+....##.....#...................
+.......#..#........#...........
+....##.#..#......###.......#...
+....#....#...#.#......#...#...#
+.......#.....##..#....#...#....
+#...#........#.........#..##...
+...........##.........#.#...#..
+....................#....#.##..
+.#..#..#.........#....#..#..##.
+......................#........
+..###....#.......#.....###.##..
+......#......#.......#.....#..#
+.....#...#.##...#......#....#..
+.....#.....##.............#....
+....#......##..#....#.......#..
+.##....#..##......###....#..#..
+...###.#.............##...#.#..
+.....#.....#.....#...#..#.#....
+..#.#.....###......#.......#...
+..........#.##......#.........#
+..##..#.......................#
+........#......#............#..
+#..#..#..#.#......#..#....#....
+...##......#.............#....#
+...........#..#..##.......#....
+.....#.........#.#..#..........
+##...#.......#.#....#..#..#....
+#.#.#...........#.##.#.#..###..
+#..#...........#.........##....
+............#.#..............#.
+.#....#....##.#...........#..#.
+....#...#..#...#....#....#.....
+....#....#...#..#......#.......
+.#.#.........#.......#.##......
+.#..##...#........#...........#
+##...#..#...#...#.....#...#....
+....###.#..#.......##.#..#...#.
+...##.......####...##.#........
+#....#....#.#............#..#..
+#.#.#...#...................##.
+##......#...........#..........
+#..#..#....#.#...#......#......
+.##...#.....#...#........#.....
+..#............#..............#
+###........#..#....#...#......#
+###..##......#.##...........#..
+........#......#..#.....#......
+...#..........#..#...........#.
+....#..#..#....#........#....#.
+.#.................#####..##..#
+.....#...##..#..........#.##...
+..#..............#...####......
+.....#.##..................#.#.
+...#.#..#..#........#..........
+...........#....#.#..#.........
+.....##.......#......#..#.#.#..
+...#.............##...#........
+...............#.......##.##.##
+.....#........#........#.#..#..
+...#..#.........#...##...###...
+...#.#.............###.#.....#.
+.#..........#......###.#.#.....
+....##..##.............###.....
+..#..#.#...##...#.......##.....
+..........###........#.....#.#.
+#.#....#..#..#......#...#...#..
+.........#......##.......#.#..#
+...#.....#.........##..#..#....
+.....##.#..##.##..##...........
+...#.#.##....#..#..#......#..#.
+#....#....#.............#...##.
+#......#..#.####.#.##.#....##..
+##.#.#....##..................#
+.....##......#.......##.......#
+..#......#.#..#...##......##...
+..#....##....#.........#..##...
+.###.....#....##...........#...
+.........#......#.#........#...
+...#...#..#.#....######.#..#...
+###......#.#.#.........##.#....
+.....#...#.........#...#.......
+....#.............#.#.........#
+..##...#...#.......#......#....
+.....#...#.#...#...#..#........
+.#......#......................
+...###..#..#....#...##.#.......
+.#.#.....##...#...#.....#...##.
+.....###..###....##............
+.....##....#..#.....#.##.......
+#........#.........#...#..#....
+...#.#.........#..#.......#.#..
+....#.#....##.....#..........#.
+.#..#....#..#.#..#..#.........#
+#...#....#..............#......
+.........#.....#.##...##...###.
+.....#....##............#..#...
+.....#.#...........#..#....#...
+.#..........#...#......#.....#.
+.#...........#.....#..#........
+..............#......##...#..#.
+...#.........#..#....#..##...##
+..##...#..................#....
+#.....#.................#......
+...#......#..#..........#.#....
+......#..#.....#.....##...#..#.
+......#........#..........#....
+...##.##....#..##.#..........#.
+..........#..#.#.##............
+..##........................#..
+.....#.#.#......#....#....##...
+#....#.........#........#......
+.##.......#...#...#........##..
+....##......#....#.#..........#
+..#.......#..............#.....
+.....#......#.#...#..#.#.#....#
+.....#..#........#.##.##.......
+##........#..........#.........
+.....#..##....#.#......###..##.
+#.#...##.........#.#.....#..#..
+#....#.#...#........#.....#..#.
+........................#......
+....###......#............#...#
+...#..##......#..##.........#..
+.............#...#......#..#..#
+....#......#....#...........#..
+..#.#.####.#.....##........#..#
+#..#...#..#..#.......#.#..#....
+..#..#..#....#.#.........##..#.
+.......#......#.#............#.
+...#.............#.#.....#.....
+...#.#.........##...#.#.......#
+........#...#...........##...#.
+..........#....#......#....##..
+..........#...........#........
+...#..#...#..........#......#..
+......#......#....#.....#..#.#.
+........##.................#..#
+.#........#.#...........#......
+#...#........#.#.#.....#.#.#...
+.........#........#..#..#....#.
+##........#..........#....#..#.
+.#.##...........#..#.#..##....#
+.......#.#....#..#......#......
+..#.....#........##..#......###
+..#...#..................#....#
+......#...#..#.##.......#......
+........#...#.#................
+.........#............#........
+..#.....##....#.#..##..........
+#.....#..........#....#........
+....#.#...#...##....#.....##...
+..#.#.......#.............#...#
+...##..............#......#....
+#......#...#................##.
+.#.#...#.#..#..................
+...##.......#...........#.#.#..
+#......#.#.#........#.##...####
+.......#..#.#.........#.#.##..#
+..............#....#.........#.
+...........#.#..#....##......#.
+#.............#...##..#.......#
+.........#............#...#.##.
+.......#.........#.#.....#..#..
+........................#.#.##.
+#......#.#......#.........#....
+...#.......#.......#.....#.....
+#..#....#................#...#.
+........#.#..##......#.........
+#..#...##....##....##.........#
+.......#...#...###.............
+#.#..#........#.#.#............
+#.....#........##.........#.#..
+.#..........#....#.#....###....
+.#.....#...#.#........#..#.##..
+...#.##......#..#.............#
+..##..#.#...................#..
+.....#....#...#.#...#...#......
+.....#..#.#....#.#.............
+#.#....#.#.##..###..........#..
+........#.#.............#..#...
+.........#.......#.............
+.##.#............##...#........
+......#................#.......
+...............#..#...........#
+...#.......#...#.##.....#....#.
+##..##..#..........#...........
+.##.#.......#...#..#...#...#...
+....#..#...........#....#.##...
+.#........#........#....#......
+.......#...#.##.#..#.#..#......
+.#..#......#....#...##....#.#..
+......#...##.#.....##.###.....#
+.#....#..#......#...#.#.....#..
+#............#....##...##.##...
+#...#.#....#...#.......##...##.
+#...........#.##..#....#.....#.
+...#..#...#.........#.......#..
+.#....#.....#............#.#..#
+.#.....#.#...#.#....##......###
+..#..#.#.#...#..#.............#
+...#...#..#....#........#...##.
+.......#.....#...##...........#
+#.##.................#...##...#
+..............##........#.....#
+............#...#..#.......#.#.
+#.#.....#.........#...#......#.
+#.###..#......#..#..#...#.....#
+.....#.......#.................
+........#..#......#.#...#......
+#.......#..#........#...#..#...
+..#...#.......##.............#.
+#.......#.......##...#.........
+.........#....#.#..##.....#...#
+..#.....#.#.......#....#.......
+...#.......#.....#..##.#..#....
+....#.......#.#.#..............
+.#..#......#........#.#..##..##
+....#...#.##.#...#....##...#...
+#..##..#.....#.......#.........
+....#..#..#.#............#.....
+#.......##...##..##............
+...............................
+....#.......#.##...#.....#.#...
+...#........#....#.#..#..#.....
+##.......#.....##.#.#....#....#
+#.............#...........#.##.
+#...........#.#..........#.....
+#..#....#....#.#.........#.#...
+......#.#.#..#.#.#.............
+...#.....#........##....#......
+..#...#...#.#.......#......#...
+.##........#...#..#..........#.
+..#...........#..##.....##.....
+............#..#.#...#.....#...
+..........#....##.......#......
+....#....#.................#..#
+....#...............#.........#
+..#.#...#......#..........##...
+.....#...........#.........#..#
+.......#.....##.....#.#........
+.#.#..........#....#...........
+.#..##....#........#....#......
+....#.#..#.......#..#.........#
+..#....#.....#......#..#.......
+......#........#.......#...#.#.
+.......#.......#....#.....##...
+....##........#..#...#.#..#...#
+.#......#...........##....#....
+##....##......#.......#.......#
+.##....#.##......#.......##..#.
+...#..#.#.#.......#..#.###.....
+..........##....#..#.##........
+...#........###.#..#........#..
+.....#....#..##....#.....#....#
+#..........#..........#.#....#.
+..#....#.....#..............#..
+#..................#......#.##.
+.#...#.#.....#.........##......
+...#...........#.....#......#..
+......#.....#.#..##......##....
+...#....###..#.....#..#..##..##
+......#.......##..#..#.........
+#..#.#....#.#..#..........##.#.
+..#..#..##..#.#.#.#.....#......
+..#.#...#..#.....###.#.........
+##.#.#......#........#.####....
+.............#..#..#....#......
+...##..........#.......#.#....#
+..#.....................#......
+..#..#...##...#.##........#....