Day 16: The Floor Will Be Lava

module Main (main) where

import qualified Data.Set as Set
import Data.Map (Map, fromList, (!))
import Data.Set (Set, empty, size, member, insert)

main :: IO ()
main = do
    input <- readFile "./input.txt"
    putStrLn $ "Part 1: " ++ show (solve1 $ parseInput input)
    putStrLn $ "Part 2: " ++ show (solve2 $ parseInput input)

type Coord = (Int, Int)

data Cell = Empty | Horizontal | Vertical | BLTR | TLBR

data Direction = North | South | East | West deriving (Eq, Ord)

type Board = (Map Coord Cell, Int, Int)

data Particle = Particle {
    coord :: Coord,
    direction :: Direction
} deriving (Eq, Ord)

parseCell :: Char -> Cell
parseCell c = case c of
    '.'  -> Empty
    '-'  -> Horizontal
    '|'  -> Vertical
    '/'  -> BLTR
    '\\' -> TLBR
    _    -> error "invalid character"

parseInput :: String -> Board
parseInput input = (arr, numRows, numCols) where
    numRows = length $ lines input
    numCols = length $ head (lines input)
    arr = fromList (concatMap (uncurry parseRow) (zip [0..] (lines input)))
    parseRow rowNum s = [((rowNum, colNum), parseCell c) | (colNum, c) <- zip [0..] s]

solve1 :: Board -> Int
solve1 board = solve board (Particle (0, 0) East)

solve :: Board -> Particle -> Int
solve (arr, numRows, numCols) start = uniquePositions $ solveRec [start] empty where
    onBoard (Particle (r, c) _) = 0 <= r && r < numRows && 0 <= c && c < numCols
    solveRec [] seen = seen
    solveRec (x:xs) seen
        | x `member` seen = solveRec xs seen
        | otherwise = solveRec queue seen' where
            resultingParticles = findResultingParticles x (arr ! coord x)
            queue = filter onBoard resultingParticles ++ xs
            seen' = x `insert` seen

findResultingParticles :: Particle -> Cell -> [Particle]
findResultingParticles (Particle (r, c) direction) cell = case (direction, cell) of
    (North, Horizontal) -> [Particle (r, c-1) West, Particle (r, c+1) East]
    (North, BLTR)       -> [Particle (r, c+1) East]
    (North, TLBR)       -> [Particle (r, c-1) West]
    (North, _)          -> [Particle (r-1, c) North]
    (South, Horizontal) -> [Particle (r, c-1) West, Particle (r, c+1) East]
    (South, BLTR)       -> [Particle (r, c-1) West]
    (South, TLBR)       -> [Particle (r, c+1) East]
    (South, _)          -> [Particle (r+1, c) South]
    (East, Vertical)    -> [Particle (r-1, c) North, Particle (r+1, c) South]
    (East, BLTR)        -> [Particle (r-1, c) North]
    (East, TLBR)        -> [Particle (r+1, c) South]
    (East, _)           -> [Particle (r, c+1) East]
    (West, Vertical)    -> [Particle (r-1, c) North, Particle (r+1, c) South]
    (West, BLTR)        -> [Particle (r+1, c) South]
    (West, TLBR)        -> [Particle (r-1, c) North]
    (West, _)           -> [Particle (r, c-1) West]

uniquePositions :: Set Particle -> Int
uniquePositions = size . Set.map coord

solve2 :: Board -> Int
solve2 board = maximum $ map (solve board) possibleStarts where
    (_, numRows, numCols) = board
    possibleStarts = [Particle (0, c)         South | c <- [0..numCols-1]] ++
                     [Particle (numRows-1, c) North | c <- [0..numCols-1]] ++
                     [Particle (r, 0)         East  | r <- [0..numRows-1]] ++
                     [Particle (r, numCols-1) West  | r <- [0..numRows-1]]

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <utility>

using namespace std;

