Advent of Code 2020 Solution Megathread - Day 3: Toboggan Trajectory

We're on to Day 3 now! I'm seeing a bunch of cool languages getting submitted, which is really fun. Let's get to the puzzle!

The Puzzle

In today’s puzzle, we're trying to toboggan down a foresty slope to get to the coast for our trip. But trees aren't conducive to safe sledding, so we're checking our options carefully before starting. 2-D grids are a staple of Advent of Codeses past, and we've seen things dealing with rational slopes too. But it'll be interesting seeing how you decide to sled down these particular rational slopes. 😉

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 03:06PM 12/12/2020 PST.

Language	Count
Python	5
Ruby	3
Rust	3
JavaScript	2
Raku	1
COBOL	1
PHP	1
Elixir	1
C	1

Merry Coding!

Comments

[Benjamin Trent]

Rust again

enum Entry {
    Tree,
    Snow
}

impl From<&str> for Entry {
    fn from(s: &str) -> Self {
        match s { 
            "." => Entry::Snow,
            "#" => Entry::Tree,
            _ => panic!(format!("unexpected string {}", s))
        }
    }
}

#[aoc_generator(day3)]
fn input_to_vec(input: &str) -> Vec<Vec<Entry>> {
    input.lines().map(|i| {
        let splt = i.split("").filter(|s| !s.is_empty()).map(|s| Entry::from(s)).collect();
        splt
    }).collect()
}

fn tree_count_for_steps(input: &Vec<Vec<Entry>>, x: usize, y: usize) -> usize {
    let mut ct = 0;
    let mut right = 0;
    for r in 1..input.len() {
        if r % y > 0 {
            continue;
        }
        let row = &input[r];
        right += x;
        right %= row.len();
        if let Entry::Tree = row[right] {
            ct += 1;
        }
    }
    ct
}

#[aoc(day3, part1)]
fn tree_count(input: &Vec<Vec<Entry>>) -> usize {
    tree_count_for_steps(input, 3, 1)
}

#[aoc(day3, part2)]
fn tree_count_for_all_paths(input: &Vec<Vec<Entry>>) -> usize {
    let mut ct = 1;
    for (x, y) in vec![(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)].into_iter() {
        ct *= tree_count_for_steps(input, x, y);
    }
    ct
}

[Christopher Kruse]

Rustaceans gonna stick together 🦀:

use aoc_runner_derive::{aoc, aoc_generator};

#[aoc_generator(day3)]
fn parse_input_day3(input: &str) -> Vec<Vec<u8>> {
    input
        .lines()
        .map(|l| {
            l.chars()
                .map(|ch| match ch {
                    '.' => 0,
                    '#' => 1,
                    _ => panic!("Unexpected character!"),
                })
                .collect()
        })
        .collect()
}

#[aoc(day3, part1)]
fn toboggan_at_fixed_slope(input: &Vec<Vec<u8>>) -> usize {
    toboggan_at_slope(input, (3, 1))
}

fn toboggan_at_slope(input: &Vec<Vec<u8>>, slope: (usize, usize)) -> usize {
    let (slope_x, slope_y) = slope;
    let mut xpos = 0;
    let mut tree_count = 0;
    for row in input.iter().step_by(slope_y) {
        if *row.get(xpos % (row.len())).unwrap() == 1 {
            tree_count += 1;
        }
        xpos += slope_x;
    }
    tree_count
}

#[aoc(day3, part2)]
fn toboggan_at_other_slopes(input: &Vec<Vec<u8>>) -> usize {
    let slopes = vec![(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)];
    slopes
        .iter()
        .map(|s| toboggan_at_slope(input, *s))
        .fold(1, |memo, x| memo * x)
}

As always, also available on Github.

---

The enum implementation for your input is cool; I wouldn't have thought of that.

[Benedict Gaster]

First time I've done Advent of Code, but here is my Haskell soloution for Day 3:

trees right down xs = let line_length = length (head xs)
                      in length $ filter (== '#') $ 
                            zipWith (\input move -> input !! (move `mod` line_length))
                                    (downs down xs) [right,right+right..]
    where
        downs d xs = let ys = drop d xs in if null ys then [] else head ys : downs d ys

main = do xs <- readFile "day3_input" <&> lines
          let task1 = trees 3 1 xs
          let task2 = [  trees 1 1 xs, trees 3 1 xs,  trees 5 1 xs, 
                         trees 7 1 xs, trees 1 2 xs ]
          print task1 >> print (product task2)

