🌟 Advent of Code (AoC) 2021 🌟

import Data.List
main = interact solve

solve input = solution drawing boards ++ "\n"
    where
        drawing = parseDraw ((head.lines) input) :: [Int]
        boards = (parseBoards.tail.lines) input :: [[Int]]

parseDraw line
    | elem ',' line = read draw:parseDraw (tail rest)
    | otherwise = read line:[]
    where (draw, rest) = break (\c -> c==',') line

parseBoards (_:a:b:c:d:e:bs) = [(map read (words a ++ words b ++ words c ++ words d ++ words e))] ++ parseBoards bs
parseBoards _ = []

solution drawing boards = "Quickest board has score " ++ show (chooseBoard drawing boards minimum)
                     ++ "\nSlowest board has score " ++ show (chooseBoard drawing boards maximum)

chooseBoard drawing boards strategy = sum remainingNumbers * last drawnNumbers
    where
        drawnNumbers = take (chosenFinishTurn+1) drawing
        remainingNumbers = boards !! (chosenBoard-1) \\ drawnNumbers
        chosenBoard = 1 + elemIndex' chosenFinishTurn finishTurnByBoard
        chosenFinishTurn = strategy finishTurnByBoard
        finishTurnByBoard = map finishTurn boards
        finishTurn board = minimum (map finishTurnRow (boardRows board))
        finishTurnRow row = maximum (remapToDrawOrder drawing row)
        boardRows board = map (map ((!!) board)) rowIndices
            where rowIndices = [[0..4], [5..9], [10..14], [15..19], [20..24], [0,5..20], [1,6..21], [2,7..22], [3,8..23], [4,9..24]]
        remapToDrawOrder drawing row = map drawOrder row
            where drawOrder n = elemIndex' n drawing

elemIndex' i xs = case elemIndex i xs of
    Just x -> x
    Nothing -> 999

#include <iostream>
#include <sstream>

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

using namespace std;

const int N = 5;

struct board
{
    int nums[N][N];
    int checks[N][N] = {0};
    int row_checks[5] = {0};
    int col_checks[5]  = {0};
    int unchecked_total = 0;
    bool winner = false;
};

vector<int> get_nums(string data, char delim)
{
    vector<int> output;
    string str;
    int num;

    stringstream sstream(data);
    while (getline(sstream, str, delim))
    {
        if (!str.empty())
        {
            stringstream s(str);
            s >> num;
            output.push_back(num);
        }
    }

    return output;

}

vector<board> get_boards(vector<string> data)
{
    vector<board> boards;
    board new_board;
    string line;

    int row = 0;
    int n_rows = data.size();
    while (row < n_rows)
    {
        line = data[row];
        //empty line signals new board
        if (line.empty())
        {
            for (int i = 0; i < N; i ++)
            {
                row +=1;
                line = data[row];
                vector<int> nums = get_nums(line,' ');
                for (int j = 0; j < N; j++)
                {
                    new_board.nums[i][j] = nums[j];
                }
            }
            boards.push_back(new_board);
        } 
        row +=1;
    }

    return boards;

}

void play_bingo(vector<board> boards, vector<int> nums, board &winner_board, int &winner_num, bool return_first)
{
    
    for (auto num:nums)
    {
        int n = boards.size();
        
        for (auto &brd : boards)
        {
            if (brd.winner)
            {
                continue;
            }

            brd.unchecked_total = 0;

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (brd.nums[i][j] == num)
                    {
                        brd.checks[i][j] = 1;
                        brd.row_checks[i] += 1;
                        brd.col_checks[j] += 1;                 
                    }

                    if (brd.checks[i][j] == 0)
                    {
                        brd.unchecked_total += brd.nums[i][j];
                    }

                    if ((brd.row_checks[i] == N || brd.col_checks[j] == N) && (!brd.winner))
                    {
                        brd.winner = true;
                    }
                }
            }
            if (brd.winner)
            {
                winner_board = brd;
                winner_num = num;
                if (return_first)
                {
                    return;
                } 
            }
        }
    }

    return;
}

