DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 3: Toboggan Trajectory

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...
pic
Editor guide
Collapse
benwtrent profile image
Benjamin Trent • 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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
ballpointcarrot profile image
Christopher Kruse • 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)
}
Enter fullscreen mode Exit fullscreen mode

As always, also available on Github.


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

Collapse
bgaster profile image
Benedict Gaster • 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)
Enter fullscreen mode Exit fullscreen mode
Collapse
particleflux profile image
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)
}
Enter fullscreen mode Exit fullscreen mode
Collapse
neilgall profile image
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);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
ballpointcarrot profile image
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).

Collapse
neilgall profile image
Neil Gall

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

Thread Thread
ballpointcarrot profile image
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, ...

Collapse
galoisgirl profile image
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.
Enter fullscreen mode Exit fullscreen mode
Collapse
patryk profile image
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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Collapse
rpalo profile image
Ryan Palo Author

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

Collapse
maartenbetman profile image
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))
Enter fullscreen mode Exit fullscreen mode
Collapse
sleeplessbyte profile image
Derk-Jan Karrenbeld • 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
Enter fullscreen mode Exit fullscreen mode
Collapse
klnjmm profile image
Jimmy Klein

Hi,

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

Full size here : Advent Of Code - Day 3

Advent of Code - Day 3

Collapse
erikbackman profile image
Erik Bäckman

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)
             ]
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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};
}
Enter fullscreen mode Exit fullscreen mode
Collapse
anvsh profile image
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))
Enter fullscreen mode Exit fullscreen mode
Collapse
mellen profile image
Matt Ellen • 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.

Collapse
rpalo profile image
Ryan Palo Author

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

Collapse
mellen profile image
Matt Ellen

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 😁

Collapse
citizen428 profile image
Michael Kohl • Edited

Raku, first time I used classes. Alas, the Perl syntax highlighter seems to have some problems with this and Raku isn't a supported syntax type.

class Slope {
  has $.right;
  has $.down;

  method new($right, $down) { self.bless(right => $right, down => $down) }
}

class Map {
  has $.grid;
  has $.height;
  has $.width;

  method from-file($fname) {
    my @grid = $fname.IO.lines.map: *.comb;
    self.new: grid => @grid, height => @grid.elems, width => @grid.first.elems;
  }

  method is-tree($x; $y) { $!grid[$y][$x % $!width] ~~ '#' }

  method count-trees($slope, $start-x = 0, $start-y = 0) {
    sub count-trees-rec($prev-x = $start-x, $prev-y = $start-y, $count = 0) {
      my $y = $prev-y + $slope.down;
      return $count if $y > $!height;

      my $x = $prev-x + $slope.right;
      count-trees-rec($x, $y, self.is-tree($x, $y) ?? $count + 1 !! $count)
    }
    count-trees-rec();
  }
}

my $map = Map.from-file('aoc-map.txt');

# part 1
$map.count-trees(Slope.new(3, 1)).say;

# part 2
my @slopes = ((1, 1), (3, 1), (5, 1), (7, 1), (1, 2)).map({ Slope.new(|$_) });
say [*] @slopes.map({ $map.count-trees($_) });
Enter fullscreen mode Exit fullscreen mode
Collapse
aspittel profile image
Ali Spittel

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
clothierdroid profile image
David Clothier • Edited

SQL works for me ;)

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

Get this table naming 'day3':

table

3.1 Solution

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

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
Enter fullscreen mode Exit fullscreen mode
Collapse
justsax profile image
JustSaX • 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)

Enter fullscreen mode Exit fullscreen mode
Collapse
adamss profile image
Adam

Vanilla JS solution in 12 lines of code:

//create arr with input as template literal

let newArr= arr.split(/\r?\n/);//split by endlines
let xCord = 0;//X coordinates
let counter = 0;//trees hit counter
for(let i = 0 ; i < newArr.length ; i++){
let temp = newArr[i].split('');//split into array of characters
if(temp[xCord]=='#'){//checking for trees
counter++;//if there is a tree increment the counter
}
xCord = xCord +3;//add +3 to the right
if(xCord>=31){//check if there is more coords than elements in array
xCord = xCord-31;//reset coords
}}
console.log(counter);//result

Collapse
pzfrenchy profile image
Dan French

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
rabbiyos profile image
Rabbi Yosef Baruch Fromer

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

Collapse
pzfrenchy profile image
Dan French

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

Thread Thread
rabbiyos profile image
Rabbi Yosef Baruch Fromer

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

Collapse
harrygibson profile image
Harry Gibson

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}")
Enter fullscreen mode Exit fullscreen mode
Collapse
artyomovs profile image
artyomovs • 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)

Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author • 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.

Collapse
dirkfraanje profile image
Dirk Fraanje (the Netherlands) • 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();
    }


}
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My JavaScript walkthrough:

Collapse
njbrunner profile image
Nick Brunner

My python solution here

Collapse
njbrunner profile image
Nick Brunner

Unrelated to the challenges, how did you do the list of post links in your post?

Collapse
rpalo profile image
Ryan Palo Author

You can add a “series” to front matter on the post. As long as they all match, they’ll get linked up by initial release date.

Collapse
njbrunner profile image
Collapse
gzuidhof profile image
Guido Zuidhof

I wrote my solution in a notebook in Javascript:

starboard.gg/nb/nLjayUM