[Neil Gall]

Rust using lots of iterators and generators. I'm trying to learn the standard library properly now.

use std::fs::File;
use std::io::prelude::*;

// --- model

#[derive(Debug)]
struct Model {
    width: usize,
    height: usize,
    bitmap: Vec<Vec<char>>
}

#[derive(Debug, Clone, Copy)]
struct Pos {
    x: usize,
    y: usize
}

#[derive(Debug, Clone, Copy)]
struct Offset {
    x: usize,
    y: usize
}

impl std::ops::Add<Offset> for Pos {
    type Output = Pos;

    fn add(self, offset: Offset) -> Self::Output {
        Pos { 
            x: self.x + offset.x,
            y: self.y + offset.y
        }
    }
}

impl Pos {
    fn slope(self, offset: Offset) -> impl Iterator<Item = Pos> {
        let mut pos = self;
        std::iter::from_fn(move || {
            let result = pos;
            pos = pos + offset;
            Some(result)
        })
    }
}

impl Model {
    fn tree_at(&self, p: &Pos) -> bool {
        self.bitmap[p.y % self.height][p.x % self.width] == '#'
    }

    fn count_trees_on_slope(&self, start: Pos, slope: Offset) -> usize {
        start.slope(slope)
            .take_while(|p| p.y < self.height)
            .filter(|p| self.tree_at(&p))
            .count()
    }
}

// --- input file

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

fn parse_input(input: &str) -> Model {
    let bitmap: Vec<Vec<char>> = input.lines().map(|line| line.trim().chars().collect()).collect();
    let min_length = bitmap.iter().map(|row| row.len()).min();
    let max_length = bitmap.iter().map(|row| row.len()).max();
    let length = bitmap.iter().next().map(|row| row.len());
    if length != min_length || length != max_length {
        panic!();
    }

    Model {
        width: length.unwrap(),
        height: bitmap.len(),
        bitmap
    }
}

// --- problems

fn part1(model: &Model) -> usize {
    model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 3, y: 1 })
}

fn part2(model: &Model) -> usize {
    let offsets = vec![
        Offset { x: 1, y: 1 },
        Offset { x: 3, y: 1 },
        Offset { x: 5, y: 1 },
        Offset { x: 7, y: 1 },
        Offset { x: 1, y: 2 }
    ];
    let start = Pos { x: 0, y: 0 };

    offsets.iter()
        .map(|offset| model.count_trees_on_slope(start, *offset))
        .product()
}

fn main() {
    let input = read_file("../input.txt").unwrap();
    let model = parse_input(&input);
    println!("part1 {}", part1(&model));
    println!("part2 {}", part2(&model));
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample_input() -> &'static str {
"..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#"
}

    #[test]
    fn test_parse_input() {
        let model = parse_input(sample_input());
        assert_eq!(model.width, 11);
        assert_eq!(model.height, 11);
        assert_eq!(model.bitmap[0][0], '.');
        assert_eq!(model.bitmap[8][7], '#');
    }

    #[test]
    fn test_count_trees_on_slope() {
        let model = parse_input(sample_input());
        assert_eq!(model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 1, y: 1 }), 2);
        assert_eq!(model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 3, y: 1 }), 7);
        assert_eq!(model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 5, y: 1 }), 3);
        assert_eq!(model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 7, y: 1 }), 4);
        assert_eq!(model.count_trees_on_slope(Pos { x: 0, y: 0 }, Offset { x: 1, y: 2 }), 2);
    }
}

[Christopher Kruse]

Nice! Didn't know about product(); will have to keep that in a pocket.

I like that your solution allows for an arbitrary starting point, rather than always just (0,0).

[Neil Gall]

One thing I've learned about AoC - try not to bake in any assumptions in part 1!

[Christopher Kruse]

Maybe this'll be our repeating problem (like the opcodes last year)... Different starting points, different types of obstacles in the snow, terrain to avoid, ...

[Stefan Linke]

A bit of Go

package main

import (
    "fmt"
)

const (
    SymbolTree  byte = '#'
    SymbolEmpty      = '.'
)

func checkPath(grid [][]byte, height, width int, path []int) int {
    numTrees := 0
    for x, y := 0, 0; y < height; {
        if grid[y][x] == SymbolTree {
            numTrees++
        }

        x = (x + path[0]) % width
        y += path[1]
    }

    return numTrees
}

