Correct in that Swift doesn't have it and swift-numerics already has an issue to list and track implementations of those kinds of utility functions: Integer utilities module · Issue #10 · apple/swift-numerics · GitHub. Someone just hasn't implemented a binary and collection version 
1 Like
gcd is one of many missing bits of functionality that makes AoC easier. Swift's lack of common tools is one of the reasons why I don't do AoC anymore. I got really tired of fighting the language just to get a performant graph type, or basic math operations, or simple input parsing.
3 Likes
I see GCD is in Numerics though: https://github.com/apple/swift-numerics/blob/main/Sources/IntegerUtilities/GCD.swift
I was wondering if there was some hesitation to add additional features, like LCM, or if say I created an issue and PR that this would be an easy way to contribute?
It is, now, unreleased, on only the main branch. Which is nice, but also the least of my issues, as gcd and lcm are trivial to implement (at least sub optimally). swift-numerics could really use a release.
1 Like
If anyone would like, I have years worth of entries and utilities in my repo: GitHub - jshier/AdventOfCode: My solutions for Advent of Code.. There are some parsing, Point, and Direction utilities that I found most useful, as virtually every year has problems that can be solved using them. Aside from 2017, the years are incomplete. I was able to solve them all in 2017, even without outside sources, which took quite a while for some of them.
Nitpick: you need lcm (least common multiple), not lcd (least common divisor, a not actually useful concept since it's always 1).
I solved day 8 part 2 by printing all the numbers I needed the LCM of, then pasting “least common multiple of those numbers” into Wolfram Alpha.
1 Like
Not to toot my own horn, but: Variadic GCD and LCM by LePips · Pull Request #276 · apple/swift-numerics · GitHub.
3 Likes
many of the Apple-maintained could benefit from a more proactive release process. i wish there were a policy for all those repos to tag at least one release every six months or so.
2 Likes
To be totally honest, for 8 I tossed them into Python's Math LCM in the terminal (debated opening a Process, but in that direction lies madness) (hides face) But I went back and got a GCD snippet I had from another project and turned it into LCM for future Challenges. Looking forward to those Integer tools. Thanks @Pippin!
So I can't really be mad at Swift for not being an ASCII mashing champion, but I'm having fun trying and learning what's there.
It's kinda a big fluffy St. Bernard in your way reminding you to be safe and use utf16! Thanks Fido! Not right now! I already dropped into the UInt8 once this year to get it out of my way, but I'm trying not to!
Soooo... for example all these different ways to extractInts from StringProtocols... thoughts (like why(?) use components over split when it requires Foundation?)... other Swift capabilities to try out? I'm trying to make myself an Int extracting sampler...
fileprivate extension StringProtocol {
//Ignores negative signs.
func extractPositiveInts() -> [Int] {
self.components(separatedBy: CharacterSet.decimalDigits.inverted).compactMap({Int($0)})
}
func extractInts() -> [Int] {
self.split(whereSeparator: {!"-0123456789".contains($0)}).compactMap({Int($0)})
}
func extractInts_split() -> [Int] {
self.components(separatedBy: CharacterSet.decimalDigits.inverted.union(CharacterSet(charactersIn:"-"))).compactMap({Int($0)})
}
//For when there is only one separator mixed in
func extractInts(separator:Self.Element) -> [Int] {
self.split(separator:separator).compactMap { Int($0)}
}
func schlurpPositiveInt() -> Int {
let filteredString = self.unicodeScalars.filter {
CharacterSet.decimalDigits.contains($0)
}.compactMap { Character($0) }
return Int(String(filteredString))!
}
gist as I discover more: Int Extraction Sampler · GitHub
I've been doing Advent of Code for a while now, and mostly in Swift. I've also been maintaining a visualization system if you want to create one. It uses either CoreGraphics or Metal to create frames, as well as AVFoundation and MetalKit to record and view the visualization.
This years solutions are on my GitHub, as well as a CoreGraphics visualization of Day 10. My repo this year is combination of the templates provided above plus my setup I've been using over the years. GitHub - stack/advent-of-code-2023: My solutions for Advent of Code 2023
My blog has most of my visualizations from years past, as well as some write ups on how the visualization systems work. https://gerstacker.us.
6 Likes
How did you find yesterdays (day 12) puzzle, in particular part 2?
For me, Dynamic Programming as a concept is completely new. I understand it requires finding base cases and a generation function, but how do you derive one in a puzzle like that?
@maartene Did you consider memoization?
yes, but my brute force solution did not use recursion.
I'm still working on part 2. I spent a lot of yesterday hunting down a glitch (works on test data not on real data) that turned out to be an off by one error in a curser that let some bad patterns in through a back door. Doh!
I'm still pretty shaky on memoizing, too. If anyone finds a resource they end up liking, I'd love to hear it. I'm not sure if my function (which has a corner that is recursive) is conducive to it or if I'll have to write it all over again.
Took care of today's first.
Seemed SO fast on Part One... oh well!
And if anyone still reads the comics with their coffee. Here's a switch statement that should be good for a laugh for the lengths I was trying to avoid recursing. (Don't do this at home...)
switch (currentSpring, binFull, previousSpring) {
//ERRORS
case (_,_,.unknown):
print("ledger:\(currentLedger.legible), pos:\(position), ")
fatalError("Put an an unknown in a finished product.")
case (_, true, .good): fatalError("Never should have put a .good in an bin.")
//DEAD ENDS
case (.bad, true, _): return .dead //cant add more to a full bin
case (.good, false, _): return .dead //can't add a . to a bin
case(.bad, nil, .bad): return .dead //(_, .nil, .bad) all ways needs a .good after it.
//REQUIRES # (In the middle of a bin)
case (.bad, false, _):
currentLedger.append(.bad)
return testOption(position: position + 1, previousSpring:currentSpring, opBinNumber:opBinNumber, currentBinQty: currentBinQty+1 ,validChild: currentLedger)
case (.unknown, false, _):
currentLedger.append(.bad)
return testOption(position: position + 1, previousSpring:.bad, opBinNumber:opBinNumber, currentBinQty: currentBinQty+1,validChild: currentLedger)
//VALID BIN ENDING
case (.good, true, _):
//great.
currentLedger.append(.good)
return testOption(position: position + 1, previousSpring:currentSpring, opBinNumber:opBinNumber+1, currentBinQty: 0,validChild: currentLedger)
case (.unknown, true, _):
currentLedger.append(.good)
return testOption(position: position + 1, previousSpring:.good, opBinNumber:opBinNumber+1, currentBinQty: 0,validChild: currentLedger)
//NEXT AFTER BIN END
case (.good, nil, .bad):
//presumably it JUST became full so this one HAS to be a, so with a .good, we're set!
currentLedger.append(.good)
return testOption(position: position + 1, previousSpring:currentSpring, opBinNumber:opBinNumber, currentBinQty: 0, validChild: currentLedger)
case(.unknown, nil, .bad) :
//presumably it JUST became full so this one HAS to be a .
currentLedger.append(.good)
return testOption(position: position + 1, previousSpring:.good, opBinNumber:opBinNumber, currentBinQty: 0, validChild: currentLedger)
//BIN STARTING - FORCED
case(.bad, nil, .good):
//Check if there's room.
//Add the first broken spring
currentLedger.append(.bad)
//Change binQty in function. (BinNum was ++ on exit)
return testOption(position: position + 1, previousSpring:currentSpring, opBinNumber:opBinNumber, currentBinQty: 1, validChild: currentLedger)
//NO BIN STARTED - FORCED
case(.good, nil, .good):
//TODO: Still Room?
currentLedger.append(.good)
return testOption(position: position + 1, previousSpring:currentSpring, opBinNumber: opBinNumber, currentBinQty: 0, validChild: currentLedger)
//TO START OR NOT START
case(.unknown, nil, .good):
//------------------------------ CHOICE. Start a basket or not?
var startBin = currentLedger
startBin.append(.bad)
var donStarBin = currentLedger
donStarBin.append(.good)
return .choice(
good:testOption(position: position + 1, previousSpring:.good, opBinNumber:opBinNumber, currentBinQty: 0, validChild: donStarBin),
bad:testOption(position: position + 1, previousSpring:.bad, opBinNumber:opBinNumber, currentBinQty: 1, validChild: startBin)
)
default:
fatalError("What did I miss??")
}
1 Like
Here's how I derived my solution for day 12.
First I'll introduce a couple of utility functions we'll need. (I didn't write them up front when I was first solving the problem, but the explanation is simpler if I define them up front.)
extension Character {
var canBeDamage: Bool { self == "#" || self == "?" }
var canBeOperational: Bool { self == "." || self == "?" }
}
The first thing I did was recognize that I would process the input one line at a time, so I wrote that loop, calling a not-yet-written function to compute the answer for one line:
let input = readInput() // a personal library function;
// you could just paste your input into a multiline string literal
var answer = 0
for line in input.split(separator: "\n") {
answer += arrangementCount(forLine: line)
}
print(answer)
Then I started on the arrangementCount(forLine:) function by parsing the input line and calling another not-yet-written function:
func arrangementCount(forLine line: Substring) -> Int {
let words = line.split(separator: " ")
let pattern = words[0]
let sizes = words[1].split(separator: ",").map { Int($0)! }
return arrangementCount(forPattern: pattern, damageSizes: sizes)
}
Of course the real puzzle is how to write arrangementCount(forPattern:damageSizes:):
func arrangementCount(forPattern pattern: Substring, damageSizes: [Int]) -> Int {
// ???
}
At this point I recognize a programming pattern I've seen before: I want to peel off the first cluster size and try to match it at the start of pattern. But that means there needs to be a first cluster size. What if damageSizes is empty?
The problem statement says that every damaged spring in pattern must be in one of the listed damage clusters (“This list always accounts for every damaged spring”). So, if damageSizes is empty, then pattern is only a valid arrangement if every character in it can be operational. There is one legal arrangement if all of pattern can be operational, and there are zero legal arrangements if any of pattern cannot be operational.
func arrangementCount(forPattern pattern: Substring, damageSizes: [Int]) -> Int {
guard let firstSize = damageSizes.first else {
return pattern.allSatisfy(\.canBeOperational) ? 1 : 0
}
// ???
}
What next? Let's consider an example:
pattern = "?#?.??."
damageSizes = [2, 1]
firstSize = 2
I (as a human) can see that pattern can start with a damage cluster of size 2 (firstSize), if I treat the pattern as "##..??.". If I peel off that damage cluster (and the operational spring following it), I am left with the remaining pattern ".??.", and I need to fit the remaining damage cluster of size 1 into that new pattern.
I can see (again, as a human) that there are two ways to match ".??." to a single damage cluster of size 1: as either ".#.." or "..#.". So, I can “back out” each of those two arrangements into an arrangement of [2, 1] in "?#?.??." with the size-2 cluster at the beginning of the full pattern. (Specifically, I can back out ".#.." to "##..#.." and I can back out "..#." to "##...#.".) So there are exactly two arrangements of [2, 1] in "?#?.??." when the 2-cluster starts at the start of the pattern.
This is the key insight. In general, if I can match a firstSize-size damage cluster at the start of pattern, then I can turn any arrangement of the remaining clusters within the remaining pattern into an arrangement of all the clusters in the full pattern. I can use recursion to count the arrangements of the remaining clusters within the remaining pattern.
To turn that insight into code, I'll first write a helper function that checks whether a pattern can start with a damage cluster of a given size:
extension Substring {
func canStartWithDamageCluster(ofSize size: Int) -> Bool {
guard
count >= size,
prefix(size).allSatisfy(\.canBeDamage)
else { return false }
if let separator = dropFirst(size).first {
return separator.canBeOperational
} else {
// damage cluster ends at my end, so no separator needed
return true
}
}
}
Now I can write code implementing the deductive process I performed as a human:
func arrangementCount(forPattern pattern: Substring, damageSizes: [Int]) -> Int {
guard let firstSize = damageSizes.first else {
return pattern.allSatisfy(\.canBeOperational) ? 1 : 0
}
var answer = 0
if pattern.canStartWithDamageCluster(ofSize: firstSize) {
// +1 for the separator, if any, after the damage cluster.
let remainingPattern = pattern.dropFirst(firstSize + 1)
let remainingSizes = damageSizes.dropFirst()
answer += arrangementCount(
forPattern: remainingPattern,
damageSizes: remainingSizes
// ^ 🛑 Cannot convert value of type 'Array<Int>.SubSequence' (aka 'ArraySlice<Int>') to expected argument type '[Int]'
)
}
// ???
}
The compiler complains that remainingSizes is an ArraySlice, not an Array. I realize at this point that it'll be more efficient if I make the damageSizes parameter be an ArraySlice, so I go back and change that. I also have to change the caller to pass a slice:
func arrangementCount(forPattern pattern: Substring, damageSizes: ArraySlice<Int>) -> Int {
// changed here ^^^^^^^^^^^^^^^^
guard let firstSize = damageSizes.first else {
return pattern.allSatisfy(\.canBeOperational) ? 1 : 0
}
var answer = 0
if pattern.canStartWithDamageCluster(ofSize: firstSize) {
// +1 for the separator, if any, after the damage cluster.
let remainingPattern = pattern.dropFirst(firstSize + 1)
let remainingSizes = damageSizes.dropFirst()
answer += arrangementCount(
forPattern: remainingPattern,
damageSizes: remainingSizes
)
}
// ???
}
func arrangementCount(forLine line: Substring) -> Int {
let words = line.split(separator: " ")
let pattern = words[0]
let sizes = words[1].split(separator: ",").map { Int($0)! }
return arrangementCount(forPattern: pattern, damageSizes: sizes[...])
// added this ^^^^^
}
So I've counted the arrangements that put the first damage cluster at the start of the pattern. Let's go back to the example I used above:
pattern = "?#?.??."
damageSizes = [2, 1]
firstSize = 2
In this example, I already found that I could match the first damage cluster at the start of the pattern (which requires treating the first "?" as "#" and the second "?" as ".".) But I have another option: I can treat the first "?" as "." and match the first damage cluster starting at the second character of the pattern (the "#"). Extrapolating:
- If the first character of the pattern can be treated as an operational spring (
"?"or"."), then I can try matching the first damage cluster starting at the second character of the pattern. If it matches, then any arrangements of the remaining clusters in the remaining pattern are also arrangements of all the clusters in the full patttern. - If the first two characters of the pattern can be treated as an operational spring (
"?"or"."), then I can try matching the first damage cluster starting at the third character of the pattern. If it matches, then any arrangements of the remaining clusters in the remaining pattern are also arrangements of all the clusters in the full patttern. - If the first three characters of the pattern can be treated as an operational spring (
"?"or"."), then I can try matching the first damage cluster starting at the fourth character of the pattern. If it matches, then any arrangements of the remaining clusters in the remaining pattern are also arrangements of all the clusters in the full patttern. - etc.
So, after I try matching the first damage cluster at the start of pattern, I'll check whether the first character of pattern can be an operational spring. If so, I'll drop that character from pattern and try matching again. I repeat this process until pattern is empty or its first character must be a damaged spring.
To drop that first character from pattern, I'll make pattern a var.
Oh, and that's all the work I need to do in this function. When the loop exits, I have the full count of arrangements of damageSizes in pattern.
func arrangementCount(forPattern pattern: Substring, damageSizes: ArraySlice<Int>) -> Int {
guard let firstSize = damageSizes.first else {
return pattern.allSatisfy(\.canBeOperational) ? 1 : 0
}
var answer = 0
var pattern = pattern
while true {
// This is exactly the same if-statement from earlier,
// but now it's nested inside a while loop.
if pattern.canStartWithDamageCluster(ofSize: firstSize) {
// +1 for the separator, if any, after the damage cluster.
let remainingPattern = pattern.dropFirst(firstSize + 1)
let remainingSizes = damageSizes.dropFirst()
answer += arrangementCount(
forPattern: remainingPattern,
damageSizes: remainingSizes
)
}
// If the first character of the pattern is definitely a
// damaged spring, then it can't be skipped, so I'm done.
guard let c = pattern.popFirst(), c.canBeOperational
else { break }
}
return answer
}
To extend the solution above to part 2, we need to replicate pattern and damageSizes five times. I did that by modifying arrangementCount(forLine:) as follows:
func arrangementCount(forLine line: Substring, reps: Int) -> Int {
let words = line.split(separator: " ")
let pattern = (0 ..< reps)
.map { _ in words[0] }
.joined(separator: "?")
let sizes = Array((0 ..< reps)
.map { _ in
words[1]
.split(separator: ",")
.map { Int($0)! }
}
.joined())
return arrangementCount(forPattern: pattern[...], damageSizes: sizes[...])
}
var answer = 0
for line in input.split(separator: "\n") {
answer += arrangementCount(forLine: line, reps: 5)
}
print(answer)
The solution above was efficient enough to solve part 1 (my longest pattern was length 20 with 17 "?" characters), but it will take many lifetimes to solve part 2.
This is where we introduce memoization. It turns out that many, many of the recursive calls to arrangementCount(forPattern:damageSizes:) pass the same argument values, and so they return the same value. We can cache those values in a hash table so each only needs to be computed once.
Each hash table key needs to hold the arguments to a call to arrangementCount(forPattern:damageSizes:), so I'll introduce a Key type:
struct Key: Hashable {
var pattern: Substring
var damageSizes: ArraySlice<Int>
}
Since this is Advent of Code and I'm racing to be on the leaderboard, I'll just use a 
global variable 
for the cache:
var cache: [Key: Int] = [:]
To actually perform memoization, I'll first rename the existing function to have an _ prefix:
func _arrangementCount(forPattern pattern: Substring, damageSizes: ArraySlice<Int>) -> Int {
guard let firstSize = damageSizes.first else {
return pattern.allSatisfy(\.canBeOperational) ? 1 : 0
}
// etc.
}
Note that this is not a refactoring! I didn't change the call sites to use an _, so this point I have compilation errors.
I'll fix those by writing a new function with the old name. The new function first checks the cache. It calls the _ function only if the cache doesn't have the answer.
func arrangementCount(forPattern pattern: Substring, damageSizes: ArraySlice<Int>) -> Int {
let key = Key(pattern: pattern, damageSizes: damageSizes)
if let answer = cache[key] {
return answer
}
let answer = _arrangementCount(forPattern: pattern, damageSizes: damageSizes)
cache[key] = answer
return answer
}
With memoization, a debug build solves part 2 in about 2 seconds (on my M3 Max).
6 Likes
@mayoff truly great write-up! thank you very much. I especially like how you build up the solution to the problem in small steps. 
As a little anti-nausea med, I have this in my utilities.swift file for AoC:
func memoize<In: Hashable, Out>(_ f: @escaping (In) -> Out) -> (In) -> Out {
var memo: [In: Out] = [:]
return {
if let result = memo[$0] {
return result
} else {
let result = f($0)
memo[$0] = result
return result
}
}
}
which I used on day 12 as
let possibilities = memoize(_possibilities)
func _possibilities(_ record: Record) -> Int {
// snip...
// try if starting with a . or ?
let ifDotCount = record.tryEatDot().map(possibilities) ?? 0
// etc...
}
Of course, this is still a global memo dictionary variable. But it guarantees it's only used for memoizing that one function, and since _possibilities is pure it's fairly principled.
It's not thread safe though, so if you try using this in Swift 6 you'd get an error – so you'd need to mark possibilities as either @MainActor or nonisolated(unsafe) (for AoC leaderboard purposes only, of course).
p.s. congrats on placing on Day 12, @mayoff
5 Likes
I was reading about Python’s @cache and was wondering what that would look like as a Swift macro. Is it essentially @Ben_Cohen’s function, or is there more to it?
I created https://golfcoder.org, a community driven leaderboard for AdventOfCode, focusing on code token length. Every name, including variables and functions, is considered as a single token, irrespective of its length. Since Swift is a very concise language, you might have a good chance being top spot with a Swift solution. Feedback is welcome!
I ended up solving Day 12 entirely differently. @mayoff's description of his solution was really informative, and I got halfway through trying to write up a similar description about my solution when I realized through writing that my solution had kind of gone halfway towards something and could have been much better.
So this isn't what I actually wrote on day 12 (though the concept is similar), this is what I should have written, and ended up writing just now.
Imagine that you have a string of just damage # and operational . and you want to verify the groups match your desired group numbers. You start out having read zero groups and zero damage in the first group, and for each character in the pattern string you read, you can either get closer to completing the groups or you discover that doing so is impossible with this pattern. And then realize (which I didn't until writing this up) that what you are actually dealing with is a DFA, a deterministic finite automaton.
Example, with groups [1,2]:
Start at A. For every character you read, follow the line for that character. If there isn't an appropriate line, fail. If you reach the end of the string of characters and are in one of the end states (E or F here), you matched successfully.
The DFA to match arbitrary groups is easy to construct. There are only 4 types of nodes:
- Start of a group. You expect a group to follow but haven't seen any damage yet. (Nodes A and C here.)
- Mid group. You've seen some damage but not enough. (Node D here.)
- End of a group. You found as much damage as you expect. (Nodes B and E here.)
- Finished. There shouldn't be any more damage. (Node F here.)
There are only 2 types of edges. Either you move on to the next node, or loop and stay in the same place. (Or the third possibility: you have no valid edge, and abort.)
You only ever need #-of-groups + sum-of-damage + 1 nodes to construct the DFA. A node per group for the start nodes. A node per damage for mid/end. And a single finished node at the very end.
Now what happens if you don't know whether a character is . or #? Let's expand our conception of the matcher. Instead of only being in a single state at a time, each node now has an integer count of the number of possibilities. You start out with all zeros except for a single possibility, a 1 at the start node A. As you read each . or # you move any non-zero count from each node to each following node according to the arrows.
If you read a ?, you copy any non-zero count from each node to BOTH the following nodes according to the arrows. Wherever an arrow doesn't exist the count just gets dropped and replaced with zero.
Since we know the groups we want to match up front, and we can convert that into a DFA with a known number of nodes, we've converted the problem into just updating the contents of an array of integer counts for each character we read. In the last example given in the advent of code description: [3,2,1] turns into an array of 10 integers that start out with [1,0,0,0,0,0,0,0,0,0] and after reading ?###???????? in part 1 end up with [0, 0, 0, 0, 1, 1, 1, 5, 4, 6]. We pull out the last 2 counts, and get 4+6=10.
In part 2, with five times the groups and the longer string, the same input leads to the output [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50625, 50625, 50625, 253125, 202500, 303750]. We pull out the last 2 counts, and get 202500+303750=506250.
Here is the code. We make an array of Nodes, and an array of counts, and then manipulate the counts for each character in the pattern according to the node instructions.
func hotSprings(_ contents: String) -> Int {
enum NodeType {
case startOfGroup
case midGroup
case endOfGroup
case finished
var operationalMove: Int? {
switch self {
case .startOfGroup, .finished: return 0
case .midGroup: return nil
case .endOfGroup: return 1
}
}
var damagedMove: Int? {
switch self {
case .startOfGroup, .midGroup: return 1
case .endOfGroup, .finished: return nil
}
}
}
func makeNodeTypes(groups: [Int]) -> [NodeType] {
var result: [NodeType] = []
for group in groups {
result.append(.startOfGroup)
for _ in 0 ..< (group-1) {
result.append(.midGroup)
}
result.append(.endOfGroup)
}
result.append(.finished)
return result
}
func next(_ c: Character, nodes: [NodeType], counts: inout [Int]) {
let operationMove = c != "#"
let damageMove = c != "."
for i in nodes.indices.reversed() {
let n = counts[i]
guard n > 0 else { continue }
counts[i] = 0
if damageMove, let move = nodes[i].damagedMove {
counts[i+move] += n
}
if operationMove, let move = nodes[i].operationalMove {
counts[i+move] += n
}
}
}
var total = 0
contents.enumerateLines { line, _ in
let parts = line.split(separator: " ")
let springs = parts[0]
let groups = parts[1].split(separator: ",").map({ Int($0)! })
var longGroups: [Int] = []
for _ in 0 ..< 5 {
longGroups.append(contentsOf: groups)
}
let nodes = makeNodeTypes(groups: longGroups)
var counts = Array(repeating: 0, count: nodes.count)
counts[0] = 1
for i in 0 ..< 5 {
for c in springs {
next(c, nodes: nodes, counts: &counts)
}
if i != 4 {
next("?", nodes: nodes, counts: &counts)
}
}
total += counts[nodes.count-1] + counts[nodes.count-2]
}
return total
}
Since this is just integer manipulation of small arrays this is very fast. It solves my part 2 input in 0.75 seconds on an M2 studio.
3 Likes