int solve(vector<string> data, bool stop_at_first)
{
    vector<int> nums = get_nums(data[0], ',');
    vector<board> boards = get_boards(data);

    int winner_num;
    board winner_board;
    play_bingo(boards, nums, winner_board, winner_num,stop_at_first);

    return winner_board.unchecked_total * winner_num;

}

int main()
{

    string filename = "../../input/day_04.txt";
    vector<string> data = read_file<string>(filename,false);
    
    int part_1 = solve(data,true);
    int part_2 = solve(data,false);

    cout << "Day 4 Part 1 solution: " << part_1 << endl;
    cout << "Day 4 Part 2 solution: " << part_2 << endl;

    return 0;
}

val input = Using.resource(Source.fromFile("4.txt"))(_.getLines().toVector)

class Board(rows: Vector[Vector[Int]], cols: Vector[Vector[Int]]):
   def mark(num: Int): Board = Board(rows.map(_.filter(_ != num)), cols.map(_.filter(_ != num)))
   def checkBingo: Boolean   = rows.exists(_.isEmpty) || cols.exists(_.isEmpty)
   def score: Int            = rows.flatten.sum

val nums = input.head.split(",").map(_.toInt)
val boards = input.tail
   .filter(_.nonEmpty)
   .grouped(5)
   .map(_.map(_.trim.split("""\D+""").map(_.toInt).toVector))
   .map(xss => Board(xss, xss.transpose))
   .toVector

val scores = nums
   .foldLeft((boards, Vector.empty[Int])) { case ((boards, score), num) =>
      val (finished, active) = boards.map(_.mark(num)).partition(_.checkBingo)
      (active, score ++ finished.map(_.score * num))
   }
   ._2

scores.head // part1
scores.last // part2

import re
from collections import defaultdict
from itertools import zip_longest

pos_count = defaultdict(int)
for line in open("5.in"):
    x1, y1, x2, y2 = map(int, re.split("\D+", line.rstrip()))

    xd = 1 if x2 > x1 else -1
    yd = 1 if y2 > y1 else -1
    for x, y in zip_longest(range(x1, x2 + xd, xd), range(y1, y2 + yd, yd), fillvalue=y1 if y1 == y2 else x1):
        pos_count[(x, y)] += 1

print(sum(1 for v in pos_count.values() if v >= 2))

import std/[strutils, strscans, sequtils, tables]

proc parseLines(s: seq[string]): seq[(int, int, int, int)] =
  for line in s:
    let (success, x1, y1, x2, y2) = scanTuple(line, "$i,$i -> $i,$i")
    doAssert success, "Failed to parse: " & line
    result.add (x1, y1, x2, y2)

proc part1(lines: seq[(int, int, int, int)]): int =
  var counts = initCountTable[(int, int)]()
  for (x1, y1, x2, y2) in lines:
    if x1 == x2 or y1 == y2:
      for i in min(x1, x2) .. max(x1, x2):
        for j in min(y1, y2) .. max(y1, y2):
          counts.inc (i, j)
  result = len(counts.values.toSeq.filterIt(it >= 2))

proc part2(lines: seq[(int, int, int, int)]): int =
  var counts = initCountTable[(int, int)]()
  for (x1, y1, x2, y2) in lines:
    if x1 == x2 or y1 == y2:
      for i in min(x1, x2) .. max(x1, x2):
        for j in min(y1, y2) .. max(y1, y2):
          counts.inc (i, j)
    elif x1 <= x2 and y1 <= y2:
      for (i, j) in zip(countup(x1, x2).toSeq, countup(y1, y2).toSeq):
        counts.inc (i, j)
    elif x1 > x2 and y1 <= y2:
      for (i, j) in zip(countdown(x1, x2).toSeq, countup(y1, y2).toSeq):
        counts.inc (i, j)
    elif x1 > x2 and y1 > y2:
      for (i, j) in zip(countdown(x1, x2).toSeq, countdown(y1, y2).toSeq):
        counts.inc (i, j)
    elif x1 <= x2 and y1 > y2:
      for (i, j) in zip(countup(x1, x2).toSeq, countdown(y1, y2).toSeq):
        counts.inc (i, j)
        
  result = len(counts.values.toSeq.filterIt(it >= 2))



let input = "input.txt".lines.toSeq.parseLines
echo "Part 1: ", part1(input)
echo "Part 2: ", part2(input)