func main() {
    grid := make([][]byte, 400)
    height := 0

    for {
        if _, err := fmt.Scanln(&grid[height]); err != nil {
            break
        }
        height++
    }

    width := len(grid[0])
    fmt.Println("part 1:", checkPath(grid, height, width, []int{3, 1}))

    part2 := checkPath(grid, height, width, []int{1, 1})
    part2 *= checkPath(grid, height, width, []int{3, 1})
    part2 *= checkPath(grid, height, width, []int{5, 1})
    part2 *= checkPath(grid, height, width, []int{7, 1})
    part2 *= checkPath(grid, height, width, []int{1, 2})
    fmt.Println("part 2:", part2)
}

[Patryk Woziński]

typical December in Europe

There is my solution, Elixir as always. I'll switch to Golang/PHP when I get stuck.

Day 3, part 1:

defmodule AdventOfCode.Day3Part1 do
  @position_move 3
  def calculate(file_path) do
    {_, trees} = file_path
    |> File.stream!()
    |> Stream.map(&String.replace(&1, "\n", ""))
    |> Enum.to_list()
    |> Enum.reduce({0, 0}, fn line, {position, trees} ->
      meet_tree = String.at(line, position) == "#"
      trees = if meet_tree, do: trees + 1, else: trees
      position = rem(position + @position_move, String.length(line))

      {position, trees}
    end)

    trees
  end
end

Day 3 part 2:

defmodule AdventOfCode.Day3Part2 do
  def calculate(file_path) do
    forest =
      file_path
      |> File.stream!()
      |> Stream.map(&String.replace(&1, "\n", ""))
      |> Enum.to_list()

      [{1, 1}, {1, 3}, {1, 5}, {1, 7}, {2, 1}]
      |> Enum.map(&(analyse_for_slope(forest, &1)))
      |> Enum.reduce(&(&1 * &2))
  end

  defp analyse_for_slope(forest, {move_down, move_right}) do
    {_, trees} =
      Enum.zip(0..Enum.count(forest), forest)
      |> Enum.filter(fn {line_number, _} -> rem(line_number, move_down) == 0 end)
      |> Enum.reduce({0, 0}, fn {_, line}, {position, trees} ->
        meet_tree = String.at(line, position) == "#"
        trees = if meet_tree, do: trees + 1, else: trees
        position = rem(position + move_right, String.length(line))

        {position, trees}
      end)

    trees
  end
end

What's your experience guys? Better to keep both parts in one class/module / whatever?

[Ryan Palo]

I typically keep them in the same file in different functions, since work from part 1 is often shared to part 2, (like today), but every so often, he throws a curveball and part 2 ends up being a total rethink, and then it may be nicer to have more separation. It probably doesn’t matter a ton :)

[Anna]

Still going strong with COBOL

   IDENTIFICATION DIVISION.
   PROGRAM-ID. AOC-2020-03-2.
   AUTHOR. ANNA KOSIERADZKA.

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
       SELECT INPUTFILE ASSIGN TO "d3.input"
       ORGANIZATION IS LINE SEQUENTIAL.

   DATA DIVISION.
   FILE SECTION.
     FD INPUTFILE.
     01 INPUTRECORD PIC X(31).
   WORKING-STORAGE SECTION.
     01 FILE-STATUS PIC 9 VALUE 0.
     01 WS-ARR-LEN PIC 9(3) VALUE 323.
     01 WS-ARRAY PIC X(31) OCCURS 1 to 500 DEPENDING ON WS-ARR-LEN.
     01 WS-TREES-PRODUCT PIC 9(20) VALUE 1.

   LOCAL-STORAGE SECTION.
     01 TREES UNSIGNED-INT VALUE 0.
     01 X UNSIGNED-INT VALUE 1.
     01 Y UNSIGNED-INT VALUE 1.
     01 DELTA-X UNSIGNED-INT VALUE 1.
     01 DELTA-Y UNSIGNED-INT VALUE 1.
     01 MAP-WIDTH  UNSIGNED-INT VALUE 31.

   PROCEDURE DIVISION.
   001-MAIN.
       OPEN INPUT INPUTFILE.
       PERFORM 002-READ UNTIL FILE-STATUS = 1.
       CLOSE INPUTFILE.
       PERFORM 004-PROCESS-DELTAS.
       DISPLAY WS-TREES-PRODUCT.
       STOP RUN.

   002-READ.
       READ INPUTFILE
           AT END MOVE 1 TO FILE-STATUS
           NOT AT END PERFORM 003-WRITE-TO-ARRAY
       END-READ.

   003-WRITE-TO-ARRAY.
       MOVE INPUTRECORD TO WS-ARRAY(X)
       ADD 1 to X.

   004-PROCESS-DELTAS.
       PERFORM 005-PROCESS-DELTAS-PAIR.
       MOVE 3 TO DELTA-Y.
       PERFORM 005-PROCESS-DELTAS-PAIR.
       MOVE 5 TO DELTA-Y.
       PERFORM 005-PROCESS-DELTAS-PAIR.
       MOVE 7 TO DELTA-Y.
       PERFORM 005-PROCESS-DELTAS-PAIR.
       MOVE 2 TO DELTA-X.
       MOVE 1 TO DELTA-Y.
       PERFORM 005-PROCESS-DELTAS-PAIR.

   005-PROCESS-DELTAS-PAIR.
       MOVE 1 TO X.
       MOVE 1 TO Y.
       MOVE 0 TO TREES.
       PERFORM 006-LOOP UNTIL X >= WS-ARR-LEN.
       COMPUTE WS-TREES-PRODUCT = WS-TREES-PRODUCT * TREES.

   006-LOOP.
       ADD DELTA-X TO X.
       ADD DELTA-Y TO Y.
       COMPUTE Y = FUNCTION MOD(Y, MAP-WIDTH).
       IF Y = 0 THEN 
           MOVE MAP-WIDTH TO Y
       END-IF.
       IF WS-ARRAY(X)(Y:1) = '#' THEN 
          ADD 1 TO TREES
       END-IF.

