From 26abda4d486c2e9efc276d6b7e85f8ce5d009828 Mon Sep 17 00:00:00 2001 From: Andinus Date: Fri, 4 Dec 2020 20:21:18 +0530 Subject: Add day-03 solution --- 2020/day-03/README.org | 162 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 162 insertions(+) create mode 100644 2020/day-03/README.org (limited to '2020/day-03/README.org') 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, $_, $_)} +); +say "Part 2: ", [*] @trees; +#+END_SRC -- cgit 1.4.1-2-gfad0