Interesting, it does. What I now want to understand: why? :-)
Edit: It seems these create closures. Creating and passing a func plus(_ a: Int, _ b: Int) -> Int { a + b } is much faster.
I'm not sure if this is intended behavior or a quirk in the parser, to be honest. For example we accept this:
let x: ((Int, Int) -> Int, (Int, Int) -> Int) = (+, +)
From a parser standpoint it would have been a bit nicer if you had to spell the reference as (+) everywhere and not just a bare operator token as we allow (in some cases) today. But at this point, it's probably best not to change the rules in either direction.
EDIT: Since return + and similar are not allowed either, I think the rule could be understood as, if you're inside a nested expression that already contains one level of (), you can just refer to the bare operator, but otherwise if you're at the top level of a statement, closure, or collection literal, you have to wrap it in parens.
That's surprising. (+) expands into a closure literal, { $0 + $1 } basically, but since the closure does not have captures it should be equivalent to a reference to a named function without captures.
Thank you for the very detailed breakdown. Certainly a lot more efficient than my solution!
@scanon -- I started out using ternary, but this is where my weak math skills come and bite me, because I couldn't think of an easy way of pulling out each ternary... trit...? out of a number. At least not at speed. Thinking about it now you could do it by dividing by decreasing powers of 3, so now I have two better solutions than what I did.
I suspect there are infinitely many. 
FWIW, staying in the integer representation to do concatenation is pretty clean (and much faster than going to String and back, not that it matters):
let power = last < 10 ? 10 : last < 100 ? 100 : 1000
if goal % power == last && canMake(goal / power, from: inputs) {
return true
}
The generation of power can be made somewhat cleaner, but the largest term is three-digits and this is dead simple.
1 Like
I did it this way but dropping in and out of strings was maybe really slow. Also checking for padding hadn't been necessary using a bit mask on only a subset of a UInt32 in part 1. Is there a faster way? (ignoring that the whole solution is super brute force and probably shouldn't be done at all 
)
func makeRadix3OperatorsList(from number:UInt32, ofWidth places:Int) -> [(Int, Int) -> Int] {
var operators = [(Int, Int) -> Int]()
//var forVis = [String]()
func cat<I:BinaryInteger>(_ a:I, _ b:I) -> I {
return(a * (I(log10(Double(b))) + 1)*10) + b
}
var r3s = String(number, radix: 3)
let width = r3s.count
if width < places {
r3s = r3s.paddingLeft(count: places-width, with: "0")
}
//print(number, r3s)
for i in 0..<places {
//print(i, r3s[i])
switch(r3s[i]) {
case "0":
operators.append(+)
//forVis.append("a")
case "1":
operators.append(*)
//forVis.append("m")
case "2":
operators.append(cat)
//forVis.append("c")
default:
fatalError("how r3s[i] (\(r3s[i])) wasn't 0,1,2 ")
}
}
//print(forVis)
return operators
}
extension StringProtocol {
subscript(offset: Int) -> Character {
self[index(startIndex, offsetBy: offset)]
}
func paddingLeft(count:Int, with c:String.Element) -> Self {
Self(stringLiteral: "\(String(Array(repeating: c, count: count)))\(self)")
}
}
func canMatchValueRadix3(_ matchValue:Int, with subValues:[Int]) -> Bool {
let places = subValues.count - 1
assert(places < 20)
let widthChars = String(Array(repeating: Character("2"), count: places))
let widthValue = UInt32(widthChars, radix: 3)!
//print(String(widthValue, radix: 3), " should be \(places) wide")
let numbersToCheck = Array(0...widthValue).shuffled()
for number in numbersToCheck {
let operatorsNumber = makeRadix3OperatorsList(from: number, ofWidth: places)
if operate(on: subValues, with: operatorsNumber) == matchValue { return true }
}
return false
}
1 Like
It's fairly straightforward to pop off the first two numbers (because there's no precedence), apply an operator, then push the result back on. Try all possibilities and see if you get the desired result:
func evaluate(_ testValue: Int, operands: [Int]) -> Bool {
let operators: [(Int,Int)->Int] = [{$0 * $1}, {$0 + $1}, { Int($0.description + $1.description)! }]
for o in operators {
let v = o(operands[0], operands[1])
if operands.count == 2 {
if v == testValue { return true }
} else {
if evaluate(testValue, operands: [v] + operands.dropFirst(2)) {
return true
}
}
}
return false
}
This naive try-em-all approach still only takes half a second to run.
I have now implemented two different approaches to today's (9) part 2. They both solve the test data, but give very very different answers for my real data.
Neither of which answer is correct! Ha!
A very AoC experience.
2 Likes
Feels so familiar! Along with the sinking feeling as you realize that your part 1 solution needs to be rewritten from scratch for part 2 because you optimized for the wrong thingsâŠ
1 Like
Probably worth a late hint that Heap from the Collections package is quite handy for part 2 today (Day 09).
Today (day 10) was (for once) the exact opposite for me. My first pass at part 1 was the solution for part 2. (I read the uniqueness requirement on the final 9, and then promptly forgot about it.)
I'm curious, does this mean there's an O(N log N) solution? As I read the problem it seems to require a first-fit free traversal for each file, O(N^2).
Yep! The key insight is that active free blocks can never get larger (you might end up with adjacent free blocks, but only in the part of the disk that you no longer care about). Therefore you can maintain a separate heap for each possible block size 1-9 and achieve O(n log n) with only two traversals of the data (one front-to-back to parse and setup the structures, one back-to-front to move each block to its final location and compute the checksum).
5 Likes
Ah! Nine heaps! Nice.
Edit - Implemented a solution which used this algorithm:
(The hard part was convincing Xcode to add the Collections package. It kept freezing in its "Preparing..." step.)
My original N^2 solution: 0.08s
Free heaps: 0.002s
40x improvement
1 Like
You are not alone. I did the exact same thing!
1 Like
Day 11 was definitely my favourite so far. Part 1 I did in a very inefficient* manner (array of strings). Of course that fell over for part 2. I'm very curious how other people approached this.
(* Although through my naive optimisations failing, I found out that the Swift compiler did a pretty good job of removing copies and allocations which is something I've been curious about as I write naive functions that take arrays and return new arrays etc.)
Spoilers For Part 2
The key for me was realising that despite the problem going out of its way to say that the order matters, and they stay in place when splitting etc etc, the actual problem just needed the sum, and so that wasn't a real restraint.
I ended up using a [String: Int], mapping the number of stones of a given value.
func part2(input: [String]) throws {
var stoneCounts: [String: Int] = [:] // problem says order matters -- it doesn't
for stone in input {
stoneCounts[stone] = (stoneCounts[stone] ?? 0) + 1
}
for i in 0..<75 {
var backCounts = stoneCounts
for (stone, count) in stoneCounts {
if stone == "0" {
backCounts[stone] = (backCounts[stone] ?? 0) - count
backCounts["1"] = (backCounts["1"] ?? 0) + count
} else if stone.count % 2 == 0 {
let newStones = split(stone)
backCounts[stone] = (backCounts[stone] ?? 0) - count
backCounts[newStones[0]] = (backCounts[newStones[0]] ?? 0) + count
backCounts[newStones[1]] = (backCounts[newStones[1]] ?? 0) + count
} else {
backCounts[stone] = (backCounts[stone] ?? 0) - count
let newStone = String(Int(stone)! * 2024)
backCounts[newStone] = (backCounts[newStone] ?? 0) + count
}
}
stoneCounts = backCounts
}
var sum = 0
for (stone, count) in stoneCounts {
sum += count
}
print("len2=\(sum)")
}
I'm sure the way I'm handling those dictionary look-ups is missing some sugar or helper function, but it works!
1 Like
Benâs memoization helper proved invaluable for Day 11. My solution.
1 Like
Nice!
I was looking for something like this. I had to wrap the function in a datastructure to prevent data races to the cache. This is a very clean solution.
1 Like
There is a very useful subscript for dictionaries that includes a default value, so you can write backCounts[newStone, default: 0] instead of (backCounts[newStone] ?? 0). The nice thing is that this works when setting as well, so the update lines can become:
backCounts[stone, default: 0] -= count
backCounts[newStone, default: 0] += count
2 Likes
Day 11 spoilers
While the total number of stones grows exponentially, the set of unique numbers on the stones grows very slowly, and converges to a stable set in iteration 89 (on my input data, but I expect other data inputs to behave about the same). This makes it very tractable, even without any memoization.
Day 11 Part 2 has been the hardest problem for me so far. I really liked it, though: there's something beautiful about the extremely short prompt of just increasing the loop count. 
At first I thought the main problem was the slow and memory-inefficient String operations I was doing, so I rewrote everything using Int instead. Due to a bug, I saw my computations overflowing even with a limited number of iterations, so I went on a small detour to Decimal before finding the bug and re-implementing the Int version.
Then... it was still not the right approach. Int bought me a few extra iterations before slowing to a crawl, but still far away from the goal, and it became evident that memory usage was too high for it to be nowhere near the right approach. I didn't know it at that point, but even with Int, generating the full array of values would have taken ~1.6 TB of memory. Ooops.
I stumbled for a while trying to find some clever pattern in the resulting number of digits without doing the multiplications (given problem constraints), obviously with no luck. I dismissed the right approach early on because looking at the raw output of a sample step, I thought there weren't enough repeated numbers for the optimization to cut down the multiple orders of magnitude separating my code from the answer.
I got spoiled that the problem had something to do with Dictionary so I implemented the optimization anyway, and, to my surprise, the result popped up instantly. Makes sense in retrospective, but still... anyhow, one of my favorite problems.
1 Like