Implementation Question
design.dropFirst(towel.count) vs design.trimmingPrefix(p)
Any reason to prefer on over the other?
That would essentially make it so that your top-level call into the search was with a String and then (so long as you are careful that it is a substring) the lower levels are called with a Substring, and yes, you get almost all the advantages while also making the top-level call site a little cleaner because you can call it with designString instead of designString[...].
It does make memoization more complicated, because dictionary keys have to be all the same type, so you'd need to only memoize if you can cast to Substring or something like that. Because of that probably not cleaner over all for this particular problem.
1 Like
I think it could be implemented as a function body macro.
1 Like
Makes a lot of sense. I may make the substring more explicit going forward, though because this is a good tip!
I chose to memoize by hand with a dictionary reference passed around as an inout cache var for "reasons" (this was one of them, needed to hand roll a key different than the inputs), so my code is gnarly already!
Day 19 part 1. Very happy with how my naive approach solved the problem in debug mode -- using String.SubSequence was very helpful, once I remembered how to slice off the front of a string.
Day 19 spoilers
private func possible(_ pattern: any StringProtocol,
_ towels: [String]) -> Bool {
for towel in towels {
if towel == pattern { return true }
if pattern.hasPrefix(towel) {
let i = pattern.index(pattern.startIndex, offsetBy: towel.count)
if possible(pattern[i...], towels) { return true }
}
}
return false
}
Part 2 required some memoization and because I'm lazy my new favourite yes-that-is-my-foot keyword, nonisolated(unsafe) came into play.
Because of the recursion, I was dealing in any StringProtocol which cannot be hashed, so I had to eat an additional string allocation. But even on my slow Linux PC, the final run only took 1.19 seconds.
nonisolated(unsafe) var cache: [String: Int] = [:]
private func countAllPatterns(_ pattern: any StringProtocol,
_ towels: [String]) -> Int {
if let value = cache[String(pattern)] {
return value
}
var sum = 0
for towel in towels {
if towel == pattern { sum += 1 }
if pattern.hasPrefix(towel) {
let i = pattern.index(pattern.startIndex, offsetBy: towel.count)
sum += countAllPatterns(pattern[i...], towels)
}
}
cache[String(pattern)] = sum
return sum
}
1 Like
Transforming into nested arrays?
I tend to use [Point: Character] dicts. One of the nice effects is that boundary detection can be done with grid[point] == nil instead of dealing with 0...max(X|Y) checks. Thankfully, AoC grids (like today's) often come with a built-in border.
Do you have a point type?
Absolutely, with lots of utility stuff so I can say point.neighbors(adjacency: .orthogonal) , let moved = point + .north and much more.
Is there a datatype in swift-collections (or elsewhere) that works out well for you over arrays or dictionaries?
Heap and Deque are useful, and this year I've relied on collection.combinations(ofCount: 2) a few times, as well as adjacentPairs() from swift-algorithms.
2 Likes
collection.combinations(ofCount: 2)
Thats a good one! I had to roll my own today. But using a battle tested version always instills more confidence.
Anyway, I was struggling today. When I finally had a solution that solved part one it took 45 minutes to produce the correct answer. OK, while I was playing FFXIV, so it might have been starved for resources but anyway.
For part 2 I had to look on Reddit for hints and found a useful one about what shortcuts really are. So I could implement a better (and in the end quite simple) algorithm. This still took way too long and suffered from an off-by-one error for way too long. But OK. Finally got there. And now it runs both parts in <15s. Good enough for me.
I just return a space character. I wouldn't have considered a dictionary, that's clever. I was going to ask about performance, but I don't think grid accesses are a problem with my horrible brute force solutions.
Speaking of 'horrible brute force solutions' doing these puzzles have given me an appreciation for how easily Swift lets me take a solution and subject all cores to my stupidity.
Main stumbling block was figuring out that this error message
was trying to say "grid is mutable, it might change by the time this task is running". But hey, I've spent enough years writing C++ that I should be used to cryptic error messages at this point. 
Edit: I left the Ocean Boiler running all morning and got no results.
Spoilers for Day 20, part 1
Of course, once I sat down and thought about what I was doing, I realised that you can just modify the previous graph that the Dijkstra algorithm outputs and it took 9 seconds to get the answer.
1 Like
Day 21 part 2:
If you just let the directional keyboard robots use vi cursor movement instead ("hjkl;" -> "<v^>A") so that all the keys are on one row, you save 207,349,278,600,190 keystrokes on my input. Almost 1%!
Changing the numeric keypad to have the 123 row at the top, telephone-style, also saves 10 trillion keystrokes (10,024,661,226,042).
4 Likes
Style question. Almost every solution I find myself declaring an empty array or dictionary. What feels more natural to people?
var widgets: [Widget] = []var widgets = [Widget]()var widgets = Array<Widget>()- other
0
voters
Great question. Honestly, I've found myself defaulting to the first option (var widgets: [Widget] = []) because it seems to be the order in which I think (name, with type, and initial value), but I think I prefer the readability and conciseness of the second option (var widgets = [Widget]()). It just feels better.
@Ben_Cohen has collected a bunch of great reasons why you should prefer the first option:
2 Likes
So I didn't (just) wake up and think "let's start an argument!", I was reading through The Swift Programming Language and this sidebar was what got me thinking:
More on topic, day 21 is the first day where I left without even the first star. I know what I did wrong, and the path to getting the solution but it's more code than I have time to write at the moment. I'm hoping to come back and polish off the stars I've missed after the fact.
Day 22 was much simpler.
Day 22 spoilers
Part 1 is basically "do what the puzzle says" and didn't require much thinking. Part 2 was solvable with a brute force search, after remembering that map and friends are allocating lists and so this:
private func purchaseBananas(from priceEntries: [PriceEntry], lookFor: [Int]) -> Int {
let changes = priceEntries.map { $0.change }
var price = 0
if let i = changes.firstRange(of: lookFor) {
price = priceEntries[i.upperBound - 1].price
}
return price
}
Is way too slow to be called in a hot loop. I replaced it with the clunkier but faster:
private func purchaseBananas(from priceEntries: [PriceEntry], lookFor: [Int]) -> Int {
for i in 3..<priceEntries.count {
if priceEntries[i].change == lookFor[3] &&
priceEntries[i - 1].change == lookFor[2] &&
priceEntries[i - 2].change == lookFor[1] &&
priceEntries[i - 3].change == lookFor[0] {
return priceEntries[i].price
}
}
return 0
}
I was trawling through a list of ~2000000 sequences, but sorting them so the higher priced ones were first meant that the answer popped out at less than 10000 iterations.
1 Like
As mentioned a couple times, I'm enjoying optimizing after the fact this year. And since we talked earlier here about Grid representations:
I switched over from [[Element]] to using [Element] with computed indices (y * width + x). There are a lot of grid problems this year, and several of them involve making temporary copies of grids (like the guard path problem in #6). I figured copying one bigger buffer ought to be faster than many small ones.
This did help pretty much across the board, except for my original implementation of #15 (double-wide recursively moving boxes). There I had been copying the grid on every step so I could do a destructive move and throw it away if it failed (boxes bumped walls). It turned out that the [[Element]] grid was much better there because most rows would be unedited so CoWing individual rows was better.
Switching over to an algorithm of try a move with no editing, returning a Bool and then only editing the grid if it succeeded (as other people mentioned here on that day) is much faster anyway.
Tweaking the algorithms can make a huge difference. With two days left to go, my original M1 MacBook Air can do all the part twos in less than a second. An M4 Mac Mini in about 2/3rds that time.
Timings
#1 0.003s
#2 0.003s
#3 0.011s
#4 0.001s
#5 0.008s
#6 0.130s 14%
#7 0.084s 9%
#8 0.001s
#9 0.002s
#10 0.002s
#11 0.033s
#12 0.019s
#13 0.016s
#14 0.182s 20%
#15 0.002s
#16 0.008s
#17 0.000s
#18 0.085s 10%
#19 0.014s
#20 0.038s
#21 0.004s
#22 0.278s 30%
#23 0.013s
total 0.937s
4 Likes
Figuring out how to determine the largest intersecting set (day 23, part 2) really hurt my brain but the code ended up running very quickly -- I thought for sure I'd end up some kind exponentially slow algorithm.
Day 23 Spoilers/Code
For part1 I initially used regex to find the initial T (not sure why), but using a sequence knocked that down. I would have liked to use tuples for everything, but the fact that (Substring, Substring, Substring) isn't hashable made me use a single struct.
class Day23: Program {
var nodes: [Substring: [Substring]] = [:]
var pairs: [(Substring, Substring)] = []
func run(input: String) async throws {
parse(input)
print("Part 1 = \(part1())")
print("Part 2 = \"\(part2())\"")
}
private func parse(_ input: String) {
let lines = input.split { $0.isNewline }
for line in lines {
let halves = line.split { $0 == "-" }
guard halves.count == 2 else { continue }
nodes[halves[0], default: []].append(halves[1])
nodes[halves[1], default: []].append(halves[0])
pairs.append((halves[0], halves[1]))
}
}
private func part1() -> Int {
var trios = Set<Trio>()
for (a, _) in nodes {
let aIsT = a.starts(with: "t")
for (b, c) in pairs {
let bIsT = b.starts(with: "t")
let cIsT = c.starts(with: "t")
guard aIsT || bIsT || cIsT else { continue }
if nodes[b]!.contains(a) && nodes[c]!.contains(a) {
var arr = [a, b, c]
arr.sort()
trios.insert(Trio(arr[0], arr[1], arr[2]))
}
}
}
return trios.count
}
private func part2() -> String {
var largestSet = Set<Substring>()
for (a, computers) in nodes {
var set = Set<Substring>()
set.insert(a)
for c in computers { set.insert(c) }
for b in computers {
if !set.contains(b) { continue }
for c in computers {
if c == b { continue }
if !nodes[c]!.contains(b) {
set.remove(c)
}
}
}
if set.count > largestSet.count {
largestSet = set
}
}
var arr = Array(largestSet)
arr.sort()
return arr.joined(separator: ",")
}
}
private struct Trio: Hashable {
let a: Substring
let b: Substring
let c: Substring
init(_ a: Substring, _ b: Substring, _ c: Substring) {
self.a = a
self.b = b
self.c = c
}
}
The problem we have to solve for day 23 part 2 is
click to expand
finding the maximum clique in the graph. I got to this official term by googling “largest fully-connected subgraph”.
If you search for algorithms to find the maximum clique, you are quickly led to the family of Bron-Kerbosch algorithms. In general, the problem is exponential time, but the classic (and simplest) Bron-Kerbosch algorithm sufficed to solve my day 23 part 2 very quickly. The code is a very straightforward translation of Wikipedia's pseudocode:
// Classic Bron-Kerbosch algorithm for finding all maximal cliques.
func bronKerbosch(
r: Set<String> = [],
p: Set<String>,
x: Set<String> = [],
neighborsOf: (String) -> Set<String>,
report: (Set<String>) -> ()
) {
if p.isEmpty, x.isEmpty {
report(r)
}
var p = p
var x = x
while let v = p.first {
let n = neighborsOf(v)
bronKerbosch(
r: r.union([v]),
p: p.intersection(n),
x: x.intersection(n),
neighborsOf: neighborsOf,
report: report
)
p.remove(v)
x.insert(v)
}
}
Note that this algorithm finds all maximal cliques, and a maximal clique is not the same as the maximum clique. The maximum clique is the largest of all maximal cliques. So you have to sort through the reported cliques and print the clique with the most members.
3 Likes
Additional swift-collections data structure use found... (I'm getting a bit excessive with the optimizations.)
Day 22 (buying bananas) involves finding the price for each possibility of 4 sets of -9...9 changes. That's 19 possibilities so you can encode a list of 4 of them into an Int from 0 to 19⁴. (There are fewer than this actually needed, since a sequence of e.g. [-9,-9,...] is impossible, but this gets you down to a manageable size and is fast.) You need to record only the first price for each possible change sequence, so you need a Set of all the change sequences you've already seen for this monkey.
Changing from using a Set<Int> for this purpose to using a BitSet from swift-collections saves a whole tenth of a second! (35% or so.)
I'd like to submit my parsing code for day 24 to be shortlisted for 'worst parsing code of the year'
private func parseLogicWire(from input: Substring, into wires: Wires) {
let gate = toLogicGate(from: input)
var input = input
let firstSpaceIndex = input.firstIndex(of: " ")!
let lhs = input[input.startIndex..<firstSpaceIndex]
let first = input.index(after: firstSpaceIndex)
input = input[first...]
let secondSpaceIndex = input.firstIndex(of: " ")!
let second = input.index(after: secondSpaceIndex)
input = input[second...]
let thirdSpaceIndex = input.firstIndex(of: " ")!
let third = input.index(before: thirdSpaceIndex)
let rhs = input[...third]
input = input[input.index(after: thirdSpaceIndex)...]
let fourthSpaceIndex = input.firstIndex(of: " ")!
let fourth = input.index(after: fourthSpaceIndex)
let name = input[fourth...]
wires[name] = LogicWire(wires: wires, name: name, lhs: lhs, rhs: rhs, gate: gate)
}
private func toLogicGate(from: Substring) -> LogicGate {
if from.contains("AND") {
return .and
} else if from.contains("XOR") {
return .xor
} else {
return .or
}
}
Day 24, part 1
The actual solution I went for in part 1 was a protocol, which is the first time I've used anything more complicated than a struct. I kept a shared dictionary instance between all the wires, and so after parsing simulating the system was trivial. Not sure if it'll scale for part 2.
1 Like
Merry Christmas! Finished up this morning before the family woke up.
Some additional optimization gets down total runtime for all problems to 0.805s. Slowest are #14 (recognize a tree) and then #6 (guard loops), which are the most brute-forcey.
Most code was for #24 (adder logic gates), which was fun to optimize because there is enough there to make data structure changes for better performance. ~250 lines of code (original slow solution was much smaller), solution in ~25 milliseconds.
2 Likes
Merry Christmas! Day 25 (part 1 -- still have stars to go back and try and get) was 99% a parsing problem. Once I parsed the data, the naïve solution worked fine on the real input.