class Day07 : AOCSolution {
    override val year = 2025
    override val day = 7

    override fun part1(inputFile: String): String {
        val diagram = readResourceLines(inputFile)
            .mapArray { line -> line.mapArray { char -> Cell.byChar(char) } }
            .toGrid()

        var count = 0
        for (y in 1 until diagram.height) {
            for (x in 0 until diagram.width) {
                // Search for beam sources in the preceding row
                if (diagram[x, y - 1] in Cell.beamSourceTypes) {
                    // Simulate the beam moving down
                    when (diagram[x, y]) {
                        Cell.Empty -> diagram[x, y] = Cell.Beam
                        Cell.Splitter -> {
                            // Split the beam and count this splitter
                            diagram[x - 1, y] = Cell.Beam
                            diagram[x + 1, y] = Cell.Beam
                            count++
                        }

                        else -> continue
                    }
                }
            }
        }

        return count.toString()
    }

    override fun part2(inputFile: String): String {
        val diagram = readResourceLines(inputFile)
            .mapArray { line -> line.mapArray { char -> Cell.byChar(char) } }
            .toGrid()
        val height = diagram.height.toLong()

        val startPosition = diagram.positionOfFirst { it == Cell.Start }

        // Working stack of beam origin and split origin positions
        val stack = ArrayDeque<Pair<Position, Position>>()
        stack.add(startPosition to startPosition)

        // Splitter positions mapped to the count of timelines to them
        // Start with the start position and 1 timeline.
        val splitters = mutableMapOf<Position, Long>(startPosition to 1)

        // Keep track of all splitters for which new beams have been spawned already
        // Could be used to solve part 1, as well
        val spawnedSplitters = mutableSetOf<Position>()

        // Count the timelines per diagram exit, which is the bottom-most row
        val diagramExits = LongArray(diagram.width)

        while (stack.isNotEmpty()) {
            // Breadth first search for memorizing the amount of paths to a splitter
            val (beamOrigin, splitOrigin) = stack.poll()
            val originPathCount = splitters.getValue(splitOrigin)

            val nextPosition = beamOrigin + Direction.DOWN

            if (nextPosition.y < height) {
                if (diagram[nextPosition] == Cell.Splitter) {
                    if (nextPosition !in spawnedSplitters) {
                        // Only spawn new beams, if they weren't spawned already
                        stack.add((nextPosition + Direction.LEFT) to nextPosition)
                        stack.add((nextPosition + Direction.RIGHT) to nextPosition)
                        spawnedSplitters.add(nextPosition)
                        // Initialize the count
                        splitters[nextPosition] = originPathCount
                    } else {
                        splitters.computeIfPresent(nextPosition) { _, v -> v + originPathCount }
                    }
                } else {
                    // Just move down
                    stack.add(nextPosition to splitOrigin)
                }
            } else {
                diagramExits[nextPosition.x.toInt()] += originPathCount
            }
        }

        // Sum the count of timelines leading to the bottom row, i.e. leaving the diagram for each position
        return diagramExits.sum().toString()
    }

    private companion object {
        enum class Cell(val char: Char) {
            Start('S'),
            Empty('.'),
            Splitter('^'),
            Beam('|');

            override fun toString(): String {
                return char.toString()
            }

            companion object {
                fun byChar(char: Char) = entries.first { it.char == char }

                val beamSourceTypes = arrayOf(Start, Beam)
            }
        }
    }
}

type
  AOCSolution[T,U] = tuple[part1: T, part2: U]

proc solve(input: string): AOCSolution[int, int] =
  var beams = newSeq[int](input.find '\n')
  beams[input.find 'S'] = 1

  for line in input.splitLines():
    var newBeams = newSeq[int](beams.len)
    for pos, cnt in beams:
      if cnt == 0: continue
      if line[pos] == '^':
        newBeams[pos-1] += cnt
        newBeams[pos+1] += cnt
        inc result.part1
      else:
        newbeams[pos] += cnt
    beams = newBeams
  result.part2 = beams.sum()

class Day07 : Puzzle {

    val grid = mutableListOf<MutableList<Char>>()
    val partTwoCache = mutableMapOf<Pair<Int, Int>, Long>()

    override fun readFile() {
        val input = readInputFromFile(2025, 7, false)
        for (line in input.lines().filter { it.isNotBlank() }) {
            grid.add(line.toCharArray().toMutableList())
        }
    }

