Advent of Code Day 6 – Guard Gallivant

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…

Advent of Code Day 5 – Print Queue

Yesterday was a busy day at work and also after, shopping for today: the Independence Day of Finland. Soon I’ll go to see the cannons fire at Linnansaari (Castle Island) with the kids’ families so just a short update on yesterday’s puzzle.

Part 1 was easy and fast to implement. I used last year’s Graph<T> algorithms I implemented to find out which book pages should precede other pages in a list of page numbers. Graph contains the list of pages (vertices) and for each page, those pages that should follow that page (edges).

Second puzzle then… I started with it way too complicated. When failed, I decided to go brute force. The goal was to fix broken page orders, so I thought that I’d just create all the permutations of page orders for a certain print job and try which of those would be correct.

Well, when the input data has page sequences like…:

74,56,86,81,84,44,53,92,12,36,15,66,95,26,71

…and you realize that this sequence of 15 elements alone has 15! permutations, that is 1 307 674 368 000, and the data set has 200+ such sequences, you’ll know that this will take way too much time.

So I left this puzzle alone yesterday and continued this morning, when I woke up after 5 am and couldn’t get any sleep, waiting for the trip to see the cannons fire.

Instead of permutations, the working (and fast) algorithm just goes through the sequence and checks if a page number following the previous is in the edge list of the previous page. If not, the pages are swapped. This is done in a loop that checks if the sequence is still not correct, the checking and swapping continues until the morale improves:

private func fix(_ pages: [Int], using graph: Graph<Int>) -> [Int] {
    var modPages = pages
    repeat {
      for index in 0..<modPages.count - 1 {
        let preceding = modPages[index]
        let following = modPages[index + 1]
        let edges = graph.edges(for: graph.vertex(for: preceding)!)?.map ( {$0.destination.item } )
        if edges != nil && !edges!.isEmpty {
          if !edges!.contains(following) {
            modPages.swapAt(index, index + 1)
          }
        } else {
          modPages.swapAt(index, index + 1)
        }
      }
    } while !isUpdateValid(modPages, graph)
    return modPages
}

This did the trick, and is fast, and the puzzle is solved. Let’s see how today’s puzzle is when I return from the morning trip.

$ swift run -c release AdventOfCode 5 --benchmark
Building for production...
[5/5] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (2.73s)
Executing Advent of Code challenge 5...
Part 1: 4689
Part 2: 6336
Part 1 took 0.006513333 seconds, part 2 took 0.020255375 seconds.

Advent of Code Day 4 – Ceres Search

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.

Advent of Code Day 3 revisited

So, originally I did this the old school style, parsing the input string character by character, managing the state of processing while discovering the elements from the input string.

Tonight I reimplemented part 1 using #Swift RegexBuilder. I’ve never been comfortable in using regular expressions (regex) but wanted to give a try.

Swift RegexBuilder code snippet showing how to pick up the mul instructions with parameters from the day's puzzle input.
Snippet of RegexBuilder code showing how to specify what elements to pick from the input string.

Got it working nicely after some hiccups, as usual – wondered why the sum of mul operations was smaller than expected, and it was because I had Repeat(1...2) instead of Repeat(1...3) in the code. Didn’t notice that some mul parameters were three numbers, since in puzzle examples there were only two numbers. So the regex was only picking first two numbers at most from the input :facepalm:

Learned something new. Maybe regexes are not so terrifying things after all…

An illustration depicting a muscular figure reminiscent of a Greek warrior, labeled "PROGRAMMERS," with an arrow lodged in its leg labeled "REGEX." The style is simplistic and humorous, emphasizing the struggles programmers face with regular expressions.

Advent of Code Day 3 – Mull It Over

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.

Advent of Code Day 2 – Red-Nosed Reports

I woke up early (not by choice) and read today’s part 1 puzzle description in bed and at breakfast coffee. The part 1 was relatively quick and easy to implement, among replying to emails. Code spoilers below.

