{"id":1130,"date":"2024-12-07T10:31:09","date_gmt":"2024-12-07T08:31:09","guid":{"rendered":"https:\/\/www.juustila.com\/antti\/?p=1130"},"modified":"2024-12-07T10:31:11","modified_gmt":"2024-12-07T08:31:11","slug":"advent-of-code-day-6-guard-gallivant","status":"publish","type":"post","link":"https:\/\/www.juustila.com\/antti\/2024\/12\/07\/advent-of-code-day-6-guard-gallivant\/","title":{"rendered":"Advent of Code Day 6 – Guard Gallivant"},"content":{"rendered":"\n

First part of today’s puzzle<\/a> was to find out the path of the guard on a map shown below, and count how many distinct positions will the guard visit before leaving the mapped area.<\/p>\n\n\n\n

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...<\/pre>\n\n\n\n
Guard starts walking upwards from the ^<\/code> and the #<\/code> ‘s are blocks on the path, and when the guard meets one, she always turns right in front of the block.<\/p>\n\n\n\n
The part 1 was quite straightforward to implement and didn’t take too long.<\/p>\n\n\n\n
In part 2 the goal was to find out in how many places a new<\/em> obstacle (#<\/code>) can be placed, so that it causes the guard to walk in circles<\/em>. <\/p>\n\n\n\n
I was working on different solutions, considering using a graph again to see if the graph contains a cycle (there are algorithms for that). Since yesterday was quite a busy day otherwise, I couldn’t focus on solving the puzzle, hence I am one day behind.<\/p>\n\n\n\n
Today morning I continued with the part 2 with the ideas I had been thinking about, not needing a Graph<\/code>.  One can detect a cycle when the same turning point is met the second time<\/em>. So I use a Set<Turn><\/code> structure, containing the point and the direction where the turn was taken. Set doesn’t allow you to add a new item that is already in the set, and if this happens, it indicates a cycle in the path.<\/p>\n\n\n\n
So I just started to add new obstacles in the Matrix<\/code> in every possible point that is not a starting point, not already containing an obstacle, and then see if this leads to a cycle in the path, counting those places.<\/p>\n\n\n\n
The solution worked with the tests, but when executed with my input data, it always produced too small a number. And I couldn’t find out why! Finally, I searched the internetz and found a comment<\/a> in Reddit, someone having the same issue and explaining the reason to it:<\/p>\n\n\n\n
\n
I was changing direction and going to the next position if there was a blockade in the same iteration, instead of changing direction or moving to the next position. This worked for part 1, but for part 2, this gave me the correct answer for sample input, but for the actual input, the answer was too low, and it took me 4 hours to figure out the issue.<\/p>\n\n\n\n
— ajzone007<\/p>\n<\/blockquote>\n\n\n\n
I was having exactly the same issue! This was a one line fix, not advancing to the next position when direction changes, until the next roll of the loop! This is relatively fast:<\/p>\n\n\n\n
$ swift run -c release AdventOfCode 6 --benchmark
Building for production...
Build of product 'AdventOfCode' complete! (0.16s)
Executing Advent of Code challenge 6...
Part 1: 4819
Part 2: 1796
Part 1 took 0.001846167 seconds, part 2 took 0.56900375 seconds.<\/pre>\n\n\n\n
Here’s the path finding algorithm, used both in part 1 and part 2, throwing an exception when a cycle is met, used in part 2 solution:<\/p>\n\n\n\n
private func findPath(\n    from start: Point,\n    in matrix: Matrix<Character>\n) throws -> (path: [Point], turns: Set<Turn>) {\n    var direction = Direction.from(matrix[start.y, start.x]!)!\n    var currentPoint = start\n    var path: [Point] = []\n    var turns: Set<Turn> = []\n    path.append(start)\n    repeat {\n      let nextPoint = currentPoint.movedTo(direction)\n      if !matrix.contains(y: nextPoint.y, x: nextPoint.x) {\n        break\n      }\n      if matrix[nextPoint.y, nextPoint.x] == \"#\" {\n        direction = direction.turnRight()\n        let (inserted, _) = turns.insert(Turn(point: currentPoint, direction: direction))\n        if !inserted {\n          throw Day06Error.hasCycles\n        }\n      }\n      else {\n        currentPoint = nextPoint\n      }\n      path.append(currentPoint)\n    } while true\n    return (path, turns)\n}<\/code><\/pre>\n\n\n\n
The Set<\/code> return value is not actually used in the calling code, so that could be taken out.<\/p>\n\n\n\n
Then to the Day 7…<\/p>\n","protected":false},"excerpt":{"rendered":"
First part of today’s puzzle was to find out the path of the guard on a map shown below, and count how many distinct positions will the guard visit before leaving the mapped area. ….#…………..#…………#…………..#………….#..^………….#.#……………#… Guard starts walking upwards from the ^ and the # ‘s are blocks on the path, and when the guard … Continue reading “Advent of Code Day 6 – Guard Gallivant”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[2],"tags":[136,48,149,70,46],"class_list":["post-1130","post","type-post","status-publish","format-standard","hentry","category-coding","tag-advent-of-code","tag-algorithms","tag-aoc2024","tag-programming","tag-swift"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/comments?post=1130"}],"version-history":[{"count":1,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1130\/revisions"}],"predecessor-version":[{"id":1131,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1130\/revisions\/1131"}],"wp:attachment":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/media?parent=1130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/categories?post=1130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/tags?post=1130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}