🌟 Advent of Code (AoC) 2021 🌟

from heapq import heapify, heappop, heappush

import numpy as np

REPEAT_COUNT = 5

p1_world = np.array([[int(c) for c in line.rstrip()] for line in open("15.in")])
p2_world = (
    np.tile(p1_world, (REPEAT_COUNT, REPEAT_COUNT))
    + np.repeat(np.arange(REPEAT_COUNT), len(p1_world))[:, None]
    + np.repeat(np.arange(REPEAT_COUNT), len(p1_world))[None, :]
)
p2_world[p2_world > 9] -= 9


def calc_risk(pos):
    return p2_world[pos[0]][pos[1]]


def generate_neighbours(world, i, j):
    HEIGHT, WIDTH = world.shape
    for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        if 0 <= (n_i := i + di) < HEIGHT and 0 <= (n_j := j + dj) < WIDTH:
            yield n_i, n_j


def find_bottom_right_risk(world):
    HEIGHT, WIDTH = world.shape
    goal = (HEIGHT - 1, WIDTH - 1)
    frontier = [(0, (0, 0))]
    heapify(frontier)
    seen = set([(0, 0)])
    while frontier:
        risk, pos = heappop(frontier)
        if pos == goal:
            return risk
        for n in generate_neighbours(world, *pos):
            if n not in seen:
                seen.add(n)
                heappush(frontier, (risk + calc_risk(n), n))
    raise NotImplementedError


print(find_bottom_right_risk(p1_world))
print(find_bottom_right_risk(p2_world))

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashMap},
    ops::Div,
};

type RiskLevel = HashMap<(usize, usize), usize>;
struct Chiton {
    map: RiskLevel,
    costs: RiskLevel,
    width: usize,
    height: usize,
}

impl Chiton {
    pub fn new(input: &str) -> Self {
        let mut map = HashMap::new();
        let mut costs = HashMap::new();
        let mut height = 0;
        let mut width = 0;

        for (y, line) in input.lines().enumerate() {
            for (x, c) in line.chars().enumerate() {
                map.insert((x, y), c.to_digit(10).unwrap() as usize);
                costs.insert((x, y), usize::MAX);
                height = y;
                width = x;
            }
        }
        Self {
            map,
            costs,
            width: width + 1,
            height: height + 1,
        }
    }

    pub fn solve_part1(&self) -> usize {
        self.solve(self.width, self.height, &self.map, self.costs.clone())
    }

    pub fn solve_part2(&self) -> usize {
        let mut new_map = HashMap::new();
        let mut costs = HashMap::new();
        for tile_y in 0..5 {
            for tile_x in 0..5 {
                for y in 0..self.height {
                    for x in 0..self.width {
                        let pos = (x + tile_x * self.width, y + tile_y * self.height);
                        let value = self.map[&(x, y)] + tile_x + tile_y;
                        new_map.insert(pos, value % 10 + value.div(10));
                        costs.insert(pos, usize::MAX);
                    }
                }
            }
        }
        self.solve(self.width * 5, self.height * 5, &new_map, costs)
    }

    fn solve(&self, width: usize, height: usize, map: &RiskLevel, mut costs: RiskLevel) -> usize {
        let mut visit = BinaryHeap::new();
        visit.push((Reverse(0), (0, 0)));

        while let Some(args) = visit.pop() {
            let (Reverse(cost), pos) = args;
            if cost < costs[&pos] {
                costs.insert(pos, cost);
                for p in self.adjacent(width, height, pos) {
                    visit.push((Reverse(cost + map[&p]), p));
                }
            }
        }
        costs[&(width - 1, height - 1)]
    }

    fn adjacent(&self, width: usize, height: usize, (x, y): (usize, usize)) -> Vec<(usize, usize)> {
        [(0, -1), (-1, 0), (1, 0), (0, 1)]
            .iter()
            .filter(|&(dx, dy)| {
                let x = x as i64;
                let y = y as i64;
                x + dx >= 0 && y + dy >= 0 && x + dx < width as i64 && y + dy < height as i64
            })
            .map(|&(dx, dy)| ((x as i64 + dx) as usize, (y as i64 + dy) as usize))
            .collect()
    }
}

fn main() {
    let input = std::fs::read_to_string("input.txt").unwrap();
    let chiton = Chiton::new(&input);
    println!("Part 1: {}", chiton.solve_part1()); // 720
    println!("Part 2: {}", chiton.solve_part2()); // 3025
}

internal class Puzzle16 : Puzzle<long>
{
    private int _versionSum;