enum Dir {
	DIR_UP,
	DIR_LEFT,
	DIR_DOWN,
	DIR_RIGHT
};

typedef pair<int, int> Coord;

const Coord advanceInDir(const Coord position, const Dir direction){
	switch(direction){
	case DIR_UP:
		return make_pair(position.first - 1, position.second);
	case DIR_LEFT:
		return make_pair(position.first, position.second - 1);
	case DIR_DOWN:
		return make_pair(position.first + 1, position.second);
	case DIR_RIGHT:
		return make_pair(position.first, position.second + 1);
	}
	__builtin_unreachable();
}

typedef pair<Coord, Dir> WalkedDir;

int solve1(const vector<string> &problem, Coord position, Dir direction, set<WalkedDir> &walked){
	WalkedDir walkedDir = make_pair(position, direction);
	if (walked.contains(walkedDir)) {
		return 0;
	}
	if (position.first < 0 || position.first >= problem.size() || position.second < 0 || position.second >= problem[0].size()) {
		return 0;
	}
	walked.insert(walkedDir);

	// cout << "at position " << position.first << " " << position.second << endl;
	
	const char curChar = problem[position.first][position.second];
	if (curChar == '.') {
		return solve1(problem, advanceInDir(position, direction), direction, walked);
	} else if (curChar == '\\') {
		switch(direction){
		case DIR_UP:
			// \ 
			// |
			return solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked);
		case DIR_LEFT: // \--
			return solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked);
		case DIR_DOWN:
			// |
			// \ ..
			return solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked);
		case DIR_RIGHT: // --\ ..
			return solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked);
		}
	} else if (curChar == '/') {
		switch(direction){
		case DIR_UP:
			// /
			// |
			return solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked);
		case DIR_LEFT: // /--
			return solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked);
		case DIR_DOWN:
			// |
			// /
			return solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked);
		case DIR_RIGHT: // --/
			return solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked);
		}
	} else if (curChar == '|') {
		switch(direction){
		case DIR_UP: case DIR_DOWN: // pointy end
			return solve1(problem, advanceInDir(position, direction), direction, walked);
		case DIR_LEFT: case DIR_RIGHT: // flat end
			solve1(problem, advanceInDir(position, DIR_UP), DIR_UP, walked);
			solve1(problem, advanceInDir(position, DIR_DOWN), DIR_DOWN, walked);
			return 1;
		}
	} else if (curChar == '-') {
		switch(direction){
		case DIR_UP: case DIR_DOWN: // flat end
			solve1(problem, advanceInDir(position, DIR_LEFT), DIR_LEFT, walked);
			solve1(problem, advanceInDir(position, DIR_RIGHT), DIR_RIGHT, walked);
			return 1;
		case DIR_LEFT: case DIR_RIGHT: // pointy end
			return solve1(problem, advanceInDir(position, direction), direction, walked);
		}
	} else {
		cout << "wtf is " << curChar << "??" << endl;
		throw new runtime_error("wtf");
	}

	return walked.size();
}

set<Coord> toCoordSet(const set<WalkedDir> walked) {
	set<Coord> out;
	for(WalkedDir d : walked) {
		out.insert(d.first);
	}
	return out;
}

void printWalkDiagram(int w, int h, const set<Coord> &walked) {
	for(int hi = 0; hi < h; hi++){
		for(int wi = 0; wi < w; wi++){
			if (walked.contains(make_pair(hi, wi))) {
				cout << "#";
			}else{
				cout << ".";
			}
		}
		cout << endl;
	}
}