[Derk-Jan Karrenbeld]

Here is my Day 3 in Ruby

require 'benchmark'

class TreeGrid
  def self.from(file)
    rows = File.readlines(file)
    TreeGrid.new(rows)
  end

  def initialize(rows)
    self.rows = rows
    self.width = rows.first.scan(/[\.\#]/).length
  end

  def at(y, x)
    self.rows[y][x % width]
  end

  def tree?(y, x)
    at(y, x) == '#'
  end

  def each(&block)
    (0...self.rows.length).each(&block)
  end

  def height
    rows.length
  end

  private

  attr_accessor :width, :rows
end

grid = TreeGrid.from('input.txt')

def count_trees(grid, slope_x, slope_y)
  trees = 0
  x = 0
  y = 0

  while y < grid.height
    trees += 1 if grid.tree?(y, x)
    y += slope_y
    x += slope_x
  end

  trees
end

Benchmark.bmbm do |b|
  b.report do
    puts [
      count_trees(grid, 1, 1),
      count_trees(grid, 3, 1),
      count_trees(grid, 5, 1),
      count_trees(grid, 7, 1),
      count_trees(grid, 1, 2)
  ].inject(&:*)
  end
end

[Ryan Palo]

OK! Here's my solution. I wasn't sure how managing the 2D grid was going to go in C since I've historically struggled with them in Rust. But it went pretty easy and ran super fast, so I'm very happy with it :)

I had trouble for a minute because my code was skipping slots in my array because of the newline characters in the input. Once I stopped incrementing my index when I saw a newline, it shaped right up!

Day3.h:

/// Day 3: Taboggan Trajectory
/// 
/// Figure out how many trees you'll have to go past given a 2D grid/slope
/// covered in them.

#ifndef AOC2020_DAY3_H
#define AOC2020_DAY3_H


#include <stdlib.h>

/// All of the possible options for a terrain square in a TreeGrid.
/// OPEN has no trees in it.
/// TREE has a tree in it.
typedef enum {
  OPEN,
  TREE,
} TerrainType;

/// A 2D grid of terrain.
/// Knows how wide and tall it is.
/// Uses a 1D list of cells, and tricky math to index.
typedef struct {
  TerrainType* cells;
  size_t width;
  size_t height;
} TreeGrid;

/// 2D indexing into a TreeGrid
#define CELL(t, x, y) ((t)->cells[y*(t)->width + x])

/// Parse the input file, which is a 2D grid of '.' (free) and '#' (tree)
/// Return a pointer to a TreeGrid.
TreeGrid* parse(const char* filename);

/// Frees a TreeGrid.
void freeTreeGrid(TreeGrid* grid);

/// Part 1 calculates how many trees we'll hit with a slope of 3 right
/// and 1 down.
size_t part1(TreeGrid* grid);

/// Part 2 has us check a few different slopes for trees.  The result
/// is the product of all tree counts.
size_t part2(TreeGrid* grid);

/// Runs both parts and outputs the results.
int day3(void);
#endif

Day3.c:

#include "Day3.h"
#include "parsing.h"

#include <stdio.h>

TreeGrid* parse(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open input file.\n");
    exit(EXIT_FAILURE);
  }

  TreeGrid* grid = malloc(sizeof(TreeGrid));
  GridSize size = measure_grid(fp);
  grid->cells = malloc(sizeof(TerrainType) * size.width * size.height);

  char c;
  for (size_t i = 0; !feof(fp);) {
    switch (c = getc(fp)) {
    case '.':
      grid->cells[i] = OPEN;
      i++;
      break;
    case '#':
      grid->cells[i] = TREE;
      i++;
      break;
    case '\n':
    case EOF:
      // Just consume the newline
      break;
    default:
      printf("Unrecognized character on char (x=%zu, y=%zu): %c.\n",
      i % size.width,
      i / size.width,
      c);
      exit(EXIT_FAILURE);
    }
  }

  fclose(fp);
  grid->height = size.height;
  grid->width = size.width;
  return grid;
}