    override fun solvePartOne(): String {
        grid[1][grid[0].indexOf('S')] = '|'

        var splits = 0
        for (r in 1..<grid.size - 1) {
            for (c in 0..<grid[r].size) {
                if (grid[r][c] == '|') {
                    if (grid[r+1][c] == '.') {
                        grid[r+1][c] = '|'
                    } else if (grid[r+1][c] == '^') {
                        grid[r+1][c-1] = '|'
                        grid[r+1][c+1] = '|'
                        splits++
                    }
                }
            }
        }
        return splits.toString()
    }

    override fun solvePartTwo(): String {
        val start = grid[0].indexOf('S')
        return (1 + processBeamPartTwo(1, start)).toString() // don't forget to count the original timeline
    }

    private fun processBeamPartTwo(row: Int, column: Int): Long {
        if (partTwoCache.contains(Pair(row, column))) {
            return partTwoCache[Pair(row, column)]!!
        }

        if (row == grid.size) return 0L
        if (column == grid[row].size || column < 0) return 0L

        val out = if (grid[row][column] == '^') { // splitter
            1L + processBeamPartTwo(row, column - 1) + processBeamPartTwo(row, column + 1)
        } else {
            processBeamPartTwo(row + 1, column)
        }
        partTwoCache[Pair(row, column)] = out
        return out
    }
}

def solve(data: str):
    grid = data.splitlines()
    m, n = len(grid), len(grid[0])

    # find the first particle
    particle_paths = [0] * n  # count of particle paths that will reach this column
    for j in range(n):
        if grid[0][j] == 'S':
            particle_paths[j] = 1
            break
    
    # count the number of splits for part 1
    splits = 0

    # simulate the particle moving down the grid
    #   optimization 1: we can start from the 3rd row (index 2) because that's where the first splitter is
    #   optimization 2: we can skip alternating rows because every other row is empty
    for i in range(2, m, 2):
        # particle paths per column after this row is processed
        next_particle_paths = [0] * n

        for j in range(n):
            if particle_paths[j] == 0:
                # skip if there are no particle paths coming from above in this column
                continue
            
            if grid[i][j] == '.':
                # no splitter here, the number of paths in this column remains the same
                # make sure to use += to account for neighboring splitters dumping additional paths into this column
                next_particle_paths[j] += particle_paths[j]
            else:
                # splitter activated here, any particle arriving here can end up in the left or right column
                # this can be simulated by adding the number of paths to the columns on either side
                splits += 1
                next_particle_paths[j-1] += particle_paths[j]
                next_particle_paths[j+1] += particle_paths[j]
        
        # update vars for next iteration
        particle_paths = next_particle_paths

    # return both 
    #   the number of splits AND 
    #   the count of timelines a particle would create
    return splits, sum(particle_paths)

sample = """.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
..............."""
assert solve(sample) == (21, 40)

function part1(inputText) {
  let beams = new Set([inputText.indexOf('S')]);
  const beamSplits = new Set();
  const lines = inputText.trimEnd().split('\n');
  for (let y = 1; y < lines.length; y++) {
    const nextBeams = new Set();
    for (const beamX of beams) {
      if (lines[y][beamX] === '.') {
    nextBeams.add(beamX);
      } else if (lines[y][beamX]) {
    beamSplits.add([beamX, y].toString());
    nextBeams.add(beamX + 1);
    nextBeams.add(beamX - 1);
      }
    }
    beams = nextBeams;
  }
  return beamSplits.size;
}

{
  const start = performance.now();
  const result = part1(document.body.textContent);
  const end = performance.now();
  console.info({ day: 7, part: 1, time: end - start, result });
}


function part2(inputText) {
  let beams = new Map([
    [inputText.indexOf('S'), 1]
  ]);
  const lines = inputText.trimEnd().split('\n');
  for (let y = 1; y < lines.length; y++) {
//     console.debug({ y, beams })
    const nextBeams = new Map();
    for (const [beamHeadX, beamCount] of beams) {
      if (lines[y][beamHeadX] === '.') {
        nextBeams.set(beamHeadX, (nextBeams.get(beamHeadX) ?? 0) + beamCount);
      } else if (lines[y][beamHeadX] === '^') {
        nextBeams.set(beamHeadX + 1, (nextBeams.get(beamHeadX + 1) ?? 0) + beamCount);
        nextBeams.set(beamHeadX - 1, (nextBeams.get(beamHeadX - 1) ?? 0) + beamCount);
      }
    }
    beams = nextBeams;
  }
  return beams.entries().reduce((accu, [_, count]) => accu + count, 0);
}

{
  const start = performance.now();
  const result = part2(document.body.textContent);
  const end = performance.now();
  console.info({
    day: 7,
    part: 2,
    time: end - start,
    result
  })
}

