From d588a22bfb5d3a848e2c04eddd1f54d601045e59 Mon Sep 17 00:00:00 2001 From: omagdy Date: Fri, 6 Dec 2024 21:16:15 +0200 Subject: Made isStuck blazingly fast by using an array of booleans to detect the cycle using the guard position and direction instead of of detecting cycle by count --- 2024/go/src/day6/main.go | 24 +++++++++++------------- 1 file changed, 11 insertions(+), 13 deletions(-) (limited to '2024/go/src/day6') diff --git a/2024/go/src/day6/main.go b/2024/go/src/day6/main.go index 2dc707e..f1505e9 100644 --- a/2024/go/src/day6/main.go +++ b/2024/go/src/day6/main.go @@ -114,34 +114,32 @@ func solve_part_one(data string) int { return trailCount } -func isStuck(grid *Grid, gPos [2]int, trials int) bool { - cnt := 0 - set := make(map[[2]int]struct{}) - set[gPos] = struct{}{} +func isStuck(grid *Grid, gPos [2]int) bool { + n, m := len(*grid), len((*grid)[0]) + visited := make([]bool, n*m*4) curOrientation := getOrientation((*grid)[gPos[0]][gPos[1]]) + visited[((gPos[0]*n)+gPos[1])*4+curOrientation] = true dx := [4]int{-1, 0, 1, 0} // Up, Right, Down, Left dy := [4]int{0, 1, 0, -1} - for trials > 0 { - prevSize := len(set) + for { nx := gPos[0] + dx[curOrientation] ny := gPos[1] + dy[curOrientation] if isValid(grid, nx, ny) { curPoint := (*grid)[nx][ny] if !isObstacle(curPoint) { gPos = [2]int{nx, ny} - // replaceCharGrid(grid, nx, ny, 'X') - set[gPos] = struct{}{} - if prevSize == len(set) { - cnt++ + if visited[((nx*n)+ny)*4+curOrientation] { + return true } + visited[((nx*n)+ny)*4+curOrientation] = true } else { curOrientation = turn90(curOrientation) } + } else { + break } - trials-- } - - return cnt >= len(set) + return false } func solve_part_two(data string) int { -- cgit v1.2.3