void freeTreeGrid(TreeGrid* grid) {
  free(grid->cells);
  grid->cells = NULL;
  free(grid);
}

/// Calculates how many trees you'll see on a linear trip down the hill.
/// If you go off the right end of the grid, wraps around infinitely wide.
static size_t calculateTrees(TreeGrid* grid, size_t xShift, size_t yDrop) {
  size_t trees = 0;
  for (size_t x = 0, y = 0; y < grid->height; y += yDrop, x = (x + xShift) % grid->width) {
    switch (CELL(grid, x, y)) {
    case TREE:
      trees++;
      break;
    case OPEN:
      break;
    }
  }
  return trees;
}

size_t part1(TreeGrid* grid) {
  return calculateTrees(grid, 3, 1);
}

size_t part2(TreeGrid* grid) {
  return calculateTrees(grid, 1, 1) *
         calculateTrees(grid, 3, 1) *
         calculateTrees(grid, 5, 1) *
         calculateTrees(grid, 7, 1) *
         calculateTrees(grid, 1, 2);
}

int day3() {
  TreeGrid* grid = parse("data/day3.txt");
  printf("====== Day 3 ======\n");
  printf("Part 1: %zu\n", part1(grid));
  printf("Part 2: %zu\n", part2(grid));

  freeTreeGrid(grid);
  return EXIT_SUCCESS;
}

Additional code to parsing.h:

// ...
/// The height and width of a 2D grid.
typedef struct {
  size_t width;
  size_t height;
} GridSize;

/// Takes in a file containing a 2D grid and returns its width/height.
GridSize measure_grid(FILE* fp);

Aaaand the implementation:

GridSize measure_grid(FILE* fp) {
  size_t lines = 0;
  size_t cols = 0;

  while (getc(fp) != '\n') cols++;
  lines++;
  while (!feof(fp)) {
    if (getc(fp) == '\n') lines++;
  }
  lines++; // Assume no newline after last line.

  rewind(fp);
  return (GridSize) {.width = cols, .height = lines};
}

[Anvesh Saxena]

Completed my day 3 with a little help from comments here

import sys

def slope_calc(data, right, down):
    tree = 0
    open_space = 0
    first = True
    position = right
    line_count = 0

    for line in data:
        if line != "":
            line_read = line.rstrip("\n")
            if first:
                first = False
            else:
                if line_count % down == 0:
                    if line_read[position] == ".":
                        open_space += 1
                    else:
                        if line_read[position] == "#":
                            tree += 1
                    position += right
                    if position > len(line_read)-1:
                        position = position-len(line_read)
        line_count += 1

    print("Tree = {}, Open = {}".format(tree, open_space))
    return tree

data = []
for line in sys.stdin:
    data.append(line.rstrip("\n"))

print(slope_calc(data,1,1) * slope_calc(data,3,1) * slope_calc(data,5,1) * slope_calc(data,7,1) * slope_calc(data,1,2))

[Maarten Betman]

Short Python solution

import math

with open("./data/Map.txt", 'r') as f:
    lines = f.read().splitlines() 

routes = ((1, 1), (3, 1), (5, 1), (7, 1), (1, 2))

total = []
for route in routes:
    c = 0
    for v in range(0, len(lines), route[1]):
        h = int(divmod((v / route[1]) * route[0], len(lines[v]))[1])
        value = lines[v][h]
        if value == "#":
            c += 1
    total.append(c)

print("Solution 1 =>", total[1])
print("Solution 2 =>", math.prod(total))