From f1ab08b2a892ca1dda6a46ae9ef03b0e8cf5c9b8 Mon Sep 17 00:00:00 2001
From: Steven Le Rouzic <steven.lerouzic@gmail.com>
Date: Fri, 6 Dec 2024 23:51:08 +0100
Subject: Day 6

---
 day6/data.txt    | 130 ++++++++++++++++++++++++++++++++++++
 day6/example.txt |  10 +++
 day6/go.mod      |   3 +
 day6/main.go     | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 go.work          |   1 +
 5 files changed, 340 insertions(+)
 create mode 100644 day6/data.txt
 create mode 100644 day6/example.txt
 create mode 100644 day6/go.mod
 create mode 100644 day6/main.go

diff --git a/day6/data.txt b/day6/data.txt
new file mode 100644
index 0000000..1992d65
--- /dev/null
+++ b/day6/data.txt
@@ -0,0 +1,130 @@
+....#.................#......................#..........................#..................#....##..#...........#.................
+...................................#...............................#......#..#...............................#....................
+..........................#................#......##.....#.....................................#...............#..#...............
+.......................................................................................................#..........................
+...................#....#.........................#..............#.....#......................................................#...
+.....#.........................................................................................................#..................
+.........................................................#....................#..#............#................#..................
+..............#...............#..................................................................#......#.........................
+.........#.....#.......#......#.......................#.............#..#........#.......#............#.......#....#..#.......#....
+........................#....#...............................................#...#.#.........................................#....
+.........................#........................................................................#.....................#.........
+.#..........#...#...............#..................#...#......#.................................#....................#.......#....
+............................................................#......#.........................................................#....
+.......................#...#..................#.#.............#......................#.............#..............................
+............................................................................................................#.........#...........
+....#..................###........#.............................#.#....................#..........#.....................#.........
+................................................................................................#.......................#.#.......
+..........................................................................#........#...#.................#.......#................
+..........................#.#..#.#...............................................#..........#..............................#......
+..............#........#.#...............#............................#..........#....................................#........#.#
+#..................................................................................................#...........#................#.
+...............................................#........................................#.................................#.......
+.....#..#......#.......#..............#........#........#...........................................................#.............
+.......#..........#.......#.#...........#................#.................................................#......................
+....#.....#...............#....#.......#...#.............................................................#...................#....
+............................................#....#.......#................................#......#......................#.....#...
+.....................#...................................#....#...........................................................#.......
+..#..............................#...........#...........................#.................................#......................
+........#.............................##...................#.....................#................................................
+................#.#.#......#...............................................#...###.........#....#.................................
+.......#.............#.............#...........#..#...............................#..................................#.....#.....#
+.....#...#.......#.........................................#..............................#........................#.............#
+...............................................#.....#..............................................................#.............
+.........#.......................................#.......................#...........#............................................
+.......................#.....#.....................................................#....................................#.........
+.............................#......................#.....................#..............#..#.......................#.............
+......#......................................#.......#.....................#.....#...........#..........#.....................#...
+..................................................#....................#.......#....#.......#...#.................................
+......................................#......#........#.....#........................................#.............#..............
+#......................#.#..............#.....#.........#...............................#...............................#.........
+#......#...............#.........................................................................................#..#.............
+.#..............................................#.................#.......#.......................................................
+...#.......#.....#.............#...................................................................................#..............
+..........................#........#........#.....................................#........................#..............#..#....
+.......#..........#.......#...................................................#.##.....#.#.........#....#.................#.......
+..##...................#.......................................#..............#.#........#........................................
+#.......#..............#...........#.....#....#....#............#........#..................................#.#.........#.........
+..................#.......................................................................................................#.......
+............................#.........#....................#...............................#..........#...........................
+.............#.....................................................................#.....#.................#......................
+...#...#............#..........................#..........................................#.......................................
+..#.............#.#........................#...#.......................#.........#....................##....#.....................
+...........................................................................................................#.........#...#........
+.............................#.#..........................................................................................#.......
+....................#........................#.#......#...............#......#.............................#......................
+....#...#.......#..................#..........................................................#........................#..........
+.#...........#..............................................#...........................................#.........................
+..............................#...........#...........................................#.........#...........................#....#
+............#.......#......#....#.......................................................................#.........................
+.........................................#...#..................#..................#.....................................#........
+................#..................#........#.........................#...................#......................................#
+............................................................#.....#........#......................................................
+..............................#............#.........................................#.............#.......#..#...................
+...#............#........................................................................#..................................#....#
+..............................#.......#.............#.................................................#...........................
+.....#.................................................#..........#...............................#..##..........................#
+.............#.........................................................#.............................#..#..............#........#.
+....................#...............#................................................................................#....#......#
+........#....#..#...........................................................................#................#..............#.....
+....#......................#...............#..........#......#.........#..^....#..........#..................#.......#............
+...........................#.#...................................................#...............................#................
+#..#.........................................................#.....#........................#.....................................
+.#.#....#.......................................#......#..........#................#..#...........................................
+...#.....#..........#...................#.......#............................#....................................................
+.............#......................................................#............#.....................#.....................#....
+...................#.............................................................................................#................
+...................#.....#...................................................................................................#....
+................#............#......................#.......#..................#..#.....................#..............#........#.
+#....#...................................................................#.......##....#..........#...............................
+.........................................#............#......#.......................#........#..............#.#..................
+.##........#.....#...........................................................................................#..............#.....
+#...........................................................#.......#....#......#..#...................................#..#.#.....
+.............#........................................#...............................#...........................................
+......................#..................................................................#..................................#.....
+...#.#........................................#.................................................................................#.
+.............#.......................#............................#.#................................#.......#..#...........#.....
+...#..#...............................................................................#................#..........................
+.......#.............................#............#..#........#.....#.........................#..................#................
+......#...............................................................................##.................................#....#...
+........#..................#.......................................................................#......#..........#............
+...........#.......#........#..........................................#........#..............#.................#.........#......
+...................#..............................#...............................#.....................#.....#...................
+.............#..#..................#.#..#.....#..#..........................................................................#.....
+..............................#...................................................#.......................#..............#........
+.......#......................#.............................#...........................#.....#...#.................#........#....
+.........#.......#....##..........................................................................................................
+........................................................................#......................#..................................
+.......................#..........##.#................................................#..#.....#......#......#.................#..
+......................................#......................................................................#....................
+.....................................#....#...............................................#...#.....#.......#...#...........#.....
+...................#..#................................................................................#..........................
+..............#.................#..............................#..............#...........#.#..................#...#.............#
+................#..#......#.........................#.....#.....#..............#..#.........................................#.....
+.....#.........................#........................................#.....#.......#...........#...................#...........
+......#....................##......................................................................................#..............
+............................................................................###...............................#...................
+#..................................#......#..............................................................................#.......#
+.....#...................#.....#............................................................#.....................#...#...........
+.......#......#........................#.....................#.#..##............#......#.................#.....................#..
+.....#..............#.................#........#..................#..#..........................##.....#..#...................#...
+........#................#................#...........#.........................................#....................#............
+.........#.........#....#................#........#........#...............#....#.................................................
+...........#...#............#..................#.............................#.#..#....................#.#........................
+.#............#..#..#................#.#................................................................##.............#..........
+...........#.......................#.........................................................#....................................
+..#..........................#...........#......#................................#.#..............................................
+............................................................#..................#...........#.....##.................#.............
+....#.........#............................##..........................................#.....#....#..........#....................
+..................#..............#........#........#....................#..............#....................#.....................
+....#...................................#.....................................................#.............#...................#.
+.........#...........#...#.............................#.............##..#................................................#.#.....
+............................##..............#................#..#........................................#....................#...
+.............................#.#......................................................##.....#..................................#.
+.............................................................................#..................#...#.................#...........
+........................#...........#..................#......#...................................................................
+.....#.......................#......#................#............#..................#.................................#..........
+#..........#...................................................................#...................#...#...............#..........
+....................#............................................#...............#........................##....#..#..............
+.#.....#............................#...............#.#.#..........................#.........#..............#.....................
+.............................#....................................#..#......#........................#............................
diff --git a/day6/example.txt b/day6/example.txt
new file mode 100644
index 0000000..b353984
--- /dev/null
+++ b/day6/example.txt
@@ -0,0 +1,10 @@
+....#.....
+.........#
+..........
+..#.......
+.......#..
+..........
+.#..^.....
+........#.
+#.........
+......#...
diff --git a/day6/go.mod b/day6/go.mod
new file mode 100644
index 0000000..a044ada
--- /dev/null
+++ b/day6/go.mod
@@ -0,0 +1,3 @@
+module stevenlr.com/aoc2024/day6
+
+go 1.22.2
diff --git a/day6/main.go b/day6/main.go
new file mode 100644
index 0000000..6461c20
--- /dev/null
+++ b/day6/main.go
@@ -0,0 +1,196 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"slices"
+	"strings"
+)
+
+func main() {
+	fmt.Println(part1(readData("example.txt")))
+	fmt.Println(part1(readData("data.txt")))
+	fmt.Println(part2(readData("example.txt")))
+	fmt.Println(part2(readData("data.txt")))
+}
+
+func part1(tiles [][]byte, x, y int) (visited int) {
+	directions := [4][2]int{
+		{0, -1},
+		{1, 0},
+		{0, 1},
+		{-1, 0},
+	}
+
+	dir := 0
+	dx := directions[dir][0]
+	dy := directions[dir][1]
+
+	for {
+		if tiles[y][x] != 'X' {
+			tiles[y][x] = 'X'
+			visited++
+		}
+
+		if y+dy < 0 || y+dy >= len(tiles) {
+			return
+		}
+
+		if x+dx < 0 || x+dx >= len(tiles[y+dy]) {
+			return
+		}
+
+		if tiles[y+dy][x+dx] == '#' {
+			dir = (dir + 1) % 4
+			dx = directions[dir][0]
+			dy = directions[dir][1]
+		} else {
+			x += dx
+			y += dy
+		}
+	}
+}
+
+type State struct {
+	x, y int
+	dir  int
+}
+
+func (state *State) GetDirection() (dx, dy int) {
+	directions := [4][2]int{
+		{0, -1},
+		{1, 0},
+		{0, 1},
+		{-1, 0},
+	}
+	dx = directions[state.dir][0]
+	dy = directions[state.dir][1]
+	return
+}
+
+func (state *State) GetNextPosition() (x, y int) {
+	dx, dy := state.GetDirection()
+	x = state.x + dx
+	y = state.y + dy
+	return
+}
+
+func (state *State) IsAboutToExit(tiles [][]byte) bool {
+	x, y := state.GetNextPosition()
+	if y < 0 || y >= len(tiles) {
+		return true
+	}
+	if x < 0 || x >= len(tiles[y]) {
+		return true
+	}
+	return false
+}
+
+func (state *State) HasObstacleInFront(tiles [][]byte) bool {
+	x, y := state.GetNextPosition()
+	return tiles[y][x] == '#'
+}
+
+func (state *State) Clone() State {
+	return State{
+		state.x, state.y, state.dir,
+	}
+}
+
+func (state *State) Rotate() {
+	state.dir = (state.dir + 1) % 4
+}
+
+func copyVisited(visited [][]byte) (visitedCopy [][]byte) {
+	visitedCopy = make([][]byte, len(visited))
+	for i, sublist := range visited {
+		visitedCopy[i] = make([]byte, len(sublist))
+		copy(visitedCopy[i], sublist)
+	}
+	return
+}
+
+func canReachExit(tiles [][]byte, visited [][]byte, state State) bool {
+	for !state.IsAboutToExit(tiles) {
+		visitedBit := byte(1) << state.dir
+		if visited[state.y][state.x]&visitedBit != 0 {
+			return false
+		}
+		visited[state.y][state.x] |= visitedBit
+
+		if state.HasObstacleInFront(tiles) {
+			state.Rotate()
+			continue
+		}
+
+		nextX, nextY := state.GetNextPosition()
+		state.x = nextX
+		state.y = nextY
+	}
+	return true
+}
+
+func part2(tiles [][]byte, startX, startY int) (positionsLooping int) {
+	state := State{startX, startY, 0}
+
+	visited := make([][]byte, len(tiles))
+	for i := range visited {
+		visited[i] = make([]byte, len(tiles[i]))
+	}
+
+	for !state.IsAboutToExit(tiles) {
+		visitedBit := byte(1) << state.dir
+		if visited[state.y][state.x]&visitedBit != 0 {
+			panic("Already visited???")
+		}
+		visited[state.y][state.x] |= visitedBit
+
+		if state.HasObstacleInFront(tiles) {
+			state.Rotate()
+			continue
+		}
+
+		nextX, nextY := state.GetNextPosition()
+		if visited[nextY][nextX] == 0 {
+			tiles[nextY][nextX] = '#'
+
+			stateCopy := state.Clone()
+			stateCopy.Rotate()
+			if !canReachExit(tiles, copyVisited(visited), stateCopy) {
+				positionsLooping++
+			}
+			tiles[nextY][nextX] = '.'
+		}
+
+		state.x = nextX
+		state.y = nextY
+	}
+
+	return
+}
+
+func readData(fileName string) (tiles [][]byte, startX, startY int) {
+	fp, err := os.Open(fileName)
+	if err != nil {
+		panic(err)
+	}
+
+	scanner := bufio.NewScanner(fp)
+
+	y := 0
+	for scanner.Scan() {
+		line := []byte(strings.TrimSpace(scanner.Text()))
+
+		x := slices.Index(line, '^')
+		if x != -1 {
+			startX = x
+			startY = y
+		}
+
+		tiles = append(tiles, line)
+		y += 1
+	}
+
+	return
+}
diff --git a/go.work b/go.work
index 492592d..4301221 100644
--- a/go.work
+++ b/go.work
@@ -6,4 +6,5 @@ use (
 	./day3
 	./day4
 	./day5
+	./day6
 )
-- 
cgit