🌟 Advent of Code (AoC) 2021 🌟

internal class Puzzle12 : Puzzle<int>
{
    public class Cave
    {
        public string Name { get; }
        public bool IsSmall { get; }
        public bool CanEnterTwice { get; set; }
        public List<Cave> Connections { get; } = new();

        public Cave(string name, bool canEnterTwice = false)
        {
            Name = name;
            IsSmall = char.IsLower(name[0]);
            CanEnterTwice = canEnterTwice;
        }

        public int EnteredCount { get; set; }
    }

    protected override void Solve(string[] lines)
    {
        var caves = new Dictionary<string, Cave>();

        Cave GetOrCreateCave(string caveStr)
        {
            if (!caves.TryGetValue(caveStr, out var cave))
            {
                caves[caveStr] = cave = new Cave(caveStr);
            }
            return cave;
        }
            
        foreach (var line in lines)
        {
            var cavesStr = line.Split('-');
            var from = GetOrCreateCave(cavesStr[0]);
            var to = GetOrCreateCave(cavesStr[1]);
            from.Connections.Add(to);
            to.Connections.Add(from);
        }

        var pathsFound = new HashSet<string>();
        FindPaths(caves["start"], pathsFound);
        One = pathsFound.Count;

        pathsFound.Clear();

        foreach (var c in caves.Values
            .Where(c => c.IsSmall && c.Name is not ("end" or "start")))
        {
            foreach (var cave in caves.Values)
            {
                cave.EnteredCount = 0;
                cave.CanEnterTwice = false;
            }
            c.CanEnterTwice = true;
            FindPaths(caves["start"], pathsFound);
        }

        Two = pathsFound..Count;
    }

    private void FindPaths(Cave cave, HashSet<string> pathsFound,
        ISet<string>? visitedCaves = null, List<string>? currentPath = null)
    {
        visitedCaves ??= new HashSet<string>();
        currentPath ??= new() { "start" };

        if (cave.Name == "end")
        {
            pathsFound.Add(string.Join(",", currentPath));
            return;
        }

        cave.EnteredCount++;
        visitedCaves.Add(cave.Name);

        foreach (var con in cave.Connections)
        {
            if (!con.IsSmall || !visitedCaves.Contains(con.Name) || (con.CanEnterTwice && con.EnteredCount < 2))
            {
                currentPath.Add(con.Name);
                FindPaths(con, pathsFound, visitedCaves, currentPath);
                currentPath.RemoveAt(currentPath.FindLastIndex(x => x == con.Name));
            }
        }

        cave.EnteredCount--;
        visitedCaves.Remove(cave.Name);
    }
}

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day12.txt")))
      (let ((edges-list (unwrap! (parse edges-parser input)))
            (edges (apps |> edges-list
                         list/iter
                         (flat-map (fun ([a b]) (iter/cons [a b] (iter/once [b a]))))
                         (filter (apps <o not (str-eq "start") cadr))
                         (map (map-cadr array/singleton))
                         (map/collect-with str-cmp array/append)))))
      (display (array/show (show-two id (array/show id)) (array/collect (map/iter edges))))
      (display (str-append "Part 1: " (show-nat (count (paths-from edges False set/nil "start")))))
      (display (str-append "Part 2: " (show-nat (count (paths-from edges True set/nil "start")))))))

(define (paths-from edges double-dip? seen from)
  (define (continue double-dip?)
    (let1 seen (if (small? from) (set/insert str-cmp from seen) seen)
      (apps |> (map/lookup! str-cmp from edges)
            array/iter
            (flat-map (paths-from edges double-dip? seen))
            (map (list/cons from)))))
  (if (str-eq from "end")
      (iter/once (list/singleton "end"))
    (if (set/member? str-cmp from seen)
        (if double-dip?
            (continue False)
          iter/nil)
      (continue double-dip?))))