package main

import (
	"aoc/utils"
)

func parseStartLine(line string) []bool {
	runes := []rune(line)
	beams := make([]bool, len(runes))

	for idx, char := range runes {
		if char == 'S' {
			beams[idx] = true
		}
	}

	return beams
}

func stepOne(input chan string) (int, error) {
	beams := parseStartLine(<-input)
	splitCount := 0

	for line := range input {
		runes := []rune(line)
		for idx, char := range runes {
			if char == '^' && beams[idx] {
				splitCount++
				if idx > 0 {
					beams[idx-1] = true
				}
				if idx < len(runes)-1 {
					beams[idx+1] = true
				}
				beams[idx] = false
			}
		}
	}

	return splitCount, nil
}

func valueBeams(beams []bool) []int {
	valBeams := make([]int, len(beams))

	for idx, b := range beams {
		val := 0
		if b {
			val = 1
		}
		valBeams[idx] = val
	}

	return valBeams
}

func stepTwo(input chan string) (int, error) {
	beams := valueBeams(parseStartLine(<-input))

	for line := range input {
		runes := []rune(line)
		for idx, char := range runes {
			bc := beams[idx]
			if char == '^' && bc > 0 {
				beams[idx] = 0
				if idx > 0 {
					beams[idx-1] += bc
				}
				if idx < len(runes)-1 {
					beams[idx+1] += bc
				}
			}
		}
	}

	sum := 0
	for _, bc := range beams {
		sum += bc
	}

	return sum, nil
}

func main() {
	inputFile := utils.FilePath("day07.txt")
	utils.RunStep(utils.ONE, inputFile, stepOne)
	utils.RunStep(utils.TWO, inputFile, stepTwo)
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>

#define GW 148
#define GH 74

static char g[GH][GW];
static uint64_t dp[2][GW];
static int w,h;

/* recursively traces beam for part 1, marking visited splitters with 'X' */
static uint64_t
solve_p1(int x, int y)
{
	if (x<0 || x>=w || y<0 || y>=h || g[y][x] == 'X')
		return 0;
	else if (g[y][x] != '^')
		return solve_p1(x, y+1);
	else {
		g[y][x] = 'X';
		return 1 + solve_p1(x-1, y) + solve_p1(x+1, y);
	}
}

/* DP for part 2 */
static uint64_t
solve_p2(void)
{
	int x,y, odd;

	for (y=h-1; y>=0; y--)
	for (x=1; x<w-1; x++) {
		/* only two rows relevant at a time, so don't store any more */
		odd = y&1;

		if (g[y][x] == 'S') {
			printf("\n");
			return dp[!odd][x] + 1;
		}

		dp[odd][x] = g[y][x] == '^' || g[y][x] == 'X'
		    ? dp[!odd][x-1] + dp[!odd][x+1] + 1
		    : dp[!odd][x];
	}

	return 0;
}

int
main()
{
	int x,y, sx,sy;

	for (h=0; ; ) {
		/* one bottom row of padding */
		assert(h < GH-1);
		/* input already side padded, plus we have \n\0 */
		if (!fgets(g[h], GW, stdin))
			break;
		/* skip empty rows */
		for (x=0; g[h][x]; x++)
			if (g[h][x] == 'S' || g[h][x] == '^')
				{ h++; break; }
	}

	w = strlen(g[0])-1; /* strip \n */

	for (y=0; y<h; y++)
	for (x=0; x<w; x++)
		if (g[y][x] == 'S')
			{ sx=x; sy=y; break; }

	printf("07: %"PRIu64" %"PRIu64"\n", solve_p1(sx,sy), solve_p2());
}

func part2() {
	// file, _ := os.Open("sample.txt")
	file, _ := os.Open("input.txt")
	defer file.Close()
	scanner := bufio.NewScanner(file)

	input := [][]rune{}

	for scanner.Scan() {
		line := []rune(scanner.Text())
		input = append(input, line)
	}

	m := len(input)
	n := len(input[0])
	grid := make([][]int, m)
	for i := range m {
		grid[i] = make([]int, n)
	}

	for i := range m {
		for j := range n {
			c := input[i][j]
			if i == 0 {
				if c == 'S' {
					grid[i][j] = 1
				}
				continue
			}
			if c == '^' {
				grid[i][j-1] += grid[i-1][j]
				grid[i][j+1] += grid[i-1][j]
			} else {
				grid[i][j] = grid[i][j] + grid[i-1][j]
			}
		}
	}

	paths := 0
	for j := range n {
		paths += grid[m-1][j]
	}

	fmt.Println(paths)
}