For those who measure at the performance of your solutions, what day is the slowest so far?
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
0
voters
I avoided the "try to do it with just Int" approach not out of foresight, but out of laziness. I thought about how to split an Int in half and decided I couldn't be bothered figuring that out at 7 PM.
Makes me wonder if there's some cleverer way to do #6. My input contains 1,882 squares that are already part of pre-existing loops should the guard wander onto them facing the right way (and it takes me ~6x as long to naively find them as it does to just solve the puzzle).
So it is NOT the case that you could optimize for just making the guard run back over some part of their original path.
TBH the most time-consuming part of updating my code to use Int instead of String was finding a pow(base: Int, exp: Int) function. I understand why Swift doesn't have one but it'd have been useful for this, since I knew the result fit in a Int.
Other than that I was somewhat surprised by how painless it was.
1 Like
No need for `pow`
Much more efficient¹ and less error-prone² to do it like this, anyway:
func tenToThe(_ n: Int) -> Int {
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000,
1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000,
][n]
}
¹ A sub-ulp accurate² floating-point pow function requires at least a few tens of cycles (source: I wrote Apple's, which is one of the fastest); needless to say a table-lookup is much faster. An integer-only pow can be more efficient than floating-point, but still requires at least a few multiplies and some logic. A table lookup is much cheaper
² If converting to floating-point and using pow or exp10, be aware that not every system C library provides sub-ulp accuracy. For those that do not, it's possible to have, e.g. pow(10, 2) evaluate to 99.9999... which will then become 99 when you convert to integer. Darwin and Glibc do not have this problem, but some other platform C libraries do.
2 Likes
I know, I read your other post. IMHO it would be great to some official Swift documentation explaining why Swift doesn't have pow(_ x: Int, _ y: Int), because currently the top result in Google is a StackOverflow answer that just does this:
Int(pow(Double(radix), Double(power)))
Which I knew was a bad idea, but many people finding the StackOverflow answer may not.
Even better if this information could be somehow discoverable in code (declare the pow(_ x: Int, _ y: Int) function but mark it as unavailable?).
Random, but Swift Stdlib does not even have any pow variant. Foundation has.
Foundation doesn’t either, it reexports the C stdlib pow.
1 Like
Wow, I struggled with Day 12 part 2 a lot. First time this year I had to look for hints.
The counting corners was interesting BTW. Using 'masks' to recognise corners in a grid sounds like something I might be able to reuse in the future. For instance to find the right grass tile to show on a map.
Code is still messy. Will do a cleanup round over the weekend - probably.
Day 12 part 2 spoilers
I didn't end up thinking in terms of corners at all, although once I saw other people mentioning it, my algorithm is equivalent.
You can think of sides as being the same as perimeter from part 1, except that you should only count a continuous straight edge once instead of one per square. If you have an 'A' region:
XYZ
AAA
and are looking at the middle A and the direction up, you can tell that its top edge is part of a shared line by 1) turn clockwise and take a step, 2) check that this square is also part of the region, 3) check that the step in the original direction (up) from there is outside the region. Similarly with step 1 turning counter-clockwise.
So this determines whether you share an edge in a direction-generic way. Now all you need to do is decide which one of them should "count". You can make your square coordinates Comparable (the obvious way - x1 < x2 or if equal y1 < y2), then only count the square you are on if it is the minimum of the squares next to it that also share the edge.
This is equivalent to finding the minimum x/y corner but doesn't involve any explicit masks or following along edges. Instead filtering with this test in a count(where:) of each square * direction in the region gives the right answer.
Edit: Never mind. I apparently had submitted the right answer with commas the first time and every time I got it after I assumed I still had it wrong. 
Day 13 Spoilers, Question
So I had a simd/accelerate Doubles based linear system solver on hand, so I used it.
func solveLinearPair(x1:Double, y1:Double, r1:Double, x2:Double, y2:Double, r2:Double) -> SIMD2<Double> {
let a = simd_double2x2(rows: [
simd_double2(x1, y1),
simd_double2(x2, y2)
])
let b = simd_double2(r1, r2)
return simd_mul(a.inverse, b)
}
It got me the answer to part one just fine in combination with an Int initializer that forgives Doubles, to a point. init?(notExactly d:Double, fuzzBy fuzz:Double). I just cannot get it to give me the right answer to part two (bring up and down the fuzz factor) I tried rewriting a solver with just ints, and again my Matrix2DInt.Inverse * Vector2DInt gets me the answer to 1 but not 2. I suspect it's a remainder problem? Is there a trick to avoid all the divisions? I feel like I must be forgetting a trick...
Weird, I could have sworn that C had a pow() for integers. I must have been tricked by my Python roots.
More Day 13 Spoilers
I couldn't manage to get around the precision issues when using Double, but I realized I could rewrite the equation to have a single division with integer numerator and denominators and, at that point, just check if the remainder was zero (let x and let y are the number of times buttons A and B are pressed):
func calculateXY(deltaA: GridDelta, deltaB: GridDelta, prize: GridDelta) -> (Int, Int)? {
let num = deltaB.y * prize.x - deltaB.x * prize.y
let denom = deltaB.y * deltaA.x - deltaB.x * deltaA.y
guard num % denom == 0 else { return nil }
let x = num / denom
let num2 = prize.x * deltaA.y - prize.y * deltaA.x
let denom2 = deltaB.x * deltaA.y - deltaB.y * deltaA.x
guard num2 % denom2 == 0 else { return nil }
let y = num2 / denom2
return (x, y)
}
Rest of the source here.
Interesting to know that using a inverse matrix works too, I thought there was no way around using Ints only. What does simd_double2's inverse return when the the matrix has no inverse? NaNs?
Really cool Part 2 today, in line with Day 11.
1 Like
More Day 13
I wrote a few specialized division styles, but in the end I pulled them all out. You can't look for only clean remainderless divisions because then you get too few answers. There are too many itsy-bitsy remainders that still count to void the answer. The most reliable was a check afterwards that you got a clean answer anyway.
I also passed around a numerator denominator pair for the inverse matrix. It's kinda nutty.
Your way is much much better. As you know, it will be a clean answer if the remainder is zero. So much nicer. Seeing a solution similar to that and trying it and getting the same answer I was getting with my code gave me the confidence to try the answer again!
(note the simd version is now in the gist. Yup NaNs for no inverse! )
For advent of code 2024 Day13... there is a simpler way! (code is very messy, apologies) · GitHub
I just did integer division:
let aPresses = (prizeLocation.x * buttonBOffset.y - buttonBOffset.x * prizeLocation.y) / ( buttonAOffset.x * buttonBOffset.y - buttonBOffset.x * buttonAOffset.y)
let bPresses = (prizeLocation.y - aPresses * buttonAOffset.y) / buttonBOffset.y
and then did a check to see if this equals the expected result:
if buttonAOffset * aPresses + buttonBOffset * bPresses == prizeLocation {
return (aPresses, bPresses, 3 * aPresses + bPresses)
} else {
return nil
}
For me the key insight was, although the puzzle says to 'give the number of A and B presses with the lowest total cost', in practice the formula's were all incrementing as well as co-prime so can only have one solution.
3 Likes
Finally got around to day 12.
Day 12 part 2 spoilers
I didn't think in terms of corners either. My solution was to count the 'connected' sides, where connected are adjacent using the same fence direction
var sides: Int {
let squares = coordinates.map { Square(point: $0, coordinates: coordinates) }
return countSides(in: squares, side: \Square.upFenced, dirA: upDownLeftRight[2], dirB: upDownLeftRight[3]) +
countSides(in: squares, side: \Square.downFenced, dirA: upDownLeftRight[2], dirB: upDownLeftRight[3]) +
countSides(in: squares, side: \Square.leftFenced, dirA: upDownLeftRight[0], dirB: upDownLeftRight[1]) +
countSides(in: squares, side: \Square.rightFenced, dirA: upDownLeftRight[0], dirB: upDownLeftRight[1])
}
(Was very happy to be able to use a KeyPath in anger. Neat!)
func countSides(in squares: [Square], side: KeyPath<Square, Bool>, dirA: Point, dirB: Point) -> Int {
var sides = 0
var lookedAt = Set<Point>()
for square in squares {
if !square[keyPath: side] || lookedAt.contains(square.point) {
continue
}
sides += 1
// Remove connected sides.
let connectedFences = connected(from: square, squares: squares, fence: side, dirA: dirA, dirB: dirB)
for fence in connectedFences {
lookedAt.insert(fence)
}
}
return sides
}
func connected(from square: Square, squares: [Square], fence: KeyPath<Square, Bool>, dirA: Point, dirB: Point) -> [Point] {
var connectedSquares = [square.point]
var toTry = [square.point + dirA, square.point + dirB]
while !toTry.isEmpty {
let trying = toTry.popLast()!
guard let tryingSquare = squares.first(where: { $0.point == trying }), tryingSquare[keyPath: fence] else {
continue
}
connectedSquares.append(trying)
let a = trying + dirA
let b = trying + dirB
if !connectedSquares.contains(a) { toTry.append(a) }
if !connectedSquares.contains(b) { toTry.append(b) }
}
return connectedSquares
}
struct Square {
let point: Point
let upFenced: Bool
let downFenced: Bool
let leftFenced: Bool
let rightFenced: Bool
init(point: Point, coordinates: [Point]) {
self.point = point
self.upFenced = coordinates.count { $0 == point + upDownLeftRight[0] } == 0
self.downFenced = coordinates.count { $0 == point + upDownLeftRight[1] } == 0
self.leftFenced = coordinates.count { $0 == point + upDownLeftRight[2] } == 0
self.rightFenced = coordinates.count { $0 == point + upDownLeftRight[3] } == 0
}
}
I'm sure I'm probably iterating over lists way too many times but it seems to work.
num.isMultiple(of: denom) is worth knowing about because (unlike %) it cannot overflow or divide by zero.
1 Like
Hmmm. Just finished day 14. Feels a bit weird.
Assuming the Christmas tree appears when all robots are on distinct locations. That sounds more like a contrived coincidence than actual design. And relying on visual checks alone didn't work as I got the tree after more than 6000 seconds.
TIL. Thanks!
Spoilers Day 14 Part 2
With no example of what the tree looks like, trying to find it programmatically felt impossible to me. None of my early programmatic approaches worked (I understood why only after seeing the actual image).
However, with no bounds on how many steps it could take to get the tree, going frame by frame also felt like a shot in the dark.
I put together a SwiftUI app displaying a new frame every 50ms anyway. I knew the iteration count had to be between 1000 and 50000 after trying a few answers in the Advent of Code website and getting a “too low”/“too high” response.
At 50ms/step it took only ~2 mins to find the frame just by staring at the simulation (high 6XXXs).
Idk, I feel like today’s problem was a bit underspecified. Was visual inspection the “intended” approach?
I've been thinking about this a little longer. I believe it's sort of a 'signal discovery' puzzle: i.e. somewhere in the input is a signal (the Christmas tree) and with the right 'tuning frequency' (in this case: time elapsed in seconds) it becomes clear.
As a naive signal processing technique, I calculated the standard deviation of the distance for all the points to the average of the point cloud. Assuming that when the signal is 'out of tune' the distribution will be more or less random and once it becomes clear, they get closer together. Returning the 'tuning' with the lowest deviation indeed produces the correct result.
Now, there's probably a better way of measuring 'coherance' in a signal like this than using standard deviation. If you know of any, please let me know.
3 Likes
Wow, I struggled with Day 12 part 2 a lot.
Definitely the toughest so far for me as well. I finally came up with the idea for doing 4 sweeps across each region collecting all "outward" facing edges and then counting the resulting groups. Code is at GitHub - gereons/AoC2024: Advent of Code 2024 if anyone's curious.