• 0 Posts
  • 21 Comments
Joined 1 year ago
Cake day: June 15th, 2023
  • Zarlin@lemmy.worldtoAdvent Of Code@programming.dev•❄️ - 2023 DAY 10 SOLUTIONS -❄️
    1·
    7 months ago

    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

    Condensed version: 
    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)
  • Zarlin@lemmy.worldtoAdvent Of Code@programming.dev•🎄 - 2023 DAY 1 SOLUTIONS -🎄
    2·
    7 months ago

    This is my solution in Nim:

    import strutils, strformat

const digitStrings = ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]

### Type definiton for a proc to extract a calibration function from a line
type CalibrationExtracter = proc (line:string): int

## extract a calibration value by finding the first and last numerical digit, and concatenating them
proc extractCalibration1(line:string): int =
  var first,last = -1
    
  for i, c in line:
    if c.isDigit:
      last = parseInt($c)
      if first == -1:
        first = last
        
  result = first * 10 + last

## extract a calibration value by finding the first and last numerical digit OR english lowercase word for a digit, and concatenating them
proc extractCalibration2(line:string): int =
  var first,last = -1
  
  for i, c in line:
    if c.isDigit:
      last = parseInt($c)
      if first == -1:
        first = last
    else: #not a digit parse number words
      for dsi, ds in digitStrings:
        if i == line.find(ds, i):
          last = dsi+1
          if first == -1:
            first = last
          break #break out of digit strings
        
  result = first * 10 + last

### general purpose extraction proc, accepts an extraction function for specific line handling
proc extract(fileName:string, extracter:CalibrationExtracter, verbose:bool): int =
  
  let lines = readFile(fileName).strip().splitLines();
  
  for lineIndex, line in lines:
    if line.len == 0:
      continue
    
    let value = extracter(line)
    result += value
    
    if verbose:
      echo &"Extracted {value} from line {lineIndex} {line}"

### public interface for puzzle part 1
proc part1*(input:string, verbose:bool = false): int =
  result = input.extract(extractCalibration1, verbose);

### public interface for puzzle part 2
proc part2*(input:string, verbose:bool = false): int =
  result = input.extract(extractCalibration2, verbose);