Day 03 - Toboggan Trajectory

• 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:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

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:

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

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:

..##.........##.........##.........##.........##.........##.......  --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

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?

count-trees is a subroutine that will count the number of trees we'll encounter, it needs @input, $right, $down.

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;
}

$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.

say "Part 1: ", count-trees(@input, 3, 1);

I found this solution by cggoebel on reddit. It makes use of infinite lazy lists, that way you don't have to check for boundary. I'll paste the solution here.

No license was attached to the code in that post. This belongs to u/cggoebel.

use v6.d;

my @input = 'input'.IO.lines;
my @map;

for @input -> $line {
    @map.push(($line.comb xx *).flat);
}

sub detect_collisions (Int $sx, Int $sy) {
    my $rval = 0;
    loop (my ($x,$y)=($sx,$sy); $y < @map.elems; $x+=$sx, $y+=$sy) {
        $rval++ if @map[$y][$x] eq '#';
    }
    return $rval
}

say "Part One: {detect_collisions(3,1)}";

my @collision;
for 1,1, 3,1, 5,1, 7,1, 1,2 -> $x, $y {
    @collision.push(detect_collisions($x, $y));
}

say "Part Two: " ~ [*] @collision;