Advent of Code day 22 in Odin

day22.odin

package main

import "core:fmt"
import "core:math"
import "core:mem"
import "core:os"
import "core:slice"
import "core:unicode"
import "core:strconv"
import "core:strings"

Board :: struct {
	cells: []u8,
	cube_size: int,
	width, height: int,
}

is_face :: proc (board: Board, i: int, j: int) -> bool {
	if i < 0 || j < 0 || i >= board.height/board.cube_size || j >= board.width/board.cube_size { return false }
	return board.cells[i*board.cube_size*board.width+j*board.cube_size] != ' '
}

make_board :: proc (lines: string) -> (result: Board) {
	tmp := lines
	for line in strings.split_iterator(&tmp, "\n") {
		if len(line) == 0 {break}
		result.width = max(result.width, len(line))
		result.height += 1
	}
	result.cells= make([]u8, result.width*result.height)
	slice.fill(result.cells, ' ')
	tmp = lines
	i := 0
	for line in strings.split_iterator(&tmp, "\n") {
		if len(line) == 0 {break}
		mem.copy(raw_data(result.cells[i*result.width:]), raw_data(line), len(line))
		i += 1
	}
	surface := len(result.cells) - slice.count(result.cells, ' ')
	result.cube_size = cast(int)math.sqrt_f64(auto_cast surface / 6)
	return
}

Move :: struct {
	step: int,
	rot: int,
}

make_moves :: proc (line: string) -> (result: []Move, ok: bool) {
	rot_map := [256]int{'R' = 1, 'L' = -1}
	moves := [dynamic]Move{}
	defer delete(moves)
	line := line
	i := 0
	j := 0
	for j < len(line) {
		for unicode.is_digit(cast(rune)line[j]) {j+=1}
		n := strconv.parse_int(line[i:j]) or_return
		r := rot_map[line[j]]
		append(&moves, Move{n,r})
		i, j = j+1, j+1
	}
	result = moves[:]
	moves = {}
	return result, true
}

pacman_map :: proc (board: Board) -> (result: [][4][3]int) {
	w, h := board.width / board.cube_size, board.height / board.cube_size
	result = make([][4][3]int, w*h)

	for i in 0 ..< h {
		for j in 0 ..<  w {
			if !is_face(board, i, j) {continue}
			// RDLU: order is important
			di := [4]int{ 0,  1,  0, -1}
			dj := [4]int{ 1,  0, -1,  0}
			c  := [4]int{}
			for d in 0 ..< 4 {
				for k in 0 ..< w {
					ii := i + k * di[d]
					jj := j + k * dj[d]
					if !is_face(board, ii, jj) { break }
					c[d] = k
				}
			}

			for d in 0 ..< 4 {
				k, bk := c[d], c[(d+2)%4]
				if k > 0 {
					result[i*w+j][d] = {i+di[d], j+dj[d], 0}
				} else {
					result[i*w+j][d] = {i-bk*di[d], j-bk*dj[d], 0}
				}
			}
		}
	}
	return
}

cube_map :: proc (using board: Board) -> (result: [][4][3]int) {
	w, h := width / cube_size, height / cube_size
	pos: [2]int
	search: for i in 0 ..< h {
		for j in 0 ..< w {
			if is_face(board, i, j) {
				pos = {i, j}
				break search
			}
		}
	}

	coords := map[[2]int]matrix[3,3]int{}
	defer delete(coords)
	coords[pos] = cast(matrix[3,3]int)1

	fill: for len(coords) < 6 {
		for p, t in coords {
			dp := [?][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
			dt := [?]matrix[3,3]int{
				{ 0,  0,  1,  0,  1,  0, -1,  0,  0 },
				{ 1,  0,  0,  0,  0,  1,  0, -1,  0 },
				{ 0,  0, -1,  0,  1,  0,  1,  0,  0 },
				{ 1,  0,  0,  0,  0, -1,  0,  1,  0 },
			}
			for k in 0 ..< 4 {
				if !is_face(board, (p+dp[k]).x, (p+dp[k]).y) {continue}
				if p + dp[k] not_in coords {
					coords[p + dp[k]] = t * dt[k]
				}
			}
		}
	}

	result = make([][4][3]int, w*h)
	for p1, t1 in coords {
		for p2, t2 in coords {
			t21 := matrix3x3_inverse(t1)*t2
			t12 := matrix3x3_inverse(t21)
			a := (t21*[3]int{0, 0, 1}).xy
			b := -(t12*[3]int{0, 0, 1}).xy

			if a != {0, 0} {
				rotation := vec2_angle(a, b)
				direction := vec2_angle({0, 1}, a)
				result[p1.x*w+p1.y][direction] = {p2.x, p2.y, rotation}
			}
		}
	}

	return
}

vec2_angle :: proc (a, b: [2]int) -> int {
	if a == b { return 0 }
	if a == -b{ return 2 }
	if a == ([2]int{-1, 1} * b.yx) {return 1}
	return 3
}

solve :: proc (msg: string, board: Board, topo: [][4][3]int, moves: []Move) {
	size := board.cube_size
	w, _ := board.width/size, board.height / size
	
	dirs := [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

	offset := slice.linear_search(board.cells, '.') or_else os.exit(1)
	full_pos := [2]int{offset / board.width, offset % board.width}
	rotation := 0
	face := full_pos / size
	pos  := full_pos % size

	for move in moves {
		for _ in 0 ..< move.step {
			new_pos  := pos + dirs[rotation]
			new_face := face
			new_rotation := rotation

			if new_pos[0] < 0 || new_pos[0] >= size || new_pos[1] < 0 || new_pos[1] >= size {
				new_pos = new_pos %% size
				transform := topo[face[0]*w+face[1]][rotation]

				switch transform.z {
					case 0:
					case 1: new_pos = [2]int{0, size-1} + [2]int{1, -1} * new_pos.yx
					case 2: new_pos = [2]int{size-1, size-1} - new_pos
					case 3: new_pos = [2]int{size-1, 0} + [2]int{-1, 1} * new_pos.yx
				}

				new_face = transform.xy
				new_rotation = (rotation + transform.z) %% 4
			}

			i := new_face.x*size+new_pos.x
			j := new_face.y*size+new_pos.y
			if board.cells[i*board.width+j] == '#' {break}
			pos = new_pos
			face = new_face
			rotation = new_rotation
		}

		rotation = (rotation + move.rot) %% 4
	}

	i := face.x*size+pos.x+1
	j := face.y*size+pos.y+1
	fmt.println(msg,i*1000 + j*4 + rotation)
}

main :: proc () {
	input := os.read_entire_file("input.txt") or_else []u8{}
	parts := strings.split(string(input), "\n\n")
	board := make_board(parts[0])
	moves := make_moves(parts[1]) or_else []Move{}
	topo1 := pacman_map(board)
	solve("part 1:", board, topo1, moves)

	topo2 := cube_map(board)
	solve("part 2:", board, topo2, moves)
}