Tag: advent of code

This was surprisingly easy! The part 1 of today’s task was correct on the first run, which is the first time this has happened to me! Usually I make stupid mistakes, not reading the puzzle carefully enough, and rushing to coding with too little planning ahead.

The puzzle part 1 was to find out positions on a map to place antinodes to prevent antennas to emit a signal that makes people 0.1% more likely to buy Easter Bunny brand Imitation Mediocre Chocolate as a Christmas gift.

Calculate the impact of the signal. How many unique locations within the bounds of the map contain an antinode?

A map looks like this:

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

Where 0 and A are antennas that are sending on a same frequency, A antennas on their own and 0 antennas theirs, respectively. To prevent their signals, the antinodes ( #)must be placed in line of the antennas, after the first and last pair of antennas, like this:

......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....A.....
...#........
#......#....
........A...
.........A..
..........#.
..........#.

To solve the problem, I implented a Dictionary with key-value -pairs (the [Character: [Point]] below), where the key is an antenna with a specific frequency and value is an array of (x, y) positions on the map where that kind of antennas are placed.

var antinodes: Set<Point> = []
let matrix: Matrix<Character> = parse(data: data)
let antennaMap: [Character: [Point]] = parseAntennaMap(matrix)

After parsing the antennas and their positions into a Matrix, and extracting the antennas and their positions into the dictionary, I could print out the dictionary keys (antennas) with the values (a list of positions for the antennas with the same frequency ):

Antenna A
  5:6
  8:8
  9:9
Antenna 0
  1:8
  2:5
  3:7
  4:4

So I could verify that everything is in order for the next step of the puzzle.

I already had a Point structure, having the x and y coordinates, as well as operations to calculate the difference of two points in the coordinate (the distance between them) as well as add together two coordinate points to extrapolate the line between two antennas to position the antinodes inline with the antennas.

So what to do with these? First I needed to handle all the antennas with the same frequency in pairs, to extrapolate the line between them to both directions to add the antinodes. The permutations(ofCount:) algorithm did that. For each pair of antennas, I determined which comes first (point is upper on the map compared to the other) and vice versa.

After that I counted the difference between the first and last point, because the antinode must be place an equal distance away from the antennas. Then I added a point above the first point (first - difference) and below the last point (last + difference).

Then I just added these two antinodes into a Set to get a number of antinodes placed on the map:

for (_, points) in antennaMap {
  let permutations = points.permutations(ofCount: 2)
  for permutation in permutations {
     let first =
     permutation.first! < permutation.last! ? permutation.first! : permutation.last!
    let last = first == permutation.first! ? permutation.last! : permutation.first!
    let difference = last - first
    antinodes.insert(first - difference)
    antinodes.insert(last + difference)
  }
}
antinodes = antinodes.filter({ matrix.contains(y: $0.y, x: $0.x) })
return antinodes.count

Finally I made sure no antinodes were placed outside the map coordinates (using filter to include only those points in the area of the matrix coordinates) and finally returning the count of antinodes placed (the puzzle answer).

Part 2 was just an addition to part 1. Instead of placing one antinode before and after the line of two antennas, place them so that the antinodes are repeated with equal spacing along the line formed by a pair of antennas, until to the edge of the map.

What I first missed in the puzzle instructions was that the positions of the antennas also count in the final answer, not just the antinodes. I did get that the unique positions only are counted (that is why the Set<Point> is used for antinode positions). As I realized this, I just formed a union of antinode and antenna positions, and count of those was the correct answer!

In total, this didn’t take long to solve, thanks to the existing data structures and algorithms, both from Swift, Swift libraries (Swift Algorithms) and my own utilities from previous years. Performance is also OK:

$ swift run -c release AdventOfCode 8 --benchmark
Building for production...
Build of product 'AdventOfCode' complete! (0.28s)
Executing Advent of Code challenge 8...
Part 1: 259
Part 2: 927
Part 1 took 0.000727958 seconds, part 2 took 0.000798333 seconds.

First part of today’s puzzle was to find out the path of the guard on a map shown below, and count how many distinct positions will the guard visit before leaving the mapped area.

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

Guard starts walking upwards from the ^ and the # ‘s are blocks on the path, and when the guard meets one, she always turns right in front of the block.

The part 1 was quite straightforward to implement and didn’t take too long.

In part 2 the goal was to find out in how many places a new obstacle (#) can be placed, so that it causes the guard to walk in circles.

I was working on different solutions, considering using a graph again to see if the graph contains a cycle (there are algorithms for that). Since yesterday was quite a busy day otherwise, I couldn’t focus on solving the puzzle, hence I am one day behind.

Today morning I continued with the part 2 with the ideas I had been thinking about, not needing a Graph. One can detect a cycle when the same turning point is met the second time. So I use a Set<Turn> structure, containing the point and the direction where the turn was taken. Set doesn’t allow you to add a new item that is already in the set, and if this happens, it indicates a cycle in the path.

So I just started to add new obstacles in the Matrix in every possible point that is not a starting point, not already containing an obstacle, and then see if this leads to a cycle in the path, counting those places.

The solution worked with the tests, but when executed with my input data, it always produced too small a number. And I couldn’t find out why! Finally, I searched the internetz and found a comment in Reddit, someone having the same issue and explaining the reason to it:

I was changing direction and going to the next position if there was a blockade in the same iteration, instead of changing direction or moving to the next position. This worked for part 1, but for part 2, this gave me the correct answer for sample input, but for the actual input, the answer was too low, and it took me 4 hours to figure out the issue.

— ajzone007

I was having exactly the same issue! This was a one line fix, not advancing to the next position when direction changes, until the next roll of the loop! This is relatively fast:

$ swift run -c release AdventOfCode 6 --benchmark
Building for production...
Build of product 'AdventOfCode' complete! (0.16s)
Executing Advent of Code challenge 6...
Part 1: 4819
Part 2: 1796
Part 1 took 0.001846167 seconds, part 2 took 0.56900375 seconds.

Here’s the path finding algorithm, used both in part 1 and part 2, throwing an exception when a cycle is met, used in part 2 solution:

private func findPath(
    from start: Point,
    in matrix: Matrix<Character>
) throws -> (path: [Point], turns: Set<Turn>) {
    var direction = Direction.from(matrix[start.y, start.x]!)!
    var currentPoint = start
    var path: [Point] = []
    var turns: Set<Turn> = []
    path.append(start)
    repeat {
      let nextPoint = currentPoint.movedTo(direction)
      if !matrix.contains(y: nextPoint.y, x: nextPoint.x) {
        break
      }
      if matrix[nextPoint.y, nextPoint.x] == "#" {
        direction = direction.turnRight()
        let (inserted, _) = turns.insert(Turn(point: currentPoint, direction: direction))
        if !inserted {
          throw Day06Error.hasCycles
        }
      }
      else {
        currentPoint = nextPoint
      }
      path.append(currentPoint)
    } while true
    return (path, turns)
}

The Set return value is not actually used in the calling code, so that could be taken out.

Then to the Day 7…

Today I got to reuse the Matrix<T> generic data structure I implemented last year. Input being a grid of characters like:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

The goal in part 1 of the puzzle was to find out how many times the word “XMAS” appears in the grid, whether it is written left-to-right, right-to-left or downwards or upwards. And diagonally, from left to right and down, or from right to left and up, as well as from left to right and up, or from right to left and down.

The Matrix implementation has an algorithm to rotate the matrix in steps of 90 degrees. So instead of traversing the grid in all those directions, I rotated it 90 degrees to find out the left-right-up-down and back occurrences of XMAS. After each rotation, I just searched let to right, covering the other directions using rotation

The diagonals are handled in the same way, but in each rotation, I only handled the upper right half of the grid, diagonally where the lines were longer than three characters. I first made the mistake of handling the corner-to-corner line in all rotated diagonals, having too large count of occurrences. When I got to see this mistake, I handled that corner-to-corner diagonal only in one of the rotations.

In all of those cases I ended up with a line, string of characters. What I needed to do then was to find out how many times the line (and the line in reversed order) contains the XMAS.

Part 2 was much more simpler than part 1, so that was quickly solved. The goal was to count how many crosses like this…:

M.S
.A.
M.S

…the matrix contains.

This required just two loops within, starting from the first line and column from the edge, finishing on second-to-last row and column, check if the cell contains an A and then check if the opposing corners are different and contain M and S.

This was quick on my work laptop (MacBook Pro M2, 2022):

$ swift run -c release AdventOfCode 4 --benchmark
Building for production...
[1/1] Write swift-version--1AB21518FC5DEDBE.txt
Build of product 'AdventOfCode' complete! (0.16s)
Executing Advent of Code challenge 4...
Part 1: 2549
Part 2: 2003
Part 1 took 0.014584666 seconds, part 2 took 0.002027958 seconds.

The matrix rotations take time, obviously, so part 1 was slower. I considered counting the results of rotated matrices in parallel, but decided not to. That may or may not produce any speed advantage, don’t know… Also could’ve tried to do not rotating in part 1, and just go all in to the matrix from all directions and back to find the words. Well’ it works so I’ll let it be.

Today’s puzzle was about parsing. Quite straightforward to implement, having done parsing earlier for different types of structured strings, like tsv, csv, json, xml, etc.

In part 1, I anticipated that part 2 would add parsing some other instructions than mul so I did implement it so. There is an Instruction structure that specifies:

• the instruction name
• expected number of parameters and
• the list of parameter values

Then the instruction is able to evaluate the result. Parsing returns an array of Instructions to execute, and then they are executed, accumulating the result of each mul instruction evaluated:

private struct Instruction {
  let instruction: String
  let params: Int
  var values: [Int] = []
    
  var result: Int {
    if instruction == "mul" {
      return values.reduce(1, *)
    }
    return 0
  }
}

In part 2, the execution just changes the state; after do instruction, following instructions are evaluated, and after don't, the instructions are ignored, until next do instruction:

func part1() -> Any {
    let instructions = parse(data, 
                     for: [
                        Instruction(instruction: "mul", params: 2)
                     ])
    return execute(instructions)
}

func part2() -> Any {
    let instructions = parse(data,
                     for: [
                      Instruction(instruction: "mul", params: 2),
                      Instruction(instruction: "do", params: 0),
                      Instruction(instruction: "don't", params: 0)
                     ])
    return execute(instructions)
}

Benchmarked:

$ swift run -c release AdventOfCode 3 --benchmark
Building for production...
[6/6] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (2.55s)
Executing Advent of Code challenge 3...
Part 1: 188116424
Part 2: 104245808
Part 1 took 0.00304425 seconds, part 2 took 0.004164459 seconds.