diff options
| -rw-r--r-- | 2020/day-03/README.org | 162 | ||||
| -rwxr-xr-x | 2020/day-03/day-03.raku | 50 | ||||
| -rw-r--r-- | 2020/day-03/input | 323 |
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 @@ +......#...........#...#........ +.#.....#...##.......#.....##... +......#.#....#................. +..............#.#.......#...... +.....#.#...##...#.#..#..#..#..# +.......##...#..#...........#... +.......#.##.#...#.#.........#.. +..#...##............##......#.# +.......#.......##......##.##.#. +...#...#........#....#........# +#............###.#......#.....# +..#........#....#..#..........# +..#..##....#......#..#......#.. +........#......#......#..#..#.. +..#...#....#..##.......#.#..... +.....#.#......#..#....#.##.#..# +......###.....#..#..........#.. +.#................#.#.......... +.........#..#...#......##...... +##...#....#...#.#...#.##..#.... +...##...#....#.........###..... +.#.#....#.........##........... +....#.#..#..#...........#...... +..#..#.#....#....#...#......... +..........##.....#.##.......... +..#.#....#..##......#.#.....##. +..#...#.##......#..........#... +......#....#..#.....#.....#...# +#.#...##.#.##.........#..#..... +...#.#.#.........#.....#.#.#... +..#.........#...............#.. +#..##.....#.........#....#..... +...#....##..##...........##..#. +......##.................#.#... +##.......#....#.#.#.....#...... +....#.#...#.................##. +#...#.........##.....#......... +#....#.###..#.....##.#....#.... +#..#....#...#....#.#.#......... +.......#...........#....#.....# +#...#.............#........#... +.......#.....#...#..#.........# +.##.....##.....##.......#...... +....##...##.......#..#.#.....#. +.##.........#......#........##. +.......#...#...###.#..#........ +..#..###......##..##........... +.#..#......##..#.#.........#... +...#.......#........#...#.#.... +...#....#..#....#.....##....... +............#......#..........# +.#.......#......#.#....#..#.#.. +##.........#.#.#..........#.... +....##.....#................... +.......#..#........#........... +....##.#..#......###.......#... +....#....#...#.#......#...#...# +.......#.....##..#....#...#.... +#...#........#.........#..##... +...........##.........#.#...#.. +....................#....#.##.. +.#..#..#.........#....#..#..##. +......................#........ +..###....#.......#.....###.##.. +......#......#.......#.....#..# +.....#...#.##...#......#....#.. +.....#.....##.............#.... +....#......##..#....#.......#.. +.##....#..##......###....#..#.. +...###.#.............##...#.#.. +.....#.....#.....#...#..#.#.... +..#.#.....###......#.......#... +..........#.##......#.........# +..##..#.......................# +........#......#............#.. +#..#..#..#.#......#..#....#.... +...##......#.............#....# +...........#..#..##.......#.... +.....#.........#.#..#.......... +##...#.......#.#....#..#..#.... +#.#.#...........#.##.#.#..###.. +#..#...........#.........##.... +............#.#..............#. +.#....#....##.#...........#..#. +....#...#..#...#....#....#..... +....#....#...#..#......#....... +.#.#.........#.......#.##...... +.#..##...#........#...........# +##...#..#...#...#.....#...#.... +....###.#..#.......##.#..#...#. +...##.......####...##.#........ +#....#....#.#............#..#.. +#.#.#...#...................##. +##......#...........#.......... +#..#..#....#.#...#......#...... +.##...#.....#...#........#..... +..#............#..............# +###........#..#....#...#......# +###..##......#.##...........#.. +........#......#..#.....#...... +...#..........#..#...........#. +....#..#..#....#........#....#. +.#.................#####..##..# +.....#...##..#..........#.##... +..#..............#...####...... +.....#.##..................#.#. +...#.#..#..#........#.......... +...........#....#.#..#......... +.....##.......#......#..#.#.#.. +...#.............##...#........ +...............#.......##.##.## +.....#........#........#.#..#.. +...#..#.........#...##...###... +...#.#.............###.#.....#. +.#..........#......###.#.#..... +....##..##.............###..... +..#..#.#...##...#.......##..... +..........###........#.....#.#. +#.#....#..#..#......#...#...#.. +.........#......##.......#.#..# +...#.....#.........##..#..#.... +.....##.#..##.##..##........... +...#.#.##....#..#..#......#..#. +#....#....#.............#...##. +#......#..#.####.#.##.#....##.. +##.#.#....##..................# +.....##......#.......##.......# +..#......#.#..#...##......##... +..#....##....#.........#..##... +.###.....#....##...........#... +.........#......#.#........#... +...#...#..#.#....######.#..#... +###......#.#.#.........##.#.... +.....#...#.........#...#....... +....#.............#.#.........# +..##...#...#.......#......#.... +.....#...#.#...#...#..#........ +.#......#...................... +...###..#..#....#...##.#....... +.#.#.....##...#...#.....#...##. +.....###..###....##............ +.....##....#..#.....#.##....... +#........#.........#...#..#.... +...#.#.........#..#.......#.#.. +....#.#....##.....#..........#. +.#..#....#..#.#..#..#.........# +#...#....#..............#...... +.........#.....#.##...##...###. +.....#....##............#..#... +.....#.#...........#..#....#... +.#..........#...#......#.....#. +.#...........#.....#..#........ +..............#......##...#..#. +...#.........#..#....#..##...## +..##...#..................#.... +#.....#.................#...... +...#......#..#..........#.#.... +......#..#.....#.....##...#..#. +......#........#..........#.... +...##.##....#..##.#..........#. +..........#..#.#.##............ +..##........................#.. +.....#.#.#......#....#....##... +#....#.........#........#...... +.##.......#...#...#........##.. +....##......#....#.#..........# +..#.......#..............#..... +.....#......#.#...#..#.#.#....# +.....#..#........#.##.##....... +##........#..........#......... +.....#..##....#.#......###..##. +#.#...##.........#.#.....#..#.. +#....#.#...#........#.....#..#. +........................#...... +....###......#............#...# +...#..##......#..##.........#.. +.............#...#......#..#..# +....#......#....#...........#.. +..#.#.####.#.....##........#..# +#..#...#..#..#.......#.#..#.... +..#..#..#....#.#.........##..#. +.......#......#.#............#. +...#.............#.#.....#..... +...#.#.........##...#.#.......# +........#...#...........##...#. +..........#....#......#....##.. +..........#...........#........ +...#..#...#..........#......#.. +......#......#....#.....#..#.#. +........##.................#..# +.#........#.#...........#...... +#...#........#.#.#.....#.#.#... +.........#........#..#..#....#. +##........#..........#....#..#. +.#.##...........#..#.#..##....# +.......#.#....#..#......#...... +..#.....#........##..#......### +..#...#..................#....# +......#...#..#.##.......#...... +........#...#.#................ +.........#............#........ +..#.....##....#.#..##.......... +#.....#..........#....#........ +....#.#...#...##....#.....##... +..#.#.......#.............#...# +...##..............#......#.... +#......#...#................##. +.#.#...#.#..#.................. +...##.......#...........#.#.#.. +#......#.#.#........#.##...#### +.......#..#.#.........#.#.##..# +..............#....#.........#. +...........#.#..#....##......#. +#.............#...##..#.......# +.........#............#...#.##. +.......#.........#.#.....#..#.. +........................#.#.##. +#......#.#......#.........#.... +...#.......#.......#.....#..... +#..#....#................#...#. +........#.#..##......#......... +#..#...##....##....##.........# +.......#...#...###............. +#.#..#........#.#.#............ +#.....#........##.........#.#.. +.#..........#....#.#....###.... +.#.....#...#.#........#..#.##.. +...#.##......#..#.............# +..##..#.#...................#.. +.....#....#...#.#...#...#...... +.....#..#.#....#.#............. +#.#....#.#.##..###..........#.. +........#.#.............#..#... +.........#.......#............. +.##.#............##...#........ +......#................#....... +...............#..#...........# +...#.......#...#.##.....#....#. +##..##..#..........#........... +.##.#.......#...#..#...#...#... +....#..#...........#....#.##... +.#........#........#....#...... +.......#...#.##.#..#.#..#...... +.#..#......#....#...##....#.#.. +......#...##.#.....##.###.....# +.#....#..#......#...#.#.....#.. +#............#....##...##.##... +#...#.#....#...#.......##...##. +#...........#.##..#....#.....#. +...#..#...#.........#.......#.. +.#....#.....#............#.#..# +.#.....#.#...#.#....##......### +..#..#.#.#...#..#.............# +...#...#..#....#........#...##. +.......#.....#...##...........# +#.##.................#...##...# +..............##........#.....# +............#...#..#.......#.#. +#.#.....#.........#...#......#. +#.###..#......#..#..#...#.....# +.....#.......#................. +........#..#......#.#...#...... +#.......#..#........#...#..#... +..#...#.......##.............#. +#.......#.......##...#......... +.........#....#.#..##.....#...# +..#.....#.#.......#....#....... +...#.......#.....#..##.#..#.... +....#.......#.#.#.............. +.#..#......#........#.#..##..## +....#...#.##.#...#....##...#... +#..##..#.....#.......#......... +....#..#..#.#............#..... +#.......##...##..##............ +............................... +....#.......#.##...#.....#.#... +...#........#....#.#..#..#..... +##.......#.....##.#.#....#....# +#.............#...........#.##. +#...........#.#..........#..... +#..#....#....#.#.........#.#... +......#.#.#..#.#.#............. +...#.....#........##....#...... +..#...#...#.#.......#......#... +.##........#...#..#..........#. +..#...........#..##.....##..... +............#..#.#...#.....#... +..........#....##.......#...... +....#....#.................#..# +....#...............#.........# +..#.#...#......#..........##... +.....#...........#.........#..# +.......#.....##.....#.#........ +.#.#..........#....#........... +.#..##....#........#....#...... +....#.#..#.......#..#.........# +..#....#.....#......#..#....... +......#........#.......#...#.#. +.......#.......#....#.....##... +....##........#..#...#.#..#...# +.#......#...........##....#.... +##....##......#.......#.......# +.##....#.##......#.......##..#. +...#..#.#.#.......#..#.###..... +..........##....#..#.##........ +...#........###.#..#........#.. +.....#....#..##....#.....#....# +#..........#..........#.#....#. +..#....#.....#..............#.. +#..................#......#.##. +.#...#.#.....#.........##...... +...#...........#.....#......#.. +......#.....#.#..##......##.... +...#....###..#.....#..#..##..## +......#.......##..#..#......... +#..#.#....#.#..#..........##.#. +..#..#..##..#.#.#.#.....#...... +..#.#...#..#.....###.#......... +##.#.#......#........#.####.... +.............#..#..#....#...... +...##..........#.......#.#....# +..#.....................#...... +..#..#...##...#.##........#.... |