    protected override void Solve(string[] lines)
    {
        var bitReader = new BitReader(string.Join(null, lines[0]
            .Select(c => Convert.ToString(Convert.ToInt32("" + c, 16), 2).PadLeft(4, '0'))));

        var result = ParsePacket(bitReader);

        One = _versionSum;
        Two = result;
    }

    private long ParsePacket(BitReader bitReader)
    {
        var version = bitReader.ReadNext(3);
        var type = bitReader.ReadNext(3);

        _versionSum += version;

        if (type == 4)
        {
            return GetPayloadForPacketType4(bitReader);
        }
            
        var packets = new List<long>();
        if (bitReader.ReadNext(1) == 0)
        {
            var length = bitReader.ReadNext(15);

            var prevIdx = bitReader.CurrentIdx;
            while ((bitReader.CurrentIdx - prevIdx) != length)
            {
                packets.Add(ParsePacket(bitReader));
            }
        }
        else
        {
            packets.AddRange(Enumerable.Range(0, bitReader.ReadNext(11))
                .Select(_ => ParsePacket(bitReader)));
        }

        return type switch
        {
            0 => packets.Sum(),
            1 => packets.Aggregate(1L, (a, b) => a * b),
            2 => packets.Min(),
            3 => packets.Max(),
            5 => packets[0] > packets[1] ? 1 : 0,
            6 => packets[0] < packets[1] ? 1 : 0,
            7 => packets[0] == packets[1] ? 1 : 0,
            _ => 0
        };
    }

    private static long GetPayloadForPacketType4(BitReader reader)
    {
        var groups = new List<long>();
        while (true)
        {
            var group = reader.ReadNext(5);
            groups.Add(group & 0xF);

            if ((group & 0x10) == 0)
            {
                break;
            }
        }

        groups.Reverse();

        long result = 0;
        for (int i = 0; i < groups.Count; i++)
        {
            result |= groups[i] << (i * 4);
        }

        return result;
    }

    private class BitReader
    {
        private readonly string _packet;
        public int CurrentIdx { get; private set; }
        public BitReader(string packet)
        {
            _packet = packet;
        }

        public int ReadNext(int bitSize) => Convert.ToInt32(_packet[CurrentIdx..(CurrentIdx += bitSize)], 2);
    }
}

internal class Puzzle17 : Puzzle<int>
{
    private ((int x, int y) from, (int x, int y) to) _targetArea;

    protected override void Solve(string[] lines)
    {
        var x = lines[0][(2 + lines[0].IndexOf("x="))..lines[0].IndexOf(",")].Split("..").Select(int.Parse).ToArray();
        var y = lines[0][(2 + lines[0].IndexOf("y="))..].Split("..").Select(int.Parse).ToArray();

        _targetArea = (
            (x[0], y[0]),
            (x[1], y[1])
        );

        var hits = 0;
        var topYShot = int.MinValue;
        foreach (var forward in Enumerable.Range(0, 300))
        {
            foreach (var upward in Enumerable.Range(-200, 400))
            {
                if (Shoot(forward, upward, out var topY))
                {
                    hits++;
                    topYShot = Math.Max(topYShot, topY);
                }
            }
        }

        One = topYShot;
        Two = hits;
    }

    private bool Shoot(int forward, int upward, out int topY)
    {
        topY = int.MinValue;
        var currentPosition = (x: 0, y: 0);

        while (true)
        {
            currentPosition.x += forward;
            currentPosition.y += upward;
            topY = Math.Max(topY, currentPosition.y);
            upward--;
            if (forward > 0)
            {
                forward -= 1;
            }
            else if (forward < 0)
            {
                forward += 1;
            }

            if (IsWithinTarget(currentPosition))
            {
                return true;
            }
            if (MissedTarget(currentPosition))
            {
                return false;
            }
        }
    }

    private bool IsWithinTarget((int x, int y) coord) => 
        _targetArea.from.x <= coord.x && _targetArea.to.x >= coord.x &&
            _targetArea.from.y <= coord.y && _targetArea.to.y >= coord.y;

    private bool MissedTarget((int x, int y) coord) => 
        coord.x > _targetArea.to.x || coord.y < _targetArea.from.y;
}

internal class Day17 : Puzzle
{
    public override object PartOne() =>
        GetTarget()
            .Pipe(Solve)
            .MaxHeight;

    public override object PartTwo() =>
        GetTarget()
            .Pipe(Solve)
            .Count;
    
