Day 12: Garden Groups
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Nim
Runtime:
7ms3.18 msPart 1: I use flood fill to count all grouped plants and keep track of each border I see.
Part 2: I use an algorithm
similar to “merge overlapping ranges”to count spans of borders (border orientation matters) in each row and column, for each group. Resulting code (hidden under spoiler) is a little messy and not very DRY (it’s completely soaked).Edit: refactored solution, removed some very stupid code.
proc groupSpans()
proc groupSpans(borders: seq[(Vec2, Dir)]): int = ## returns number of continuous groups of cells with same Direction ## and on the same row or column var borders = borders var horiz = borders.filterIt(it[1] in {U, D}) while horiz.len > 0: var sameYandDir = @[horiz.pop()] var curY = sameYandDir[^1][0].y var curDir = sameYandDir[^1][1] for i in countDown(horiz.high, 0): if horiz[i][0].y == curY and horiz[i][1] == curDir: sameYandDir.add horiz[i] horiz.del i sameYandDir.sort((a,b)=>cmp(a[0].x, b[0].x), Descending) var cnt = 1 for i, (p,d) in sameYandDir.toOpenArray(1, sameYandDir.high): if sameYandDir[i][0].x - p.x != 1: inc cnt result += cnt var vert = borders.filterIt(it[1] in {L, R}) while vert.len > 0: var sameXandDir = @[vert.pop()] var curX = sameXandDir[^1][0].x var curDir = sameXandDir[^1][1] for i in countDown(vert.high, 0): if vert[i][0].x == curX and vert[i][1] == curDir: sameXandDir.add vert[i] vert.del i sameXandDir.sort((a,b)=>cmp(a[0].y, b[0].y), Descending) var cnt = 1 for i, (p,d) in sameXandDir.toOpenArray(1, sameXandDir.high): if sameXandDir[i][0].y - p.y != 1: inc cnt result += cnt
type Dir = enum L,R,U,D Vec2 = tuple[x,y: int] GroupData = object plantCount: int borders: seq[(Vec2, Dir)] const Adjacent: array[4, Vec2] = [(-1,0),(1,0),(0,-1),(0,1)] proc solve(input: string): AOCSolution[int, int] = let grid = input.splitLines() var visited = newSeqWith(grid.len, newSeq[bool](grid[0].len)) var groups: seq[GroupData] proc floodFill(pos: Vec2, plant: char, groupId: int) = visited[pos.y][pos.x] = true inc groups[groupId].plantCount for di, d in Adjacent: let pd: Vec2 = (pos.x+d.x, pos.y+d.y) if pd.x < 0 or pd.y < 0 or pd.x > grid[0].high or pd.y > grid.high or grid[pd.y][pd.x] != plant: groups[groupId].borders.add (pd, Dir(di)) continue if visited[pd.y][pd.x]: continue floodFill(pd, plant, groupId) for y in 0..grid.high: for x in 0..grid[0].high: if visited[y][x]: continue groups.add GroupData() floodFill((x,y), grid[y][x], groups.high) for gid, group in groups: result.part1 += group.plantCount * group.borders.len result.part2 += group.plantCount * group.borders.groupSpans()
Codeberg repo