object Day5 {
	val data = readLines("5/data.txt")

	case class Coord(x: Int, y: Int)
	case class Line(x1: Int, y1: Int, x2: Int, y2: Int) {
		val length = max(abs(x2 - x1), abs(y2 - y1))
		val coords = (0 to length).map(i => Coord(x1 + (x2 - x1) * i / length, y1 + (y2 - y1) * i / length))
		def horizOrVert = x1 == x2 || y1 == y2
	}

	val lines = data.map { case s"${int(x1)},${int(y1)} -> ${int(x2)},${int(y2)}" => Line(x1, y1, x2, y2) }

	def main(args: Array[String]): Unit = {
		def countDangers(lines: Seq[Line]) = {
			val allZeroMap = Map.empty[Coord, Int].withDefaultValue(0)
			val cellCount = lines.foldLeft(allZeroMap) { case (map, line) =>
				map ++ line.coords.map(c => (c, map(c) + 1)).toMap
			}
			cellCount.values.count(_ > 1)
		}

		// part 1
		println(countDangers(lines.filter(_.horizOrVert)))

		// part 2
		println(countDangers(lines))
	}
}

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"strconv"
	"strings"
)

type Bingo struct {
	Balls     []int
	Boards    []Board
	BoardSize int
}

type Board struct {
	BingoFound     bool
	Rows           []uint
	NumberPosition map[int]Position
	PositionNumber map[string]int
}
type Position struct {
	X int
	Y int
}

type Result struct {
	Sum     int
	Ball    int
	Product int
}

func findBingoScores(bingo Bingo) []Result {
	var results []Result
	for _, ball := range bingo.Balls {
		if len(results) == len(bingo.Boards) {
			break
		}
		for j, board := range bingo.Boards {
			if board.BingoFound {
				continue
			}
			pos, ok := board.NumberPosition[ball]
			if !ok {
				continue
			}
			board.Rows[pos.Y] = setBit(board.Rows[pos.Y], reversePosX(bingo.BoardSize, pos.X))
			if isBingoHorizontal(bingo, board, pos) ||
				isBingoVertical(bingo, board, pos) {
				sum := findUnmarked(board, bingo.BoardSize)
				score := sum * ball
				results = append(results, Result{
					Sum:     sum,
					Ball:    ball,
					Product: score,
				})
				bingo.Boards[j].BingoFound = true
			}
		}
	}
	return results
}

func isBingoHorizontal(bingo Bingo, board Board, pos Position) bool {
	return bingo.BoardSize == bits.OnesCount(board.Rows[pos.Y])
}

func reversePosX(boardSize int, x int) uint {
	return uint(boardSize - 1 - x)
}

func isBingoVertical(bingo Bingo, board Board, position Position) bool {
	allVerticalOnes := true
	for y := 0; y < bingo.BoardSize; y++ {
		if y == position.Y {
			continue
		}
		if !hasBit(board.Rows[y], reversePosX(bingo.BoardSize, position.X)) {
			allVerticalOnes = false
			break
		}
	}
	return allVerticalOnes
}

func findUnmarked(board Board, boardSize int) int {
	var sum int
	for y, row := range board.Rows {
		for x := 0; x < boardSize; x++ {
			if !hasBit(row, reversePosX(boardSize, x)) {
				ball := board.PositionNumber[getPositionNumberKey(x, y)]
				sum += ball
			}
		}
	}
	return sum
}

func setBit(n uint, pos uint) uint {
	n |= 1 << pos
	return n
}

func hasBit(n uint, pos uint) bool {
	val := n & (1 << pos)
	return val > 0
}

func getPositionNumberKey(x int, y int) string {
	return fmt.Sprintf("%d,%d", x, y)
}

func getPartOne(bingo Bingo) int {
	return findBingoScores(bingo)[0].Product
}

func getPartTwo(bingo Bingo) int {
	scores := findBingoScores(bingo)
	return scores[len(scores)-1].Product
}