    private static (int Count, int MaxHeight) Solve(Area target)
    {
        var count = 0;
        var maxVerticalVelocity = 0;
        var minHorizontalVelocity = CalculateMinHorizontalVelocity(target.X1);

        for (var vY = target.Y1; vY <= -target.Y1 - 1; vY++) 
        for (var vX = minHorizontalVelocity; vX <= target.X2; vX++)
        for (var t = 0; t < int.MaxValue; t++)
        {
            var verticalPosition = CalculatePosition(vY, t);
            var horizontalPosition = CalculateHorizontalPosition(vX, t);

            if (verticalPosition.IsBetween(target.Y1, target.Y2) && horizontalPosition.IsBetween(target.X1, target.X2))
            {
                maxVerticalVelocity = vY;
                count += 1;
                break;
            }

            if (verticalPosition < target.Y1)
                break;
        }

        return (count, CalculateMaxPosition(maxVerticalVelocity));
    }

    private static int CalculateMaxPosition(int v) => v * (v + 1) / 2;
    private static int CalculatePosition(int v, int t) => (t + 1) * (2 * v - t) / 2;
    private static int CalculateHorizontalPosition(int v, int t) => t >= v ? CalculateMaxPosition(v) : CalculatePosition(v, t);
    private static int CalculateMinHorizontalVelocity(int pos) => (int)Math.Ceiling((Math.Sqrt(8 * pos + 1) - 1) / 2);

    private Area GetTarget()
    {
        var values = Utilities.GetInput(GetType())
            .Pipe(x => Regex.Matches(x, @-?\d+)
                .Select(y => int.Parse(y.Value))).ToArray();

        return new Area(values[0], values[1], values[2], values[3]);
    }

    private record Area(int X1, int X2, int Y1, int Y2);
}

int solve_part1(area t)
{
    int v0_ymax = abs(t.ymin)-1;  //the maximum y velocity still hitting y_min
    int y_max = v0_ymax * (v0_ymax+1)/2; //integrate to velocity zero (arithmetic series sum)

    return y_max;

}

int solve_part2(area t)
{

    int v0x_min = int( -.5+sqrt((2.0d*double(t.xmin)+0.25d)));
    int v0x_max = t.xmax;
    int v0y_min = t.ymin;
    int v0y_max = abs(t.ymin) -1 ;

    int x,y,vx,vy,i;

    int n = 0;
    for (int v0x = v0x_min; v0x <= v0x_max; v0x++)
    {
        for (int v0y = v0y_min; v0y <= v0y_max; v0y++)
        {
            vy = v0y;
            vx = v0x;
            
            x = y = 0;
            while (true)
            {
                x += (vx > 0) * vx;
                y += vy;
                if (x > t.xmax || y < t.ymin)
                {
                    //this is a miss
                    break;
                }
                else if (x >= t.xmin && x <= t.xmax)           
                {
                    if (y >= t.ymin && y <= t.ymax)
                    {
                        n++;
                        break;
                    }
                }
                vx--;
                vy--;
            }
        }
    }

    return n;
}

#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#include "../utils/file_reader.cpp"
#include "../utils/result_printer.cpp"

typedef pair<int,int> coord;
typedef pair<coord,int> point;
typedef map<coord,int> grid;

struct risk_map_struct
{
    int x_size;
    int y_size;
    grid risk_level;
};

vector<coord> get_neighbours()
{
    vector<coord> neighbours = {{1,0},{0,1},{0,-1},{-1,0}};
    return neighbours;
}

risk_map_struct parse(vector<string> str_data)
{
    risk_map_struct risk_map;
    grid risk_level;

    int n_rows = str_data.size();
    int n_cols = str_data[0].size();
    for (int i = 0; i < n_rows; i++)
    {
        string str_row = str_data[i];
        for (int j = 0; j < n_cols; j++)
        {
            risk_level.insert(make_pair(make_pair(i,j),int(str_row[j]-48)));
        }
        
    }

    risk_map.risk_level = risk_level;
    risk_map.x_size = n_cols;
    risk_map.y_size = n_rows;

    return risk_map;

}

risk_map_struct expand_grid(risk_map_struct risk_map)
{
    risk_map_struct expanded_map;
    expanded_map.x_size = risk_map.x_size*5;
    expanded_map.y_size = risk_map.y_size*5;
    grid exp_risk_level;
    vector<vector<int>> test;

    for (int i = 0; i < expanded_map.y_size; i++)
    {   
        vector<int> str_row;
        for (int j = 0; j < expanded_map.x_size; j++)
        {
            
            int col = j%risk_map.x_size;
            int row = i%risk_map.y_size;

            coord coord_ = make_pair(row, col);
            int val = (risk_map.risk_level.at(coord_));
            int add = i/risk_map.y_size + j/risk_map.x_size;
            int new_val = val + add;

            while (new_val > 9)
            {
                new_val-=9;
            }

            exp_risk_level.insert(make_pair(make_pair(i,j), new_val));
            
        }
        test.push_back(str_row);
    }

    expanded_map.risk_level = exp_risk_level;    
    
    return expanded_map;
}