int main() {
	vector<string> problem;
	for(;;) {
		string input;
		getline(cin, input);
		if(input.empty()){
			break;
		}
		problem.push_back(input);
	}
	
	/*/ // part1

	set<WalkedDir> walked;
	solve1(problem, make_pair(0, 0), DIR_RIGHT, walked);

	set<Coord> coords = toCoordSet(walked);

	printWalkDiagram(problem[0].size(), problem.size(), coords);

	cout << coords.size() << endl;

	/**/

	/**/ // part 2

	int maxTiles = 0;

	// top row
	for(int i = 0; i < problem[0].size(); i++) {
		set<WalkedDir> walked;
		solve1(problem, make_pair(0, i), DIR_DOWN, walked);
		set<Coord> coords = toCoordSet(walked);
		maxTiles = max(static_cast<int>(coords.size()), maxTiles);
	}
	// bottom row
	for(int i = 0; i < problem[0].size(); i++) {
		set<WalkedDir> walked;
		solve1(problem, make_pair(problem.size() - 1, i), DIR_UP, walked);
		set<Coord> coords = toCoordSet(walked);
		maxTiles = max(static_cast<int>(coords.size()), maxTiles);
	}
	// left row
	for(int i = 0; i < problem.size(); i++) {
		set<WalkedDir> walked;
		solve1(problem, make_pair(i, 0), DIR_RIGHT, walked);
		set<Coord> coords = toCoordSet(walked);
		maxTiles = max(static_cast<int>(coords.size()), maxTiles);
	}
	// right row
	int rightRow = problem[0].size() - 1;
	for(int i = 0; i < problem.size(); i++) {
		set<WalkedDir> walked;
		solve1(problem, make_pair(rightRow, 1), DIR_LEFT, walked);
		set<Coord> coords = toCoordSet(walked);
		maxTiles = max(static_cast<int>(coords.size()), maxTiles);
	}

	cout << maxTiles << endl;

	/**/

	return 0;
}

This simply came down to following the beam. The only thing I overlooked at first was that I couldn't start with the beam already on the grid (as the instructions had implied) but had to start with the beam shining into the grid from the outside. My top-left corner in the puzzle input had a mirror, and because I had assumed that's where the beam starts, it was ignored. I feel like that must have been deliberate. Did anyone else have that?

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub struct Coordinate {
    pub x: isize,
    pub y: isize,
}

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct PuzzleInput {
    pub grid: Array2<char>,
}

[...]

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub enum Direction {
    #[default]
    North,
    East,
    South,
    West,
}

impl Direction {
    pub fn turn_left(&self) -> Self {
        match self {
            Self::North => Self::West,
            Self::East => Self::North,
            Self::South => Self::East,
            Self::West => Self::South,
        }
    }

    pub fn turn_right(&self) -> Self {
        match self {
            Self::North => Self::East,
            Self::East => Self::South,
            Self::South => Self::West,
            Self::West => Self::North,
        }
    }
}

impl Into<Coordinate> for Direction {
    fn into(self) -> Coordinate {
        match self {
            Self::North => Coordinate { x: 0, y: -1 },
            Self::East => Coordinate { x: 1, y: 0 },
            Self::South => Coordinate { x: 0, y: 1 },
            Self::West => Coordinate { x: -1, y: 0 },
        }
    }
}


#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)]
pub struct Beam {
    pub cur_pos: Coordinate,
    pub direction: Direction,
}

