Nim

This was a great challenge, it was complex enough to get me to explore more of the Nim language, mainly (ref) types, iterators, operators, inlining.

I first parse the input to Tiles stored in a grid. I use a 1D seq for fast tile access, in combination with a 2D Coord type. From the tile “shapes” I get the connection directions to other tiles based on the lookup table shapeConnections. The start tile’s connections are resolved based on how the neighbouring tiles connect.

Part 1 is solved by traversing the tiles branching out from the start tile in a sort of pathfinding-inspired way. Along the way I count the distance from start, a non-negative distance means the tile has already been traversed. The highest distance is tracked, once the open tiles run our this is the solution to part 1.

Part 2 directly builds on the path found in Part 1. Since the path is a closed loop that doesn’t self-intersect, I decided to use the raycast algorithm for finding if a point lies inside a polygon. For each tile in the grid that is not a path tile, I iterate towards the right side of the grid. If the number of times the “ray” crosses the path is odd, the point lies inside the path. Adding all these points up give the solution for Part 2.

Initially it ran quite slow (~8s), but I improved it by caching the tile connections (instead of looking them up based on the symbol), and by ditching the “closed” tiles list I had before which kept track of all the path tiles, and switched to checking the tile distance instead. This and some other tweaks brought the execution speed down to ~7ms, which seems like a nice result :)

Part 1 & 2 combined

proc solve*(input:string):array[2, int]=
  let lines = input.readFile.strip.splitLines.filterIt(it.len != 0)
  
  # build grid
  var grid = Grid(width:lines[0].len, height:lines.len)
  for line in lines:
    grid.tiles.add(line.mapIt(Tile(shape:it)))
  
  # resolve tile connections
  for t in grid.tiles:
    t.connections = shapeConnections[t.shape]
  
  # find start coordinates and resolve connections for it
  let startCoords = grid.find('S')
  let startTile = grid[startCoords]
  startTile.connections = startCoords.findConnections(grid)
  startTile.distance = 0
  
  # Traverse both ends of path from start
  var open: Deque[Coord]
  open.addLast(startCoords)
  
  while open.len != 0:
    let c = open.popFirst # current coordinate
    let ct = grid[c] # tile at c
    
    #find and add connected neighbour nodes
    for d in ct.connections:
      let n = c+d
      let nt = grid[n]
      # if not already on found path and not in open tiles
      if nt.distance == -1 and not (n in open):
        nt.distance = ct.distance + 1
        result[0] = max(result[0], nt.distance)
        open.addLast(n)
    
  # Part 2
  for c in grid:
    let ct = grid[c]
    
    #path tiles are never counted
    if ct.distance >= 0:
      continue
    
    # search from tile to end of row
    var enclosed = false
    for sx in c.x.. 0):
        enclosed = not enclosed
      
    result[1] += ord(enclosed)