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

  • janAkali
    link
    fedilink
    English
    2
    edit-2
    10 hours ago

    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()
    

    Codeberg repo