Then I had other things to do, went for a run (7 km, really windy, cloudy and partly rainy), then sauna and lunch. I tend to take Monday mornings to myself since I teach from 12 until 18.30.

In between supervising students in Zoom (and handling emails), I worked on the part 2 of the puzzle. I tried to find a fancy mathematical way to handle the part 2 change to part 1. Couldn’t get any of those attempts to work (I am not a math person) so I ended up in recursively trying to remove a single element from the data to see if it then satisfies the puzzle problem.

I’m sure there is a fancy solution using cleverly all the Swift algorithms and data structures etc. My solutions tend to be plain old imperative programming style kind of solutions. Well at least I got it working, and it’s not slow:

$ swift run -c release AdventOfCode 2 --benchmark
Building for production...
[5/5] Linking AdventOfCode
Build of product 'AdventOfCode' complete! (1.84s)
Executing Advent of Code challenge 2...
Part 1: 663
Part 2: 692
Part 1 took 0.003531042 seconds, part 2 took 0.005103042 seconds.

This year’s puzzles (so far) do not require any especially fast ways to do things, though, data sets are small… Maybe they’ll come later.

Here’s the part 1 solution for today’s puzzle:

func part1() -> Any {
    var safeLines = 0
    let matrix: Matrix<Int> = parse(data: data)
    for lineNumber in 0..<matrix.height {
      let line = matrix.elements[lineNumber]
      let direction = line[1]! - line[0]!
      if abs(direction) > 3 || direction == 0 {
        continue
      }
      var lineIsSafe = true
      for columnNumber in 2..<line.count {
        let nextDirection = line[columnNumber]! - line[columnNumber - 1]!
        if direction.signum() != nextDirection.signum() || abs(nextDirection) > 3 || nextDirection == 0 {
          lineIsSafe = false
          break
        }
      }
      if lineIsSafe {
        safeLines += 1
      }
    }
    return safeLines
}

For Part 2 I implemented a recursive function to solve the partially safe lines to see if changing one level would satisfy the puzzle, limiting the level of recursion so that only one attempt is made to fix an issue in one of the items in the levels by removing it:

private func isSafe(_ line: [Int?], level: Int) -> Bool {
    var diffs: [Int] = []
    for index in 1..<line.count {
      diffs.append(line[index]! - line[index - 1]!)
    }
    let tooLargeDiffsCount = diffs.filter( { abs($0) > 3 } ).count
    let noDiffCount = diffs.filter( { $0 == 0 } ).count
    var dirChangeCount = 0
    for index in 1..<diffs.count {
      if diffs[index] != diffs[index - 1] {
        if diffs[index].signum() != diffs[index - 1].signum() {
          dirChangeCount += 1
        }
      }
    }
    if tooLargeDiffsCount == 0 && noDiffCount == 0 && dirChangeCount == 0 {
      return true
    } else if level < 1 {
      for index in 0..<line.count {
        var attempt = line
        attempt.remove(at: index)
        if isSafe(attempt, level: level + 1) {
          return true
        }
      }
    }
    return false
}

I might check later how others have solved the puzzle to see if I’d get some inspiration for other styles of solving the puzzle in Swift.

Advent of Code 2024 Day 1

Participating the Advent of Code this year, as far as I am able to. That is, depending on how busy I am at work and at home.

Last year I got 30 stars, about 15 days of participation, last day I got stars (2) was Dec 16th. I missed some second stars for some days. As warmup for this year, I finished one missing second star from last year, now totaling 31 stars out of 50.

For today, the first day, I got two stars:

$ swift run -c release AdventOfCode 1 --benchmark 
Building for production...
...
Build of product 'AdventOfCode' complete! (0.35s)
Executing Advent of Code challenge 1...
Part 1: 1938424
Part 2: 22014209
Part 1 took 0.000817167 seconds, part 2 took 0.0012365 seconds.