fn traverse(input: &PuzzleInput, beam: Beam) -> ArrayVec<[Beam; 2]> {
    let next_coord = beam.cur_pos + beam.direction.into();
    let mut result: ArrayVec<[Beam; 2]> = ArrayVec::new();

    let idx: Result<[usize; 2], ()> = next_coord.try_into();

    if idx.is_err() {
        return result;
    }

    let idx = idx.unwrap();

    match input.grid.get(idx) {
        None => return result,

        Some('.') => result.push(Beam {
            cur_pos: next_coord,
            direction: beam.direction,
        }),

        Some('/') => match beam.direction {
            Direction::North | Direction::South => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction.turn_right(),
            }),

            Direction::East | Direction::West => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction.turn_left(),
            }),
        },

        Some('\\') => match beam.direction {
            Direction::North | Direction::South => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction.turn_left(),
            }),

            Direction::East | Direction::West => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction.turn_right(),
            }),
        },

        Some('-') => match beam.direction {
            Direction::East | Direction::West => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction,
            }),

            Direction::North | Direction::South => {
                result.push(Beam {
                    cur_pos: next_coord,
                    direction: beam.direction.turn_left(),
                });
                result.push(Beam {
                    cur_pos: next_coord,
                    direction: beam.direction.turn_right(),
                });
            }
        },

        Some('|') => match beam.direction {
            Direction::North | Direction::South => result.push(Beam {
                cur_pos: next_coord,
                direction: beam.direction,
            }),

            Direction::East | Direction::West => {
                result.push(Beam {
                    cur_pos: next_coord,
                    direction: beam.direction.turn_left(),
                });
                result.push(Beam {
                    cur_pos: next_coord,
                    direction: beam.direction.turn_right(),
                });
            }
        },

        _ => unreachable!("Invalid tile at {:?}", next_coord),
    }

    result
}

[...]

