Make sure you're building in release mode, Swift's debug mode collections can be very slow.
1 Like
Assuming grid[y] is a String, index(_:offsetBy:) is an O(n) operation; it has to iterate from the start of the string to your specified offset, so you're in an O(n^3) loop. There are a few different ways around that – use String.withUTF8 since you know you're dealing with ASCII, make an array of the indices after calling String.makeContiguousUTF8() and then use integer-based indexing into that, refactor your loop so you're offsetting from a known index rather than from the start of the string each time, work on String.utf8CString() instead, etc.
2 Likes
I just parsed whole file into [[String]] where each element is one character and solution works for less than a second. With that you will work with array of strings where lookup will be O(1) as in any array instead of indexing a String. You can use a [[Character]] as well but a String is more convenient to cast into Ints
1 Like
Thanks folks .. it was a face palm where I was accessing grid as a computed property. I changed it around to only compute once, and tests are < 1s in debug mode. I'm going to play with UTF8 and [[Character]] tonight for fun, really appreciate the feedback!
1 Like
I have found in the past years (2019-2022) that having a fast and easy way to parse inputs makes the challenges much easier to solve. I historically have used a hand rolled parser combinator based on pointfreeco's parsing series, and I'd highly recommend checking out their parsing library GitHub - pointfreeco/swift-parsing: A library for turning nebulous data into well-structured data, with a focus on composition, performance, generality, and ergonomics. which makes these concepts accessible and performant. (Shout out to @stephencelis and @mbrandonw to their great work!)
6 Likes
Another option is to track coordinates of the grid independently. For example, here's a sketch of my solution:
spoilers
// struct to hold a part number, and it's location along the line
struct PartNumber {
var number: Int = 0
let start: Int
var end: Int
}
// and one for parts
struct Part {
let symbol: Character
let x, y: Int
var adjacent: [Int] = []
}
for (y, line) in lines.enumerated() {
for (x, c) in line.enumerated() {
if let digit = c.wholeNumberValue {
// stash the (x,y) coordinate for this number, record you've started parsing a number,
// and keep parsing it forward digit by digit
} else {
// stop parsing a number if you were, stash the part in a list for line y
// then check if this character represents a part
if c != "." {
// ...
}
}
// post process to zip together the accumulated parts and part numbers
I appreciate many will find this extra bookkeeping a hassle. I am biased, but I prefer it this way for two reasons:
- I am amazed at people who can just crunch these things and get on the leaderboard in under 10 minutes, entirely based on arrays, dicts, and integer index manipulation, without defining types or helper methods. That's beyond me. The code above takes a bit longer, but I'm more confident it'll be right.
- More importantly: for today's puzzle, if there was any non-ASCII character then the utf8 approach falls over epically. And I'm not just talking family emoji with skin tone here. Any character that takes two code units will screw everything up. And OK, fine, this is Advent of Code and they're going to stick to ascii. But most data in the wild makes no such promises.
So I'd suggest if you want an integer-indexed solution, going with [[Character]]. Using this approach, I translated this leaderboard solution from python to Swift pretty much line for line.[1] But unlike the Python version, the Swift one will handle non-ascii characters. A swift version that used the utf8 view wouldn't, though.
except for the
Set<(Int,Int)>... since we don't have tuple conformances yet. I used aSIMD2<Int>which is close enough. ↩︎
6 Likes
Think will be able to write complex regular expressions myself by the end of advent 
which I wanted to figure out for quite long, so win-win 
1 Like
Another types-and-helper-methods approach: Last year's AOC 2022 had several grid-based problems, so after the first couple, I ended up writing a generic Grid Collection, where you initialize it with the problem input string and a closure to map an input Character to whatever your desired Element type is. (And you can make [[Character]] your internal structure by just passing the identity {$0} as the mapping closure.)
Reusing that yesterday helped a lot.
3 Likes
I don’t think it made a practical difference in my day 5 p2 solution, but shoutout to @nnnnnnnn (and everyone else who worked on it) for GitHub - apple/swift-se0270-range-set: Swift Evolution preview package for SE-0270.
4 Likes
Hey so I got stuck on Day 5 for a little bit because my code hung on the part 2 data and I spent a long time thinking my code was inefficient, but it was actually a weird hang!
I wrote an extension on ClosedRange<Int> which contained the code
guard !other.contains(self) else {
print("other contains source entirely. Nothing left over.")
return []
}
Which I expected other.contains(self) would return true if self was fully inside or== to other but I didn't put it to a hard test and it worked fine on the sample data.
When I loaded the real data it just freezes entirely. Recreated here with my very verbose extension that got really long as I tried to find the problem.
//This one works fine.
let resultC = (2442...2679).crop(by:2321...2446)
print(resultC)
print(Int.max)
//This one Hangs.
let resultD = (2442763622...2679835230).crop(by:2321931404...2446354471)
//let result = (0...9).crop(by:3...8)
print(resultD)
I wrote my own fullyContains, every thing worked fine.
I feel like there must be something obvious about those numbers or how Range.contains() works or both that makes the problem obvious and I'd love to be pointed in the right direction since I will likely be using Range again!.
Thanks!
3 Likes
Because it's probably doing a full sequence search - which means it has to expand those ranges into a collection eventually and that is most likely where the time is being spent.
So it's searching for a collection with 2446354471 - 2321931404 + 1= 124,423,068 elements inside a collection with 2679835230 - 2442763622 + 1 = 237,071,609 elements! I wouldn't recommend laying out collections with hundreds of millions of numbers in memory.
Checking the bounds is the way to go, or use the provided overlaps which does that - and returns quickly (albeit idk what you are expecting your output to be).
Edit: if you want some memory math with 64 bit Int (and this is just a lower bound):
a = 237,071,609 * 64 bits to GB = 1.8965729 GB
b = 124,423,068 * 64 bits to GB = 0.9953845 GB
a + b = 2.8919574 GB
So first it has to build those collections and then search through them. Running that code through a package or command line project will show that behavior.
1 Like
Okay, let me see if I understand. In Swift, Range is not is own thing, but inherits .contains() from the Collection protocol(?) and since a Collection is not necessarily contiguous the default .contains() going through every item in the range rather than just doing the bounds checking (which was an erroneous assumption on my part)?
Hunh. Good to know. Sounds like I need to spend some more quality time studying the Collection code if I want to use them for this. But Since a Range will always be contiguous by definition (yes?), it might be a good pitch to have the built in contains() be a bounds check? Possible pitch 
2 Likes
This doesn't even need a pitch, since there's no change to the behavior and no new functionality introduced.
2 Likes
Yes, Range and ClosedRange conform to Collection so it inherits the sequence contains, which you are using.
The way they are designed makes sense in their domains: collections check to see if they "contain" one another and ranges check to see if they "overlap" one another.
it might be a good pitch to have the built in
contains()be a bounds check?
Range and ClosedRange implement their own contains for single elements, which compare against the bounds.
2 Likes
Oh, so, does this seem like a reasonable change to the default behavior? Should I create its own forum post? A Feedback? An Issue? I don't feel "at one" with the Range code / how people currently use it by a long shot so I'd hesitate to go straight to a PR 
Going straight to a PR would be completely fine, but an issue on the Swift GitHub repo is also OK.
2 Likes
It kinda does make theoretical sense to have Range/ClosedRange implement their own contains of signature:
public func contains<C>(_ other: C) -> Bool where C: Collection, C.Element: Strideable, C.Element.Stride == Int
which is an O(n) performing bounds and stride checks linearly in other. However whether this belongs in the standard library is unknown to me.
Just a small note, Collection and Sequence are protocols, so you don't inherit, but more like implement or define behaviour.
On this note have a question—I don't see Range and ClosedRange having contains(_: Self) being implemented, can someone point me out? 
ah, ok, found it here
So it's like default implementation for Collection if Element is Equatable (that's why I haven't seen the implementation on my side...) in String processing.
There is even a issue like that And agree here, shouldn't be exposed to all Collections...
Question related to Day 8:
Am I right in that Swift doesn't provide a built-in LCD function? Seems like it's common in other languages, and it would be an easy add to swift-numerics, for example. Should it be?