Update (16.40 pm): I took a closer look at the Part 2 and managed to get a significant (relative) performance increase:

Part 1 took 0.000780209 seconds, part 2 took 0.000682292 seconds.

Improved time of 0.000682292 seconds is 55% of the original time of 0.0012365 seconds so almost a half.

The goal here is basically to find how many times a value in table 1 appears in table 2. I first sorted both tables and used Swift filter() to filter out and count the matching values from table 2 (original timing above).

Then I changed it to a simple O(n2) loop without any sorting, which to my surprise performs nicely with the data where n = 1000 (only). That takes about 0.00098nn seconds, usually, better than the original solution using sorting and filtering.

Then I wanted to see how much time I can slice off when adding back sorting of the tables and then use binary search to search for the first occurrence of the value in the second table, and step through the equal values in the table 2, counting how many times they occur. This was the fastest solution. Thought the first was shortest in lines of code, this is much faster.

End update.

Not taking too much stress out of this, not aiming to be fast and do not attempt to be at top of the leaderboards. Today I am 33rd on private SwiftLang leaderboard, but may soon fall down.

I’ve heard last year was more difficult than usual. Last year was my first, and this year I am more prepared. I brought in some utility code I wrote last year to this year project, and also searched for some nice snippets from others, porting some code from other languages to Swift.

Advent of Code status update

Today (Dec 22nd…) I solved the Day 16 puzzle, using a graph data structure that I generalised from Day 8 implementation specific graph. I brute forced the part 2 of the puzzle. Probably would get it much faster if I would modify it to be a little bit more clever solution. Maybe won’t, since who cares.

I am still using Swift, though at some points I’ve considered if I should use C++ or Java. I could then utilise my old code. For example, graph data structure implementations done for teaching, with both Java and C++.

I got left behind at day 12, where the puzzle was the first one I had no idea how to start solving it. Maybe a bit too mathematical to my taste. The overall feeling with this puzzle was “meh…? :/” The first puzzle that I was not even interested to solve. Eventually I did solve the part one, but since brute forcing doesn’t really work with part two, I have not tried since. I did take a look at some solutions with Python and C++ from the community but didn’t follow their examples. I know memoization, it would help here, but with this data…

The next problematic puzzle was day 13, part 2. Part 1 was OK, but again for part 2 I would need to find a faster solution. Also, I do not manage to get the expected result using real data, although the unit tests with test data do pass. Maybe I will return to this after the holidays…?

I agree with those comments in the AoC community that some of the puzzle descriptions and/or test data are deliberately vague, perhaps to prevent or hinder using “AI” in solving the puzzles. The negative impact is that this also creates interpretation problems and requires deep dwelling into the input data. To find out why solutions that pass tests with test data, do not provide the correct answer with the real data. Oftentimes this helps, with the support from insights from the AoC community.

In addition to the generic graph data structure, I also implemented a generic Matrix (or Grid) data structure, to make it easier and faster to parse grid data (2D array) from the input data.

A code snippet in Swift: 
func parse<Character>(data: String) -> Matrix<Character> {
	var matrix: Matrix<Character> = Matrix()
	data.components(separatedBy: .newlines).forEach { line in
		if line.count > 0 {
			matrix.append(row: Array(line) as! [Character])
		}
	}
	return matrix
}
An algorithm to create a Matrix (generic 2D array) of characters from input data string.

When looking at some repositories from people participating for many years in AoC, they often have a good collection of tools to help in solving the puzzles. Since many puzzles are similar to ones in previous years, it helps when you just pick up what you need from the data structures and algorithms you already have, to build the solution. I have avoided the temptation to take these building blocks from others, and built my own. In case I participate again next year.