func getRows(filename string) Bingo {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	var bingo Bingo
	rowIndex := 0
	y := 0
	var board Board
	for scanner.Scan() {
		row := scanner.Text()
		if rowIndex == 0 {
			numbers := strings.Split(row, ",")
			for _, number := range numbers {
				val, err := strconv.Atoi(number)
				if err != nil {
					panic(err)
				}
				bingo.Balls = append(bingo.Balls, val)
			}
		} else {
			if len(row) == 0 {
				if board.NumberPosition != nil {
					bingo.Boards = append(bingo.Boards, board)
				}
				board = Board{}
				board.NumberPosition = map[int]Position{}
				board.PositionNumber = map[string]int{}
				y = 0
			} else {
				fields := strings.Fields(row)
				for x, field := range fields {
					val, err := strconv.Atoi(field)
					if err != nil {
						panic(err)
					}
					board.NumberPosition[val] = Position{
						X: x,
						Y: y,
					}
					board.PositionNumber[getPositionNumberKey(x, y)] = val
				}
				board.Rows = append(board.Rows, 0)
				y++
			}
		}
		rowIndex++
	}
	bingo.Boards = append(bingo.Boards, board)
	bingo.BoardSize = y
	return bingo
}

func main() {
	fmt.Println("Part one:", getPartOne(getRows("../input.txt")))
	fmt.Println("Part two:", getPartTwo(getRows("../input.txt")))
}

#include <iostream>
#include <regex>

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

struct line
{
    int x1;
    int y1;
    int x2;
    int y2;
};

vector<line> parse(vector<string> data, vector<vector<int>> &grid)
{
    vector<line> output;
    int x_max_grid = 0, y_max_grid = 0;
    int x1, x2, y1, y2;

    std::string regex_string = "^([0-9]+),([0-9]+)\\s->\\s([0-9]+),([0-9]+)$";
    regex regex(regex_string);
    smatch matches;

    int n_rows = data.size();
    for (int i = 0; i < n_rows; i++)
    {
        bool match = regex_search(data[i],matches,regex);
        if (match)
        {
            int x1 = stoi(matches[1]);
            int y1 = stoi(matches[2]);
            int x2 = stoi(matches[3]);
            int y2 = stoi(matches[4]);

            line new_line = {x1, y1, x2, y2};
            
            output.push_back(new_line);

            if (x1 > x_max_grid){x_max_grid = x1;}
            if (x2 > x_max_grid){x_max_grid = x2;}
            if (y1 > y_max_grid){y_max_grid = y1;}
            if (y2 > y_max_grid){y_max_grid = y2;}
        }
    }
    //output.push_back(grid_diagonal);
    grid.resize(x_max_grid + 1, vector<int> (y_max_grid + 1,0));

    return output;
}

int draw_lines(vector<line> lines,vector<vector<int>> grid, bool skip_diagonals = true)
{
    int count = 0;
    int n_lines = lines.size();
    int row_step,col_step;

    for (auto line : lines)
    {
        if (line.x1 == line.x2)
        {
            //vertical line
            line.y1 > line.y2? row_step = -1 : row_step = 1;
            int row = line.y1;
            while (row != (line.y2+row_step))
            {
                if (grid[line.x1][row] == 1)
                {
                    count++;
                }
                grid[line.x1][row]++;
                row += row_step;
            }

        }
        else if (line.y1 == line.y2)
        {
            //horizontal line
            line.x1 > line.x2? col_step = -1 : col_step = 1;
            int col = line.x1;
            while (col != (line.x2+col_step))
            {
                if (grid[col][line.y1] == 1)
                {
                    count++;
                }
                grid[col][line.y1]++;
                col+= col_step;
            }
        }
        else
        {
            if (skip_diagonals)
            {
                continue;
            }    
            //45 degree diagonal line
            int col = line.x1;
            line.x1 > line.x2? col_step = -1 : col_step = 1;
            int row = line.y1;
            line.y1 > line.y2? row_step = -1 : row_step = 1;
            while (col != (line.x2 + col_step))
            {
                if (grid[col][row] == 1)
                {
                    count++;
                }
                grid[col][row]++;
                col += col_step;
                row += row_step;
            }
        }
    }
    return count;
}

