From 68f5cce6fb9f69c666471ee64d0c9d004f24e483 Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Tue, 17 Dec 2024 20:05:10 +0100 Subject: Day 16 --- day13/main.go | 2 +- day16/data.txt | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day16/example.txt | 15 ++++++ day16/example2.txt | 17 +++++++ day16/go.mod | 3 ++ day16/main.go | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++ day16/simple.txt | 9 ++++ go.work | 1 + 8 files changed, 325 insertions(+), 1 deletion(-) create mode 100644 day16/data.txt create mode 100644 day16/example.txt create mode 100644 day16/example2.txt create mode 100644 day16/go.mod create mode 100644 day16/main.go create mode 100644 day16/simple.txt diff --git a/day13/main.go b/day13/main.go index c4261c3..914c4c5 100644 --- a/day13/main.go +++ b/day13/main.go @@ -55,7 +55,7 @@ func (queue *CandidateQueue) Len() int { } func (queue *CandidateQueue) Less(i, j int) bool { - return queue.elements[i].Cnd.EstimateCost < queue.elements[i].Cnd.EstimateCost + return queue.elements[i].Cnd.EstimateCost < queue.elements[j].Cnd.EstimateCost } func (queue *CandidateQueue) Swap(i, j int) { diff --git a/day16/data.txt b/day16/data.txt new file mode 100644 index 0000000..2b7a59d --- /dev/null +++ b/day16/data.txt @@ -0,0 +1,141 @@ +############################################################################################################################################# +#.....#.........#.............#.............................#...........#.............#.......#.....#...#...........#.........#.......#....E# +#.#.#.#.#.#######.#####.#####.#.#############.###.###.#.###.#.#####.###.#######.#.###.#.###.###.###.#.#.#.#######.#.#.#######.#.###.#.#.###.# +#.#.#...#...#.....#...#.....#.......#.....#.....#.#...#...#.#.#.....#.#.......#.#...#...#.#...........................#...#...#.#.#.#.#...#.# +#.###.###.#.#.#####.#.#####.###.###.#.###.#.#.#.#.#.###.#.#.#.#.#####.#.#####.#.#.#.#####.#######.###.#######.#######.#.#.#.#.#.#.#.#.###.#.# +#...#.#...#.#.....#.#.#...#.....#.....#.#...#...#.#.....#.#.....#...#.........#...#.#.......#...#.#...#...#...#...#...#.#.#...#...#.#...#.#.# +#.#.#.#.#.#.###.#.#.#.#.#.#####.#######.#####.###.#######.###.#####.#.###########.#.#.#####.#.#.#.#.###.###.###.#.#.###.#.###.###.#.#.#.###.# +#.#.#...#.#.....#.#.#...#.....#...#.......#...#.....#...#.........#.#.......#.....#.#.#.....#.#.#.#.#...#...#...#...#.#.#.......#.#...#.....# +#.#.#.###.###.#.#.#.#######.###.#.#####.###.#.#.#####.#.#.#.#.###.#.#######.###.#.#.###.###.#.#.#.#.###.#.###.#######.#.#.###.#.#.###.#####.# +#.#.#...#...#.#.#.#.....#...#.....#.....#...#...#.....#.#.#.....#...#.....#...#.#.#...#...#.#.#...#.....#.#...#...........#...#.#.#...#...#.# +#.#.#.#.#.#.#.#.#.#.#####.#.#.#####.#####.#.#.###.#####.#.#.#.#.#####.###.###.#.#####.#.#.###.#.#######.#.#.###.###.#.###.#.#.#.#.#.#.###.#.# +#.#...#.#...#...#.#.#...#.#.#.#...#.#...#...#...#...#...#.#.#.........................#.#.#...#.#.....#.#...#.....#.#.#...#.....#.#.#...#...# +#.###.#.#.#####.#.###.#.#.###.#.#.#.#.#.###.#.#####.#.###.###.###.#.###.#####.#.###.#.#.#.#.#####.#.#.#.###########.#.#.#.#.#####.#.#.#.###.# +#.....#...#...#.#...#.........#.#...#.#...#.#.#.....#.#.....#.#.....................#.#.#.#.#.....#.#.#.......#.....#.#.#...#.....#...#...#.# +#.#.#.###.#.#.#.###.#.###.#.###.#####.###.#.#.#.#####.#.###.#.#.###.#.###.#.#######.#.###.#.#.#####.#.#######.#.###.#.#.#.#.#.#.#####.###.#.# +#.#.....#.#.#.#...#...#.#.#...#.....#.#.#...#.#.#.#...#...#.#.....#.....#...#.....#.......#...#.....#...#...#...#...#.#...#...#.#...#...#.#.# +#.###.#.#.#.#.###.#####.#.###.#.###.#.#.#.#.###.#.#.###.#.#.#####.#.###.#######.#.#####.#####.#.#######.#.#.#####.#.#.###.#####.#.###.#.#.#.# +#.#...#...#.#.#...#.....#.#...#...#.....#...#...#.......#...#...#...#.#.#.......#...#...#...#.#.........#.#.......#.#...........#...#.#...#.# +#.#.#.#.#.#.#.#.#.#.#.###.#.#####.#########.#.###.###########.#.#####.#.#.###.#####.#####.#.#.#.#.#######.#####.###.###.#.#.#####.#.#.#.##### +#...#.#.#...#...#...#.#...#.#.#.....#.....#...#...#.......#...#...#.....#.#...#...........#.#.#.#...#...........#.#...#.#...#.....#.#.#.#...# +#####.#.#.#######.###.#.###.#.#.#####.###.#.#######.#####.#.#####.#.#.#.#.#.#.#############.#.#.#####.#.###.#####.###.#.#########.#.#.###.#.# +#.....#.#.....#...#.#.....#.#...#.....#.#.#.#.......#...#...#.....#.#.#.#.#.......#.....#...#.#...#...#.....#.......#.#.........#.#.........# +#.#.###.#####.#.###.#######.#.###.#####.#.###.#####.#.#.#####.#####.#.#.#####.###.#.#.###.#######.#.###.#.#########.#.#######.#.###.#.###.#.# +#.#.....#...#.#.#...#.....#.#.#...#.....#...#.....#...#.....#...#...#.......#.#...#.#.#...#.......#.#...#.#.................#...#...#...#.#.# +#.#######.###.#.#.#.#.###.#.#.#.#####.#####.#####.#.###.#####.#.###########.#.#.#####.#.#####.###.#.#.#.#.#.#####.#.###.#####.###.###.#.###.# +#.......#.#...#.#.#.#...#...#.#.....#.#...#.#.....#.#...#...#.#.#.....#...#.#.#...#...#.....#...#.#...#.#...#...#.#...#.....#...#...#.#...#.# +#######.#.#.#.#.#.#.###.###########.#.#.#.#.#.#####.#.###.#.#.#.#.###.###.#.#.###.#.#######.#.#.#######.#######.#.#####.###.###.###.#.###.#.# +#.....#...#.#.#.#.#...#.....#.....#.#.#.#...#...#...#.#...#.#.#...#...#...#.#.#...#.......#.#.#.......#...#.....#.#...#.#.#.....#...#...#...# +#.#####.###.#.#.###.#######.#.###.#.#.#.#.#.###.#.#.###.###.#######.###.#.#.###.###.###.#.#.#.#######.###.###.#.#.#.#.#.#.#.#####.#.###.###.# +#.......#...#.#...#.....#.#.#.....#.#.#.#.#...#.#...#...#...........#.#.....#...#.#.#.#.#.#.#.......#...#.....#.#...#...#.........#...#...#.# +#.#######.###.###.#.#.#.#.#.###.#.#.#.#.###.#.#.###.#.###.###.#.#.###.#.#####.###.#.#.#.#.#.#####.###.#########.#.#############.#####.###.### +#.........#...#...#.#.#.#.#...#.#.#...#...#.#.......#.#.#.#...#...#...........#.......#.#.#.........#.....#...#.#...#.........#.#.....#.#...# +#.#######.#.###.###.#.#.#.#.#.#.#.###.###.#.#######.#.#.#.#.#.###.###################.#.#######.###.###.#.###.#.#.#.#.#.#####.#.#.#####.###.# +#.#.......#.#.#.#...#.#...#.#.#.#.#.....#...#.....#...#...#.#...#.#...#...............#...........#.#...#.....#.#.#.#.#.....#.#.#.#.......#.# +#.#.#######.#.#.###.#.###.#.#.#.#.#.#####.###.###.#.###.###.###.###.#.#.#############.#.###.#######.#.#######.#.#.#.#######.#.#.#.#.#####.#.# +#.#.#...#.....#...#.#.#...#.#...#.#.#.........#...#...#...#.#.#.........#.......#...#.#...#...#.......#.#.....#...#.........#...#.#...#.#.#.# +#.#.#.#.#########.#.#.###.#.#.###.#.#.#########.#####.###.#.#.###########.#####.###.#.#######.#.#####.#.#.#############.#####.###.###.#.#.#.# +#.................#.#...#.#...#.#.#.#.......#.#.#.....#...#.#.......#.......#.......#...#...#.#.#...#...#.#...#.........#...#...#...#.#...#.# +#.#####.#.#########.###.#######.#.#.#######.#.#.#.#####.###.#.#####.#######.#.#########.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.#.#.#.#.###.#.#.###.# +#.#...#...#.....#...#.#.#.......#.#...#...#.#.........#.#.....#.........#...#.#...#...#.#.#.#...#.#.#.#.#.#.#.#.#...#.#.#.#...#.....#.#.#.#.# +#.#.#####.#####.#.###.#.#.#.#####.###.#.#.#.#######.#.###.###.#########.#.#.###.#.#.#.#.#.#.#####.#.###.#.#.#.#.#.#.#.###.###########.#.#.#.# +#...#...#.....#...#...#.#.#.....#.....#.#...#.....#.#...#...#...#...#.#...#.#...#...#.#...#.......#...#.#.#.#.#.#.#.#...#.#.#.........#...#.# +#.###.#.#####.#.###.#.#.#.#####.#######.###.#.###.#.###.###.#.#.#.#.#.#.#.#.#.#######.#####.#########.#.#.###.#.#.#.###.#.#.#.#######.#####.# +#...............#...#.#.....#.....#.....#.#.#.#.#.#...#...#.#.#...#.#.#.#.#.#...#.........#...#.#.....#.....#.#...#.#...#.#...#...#...#.....# +#.#.###.#.#.#.#.#####.#######.#####.#####.#.#.#.#.###.#.#.#.#.#####.#.#.#.###.###.#.#.###.#.#.#.#.#########.#.#####.#.###.#.###.#.#.#.#.###.# +#.#...#.#.#...#...........#...#.....#...#...#...#.#...#.....#.#...#.#...#.........#.#.#.#...#.#.#.......#...........#...#.#.................# +###.###.#.#####.#.#########.#.#.#####.#.#####.###.#.#####.#.#.#.###.#.#.#.#####.###.#.#.#####.#.#######.#.#####.#.#.###.#.#.#.#######.#.#.#.# +#...#...#.#.....#.#...#...#.#.#.......#...#...#...#.#.#...#.#...#...#.#.#...#.#.#.#...#.....#.....#...#.#.#...#...#...#...#.#.#.....#.#.#...# +#.###.###.###.#.###.#.#.#.#.#.###########.#.###.###.#.#.###.#####.###.#.###.#.#.#.#########.###.###.#.#.###.#.#######.#.#.#.#.#.###.#.#.#.### +#.#.#.#.......#.....#.#.#...#.....#.....#...#.#.......#...........#.#.#.......#.#.............#.#...#.#...#.#.......#.#...#.#.#.#...#.#.#.#.# +#.#.#.###############.#.#########.#.#.#.#####.#####################.#.###.#####.#.###.#####.###.#.###.#.#.#.#.#.#.#.#.#######.#.###.###.#.#.# +#...#...............#.#.#.........#...#.......#.#.........#...#.................#...#.....#.#...#.#.#.#.#.#.#...#.#.#.#.....#.#...#.....#.#.# +###.###############.#.#.#.#####.#.###.###.###.#.#.#######.#.#.###.#################.#####.###.###.#.#.#.#.#.#####.###.#.###.#.###.#######.#.# +#.#.#.........#...#.#.#.#.#...#.#...#...#.#.......#.....#...#...#...#.......#.....#.#...#.......#.....#.#.#...#.#.....#...#...#...#.#.....#.# +#.#.#.#######.#.#.#.#.#.#.#.#.#.###.#.###.#.#####.#.###.#######.###.#.#####.#.#.#.###.#.#.#######.#.###.#.###.#.#########.#.###.###.#.#.###.# +#.#.#...#...#...#.#.#...#...#.#.#...#.#...#...#...#.......#.....#...#.....#.#.#.......#.#.#.......#...#.#...#...#.........#.#.............#.# +#.#.#.#.#.#######.#.#.#######.###.#####.###.###.###.###.###.###.###.#.###.#.#.#########.###.#########.#.###.###.#.#########.#.#####.#.#.#.#.# +#.#.#.#.#.....#...#.........#...#.#.....#...#...#.#...#...#.......#...#...#.#.........#.#...#.......#.#.#.#...#...#.........#.....#.....#...# +#.#.###.#.#.###.###########.#.#.#.#.#.###.###.###.###.###.#######.###.#.###.###.#####.#.#.###.#.###.#.#.#.#.#######.#########.###.#####.###.# +#.#.....#.......#.....#...#.#.#.#.#.#.#.....#.#.....#.#.#.......#.....#...#...#.#...#.#.#...........#.#...#.......#.#.....#.......#.......#.# +#.#######.#####.#.#.#.#.#.#.#.#.#.###.#.#####.###.#.#.#.#.#####.###.#.#.#.###.#.#.#.#.#.###.###.#####.#####.#####.#.#.#####.#.#####.###.#.### +#.....#.#.....#...#.#...#.#.#.#.#.....#.#.....#...#.#...#.#.#...#...#.#...#...#...#.#.#.#.......#...#.............#...#.....#.#.........#...# +#.###.#.#####.#####.###.#.#.#.#.#.#######.#####.#####.###.#.#.#.#.#####.###.#######.#.#.#.#######.#########.#.#######.#.#######.#######.###.# +#...#.#.............#.....#.#.#...#.......#.....#.....#...#.#.#.#.....#.#...#.......#.#.#.....#...#.........#.#.......#.....#.......#.......# +#.#.#.###.#.#########.#####.#######.#########.###.#####.###.#.#.#####.#.#.###########.#.#####.#.###.###.###.#.#.###########.#.#.#####.#.###.# +#.#.#...#.#...#.............#.......#.......#.#...#...#.#...#.#.....#.#.#...#.....#...#.......#.....#.......#.#.....#.....#...#.....#.#...#.# +#.#.#.#.###.#.#.#####.#####.#.#######.#####.#.#.###.###.###.#.###.#.#.#.###.#.###.#.###########.#####.###.###.#####.#.###.#####.###.#.#.###.# +#...........#.#.#...#.#.....#.#.......#.....#.#.....#...#...#.....#.#.#...#.#.#...#.#...........#...#.#...#.......#...#.....#...#.#.#.#.....# +#.#.#.#########.#.#.#.#.###.#.#######.#.#####.#.#####.###.#.#######.#.###.#.#.#.###.#######.#.###.#.#.#.###.#.#.#######.#####.#.#.#.#.#.##### +#.#.#.#.........#.#...#...#.#...#.....#...#...#.#.....#.....#.....#.#.....#.#.#.#.#...#...#...#...#.#.#...#.#.#.........#.#...#...#.#.#.#...# +#.#.#.#.#########.###.###.#####.#.#######.#.###.#.#####.###.###.###.#####.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#.#########.#.###.#.#.#.#.###.# +#.#.....#.....#...#...#.#.....#...#.....#.#.....#.#.....#.#.....#...#.#.#.#...#.#...#.#.#.#.....#.....#...#.#...#.........#...#...#...#.....# +#.###.###.#.#.#.###.###.#####.#####.###.#.#######.#.#####.#.#.#.#.###.#.#.#####.#.###.#.#.#######.###.#.#####.###.#######.#.#.#.###########.# +#.......#.#.#...#.#.....#...#.#...#.#...#...#.....#...#.....#...#.#...#.#.#.....#...#...#.......#.#...#.....#...#...#.....#...#.....#...#...# +#####.#.###.#####.#####.#.#.#.#.#.#.#.#####.#.#######.#.#.###.###.#.#.#.###.#######.###########.#.#########.###.#####.#####.###.#.#.###.#.### +#.....#.....#...#.....#...#.#...#...#.....#.#...#.....#.#.....#.#...#.#...#.#...#...#.......#...#.#...#...#.#...#.....#.....#...#.#.#...#...# +#.###.#######.#.#####.###.#.###########.###.#.#.#.#####.#######.#####.###.#.#.###.#######.#.#.###.#.#.#.#.#.#.###.###.#.#.###.#.#.#.#.#.###.# +#...#.#.......#.......#.....#...#.......#...#.#.#.#...#.#.........#.#...#...#...#.......#.#.#.#.#...#...#.........#...#.#.....#...#...#.#...# +#.#.#.#.###########.###.#######.#.#.#####.#####.#.#.#.#.#.#######.#.###.#####.#.#.#####.#.#.#.#.#.#############.#######.#.###.#####.#####.### +#.#.#.#.#.....#...#.....#.....#.#.......#.....#.#.#.#.#.#.....#.......#.....#.#...#...#...#.#.#.#...#...#.......#.........#...#...#.#.......# +###.#.#.#.###.#.###.#.#.###.#.#.#.#####.#####.#.#.#.#.#.#####.#.###########.#######.#.#####.#.#.###.#.#.#.#######.#######.#####.#.###.#####.# +#...#...#.#...#.....#.#...#.....#.....#.....#.#.#.#.#.#.......#...#.......#.......#.#...#...#.#...#...#.#...#...#...#.....#.....#...#.#...#.# +#.###.###.#.###.#.#.#.#.#.#.###.#.###.#####.#.#.#.#.###########.###.#####.#######.#.#.#.#.#.#.#.#.#####.###.#.#.###.#####.#.#######.#.#.#.### +#.#.......#.#...#...#...#...#...#.#.#.....#...#.#.#.........#...#...#...#...#.....#.#...#...#.#.#.#.........#.#...#...............#...#.#...# +#.#.#######.#.###############.###.#.#####.#####.#.#.#######.#.###.#####.###.#.#.###.#.#######.#.###.#######.#.###.#####.#.#############.###.# +#...#.............#.........#.#...#.....#.......#.#.#.....#.#...#.........#.#.......#.........#...#.......#.#.#.#.....#.#...#...........#.#.# +#.###.#.#####.#.#.#######.#.#.#.#.#.###.#########.#.#####.#.###.#########.#.###################.#.#######.###.#.#####.#.#####.###########.#.# +#...#.#...#...#.#...#.....#.#...#...#.....#.......#...#...#...#.#.#.....#.#...........#.........#.......#...#.#.......#.....#.....#.......#.# +###.#.###.###.#.###.#.#####.#####.###.###.#####.#####.#.###.###.#.#.###.#.###.#######.#.#####.#.###.###.###.#.#.###.#.#.#.#.#####.#.#####.#.# +#.#.#...........#...#.#...#.#.......#.#...#...#.#...#.#...#...#...#.#...#.#.#.....#.....#...#.#.#.#.#.....#...#.#...#.#...#.....#.#...#.....# +#.#.#.#####.#######.#.#.#.#.#########.#.###.#.#.#.#.#.###.###.###.#.#.###.#.#####.#####.#.#.#.#.#.#.###########.#####.#.###.#####.###.#.#.#.# +#.#.#.....#...#...#.#.#.#...#.........#.#...#.#.#.#.#.......#.....#.#...#.#.#...#.....#...#...#...#.#.......#...#.....#...#.....#...#.#...#.# +#.#.#.#.#####.#.#.#.#.#.#####.#########.#.###.#.#.#.#.#############.###.#.#.#.#.#####.#####.#.###.#.#.###.#.###.#.###########.#.###.#.###.#.# +#...#.#.#.....#.#.#...#.#.....#...#.......#...#.#.#.#.#...............#...#...#.....#.....#...#...#.#...#.#.....#.#.#.......#.#.....#...#.#.# +#.#####.#.#####.#.#####.#.#####.#.#.#########.#.#.#.#.#.#################.#.#######.#####.#####.###.###.#.#####.#.#.#.#.###.#.#######.#.#.#.# +#.......#.......#.#...#.#.....#.#.#.#.......#.....#.#.#.............#...#.#...#.....#.........#.#.#.....#.....#.#.#.#.#.#...#.........#.#.#.# +###.#########.#.#.#.#.#.#####.#.#.#.#.#####.#####.#.#########.#####.#.#.#.###.#.###.#.#.#####.#.#.###########.###.#.#.#.#.#############.#.#.# +#...#.........#.#...#.#.....#.#.#.#.#.....#.......#.....#...#...#...#.#.#...#.#.#.#.#.#.....#.#.......#.....#.....#.#.#.#...........#.#.#.#.# +#.###.#######.#.#####.#####.#.###.#.#####.#############.#.#.###.#.###.#.###.###.#.#.#######.#.#######.#.###########.#.#.###########.#.#.#.#.# +#...............#...#.#.......#...#...#...........#...#...#.......#...#...#...#.#...#.....#.#...#.#...#.#...#.....#...#...#...#.....#...#.#.# +#.#.#.#.#.###.###.#.#.#########.#.#.###.#########.#.#.###.#########.#####.###.#.###.#.###.#.#.#.#.#.###.#.#.#.###.#.#####.#.###.#####.###.#.# +#.....#...........#.#.....#.....#.#.#...#.....#...#.#...#...#...#...#.....#...#...#...#.#...#.#.....#.....#.#...#.#.#...#.#.........#.#...#.# +###.#.#######.#####.#####.#.#.#.###.#.###.###.#.###.###.#.###.#.#.###.#####.#####.#####.###.#.#####.#####.#.###.#.#.#.#.#.#.#######.###.###.# +#...#.#...#...#...........#...#.....#...#.#.#.#...#...#.......#...#.........#.....#...#.....#.#...#.....#.#.....#...#.....#...#...#...#.#...# +#.###.#.#.#.#.#########.#.#####.#######.#.#.#.###.###.#############.###.#.#####.###.#.###.###.#.#.#####.#.###########.#########.#.###.#.###.# +#...#...#...#.#.......#.#.....#.#.....#.#.#...........#.#.........#...#.#.....#...#.#.......#...#.#.....#.#.........#...........#.#.........# +###.#########.#.#####.#.#####.#.#.###.#.#.#############.#.#######.###.#.###.#.###.#.###.###.#####.#.#####.#.###.#####.###########.#.#####.#.# +#.#.#.......#.#.....#.#.......#.#...#.#.#.....#.........#.#.....#.#...#.....#.#...#.#.#.#.......#.#.#.#...#.#...#...#.#.....#.....#.......#.# +#.#.#.#######.###.###.#########.###.#.#.#####.#.#######.#.#####.#.#.#########.#.#.#.#.#.#####.###.#.#.#.#####.#.#.#.#.#.###.#.#############.# +#...#...#.....#...#...#.......#...#.#.#.....#.#.....#...#.....#.#...#.......#.#.#.#.#.....#...#...#.........#.#.#...#.#.#.#.#.#.#.........#.# +#.###.#.#.###.#.###.###.#######.###.#.#####.#.#####.#.#.#.#.#.#.#######.###.#.#.#.#.#####.#####.#.#.###.#.#.#.#.#.#.###.#.#.#.#.#.###.#####.# +#.#...#.#...#.#.#.#.#...........#...#.#.....#.#.......#.#.#.#.#...#...#.#...#...#.#...#.....#...#.#...#...#...#.#.#.#...#.................#.# +#.#####.###.#.#.#.#.#.###########.###.#.#####.###.#.#.###.#.#.#.#.#.#.#.#.###.#####.#.#.###.#.###.###.###########.#.#.###.###.#####.###.#.#.# +#.......#...#.#...#.#.......#.....#.#...#...#...#...#...#...#...#.#.#...#...#.#...#.#...#.#.....#.#.#.#...........#.#...#.#...#.....#...#...# +#########.###.###.#.#.#######.#####.#####.###.#.###.###.#.#.#####.#.#######.###.#.#.###.#.#####.#.#.#.#.###########.#.#.#.###.#.###.#.####### +#.........#...#...#.#.#.......#...........#.....#.#.#.#...#.#...#...#.....#.....#.#.#...#.......#...#.#.#.........#.#...#...#...............# +#.#######.###.#.###.#.#.#######.#######.###.#####.#.#.#####.#.#.###.#.#.#########.#.#.###.###.#####.#.#.#.#######.#.#.#####.#.#.#.#####.#.### +#...#...#.#.....#...#.#.#.....#.#.....#.#...#.......#.......#.#...#...#.........#.#.#.#.....#.......#.#.#...#.....#.#.....#...#.#.#.....#...# +###.#.#.#.#.#.###.#####.#.###.#.#####.#.#.###.#########.#####.###.#.#####.#####.#.#.#.#####.#########.#.###.#.###.#.#.###.#######.#.#####.#.# +#...#.....#.....#.#.....#.#.#...#.....#.#...#...........#...#...#.....#...#.....#.#.#.....#.........#.#.#...#.#.#.#.#.#...#.....#.#...#...#.# +#.###.#.#####.#.#.#.#####.#.#####.#####.###.###.#########.#.###########.#.#######.#######.#####.###.#.#.#.###.#.#.#.###.###.###.#.###.#####.# +#.#.....#.....#.#.#.....#.#.....#.#...#...#...#...........#...........#.#.#.......#.......#.#.......#...#.#...#...#...#.....#...#...#.#.....# +#.###.#.#.#.#.#.#.#####.#.#.#.#.#.#.#.###.###.#####.#.#####.#########.#.#.#.#######.#######.#.#########.###.###.#####.#.#####.#####.#.#.#.#.# +#.........#.....#.....#.#.#.#.#...#.#.......#.....#.#.........#.......#.#.......#...#.......#.#.............#.#.....#.#...#...#.....#...#.#.# +#.###.#.###.#.#####.#.#.#.###.###.#.#########.###.#.#.#######.#.#######.#######.#.###.#.#####.#.#########.###.#.#####.#.###.###.#.#.#####.#.# +#...#.....#.....#.....#.#...#...#.#.#.......#.#...#.#.#...#...#.#.............#...#...#.#.....#.#...#...#.#.....#.....#.#...#...#.#...#.....# +###.#.#.#.###.###.#.###.#.#.###.#.#.#.#####.###.###.#.#.#.#.###.###.#######.#.#####.###.#.#####.#.#.#.###.#.#.###.###.#.#.###.###.###.#.##### +#.#.#...#...#.....#.#...#.#.#...#...#.#...#...#...#.......#...#...#.#.......#.#.......#.#.#...#...#...#...#.#.....#...#.#.#.....#.#...#.....# +#.#.#.#.###.#.#######.#####.#.#.#.###.#.#.###.#.#.#.#########.###.###.#.#####.#.#####.#.#.#.#.#######.#.#####.#######.#.#.#####.#.#.#######.# +#.....#...#.#.......#...#...#...#.#...#.#.........#.#...#...#...#.#...#.......#.....#.#.#.#.#.#...#.#.#.......#.....#...#...#...#.#.#.....#.# +#.###.#.#.#.#.#####.###.#.###.#.#.#.###.#.###########.#.#.#.###.#.#.#.#.#####.#####.#.#.#.#.#.#.#.#.#.#.#####.#.###.#.#####.#####.#.#.#.###.# +#.#.......#.#.#.......#...#.............#.#...#.......#.....................#.......#.......#...#...#.....#.....#...#.....#.....#.#.#.#.....# +###.###.###.#.#.#####.#####.#.#########.#.###.#.###.#######.#.#########.#.#.#######.###.###############.#.###.###.###.#########.#.#.#.####### +#...#...#.......#...#...#...#.#.......#.#.#...#.#.........#.#.#...#.....#.#.......#.....#...............#...#...#.#...#.........#.#.#.#.#...# +#.###.#.#####.###.#.###.#.#.#.#.#####.#.#.#.#.#.###.#.#####.#.#.#.#.###.#.#######.#####.#.#########.#.#.###.#.#.#.#####.#########.###.#.#.#.# +#.#...#...#.......#.........#...#...#.#.#...#.#.....#.#...#.#...#...#.....#.....#...#...#.....#.#...#.#...#.....#.....#...#.........#.#...#.# +#.#.#####.###.#############.#####.###.#.#############.#.#.#.#.#######.#.###.#######.#.#.#####.#.#.#####.#.###########.#.#.###.#####.#.#####.# +#...#...#...#.#.....#.........................#...#...#.#...#.......#.#.........#...#.......#...#.#...#.#.........................#.#.......# +#.###.#.###.###.###.#.###.###.###.#.###.#####.#.#.#.###.#############.#.#######.#.###.#.#######.#.#.#.#.#####.#.###########.#.###.#.#######.# +#S....#...#.......#.....#.......#...........#...#.....#.........................#.....#.........#...#.......#...............#.....#.........# +############################################################################################################################################# diff --git a/day16/example.txt b/day16/example.txt new file mode 100644 index 0000000..faf2ad6 --- /dev/null +++ b/day16/example.txt @@ -0,0 +1,15 @@ +############### +#.......#....E# +#.#.###.# ###.# +#.....#.#...#.# +#.###.#####.#.# +#.#.#.......#.# +#.#.#####.###.# +#...........#.# +###.#.#####.#.# +#...#.....#.#.# +#.#.#.###.#.#.# +#.....#...#.#.# +#.###.#.#.#.#.# +#S..#.....#...# +############### diff --git a/day16/example2.txt b/day16/example2.txt new file mode 100644 index 0000000..d4b8fad --- /dev/null +++ b/day16/example2.txt @@ -0,0 +1,17 @@ +################# +#...#...#...#..E# +#.#.#.#.#.#.#.#.# +#.#.#.#...#...#.# +#.#.#.#.###.#.#.# +#...#.#.#.....#.# +#.#.#.#.#.#####.# +#.#...#.#.#.....# +#.#.#####.#.###.# +#.#.#.......#...# +#.#.###.#####.### +#.#.#...#.....#.# +#.#.#.#####.###.# +#.#.#.........#.# +#.#.#.#########.# +#S#.............# +################# diff --git a/day16/go.mod b/day16/go.mod new file mode 100644 index 0000000..5f0155e --- /dev/null +++ b/day16/go.mod @@ -0,0 +1,3 @@ +module stevenlr.com/aoc2024/day16 + +go 1.23.3 diff --git a/day16/main.go b/day16/main.go new file mode 100644 index 0000000..fd8b346 --- /dev/null +++ b/day16/main.go @@ -0,0 +1,138 @@ +package main + +import ( + "bufio" + "container/heap" + "fmt" + "math" + "os" + "strings" +) + +func main() { + fmt.Println(7036, 45) + fmt.Println(part1And2(readData("example.txt"))) + fmt.Println(11048, 64) + fmt.Println(part1And2(readData("example2.txt"))) + fmt.Println(89460, 504) + fmt.Println(part1And2(readData("data.txt"))) +} + +type Position struct { + x, y int +} + +type PositionDir struct { + x, y int + dir int +} + +type Candidate struct { + x, y int + dir int + cost int + visited []PositionDir +} + +type CandidateQueue struct { + elements []Candidate +} + +func (queue *CandidateQueue) Len() int { + return len(queue.elements) +} + +func (queue *CandidateQueue) Less(i, j int) bool { + return queue.elements[i].cost < queue.elements[j].cost +} + +func (queue *CandidateQueue) Swap(i, j int) { + queue.elements[i], queue.elements[j] = queue.elements[j], queue.elements[i] +} + +func (queue *CandidateQueue) Push(x any) { + queue.elements = append(queue.elements, x.(Candidate)) +} + +func (queue *CandidateQueue) AddElement(candidate Candidate) { + heap.Push(queue, candidate) +} + +func (queue *CandidateQueue) Pop() any { + if len(queue.elements) == 0 { + return nil + } else { + elmt := queue.elements[len(queue.elements)-1] + queue.elements = queue.elements[:len(queue.elements)-1] + return elmt + } +} + +func cloneVisited(v []PositionDir) []PositionDir { + clone := make([]PositionDir, len(v)) + for i, p := range v { + clone[i] = p + } + return clone +} + +var directions = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}} + +// Originally I had implemented A* for part1. But because of part2 I modified it to be +// dumber. I wish we had full requirements from the start so I wouldn't waste time... + +func part1And2(maze [][]byte) (scorePart1, scorePart2 int) { + endX, endY := len(maze[0])-2, 1 + startX, startY := 1, len(maze)-2 + + queue := new(CandidateQueue) + heap.Push(queue, Candidate{startX, startY, 0, 0, []PositionDir{{startX, startY, 0}}}) + minCost := math.MaxInt + visitedCost := make(map[PositionDir]int) + onOptimalPath := make(map[Position]bool) + + for queue.Len() > 0 { + candidate := heap.Pop(queue).(Candidate) + posDir := PositionDir{candidate.x, candidate.y, candidate.dir} + + alreadyVisitedCost, alreadyVisited := visitedCost[posDir] + if alreadyVisited && alreadyVisitedCost < candidate.cost { + continue + } + visitedCost[posDir] = candidate.cost + + tryDirection := func(dir int, cost int) { + fwdX := candidate.x + directions[dir][0] + fwdY := candidate.y + directions[dir][1] + realCostFwd := candidate.cost + cost + if maze[fwdY][fwdX] != '#' && realCostFwd <= minCost { + if fwdX == endX && fwdY == endY && realCostFwd <= minCost { + for _, p := range candidate.visited { + onOptimalPath[Position{p.x, p.y}] = true + } + minCost = realCostFwd + } else { + visited := append(cloneVisited(candidate.visited), PositionDir{fwdX, fwdY, dir}) + c := Candidate{fwdX, fwdY, dir, realCostFwd, visited} + heap.Push(queue, c) + } + } + } + + tryDirection(candidate.dir, 1) + tryDirection((candidate.dir+1)%4, 1001) + tryDirection((candidate.dir+3)%4, 1001) + } + + return minCost, len(onOptimalPath) + 1 +} + +func readData(fileName string) (maze [][]byte) { + fp, _ := os.Open(fileName) + scanner := bufio.NewScanner(fp) + + for scanner.Scan() { + maze = append(maze, []byte(strings.TrimSpace(scanner.Text()))) + } + return +} diff --git a/day16/simple.txt b/day16/simple.txt new file mode 100644 index 0000000..75f51ed --- /dev/null +++ b/day16/simple.txt @@ -0,0 +1,9 @@ +##### +# E# +# # # +# # # +# # # +# # # +# # # +#S # +##### diff --git a/go.work b/go.work index b5be743..60d840c 100644 --- a/go.work +++ b/go.work @@ -8,6 +8,7 @@ use ( ./day13 ./day14 ./day15 + ./day16 ./day2 ./day3 ./day4 -- cgit