AoC has been a good learning experience seeing how others approach the problem solving. Like the one where I used a grid of characters. Some saw that you could interpret the symbols in lines of the grid as zeroes and ones, and then handle the data as arrays of bits or rows of integers, and use operations like xor to find differences in lines (arrays of bits/integer values). A thought like this vaguely passed through my mind but I never grasped it but let it pass, and continued away with grid / array based solution. A good reminder for me to consider to stop thinking for a while, instead of storming ahead with some idea that may not actually be so good in solving the puzzle.

Apart from moments of frustration and lack of motivation with some puzzles, AoC has been fun so far. Some participants have commented that this year is more challenging than the previous ones. Probably I’ll try to finish all this year puzzles, although late. Positions in leaderboards are not too important for me, but it is nice to see that I managed to stay in top-50 in Swift leaderboard after checking in day 16 solution.

Probably will fall in position since Christmas preparations are going to start full speed today, and I haven’t bought yet a single present to anyone…. It helps a bit that both my kids and their families are not in town until January and we’ll celebrate with gifts then.

Advent of Code – hanging on, so far

I’ve solved all the puzzles by now, both part 1 and 2. Some have been quite tricky to solve. Other issues I’ve had — mainly stupid parsing problems.

Having an effective parser would be something that helps. Also, as someone suggested in the Swift forums, a (generic) grid would help since apparently many puzzles have a grid to navigate.

Already today I thought that the puzzle could be done using a graph. Went for maps (dictionaries) and arrays again, though. Unfortunately all my graph implementations I could reuse are either in Java or C++, and I’ve been doing everything so far in Swift. Maybe I’ll prepare a Graph struct/class in Swift just to be ready when it is needed….

Today’s part 2 was hard in a sense that the solution took almost eight minutes to run on my Mac Mini M1. Surely there should be a way to optimise. But — won’t do that, I already passed the challenge. I still am busy with teaching, so all these puzzles are done on extra time.

Anyways, today I rose to position 16 on private AoC Swift leaderboard. Even though I am not competing and skipping a day or failing a puzzle is no issue to me, it is nice to see that I do relatively well – so far…

By now I’ve used Sets, Dictionaries, arrays, ranges, string manipulation, string splitting, enumerations, and those grid operations. Let’s see what comes up tomorrow…

Advent of code day 1

The accompanying challenge doggie

For the first time, I started the Advent of Code challenge. I’ll be working with Swift using the AoC project template from Apple folks in GitHub, announced in the Swift discussion forums.

Got the two stars from the first day of the challenge. ? and rewarded myself with the traditional Friday pizza with red wine ??

Part two of day one required some interpretation. I finally got the idea and finished with success.

Don’t want to spoil the challenge but I did the part two in two different ways:

  • Going through the input string using String.Index, character by character, picking up words of numbers (“one” etc) converting them to digits (“1”) to a result string. This should be O(n) where n is the number of chars in the input data string.
  • Replacing words using Swift String replaceOccurrences using two different Dictionaries. This has two consecutive for loops iterating two dictionaries replacing text in input string using keys in dictionaries (eg “oneight”) with values (“18”) in dictionaries. This should be O(n*m) where m is the number of entries in the two dictionaries (ca 15 +/- some), n being the number of characters in the input string.

Surprisingly, the first option took 12 secs as using the higher APIs took only 0.007 secs. Maybe I did the first wrong somehow or Swift String index operations are really slow here because of Unicode perfectness. I’ve understood that the collections APIs used with strings are not so picky about Unicode correctness.

Otherwise I used conditional removal of characters that are letters from the string, map algorithms to map the strings containing numbers to integers and reduce algorithm to calculate the sum.

Challenges like this are a good way to brush up my skills. And learn more about Swift. I added myself to the Swift leaderboard to see how other Swift programmers do.

Tomorrow is the day two. Should have time for that in the morning since I wake up early nowadays, both because of myself and the dog. He is already 14+ years and having health issues unfortunately. Meaning early wake-ups every now and then.

The end part of the AoC maybe a real challenge because of all the Christmas hassle in the house. And the busy end of the semester at the university. Interesting to see how far I get and with how many gaps.