DEV Community

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

Ryan Palo on December 03, 2020

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

Read full post

Benjamin Trent • Dec 3 '20 • Edited

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 • Dec 3 '20 • Edited

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 • Dec 3 '20 • Edited

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 • Dec 3 '20

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 • Dec 3 '20

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 • Dec 4 '20

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

Christopher Kruse • Dec 4 '20

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 • Dec 3 '20

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 • Dec 3 '20

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 • Dec 3 '20

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 • Dec 3 '20

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 • Dec 4 '20 • Edited

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 • Dec 3 '20

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 • Dec 7 '20

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 • Dec 7 '20

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

Matt Ellen-Tsivintzeli • Dec 3 '20 • Edited

I put my solution in a gist. It's only for the second part, but I think it's easy enough to adjust it back for the first.

Ryan Palo • Dec 3 '20

That was quick! I'm just going to put that this one is in JavaScript for my future language-tallying self 😊 Thanks for sharing!

Matt Ellen-Tsivintzeli • Dec 3 '20

I'm always amazed by the main leader board. Some people seem to have solved the tasks in under five minutes. I can't even read it in that time 😁

Ali Spittel • Dec 4 '20

Mine!

import math

right_list = [1, 3, 5, 7, 1]
down_list = [1, 1, 1, 1, 2]

def get_trees_for_slope(right, down, lines):
    x = right
    y = down
    trees = 0
    while y < len(lines):
        if x > len(lines[y]) - 1:
            x = x % len(lines[y])
        if lines[y][x] == '#':
            trees += 1
        x += right
        y += down
    return trees


with open('input.txt') as inp:
    lines = [line for line in inp]
    height = len(lines)
    width = len(lines[0])
    lines = [list(line.rstrip()) for line in lines]

    print("Part 1", get_trees_for_slope(3, 1, lines))

    all_trees = 1
    for (right, down) in zip(right_list, down_list):
        all_trees *= get_trees_for_slope(right, down, lines)

    print("Part 2", all_trees)

Jimmy Klein • Dec 4 '20

Hi,

In PHP again, for fun, I try to have the minimum of temporary variables.

Full size here : Advent Of Code - Day 3

Erik Bäckman • Dec 10 '20

Haskell

import Control.Lens ((^?))
import Control.Lens.At (Ixed(ix))
import Data.Maybe (catMaybes, isJust)

matrixLookup :: [[a]] -> (Int, Int) -> Maybe a
matrixLookup m (x, y) = m ^? ix (abs y) . ix (abs x)

slope :: (Int, Int) -> [(Int, Int)]
slope (run, rise) = zip [0,run..] [0,rise..]

charsAlongSlope :: [String] -> (Int, Int) -> [Char]
charsAlongSlope grid (run, rise) = catMaybes
                                 $ takeWhile isJust
                                 $ matrixLookup grid <$> slope (run, rise)

parseInput :: String -> [String]
parseInput = fmap cycle . lines

solveForSlope :: String -> (Int, Int) -> Int
solveForSlope i s = length . filter (== '#') $ charsAlongSlope (parseInput i) s

solveP1 :: String -> Int
solveP1 inp = solveForSlope inp (3, -1)

solveP2 :: String -> Int
solveP2 inp = product (solveForSlope inp <$> slopes)
  where
    slopes = [ (1, -1)
             , (3, -1)
             , (5, -1)
             , (7, -1)
             , (1, -2)
             ]

Dan French • Dec 5 '20

Python effort, short and simple and gives the right answer.

treeCounter = 0
right = 5
down = 1
x = 0
y = 0

with open('day3.txt', 'r') as file:
    lines = file.read().splitlines()
    while y < len(lines):
        line = lines[y]
        for n in range(7):
            line = line + line
        if line[x] == "#":
            treeCounter += 1
        x = x + int(right)
        y = y + int(down)
    print(treeCounter)

Rabbi Yosef Baruch Fromer • Dec 20 '20

