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: 7ms 3.18 ms
Part 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()