pub fn energized_tiles(input: &PuzzleInput, start: Beam) -> HashSet<Coordinate> {
    let mut energized = HashSet::default();

    energized.insert(start);

    let mut q = VecDeque::new();
    q.push_back(start);

    while let Some(beam) = q.pop_front() {
        for next_beam in traverse(input, beam) {
            if next_beam.cur_pos.x < input.grid.ncols() as isize
                && next_beam.cur_pos.y < input.grid.nrows() as isize
                && next_beam.cur_pos.x >= 0
                && next_beam.cur_pos.y >= 0
                && energized.insert(next_beam)
            {
                q.push_back(next_beam);
            }
        }
    }

    energized
        .iter()
        .map(|beam| beam.cur_pos)
        .collect::<HashSet<_>>() // NOTE: This includes the start coordinate

day_16_bench  fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ parse      129 µs        │ 208.1 µs      │ 130.9 µs      │ 132.5 µs      │ 100     │ 100
├─ part1      834.7 µs      │ 1.052 ms      │ 864.5 µs      │ 862.5 µs      │ 100     │ 100
╰─ part2      194.6 ms      │ 270.5 ms      │ 199.8 ms      │ 208.9 ms      │ 100     │ 100

Few bugs I had to work out in my implementation of this one, like getting the directions of the mirror right and stopping infinite loops.

One thing I am grateful for with Go is the grest debugger support in VS code. If I ever end up in a C/C++ environment again, setting that up will be job one.

# Advent of Code 2023
# Day 16: The Floor Will Be Lava

with open("inputs/day_16.txt") as file:
    machine = [list(line.rstrip("\n")) for line in file]
    width = len(machine[0])
    height = len(machine)

def energized_tiles(x, y, direction):
    beams = [[x, y, direction]]
    seen_beams = set()
    energized = set()

    while beams:
        for beam in beams.copy():
            if (
                beam[0] < 0 or beam[0] >= width
                or beam[1] < 0 or beam[1] >= height
                or tuple(beam) in seen_beams
            ):
                beams.remove(beam)
                continue

            seen_beams.add(tuple(beam))
            energized.add((beam[0], beam[1]))

            tile = machine[beam[1]][beam[0]]

            if tile == "/":
                if beam[2] == "right":
                    beam[2] = "up"
                elif beam[2] == "down":
                    beam[2] = "left"
                elif beam[2] == "left":
                    beam[2] = "down"
                else:
                    beam[2] = "right"
            elif tile == "\\":
                if beam[2] == "right":
                    beam[2] = "down"
                elif beam[2] == "down":
                    beam[2] = "right"
                elif beam[2] == "left":
                    beam[2] = "up"
                else:
                    beam[2] = "left"
            elif tile == "|" and beam[2] in ("right", "left"):
                beam[2] = "down"
                beams.append([beam[0], beam[1] - 1, "up"])
            elif tile == "-" and beam[2] in ("down", "up"):
                beam[2] = "right"
                beams.append([beam[0] - 1, beam[1], "left"])

            if beam[2] == "right":
                beam[0] += 1
            elif beam[2] == "down":
                beam[1] += 1
            elif beam[2] == "left":
                beam[0] -= 1
            else:
                beam[1] -= 1

    return len(energized)

print(f"Part 1: {energized_tiles(0, 0, 'right')}")

starts = []

for x in range(width):
    starts.append([x, 0, "down"])
    starts.append([x, height - 1, "up"])

for y in range(height):
    starts.append([0, y, "right"])
    starts.append([width - 1, y, "left"])

print(f"Part 2: {max(energized_tiles(*start) for start in starts)}")

defmodule AdventOfCode.Solution.Year2023.Day16 do
  defmodule Silliness do
    defmacro __using__(_) do
      quote do
        import Kernel, only: :macros
        def unquote(:.)(h), do: [h]
        def unquote(:/)({x, y}), do: [{-y, -x}]
        def unquote(:"\\")({x, y}), do: [{y, x}]
        def unquote(:-)({0, _}), do: [{-1, 0}, {1, 0}]
        def unquote(:-)(h), do: [h]
        def unquote(:|)({_, 0}), do: [{0, -1}, {0, 1}]
        def unquote(:|)(h), do: [h]
      end
    end
  end

  defmodule TurnOps, do: use(Silliness)

  alias AdventOfCode.Grid, as: G

  defstruct [:beams, history: MapSet.new()]

  def part1(input) do
    input
    |> G.from_input(&String.to_existing_atom(<<&1>>))
    |> count_energized({{0, 0}, {1, 0}})
  end

  def part2(input) do
    grid = G.from_input(input, &String.to_existing_atom(<<&1>>))

    grid
    |> stream_init_beam_states()
    |> Task.async_stream(&count_energized(grid, &1), ordered: false)
    |> Stream.map(fn {:ok, count} -> count end)
    |> Enum.max()
  end

  defp count_energized(grid, init_beam_state) do
    %__MODULE__{beams: [init_beam_state]}
    |> Stream.iterate(&step_beams(&1, grid))
    |> Enum.find(&match?(%{beams: []}, &1))
    |> then(& &1.history)
    |> MapSet.new(fn {coords, _heading} -> coords end)
    |> MapSet.size()
  end

  defp step_beams(%{beams: beams, history: history}, grid) do
    %__MODULE__{
      beams: Enum.flat_map(beams, &if(&1 in history, do: [], else: step_beam(&1, grid))),
      history: MapSet.union(history, MapSet.new(beams))
    }
  end

  defp step_beam({coords, heading}, %{width: w, height: h} = grid) do
    apply(TurnOps, G.at(grid, coords), [heading])
    |> Stream.map(fn new_heading -> {sum_coords(coords, new_heading), new_heading} end)
    |> Enum.filter(fn {{x, y}, _} -> x in 0..(w - 1)//1 and y in 0..(h - 1)//1 end)
  end

  defp stream_init_beam_states(%{width: w, height: h}) do
    [
      Stream.flat_map(1..(h - 2)//1, fn y -> [{{0, y}, {1, 0}}, {{w - 1, y}, {-1, 0}}] end),
      Stream.flat_map(1..(w - 2)//1, fn x -> [{{x, 0}, {0, 1}}, {{x, h - 1}, {0, -1}}] end),
      Stream.flat_map([{0, 0}, {w - 1, 0}, {0, h - 1}, {w - 1, h - 1}], fn {x, y} ->
        x_headings = if x == 0, do: [0, 1], else: [0, -1]
        y_headings = if y == 0, do: [1, 0], else: [-1, 0]

        for heading <- Enum.zip(x_headings, y_headings), do: {{x, y}, heading}
      end)
    ]
    |> Stream.concat()
  end

  defp sum_coords({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}
end