package main

import "core:container/queue"
import "core:fmt"
import "core:math"
import "core:math/linalg"
import "core:os"
import "core:slice"
import "core:strconv"
import "core:strings"
import "core:time"
import "core:unicode/utf8"

import util "../util"

Vec2 :: [2]int

count_paths :: proc(pos: Vec2, lines: []string, cache: ^map[Vec2]i64) -> i64 {
	if pos.y >= len(lines) do return 1

	if cached, ok := cache[pos]; ok do return cached

	result: i64 = 0
	switch lines[pos.y][pos.x] {
	case '^':
		result =
			count_paths(Vec2{pos.x - 1, pos.y + 1}, lines, cache) +
			count_paths(Vec2{pos.x + 1, pos.y + 1}, lines, cache)
	case:
		result = count_paths(Vec2{pos.x, pos.y + 1}, lines, cache)
	}
	cache[pos] = result

	return result
}

part_1 :: proc(lines: []string) {
	result: i64 = 0
	start_x, _ := slice.linear_search(transmute([]u8)lines[0], 'S')

	stack := make([dynamic]Vec2)
	visited := make(map[Vec2]struct{})
	append(&stack, Vec2{start_x, 0})

	for len(stack) > 0 {
		pos := pop(&stack)
		if pos.y >= len(lines) do continue
		if pos in visited do continue
		visited[pos] = {}

		switch lines[pos.y][pos.x] {
		case '^':
			append(&stack, Vec2{pos.x - 1, pos.y + 1})
			append(&stack, Vec2{pos.x + 1, pos.y + 1})
			result += 1
		case:
			append(&stack, Vec2{pos.x, pos.y + 1})
		}
	}

	fmt.printfln("  [Result] %v", result)
}

part_2 :: proc(lines: []string) {
	cache := make(map[Vec2]i64)
	start_x, _ := slice.linear_search(transmute([]u8)lines[0], 'S')
	result := count_paths(Vec2{start_x, 0}, lines, &cache)
	fmt.printfln("  [Result] %v", result)
}

main :: proc() {
	context.allocator = context.temp_allocator
	defer free_all(context.temp_allocator)

	INPUT :: #load("input.txt", string)
	lines := strings.split(INPUT, "\n")
	lines = lines[:len(lines) - 1]

	fmt.println("[Part 1]")
	start := time.tick_now()
	part_1(lines)
	duration := time.tick_diff(start, time.tick_now())
	fmt.printfln("  [Time]   %vms\n", time.duration_milliseconds(duration))

	fmt.printfln("[Part 2]")
	start = time.tick_now()
	part_2(lines)
	duration = time.tick_diff(start, time.tick_now())
	fmt.printfln("  [Time]   %vms", time.duration_milliseconds(duration))
}