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

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
}

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

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

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)

   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.

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

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

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

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

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)