int main()
{

    string filename = "../../input/day_05.txt";
    vector<string> data = read_file<string>(filename,true);
    vector<vector<int>> grid;
    vector<line> lines = parse(data, grid);

    int part_1 = draw_lines(lines, grid, true);
    int part_2 = draw_lines(lines, grid, false);

    cout << "Day 5 Part 1 solution: " << part_1 << endl;
    cout << "Day 5 Part 2 solution: " << part_2 << endl;

    return 0;

}

(import std)

(define main
  (do io/bind
      (<- input (io/map unwrap! (read-file "inputs/day5.txt")))
      (let (([ortho-points diag-points]
             (map-both array/collect-list
                       (partition-eithers (flat-map (<o line-points parse-line) (lines input)))))
            (ortho-sorted (merge-sort point-cmp ortho-points))
            (all-sorted (merge-sort point-cmp (array/append ortho-sorted diag-points)))
            ))
      (display (str-append "Part 1: " (show-int (count-intersections ortho-sorted))))
      (display (str-append "Part 2: " (show-int (count-intersections all-sorted))))))

;; The boxing of the accumulation is a hack to work around a bug in the codegen. `foldl` should
;; always be tail call optimized, but apparently it is not when the type of the accumulation is too
;; big or complex or something like that. No TCO => stack overflow / segfault for long
;; iterators. Boxing reduces the type to a simple pointer, which does not break TCO.
(define (count-intersections ps)
  (define (point-eq p1 p2) (match (point-cmp p1 p2) (case Eq True) (case _ False)))
  (let (([p0 ps] (next! (array/iter ps)))
        ([p1 ps] (next! ps))
        (init (if (point-eq p0 p1) 1 0)))
    (car (deref (foldl (fun ((Box [n p0 p1]) p2)
                         ;; Don't count more than one intersection when more than one duplicate
                         (box [(if (and (point-eq p2 p1) (not (point-eq p2 p0))) (+ n 1) n) p1 p2]))
                       (box [init p0 p1])
                       ps)))))

(define parse-line
  (<o unwrap! (parse (do parse/bind
                         (<- x1 parse/nat) (parse/string ",") (<- y1 parse/nat)
                         (parse/string " -> ")
                         (<- x2 parse/nat) (parse/string ",") (<- y2 parse/nat)
                         (parse/pure [[(to-int x1) (to-int y1)] [(to-int x2) (to-int y2)]])))))

(define (line-points [[x1 y1] [x2 y2]])
  (if (= x1 x2)
      (map Left (zip (repeat x1) (range (min y1 y2) (max y1 y2))))
    (if (= y1 y2)
        (map Left (zip (range (min x1 x2) (max x1 x2)) (repeat y1)))
      (let ((mag (abs (- x2 x1))) (dx (sign (- x2 x1))) (dy (sign (- y2 y1))))
        (map (fun (i) (Right [(+ x1 (* dx i)) (+ y1 (* dy i))])) (range 0 mag))))))

(define (point-cmp [x1 y1] [x2 y2])
  (match (int/cmp x1 x2) (case Lt Lt) (case Gt Gt) (case Eq (int/cmp y1 y2))))

import qualified Data.Set as Set
main = interact solve

solve :: String -> String
solve input = "Problem 1: " ++ show (countOverlaps (filter (not.isDiagonal) measurements)) ++ "\n"
           ++ "Problem2: " ++ show (countOverlaps measurements) ++ "\n"
    where
        measurements = map splitNumbers (lines input) :: [[Int]]
        splitNumbers line = read num : if null rest then [] else splitNumbers rest
            where
                (num,rest) = span isNum (dropWhile (not.isNum) line)
                isNum c = elem c "0123456789"

countOverlaps measurements = length (snd (foldr countPts (Set.empty, Set.empty) measurements))
    where
        countPts line (allPts, dups) = (allPts', dups')
            where
                allPts' = Set.union allPts newPts
                dups' = Set.union dups (Set.intersection allPts newPts)
                newPts = Set.fromList (points line)

points line@(x1:y1:x2:y2:[]) = if isDiagonal line then zip xs ys else [(x,y) | x<-xs, y<-ys]
    where
        xs = listPts x1 x2
        ys = listPts y1 y2
        listPts p1 p2
            | p1 > p2 = reverse [p2..p1]
            | otherwise = [p1..p2]

