UP / HOME

Day 03 - Toboggan Trajectory

Table of Contents

Puzzle

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?

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.

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

Part 2

For part 2 we calculate the number of trees for different sets of ($right, $down), multiply those numbers & print it.

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;

Other solution

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;

Andinus / / Modified: 2020-12-12 Sat 19:54 Emacs 27.1 (Org mode 9.4)