int solve(risk_map_struct risk_map, bool part2)
{
    if (part2) risk_map = expand_grid(risk_map);
    vector<coord> nbs = get_neighbours();

    point source;
    map<coord,coord> prevs;

    coord start = make_pair(0,0);
    coord target = make_pair(risk_map.x_size-1 ,risk_map.y_size-1);
    grid risk(risk_map.risk_level);


    auto cmp = [](const point &a, const point &b) {
        return a.second > b.second;
    };  
    priority_queue< point, vector<point>, decltype(cmp)> queue(cmp);
        
    for (auto const& [key, val] : risk_map.risk_level)
    {
        risk.at(key) = INT_MAX;  
    }
    risk.at(start) = 0;


    source = make_pair(start,0);
    queue.push(source);
    while(queue.size()>0)
    {
        //cout << queue.size() << endl;;
        source = queue.top();
        queue.pop();
        
        for (auto &nb:nbs)
        {
            coord u = make_pair(source.first.first+nb.first, source.first.second+nb.second);
            
            if (!risk.count(u)) continue;
            int new_risk = source.second + risk_map.risk_level.at(u);
            if (new_risk < risk.at(u))
            {
                risk.at(u) = new_risk;
                queue.push(make_pair(u,new_risk));
                prevs.insert(make_pair(u,source.first));
            }
        }
    }

    return risk.at(target);   

}

use std::{iter, str::FromStr};

#[derive(Debug, Default, Clone, Copy)]
pub struct Point(i64, i64);

#[derive(Debug, Default, Clone, Copy)]
pub struct Area {
    start: Point,
    end: Point,
}

#[derive(Debug, Default, Clone, Copy)]
pub struct Probe {
    pos: Point,
    velocity: Point,
    area: Area,
}

impl FromStr for Area {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let r: Vec<_> = s
            .split(",")
            .flat_map(|s| s.split(".."))
            .map(|s| {
                s.chars()
                    .filter(|&c| matches!(c, '0'..='9' | '-'))
                    .collect::<String>()
            })
            .filter_map(|s| s.parse::<i64>().ok())
            .collect();

        Ok(Self {
            start: Point(r[0], r[2]),
            end: Point(r[1], r[3]),
        })
    }
}

impl Area {
    pub fn check(&self, point: Point) -> bool {
        let min_x = self.start.0.min(self.end.0);
        let max_x = self.start.0.max(self.end.0);
        let min_y = self.start.1.min(self.end.1);
        let max_y = self.start.1.max(self.end.1);
        min_x <= point.0 && max_x >= point.0 && min_y <= point.1 && max_y >= point.1
    }

    pub fn range(&self) -> impl Iterator<Item = (i64, i64)> {
        let max_x = self.start.0.max(self.end.0);
        let min_y = self.start.1.min(self.end.1);
        (1..=max_x).flat_map(move |r| iter::repeat(r).zip(min_y..=min_y.abs()))
    }
}

impl Probe {
    pub fn new(area: Area, velocity: Point) -> Self {
        Self {
            pos: Default::default(),
            velocity,
            area,
        }
    }

    pub fn step(&mut self) {
        self.pos.0 += self.velocity.0;
        self.pos.1 += self.velocity.1;
        self.velocity.0 -= self.velocity.0.signum();
        self.velocity.1 -= 1;
    }

    pub fn within_target(&self) -> bool {
        self.area.check(self.pos)
    }

    pub fn bounds_check(&self) -> bool {
        let max_x = self.area.start.0.max(self.area.end.0);
        let min_y = self.area.start.1.min(self.area.end.1);
        max_x < self.pos.0 || min_y > self.pos.1
    }

    pub fn simulate(&mut self) -> Option<i64> {
        let mut max = 0;
        while !self.bounds_check() {
            max = self.pos.1.max(max);
            self.step();
            if self.within_target() {
                return Some(max);
            }
        }
        None
    }
}

pub fn solve(area: Area, mut func: impl FnMut(i64) -> bool) {
    for (x, y) in area.range() {
        if let Some(value) = Probe::new(area, Point(x, y)).simulate() {
            if !func(value) {
                return;
            }
        }
    }
}

fn main() {
    let area = std::fs::read_to_string("input.txt")
        .unwrap()
        .lines()
        .filter_map(|s| s.parse::<Area>().ok())
        .next()
        .unwrap();

    let mut max = 0;
    solve(area, |value| {
        max = max.max(value);
        if max > value {
            return false;
        }
        true
    });
    println!("Part 1: {}", max); // 2850

    let mut count = 0;
    solve(area, |_| {
        count += 1;
        true
    });
    println!("Part 2: {}", count); // 1117
}