aoc – Antti Juustila

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

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.