Hi,
Can you explain why "line = line + line" 7 times?
(Maybe i missed something in the question...)
10x :)

Dan French • Dec 20 '20

Hi Rabbi, you have a short string that repeats indefinitely. As you move right you quickly hit the end of the string. It was a very simple way to repeat the pattern otherwise you get an index out of range error when you exceed the original string length.
Its not very efficient as it repeats every line but it works in this instance. If you had to create longer strings you might want to refactor to check if you've hit end of string and only repeat then.
Dan

Rabbi Yosef Baruch Fromer • Dec 20 '20

Great! That helped me understand my mistake (Thous that end of line leads to the next line) :)

Harry Gibson • Dec 8 '20

Python implementation using numpy.

Spent ages trying to get this figured using array striding but eventually my head exploded and I resorted to using indices.

import numpy as np
from io import StringIO
import math

def count_trees(arr, steps_right, steps_down):
    n_rows, n_cols = arr.shape    
    n_down_steps = math.floor(n_rows / steps_down)
    across_positions = [(steps_right * n)  % n_cols 
                        for n in range(n_down_steps)]
    flat_array_positions = [
        (rownum * n_cols * steps_down) + across_positions[rownum] 
        for rownum in range(n_down_steps)]
    total_trees = arr.ravel()[flat_array_positions].sum()
    return total_trees

with open('input.txt', 'r') as f:
   data = f.read().replace('.', '0').replace('#', '1')
# using converters parameter to change #/. to 1/0 is a pain if 
# we don't know the number of columns. So string-replace them all first
trees_map = np.genfromtxt(StringIO(data), delimiter=1, dtype='uint8')

part_2_slopes = ((1,1), (3,1), (5,1), (7,1), (1,2))
part_1_slope = part_2_slopes[1]

print (f"Part 1: {count_trees(trees_map, *part_1_slope)} trees hit")

part_2_trees = [count_trees(trees_map, *s) for s in part_2_slopes]
part_2_res = np.prod(part_2_trees)
print (f"Part 2: Product of total trees hit is {part_2_res}")

Adam • Dec 16 '20

Vanilla JS solution in 12 lines of code:

//create arr with input as template literal

David Clothier • Dec 15 '20 • Edited

SQL works for me ;)

0 lines of code. No loops, no boolean flag, only SQL.

Get this table naming 'day3':

3.1 Solution

SELECT COUNT(*) 
FROM   (SELECT id, 
               REPEAT(line, 32) toboggan 
        FROM   day3 
        HAVING MID(toboggan, ( ( id * 3 ) - 2 ), 1) = '#') found_trees

3.2 Solution

SELECT ROUND(EXP(SUM(LN(x.a))),0) solution
FROM
(
SELECT COUNT(*) as a
FROM   (SELECT id, 
               REPEAT(line, 32) toboggan 
        FROM   day3 
        HAVING MID(toboggan, id, 1) = '#') found_trees 

UNION ALL
SELECT COUNT(*)
FROM   (SELECT id, 
               REPEAT(line, 32) toboggan 
        FROM   day3 
        HAVING MID(toboggan, ( ( id * 3 ) - 2 ), 1) = '#') found_trees
UNION ALL
SELECT COUNT(*)
FROM   (SELECT id, 
               REPEAT(line, 55) toboggan 
        FROM   day3 
        HAVING MID(toboggan, ( ( id * 5 ) - 4 ), 1) = '#') found_trees
UNION ALL
SELECT COUNT(*)
FROM   (SELECT id, 
               REPEAT(line, 75) toboggan 
        FROM   day3 
        HAVING MID(toboggan, ( ( id * 7 ) - 6), 1) = '#') found_trees
UNION ALL
SELECT COUNT(*)
FROM   (SELECT id, 
               REPEAT(line, 16) toboggan 
        FROM   day3 WHERE (id % 2) = 1
        HAVING MID(toboggan, ((id + 1) / 2), 1) = '#') found_trees
) AS x