isDiagonal (x1:y1:x2:y2:[]) = x1/=x2 && y1/=y2

use std::fs;

pub fn run() {
    let data = fs::read_to_string("dec_04.txt").expect("unable to read file");

    let mut cards = vec![vec![vec![]]];
    let mut card = vec![vec![]];
    let mut bingo_balls = vec![0];

    for line in data.lines().rev() {
        match line.len() {
            i if i > 16 => {
                bingo_balls = line.split(",").map(|s| s.parse().unwrap()).collect();
            }
            i if i == 14 => {
                let bingo_line: Vec<i32> = line.split(" ").filter_map(|s| s.parse().ok()).collect();

                card.push(bingo_line);
            }
            0 => {
                cards.push(card.clone());
                card.clear();
            }
            _ => println!("Bad data"),
        }
    }

    let mut high_score = 500;
    let mut winning_card = 0;
    let mut winning_line = vec![];
    for (card_index, card) in cards.iter().enumerate() {
        let mut row = vec![0; 6];
        let mut col = vec![0; 6];
        let mut score_line = vec![];

        for (score, ball) in bingo_balls.iter().enumerate() {
            for (x, line) in card.iter().enumerate() {
                for (y, n) in line.iter().enumerate() {
                    if n == ball {
                        row[x] += 1;
                        col[y] += 1;
                        score_line.push(*ball);
                        if (row[x] == 5) || (col[y] == 5) {
                            if score < high_score {
                                high_score = score;
                                winning_card = card_index;
                                winning_line = score_line.clone();
                            }
                        }
                    }
                }
            }
        }
    }

    let sum1: i32 = winning_line.iter().sum();

    let mut sum2 = 0;
    for card in &cards[winning_card] {
        for n in card {
            sum2 += n;
        }
    }

    let awnser = (sum2 - sum1) * winning_line.last().unwrap();
    println!("Awnser {}", awnser);
}

internal class Puzzle4 : Puzzle<int>
{
    private class Square
    {
        public int Number { get; }
        public bool IsMarked { get; set; }

        public Square(int number) => Number = number;
    }

    private readonly List<int> _bingoResults;

    public Puzzle4()
    {
        var lines = File.ReadAllLines("Inputs/Puzzle4.txt");
        var numbers = lines[0].Split(',')
            .Select(int.Parse)
            .ToArray();
        var boards = lines.Skip(1)
            .Where(x => !string.IsNullOrWhiteSpace(x))
            .Select(boardLine => boardLine
                .Split(' ', StringSplitOptions.RemoveEmptyEntries)
                .Select(x =>  new Square(int.Parse(x)))
                .ToArray())
            .Chunk(5)
            .ToArray();

        _bingoResults = PlayBingo(numbers, boards);
    }

    public override int One() => _bingoResults.First();

    public override int Two() => _bingoResults.Last();

    private static List<int> PlayBingo(int[] numbers, Square[][][] boards)
    {
        var winningResults = new List<int>();
        var playingBoards = boards.ToList();

        foreach (var number in numbers)
        {
            foreach (var board in playingBoards.ToList())
            {
                var numbersToCheck = board
                    .Select(line => line.FirstOrDefault(s => s.Number == number))
                    .Where(s => s != null);

                foreach (var numberToCheck in numbersToCheck)
                {
                    numberToCheck!.IsMarked = true;
                }

                if (HasRowWin(board) || HasColumnWin(board))
                {
                    var score = board.Sum(line => line.Where(s => !s.IsMarked).Sum(s => s.Number)) * number;
                    winningResults.Add(score);
                    playingBoards.Remove(board);
                }
            }

            if (playingBoards.Count == 0)
            {
                break;
            }
        }

        return winningResults;
    }

    private static bool HasRowWin(Square[][] board) =>
        board.Any(line => line.All(s => s.IsMarked));

    private static bool HasColumnWin(Square[][] board)
    {
        for (int col = 0; col < board.Length; col++)
        {
            var hasColumnWin = true;
            for (int row = 0; row < board[col].Length; row++)
            {
                if (!board[row][col].IsMarked)
                {
                    hasColumnWin = false;
                }
            }

            if (hasColumnWin)
            {
                return true;
            }
        }

        return false;
    }
}