(define edges-parser
  (define pcave (parse/take-bytes-while1 alphabetic-byte?))
  (parse/sep-by1 parse/space1 (parse/lift2 cons' pcave (parse/thenr (parse/string "-") pcave))))

(define (small? s) (lowercase-byte? (string/nth-byte! (to-nat 0) s)))

use std::collections::{HashMap, HashSet};

fn main() {
    let input = std::fs::read_to_string("input.txt").unwrap();
    let data: Vec<_> = input.lines().filter_map(|s| s.split_once('-')).collect();

    let mut map: HashMap<_, HashSet<_>> = HashMap::new();
    for (begin, end) in data {
        map.entry(begin).or_default().insert(end);
        map.entry(end).or_default().insert(begin);
    }

    println!("Part 1: {}", paths(&map, HashSet::new(), "start", false)); // 3230
    println!("Part 2: {}", paths(&map, HashSet::new(), "start", true)); // 83475
}

fn paths<'a>(
    data: &HashMap<&str, HashSet<&'a str>>,
    mut visited: HashSet<&'a str>,
    id: &'a str,
    mut twice: bool,
) -> u32 {
    if id == "end" {
        return 1;
    }

    if is_small(id) {
        if visited.contains(id) {
            if twice && id != "start" {
                twice = false;
            } else {
                return 0;
            }
        } else {
            visited.insert(id);
        }
    }

    match data.get(id) {
        Some(ids) => ids
            .iter()
            .fold(0, |acc, v| acc + paths(data, visited.clone(), v, twice)),
        _ => 0,
    }
}

pub fn is_small(s: &str) -> bool {
    s.chars().all(char::is_lowercase)
}

struct cave
{
    bool big;
    int n_visits = 0;
    list<string> nb;
};

typedef map<string,cave> cave_map;

void add_cave(string cave_1, string cave_2, cave_map &caves)
{
    if (caves.count(cave_1) == 0)
    {
        cave new_cave;
        new_cave.big = any_of(cave_1.begin(), cave_1.end(), [](char c)
                              { return isupper(c); });
        new_cave.nb.push_back(cave_2);
        caves.insert(make_pair(cave_1, new_cave));
    }
    else
    {
        caves.at(cave_1).nb.push_back(cave_2);
    }
}

cave_map parse(vector<string> str_data)
{
    cave_map caves;

    string regex_str = "^(\\w+)-(\\w+)$";
    regex regex_obj(regex_str);
    smatch matches;

    int n_rows = str_data.size();
    for (int i = 0; i < n_rows; i++)
    {
        regex_search(str_data[i], matches, regex_obj);

        string cave_1 = matches.str(1);
        string cave_2 = matches.str(2);

        add_cave(cave_1, cave_2, caves);
        add_cave(cave_2, cave_1, caves); 
    }

    return caves;

}

int recursive_dfs(string start, cave_map &caves, bool allow_twice)
{
    int n_paths = 0;
    int n_caves = caves.size();
    list<string>::iterator list_it;
    cave_map::iterator cave_it;

    cave &ccave = caves.at(start);
    if (!ccave.big) ccave.n_visits++;
   
    if (ccave.n_visits==2) allow_twice = false;

    for (list_it = ccave.nb.begin(); list_it!= ccave.nb.end(); ++list_it)
    {
        if ((*list_it) == "start") ; //do nothing
        else if ((*list_it) == "end")
        {
            n_paths++;
            continue;
        }

        else if (allow_twice || caves.at(*list_it).n_visits <= 0)
        {
            n_paths += recursive_dfs(*list_it, caves, allow_twice);
        }
  
    }

    ccave.n_visits--;
    if (ccave.n_visits == 1) allow_twice = true;

    return n_paths;
}

int solve(cave_map caves, bool part_2)
{
    //using DFS

    int n_paths = recursive_dfs("start", caves, part_2);
    return n_paths;
}

val input = Using.resource(Source.fromFile("12.txt"))(_.getLines().toSet)
val caves = input.flatMap { case s"$u-$v" => Set(u -> v, v -> u) }.groupMap(_(0))(_(1))

def dfs(caves: Map[String, Set[String]], visitTwice: Boolean): Int =
   def recur(u: String, visited: Set[String], visitTwice: Boolean): Int =
      caves(u).foldLeft(0) { (count, v) =>
         if v == "end" then count + 1
         else if visited.contains(v) then
            if visitTwice && v.head.isLower && v != "start" then count + recur(v, visited, false)
            else count
         else count + recur(v, if v.head.isUpper then visited else visited + v, visitTwice)
      }
   recur("start", Set("start"), visitTwice)

dfs(caves, false) // part1
dfs(caves, true)  // part2

import * as fs from 'fs'

const readCaveSystem = () => {
  const nodes = { }
  fs
    .readFileSync('./src/day12/input.txt', 'utf-8')
    .split('\n')
    .filter(l => l)
    .map(l => l.split('-'))
    .forEach(edge => {
      const node1 = edge[0]
      const node2 = edge[1]
      nodes[node1] = nodes[node1] ? [node2, ...nodes[node1]] : [node2]
      nodes[node2] = nodes[node2] ? [node1, ...nodes[node2]] : [node1]
    })
  return nodes
}

const calcPaths = (nodes, calcSubPaths) => {
  const paths = []
  nodes.start.forEach(node => {
    const path = ['start', node]
    paths.push(...calcSubPaths(nodes, path))
  })
  return paths
}

const calcSubPathsVisitingSmallOnce = (nodes, path) => {
  const current = path[path.length - 1]
  return isNodeEnd(current)
    ? [path]
    : nodes[current]
      .flatMap(next =>
        isNodeLarge(next) || !isNodeInPath(path, next)
          ? calcSubPathsVisitingSmallOnce(nodes, [...path, next])
          : [null]
      )
      .filter(p => p !== null)
}

const calcSubPathsVisitingSmallTwiceOnce = (nodes, path) => {
  const current = path[path.length - 1]
  return isNodeEnd(current)
    ? [path]
    : nodes[current]
      .flatMap(next =>
        isNodeLarge(next) || !isNodeInPath(path, next) || (!isNodeStart(next) && !hasSmallTwice(path))
          ? calcSubPathsVisitingSmallTwiceOnce(nodes, [...path, next])
          : [null]
      )
      .filter(p => p !== null)
}

const hasSmallTwice = (path) =>
  path.some((n1, i1) =>
    !isNodeLarge(n1) && path.some((n2, i2) =>
      n1 === n2 && i1 !== i2
    )
  )

const isNodeStart = (node) =>
  node === 'start'

const isNodeEnd = (node) =>
  node === 'end'

const isNodeLarge = (node) => {
  const allCaps = /^[A-Z]*$/
  return node.match(allCaps) !== null
}

const isNodeInPath = (path, node) =>
  path.includes(node)

export const solvePart1 = () => {
  const nodes = readCaveSystem()
  const paths = calcPaths(nodes, calcSubPathsVisitingSmallOnce)
  return paths.length
}

export const solvePart2 = () => {
  const nodes = readCaveSystem()
  const paths = calcPaths(nodes, calcSubPathsVisitingSmallTwiceOnce)
  return paths.length
}

internal class Day12 : Puzzle
{
    public override object PartOne() => GetPathCount(new HashSet<Node>(), GetStartNode(), false);

    public override object PartTwo() => GetPathCount(new HashSet<Node>(), GetStartNode(), true);

    private static int GetPathCount(HashSet<Node> visitedLimitedNodes, Node node, bool allowVisitOneLimitedNodeTwice)
    {
        if (node.IsEnd) return 1;

        if (allowVisitOneLimitedNodeTwice && node.LimitedVisits && visitedLimitedNodes.Contains(node))
            allowVisitOneLimitedNodeTwice = false;

        if (node.LimitedVisits)
            visitedLimitedNodes = new HashSet<Node>(visitedLimitedNodes, visitedLimitedNodes.Comparer) { node };

        return node.ConnectedNodes
            .Where(x => !x.IsStart && 
                        (!x.LimitedVisits || allowVisitOneLimitedNodeTwice || !visitedLimitedNodes.Contains(x)))
            .Sum(x => GetPathCount(visitedLimitedNodes, x, allowVisitOneLimitedNodeTwice));
    }

    private Node GetStartNode()
    {
        var paths = Utilities.GetInput(GetType())
            .Split(Environment.NewLine)
            .Select(x => x.Split("-").ToArray())
            .Select(x => (Start: x[0], Destination: x[1]));

        var nodesDict = new Dictionary<string, Node>();

        foreach (var (start, destination) in paths)
        {
            nodesDict.TryAdd(start, new Node(start));
            nodesDict.TryAdd(destination, new Node(destination));

            var (startNode, destinationNode) = (nodesDict[start], nodesDict[destination]);

            startNode.ConnectedNodes.Add(destinationNode);
            destinationNode.ConnectedNodes.Add(startNode);
        }

        return nodesDict["start"];
    }

    private class Node
    {
        public readonly bool IsStart;
        public readonly bool IsEnd;
        public readonly bool LimitedVisits;

        public Node(string name)
        {
            ConnectedNodes = new List<Node>();
            IsStart = name == "start";
            IsEnd = name == "end";
            LimitedVisits = name == name.ToLower();
        }

        public IList<Node> ConnectedNodes { get; }
    }
}

object Day13 {
	val data = readLines("13/data.txt")
	val parts = data.splitBetween((_, s) => s.isEmpty)
	val dots = parts.head.map { case s"${int(x)},${int(y)}" => (x, y) } .toSet
	val folds = parts.last

	def flip(v: Int, axis: Int) = if(v > axis) axis * 2 - v else v

	def fold(dots: Set[(Int, Int)], instruction: String) = instruction match {
		case s"fold along x=${int(col)}" => dots.map { case (x, y) => (flip(x, col), y) }
		case s"fold along y=${int(row)}" => dots.map { case (x, y) => (x, flip(y, row)) }
	}

	def main(args: Array[String]): Unit = {
		// part 1
		println(fold(dots, folds.head).size)

		// part 2
		var tDots = dots
		folds.foreach { instruction =>
			tDots = fold(tDots, instruction)
		}

		val maxX = tDots.map(_._1).max
		val maxY = tDots.map(_._2).max
		for(y <- 0 to maxY) {
			val chars = Array.fill[Char](maxX + 1)(' ')
			tDots.filter(_._2 == y).map(_._1).foreach(x => chars(x) = '#')
			println(new String(chars))
		}
	}
}

internal class Puzzle13 : Puzzle<int, string>
{
    public record Instruction(int FoldAt, bool FoldUp);

    protected override void Solve(string[] lines)
    {
        var coords = lines
            .TakeWhile(x => !string.IsNullOrWhiteSpace(x))
            .Select(x => x.Split(',').Select(int.Parse).ToArray())
            .Select(c => (x: c[0], y: c[1]))
            .ToList();

        var grid = new bool[coords.Max(x => x.x) + 1, coords.Max(y => y.y) + 1];
        foreach (var (x, y) in coords)
        {
            grid[x, y] = true;
        }

        var instructions = lines[(coords.Count + 1)..]
            .Select(x => new Instruction(int.Parse(x[(x.IndexOf("=") + 1)..]), x.Contains('y')))
            .ToList();

        var newGrid = Fold(grid, instructions[0]);
        One = Grid.Iterate(newGrid).Count(x => newGrid[x.x, x.y]);

        var finalGrid = instructions.Aggregate(grid, (a, b) => Fold(a, b));
        var sb = new StringBuilder(Environment.NewLine);
        for (var y = 0; y < finalGrid.GetLength(1); y++)
        {
            for (var x = 0; x < finalGrid.GetLength(0); x++)
            {
                sb.Append(finalGrid[x, y] ? '#' : '.');
            }
            sb.AppendLine();
        }
        Two = sb.ToString();
    }

    private static bool[,] Fold(bool[,] grid, Instruction foldInstruction)
    {
        bool[,] newGrid;
        if (foldInstruction.FoldUp)
        {
            newGrid = new bool[grid.GetLength(0), grid.GetLength(1) / 2];
            foreach (var (x,y) in Grid.Iterate(grid).Where(c => grid[c.x, c.y]))
            {
                newGrid[x, y < foldInstruction.FoldAt ? y : (2 * foldInstruction.FoldAt - y)] = true;
            }
        }
        else
        {
            newGrid = new bool[grid.GetLength(0) / 2, grid.GetLength(1)];
            foreach (var (x, y) in Grid.Iterate(grid).Where(c => grid[c.x, c.y]))
            {
                newGrid[x < foldInstruction.FoldAt ? x : (2 * foldInstruction.FoldAt - x), y] = true;
            }
        }

        return newGrid;
    }
}

struct manual
{
    set<pair<int,int>> dots;
    vector<pair<bool,int>> folds;
    pair<int,int> grid_size;
    bool folded = false;
};

manual parse(vector<string> str_data)
{
    
    manual data;
    int n_rows = str_data.size();

    string regex_str = "^([0-9]+),([0-9]+)$";
    regex regex_obj(regex_str);
    smatch matches;
    int row = 0;
    while (!str_data[row].empty())
    {
        regex_search(str_data[row], matches, regex_obj);
        data.dots.insert(make_pair(stoi(matches.str(1)),stoi(matches.str(2))));

        row++;
    }

    regex_obj.assign("(\\w)=([0-9]+)$");
    bool fold_x;
    int fold_nr = 0;
    while (row < n_rows)
    {
        if (str_data[row].empty())
        {
            row++;
            continue;
        }

        regex_search(str_data[row], matches, regex_obj);
        fold_x = (matches.str(1)=="x")? 1:0;    
        data.folds.push_back(make_pair(fold_x,stoi(matches.str(2))));

        row++;
    }
    
    return data;

}

void draw(manual f_manual)
{
    set<pair<int,int>>::iterator it;
    vector<vector<char>> frame(f_manual.grid_size.second, vector<char>(f_manual.grid_size.first,'.'));

    for (it = f_manual.dots.begin(); it != f_manual.dots.end(); ++it)
    {
        frame[(*it).second][(*it).first] = '#';
    }
    
    for (int i = 0; i < f_manual.grid_size.second; i++)
    {
        for (int j = 0; j < f_manual.grid_size.first; j++)
        {
            cout << frame[i][j];
        }
        cout << endl;        
    }
    cout << endl;
}

int solve(manual &man, bool part2 = false)
{
    set<pair<int,int>> new_dots;;
    set<pair<int,int>>::iterator dot_it;
    int x, y, fold_val, n_dots;

    int n_folds = man.folds.size();

    for (int i = 0; i < n_folds; i++)
    {
        man.folded = true;
        fold_val = man.folds[i].second;

        new_dots.clear();
        for (dot_it = man.dots.begin(); dot_it != man.dots.end(); ++dot_it)
        {
            x = get<0>(*dot_it);
            y = get<1>(*dot_it);

            switch (man.folds[i].first)
            {
                case true:
                    x = (x > fold_val)? 2*fold_val-x : x;
                    man.grid_size.first = fold_val;
                break;
                case false:
                    y = (y > fold_val)? 2*fold_val-y : y;
                    man.grid_size.second = fold_val;
                break;
            }

            new_dots.insert(make_pair(x,y));

        }
        man.dots = new_dots;
        if (!part2) return new_dots.size();
    }

    draw(man);
    return 0;
}