Justin Hinckley • Apr 20 '21

Here's my beginner's Haskell solution:

ans1 :: [String] -> Int -> Int -> Int
ans1 inp right down = length $ filter (\(ind, row) -> ind `mod` down == 0 && row !! (ind `div` down * right `mod` length row) == '#') $ zip [0..] inp

ans2 :: [String] -> [(Int, Int)] -> Int
ans2 inp = product . map (uncurry (ans1 inp))

main :: IO ()
main = do
    contents <- readFile "adventofcode3.input"

    print $ ans1 (lines contents) 3 1
    print $ ans2 (lines contents) [(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)]

JustSaX • Dec 6 '20 • Edited

My solution in Python below for part 1. The hardest part for my was to figure out that the starting point is one further to the right then I expected...

file = open('d3-input.txt')
input_file = file.readlines()
input_file = [line.replace('\n','') for line in input_file]

right_counter = 3
count_trees = 0
for index, line in enumerate(input_file):
    if index > 0:
        if list(line)[right_counter] == '#':
            count_trees+=1
        right_counter+=3
        if right_counter >= len(line):
            right_counter = right_counter-len(line)
print(count_trees)

artyomovs • Dec 7 '20 • Edited

My ugly python version

from pprint import pprint

lines = list()

with open("input.txt", "r") as f:
    lines = [line.strip() for line in f.readlines()]

pprint(lines)

width = len(lines[0])
height = len(lines)

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

def get_next_spot(x, y, route):
    y = y + route[1]
    x = x + route[0]
    if x > width:
        x = x % width
    return x, y

x = 1 
y = 1

all_trees = 1


# print(lines[0])
for route in routes:
    trees = 0
    print('-------------')
    print(f"dx = {route[0]} dy = {route[1]}\n")
    y = route[1]
    x = 1
    j = 0
    lines_new = list(lines)
    for line in lines[1:]:
        s = line        
        if (j + 1) % (route[1]) == 0:    
            x, y = get_next_spot(x, y, route)
            s = line[:x - 1] + "O" + line[x:] 
            if line[x - 1] == "#":
                trees += 1
                s = line[:x - 1] + "X" + line[x:]                
        lines_new[j + 1] = s
        j = j + 1
    all_trees = all_trees * trees
    pprint(lines_new)    
    print(f"dx = {route[0]} dy = {route[1]} trees = {trees} all_trees = {all_trees}")


print(all_trees)

Ryan Palo • Dec 7 '20 • Edited

Hi! Thanks for sharing!

FYI, if you want to get some syntax highlighting in your comments, you can use three backtics followed by the language name to open and three backticks by themselves to close. Here's the Markdown cheat sheet for reference.

Dirk Fraanje (the Netherlands) • Dec 7 '20 • Edited

My solution in C#:

public static class Day3
{
    static int r;
    static int d;
    static string[] input = new string[] { //input };
    static Stopwatch timer = new Stopwatch();

    static int trees = 0;

    public static void Execute()
    {
        timer.Start();
        findNextLocationAndUpdateTreeCount();
    }

    private static void findNextLocationAndUpdateTreeCount()
    {
        var line = input[d];
        var positionOnLine = line.ToCharArray()[r];
        if (positionOnLine == '#')
            trees++;
        //For part 2 change r and d to the values you have to check
        r += 3;
        d += 1;
        if (input.Length <= d) {
            timer.Stop();
            Console.WriteLine($"Answer: {trees} trees");
            Console.WriteLine($"Executed in: {timer.ElapsedMilliseconds} milliseconds ({timer.ElapsedTicks}  Ticks)");
            Console.ReadLine();
        }
        if(line.Length <= r)
        {
            //By using r - line.Length you don't have to copy the whole input when you reached the end on the right (also possible to use Mod)
            r = r - line.Length;
        }
        findNextLocationAndUpdateTreeCount();
    }


}