Adventures in Advent of Code | Hacker News Reader

Adventures in Advent of Code

davedelong.com

136 pointsingve67 comments

When your code fails it's never the fault of the language. It's always ones own fault, a typo, some error in the logic, or something. Debugging always reveals that with a stone face. Always.

Except

> "It turns out, there was a bug in Set.intersection(_:), but it had only been discovered this past June, and the fix hasn’t made it into a public version of Swift yet. "

Don't know what to search for to bring it up but there's a story HN used to post occasionally about finding a CPU bug... talk about Always. Except.

(Hi, I'm the author of the post)

It turns out the bug fix has been released publicly, but only on newer OS versions.

Or if you compile in release mode, in which case the fixed version is (maybe only sometimes?) inlined into your executable.

I ran into the same bug, but since I'd included a `precondition` to verify that each elf-group had only one common item type, I discovered the bug immediately. I then needed about 5-10 minutes to convince myself that it really was a Swift bug and not a mayoff bug.

Yeah, luckily, those exceptions are really rare. Last time one happened to me I wasted three days before finding the culprit.

As someone who worked on C compilers for DSPs for a few years, I was conditioned for a while to think "compilers are broken, libraries are broken - you have no hope" for a while, when all I dealt with was our software. Obviously that's heavily influenced by what I was actually dealing with day to day and not by normal software development, but still :)

One of the guys in my team handled a frantic support request from a Formula 1 team because they required reproducible builds or else they got some fine from the FIA, and they somehow hit a situation where our compiler was outputting different code depending on time of day. Wild.

From your description of the bug, I think even know which compiler you worked on. I worked on a competitors compiler. The state of embedded tools in the lates 90s and early 2000s was deplorable. I'm surprised we got anything working. (I went to work for the compiler team because I was so pissed off at how poorly they worked.)

I should maybe have just said, it's not like it's sensitive information. It was @ Analog Devices, and given the engineer who was assigned to this bug I think it would have been for their TigerSHARC DSP. Trying to think who you might have worked for - Green Hills maybe?

The compiler itself felt well-written and there were some very smart people involved in developing it. And now that I think about it the bug wasn't different code being output but some value elsewhere in the generated binary itself - maybe some ELF header? I wish I could remember

Ah, I worked at ADI too. I rewrote the TigerSHARC register allocator (not adopted [complicated reasons, but Edinburgh wouldn't accept changes from the US]), and left the DSP group, and soon afterwards ADI.

I thought you meant TI. Their compiler would compile in the date of compilation as a string by default (it wasn't deadcode eliminated in the linker because it was sucked in their panic libraries, if memory serves).

In any case, yeah, ADI.

Miscompilations (interpretations) are fairly common in my experience; just most of them don't drastically affect the final result.

I used to have a methodical way of investigating most bugs: (1) here's what I know, (2) here's what I don't, (3) here's the thing I would like to know to most restrict the remaining search space. It was fine enough for awhile, but when you don't know things like "I wrote a 0 here, therefore a 0 exists here", or "my code explicitly uses aligned 32-bit reads, so I issued an aligned 32-bit read here", the errors in your assumptions quickly get amplified into nonsense. Nowadays I explicitly includle miscompilation (interpretation), bit-flips, and other such garbage as I write down what I do or don't know about the system, and I throw in ballpark probabilities to figure out where to look next. Most debugging isn't noticably slower that way, but the hairy problems are easily 10x easier when you haven't conditioned yourself to ignore the real solution.

For most engineers, you’ll have a handful of times in your career when the compiler or runtime really is the problem. The rest of the time it’s like 95% your fault and 5% the library’s fault.

I'll be doing AoC in C this year. And I've decided to do that every year as I enjoy doing it in C and trying to get the entire calendar, all 50 parts to run in less than one second on a single core, which it turns out is quite doable, but only with a much deeper understanding of the problems. I end up learning a lot more computer science this way.

I also like it since I don't do any work or even side projects in C these days, and so it's nice to keep my C chops up to scratch.

Nice! I’m writing in C this year too, although I’m very much a beginner in C.

What kinds of optimisations have you had to do? Are you hosting your code anywhere?

For doing it in C, by far the most useful thing you could do is implement your own generic hash table. Having a good hash table handy makes things a lot easier. Though since you're a beginner you might want to find a good library for it at first. Writing a hash table is great C exercise though, so I definitely recommend doing it at some point.

I don't necessarily want to share my github as it contains my real name, but I'd be willing to send you a tarball of my 2020 code tomorrow if you send an email to mtlmtlmtlmtl at pm.me

I've just now started on day 1 for this year, so no code there yet worth showing off.

I think I understand how to build a hash table except for one thing: which hash function should you use? Is there a simple one that’s good enough for most things? How do you pick one?

if your hash table is a really good modern open addressed hash table, something like Google's Swiss Tables, you need a really good hash because you will be badly penalised otherwise, these modern structures demand a hash with proper behaviour for even halfway reasonable performance.

If it's just a My First Hash table with closed addressing, buckets etc. you needn't care too much. If you're hashing integers, just use the integer itself, that's a terrible "hash" but with this like 1980s data structure it's good enough.

A lot of the time if the key is an int however you can get away with an array assuming the range is reasonably small.

Worth noting that for AOC I got by just fine with the simplest possible bucket based implementation.

You would write your hash table constructor to accept a hash function as a function pointer then pass in the appropriate hash function for whatever the key type is.

You can use the same hash function for any arbitrary struct as long as there's no pointers in it. If there are pointers, you'd have to implement one combining the hashes of all the members through something like xor. I used fnv1a_64 for my hash function in AOC 2020 which is a pretty good general choice for strings and other contiguous objects and is just 10 lines of code. Pseudocode on Wikipedia or I'm sure you can find C code on Stackoverflow. Hope that helps :)

Short answer: FNV-1a.

https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo...

https://github.com/rurban/smhasher#summary

Hat tip if you did 2021:14:2 under this constraint. I didn’t find the trick to allow that type of performance.

I don't think I did the 2021 one, but I did do 2020.

Is that the right day? My code for 2021:14 runs in 440 microseconds for both parts. 2021:23:2 is the only day I couldn't get under 1 second.

https://github.com/forrestthewoods/aoc2021/blob/master/rust/...

I struggled with that one; thanks for linking your code; I’ll have a look and see the trick I missed.

The key is you didn’t need to keep track of the strings, just the counts.

I have a writeup of my 2021 solutions at https://programsareproofs.com/articles/aoc_2021.html. I got day 23 down to 31ms using Rust.

My 2021 day 23 runs in 5 milliseconds for both parts using A* with a custom heuristic: https://github.com/orlp/aoc2021/blob/master/src/bin/day23.rs

Day 22 (https://adventofcode.com/2021/day/22) is the one that nearly killed me in 2021. I did get it using a technique of breaking any overlaps into smaller and smaller rectangles, but it took like 30s to run. I looked on the AoC reddit, and honestly I still don't understand what I needed to do to make it better, but visualizing 3d spaces has always been a weakness for me.

My target is usually 1 second each, because that feels about right for my patience, rather than 1 second overall target.

My 2021 (Rust) solutions all meet that, but some only do so when optimized, and day 22 was one of those where without the optimizer I'm waiting 2-3 seconds for an answer.

IIRC the trick was to compact the indices, so e.g instead of thinking about X values of 120203 494302 and 109383 you call those 1, 2, 0. Do all the working out of which cells within the resulting tiny structure are on or off, and then expand the 1x1 cells you're talking about to their true size based on the real values instead of indices.

My day 22 solution runs in <10ms: https://github.com/orlp/aoc2021/blob/master/src/bin/day22.rs

The trick I used was to represent signed volumes, compute the intersection and then store the 'negative cube' instead of splitting up cubes.

Yeah same! It really was a tricky one for me: https://github.com/sordina/advent2021/blob/solutions/src/Adv...

Having to update your entire OS to get bug fixes in a programming language is... not ideal.

It’s the way it works with libc too, right?

That depends on if you consider libc to be a part of the OS. Only the BSDs (including MacOS) do.

Wow, Dave DeLong! A name that reminds me of learning Objective-C for an internship in 2010. As he was very active on Stackoverflow back then, and blogging too, maybe? I haven’t kept track much of Swift and the he Apple ecosystem since, but seeing this post brings back good memories.

I'm confused. The post mentioned that this was fixed in Swift 5.7, but I have Swift 5.7.1 on my macOS Monterey and the bug is still present if I modify my AoC solution to exhibit the problem. Is Swift 5.7.1 on Monterey different from the 5.7.1 on Ventura?

    $ swift -v
    Apple Swift version 5.7.1 (swiftlang-5.7.1.135.3 clang-1400.0.29.51)
    Target: arm64-apple-macosx12.0

I love Swift as a language, but the lack of release notes for 5.7.1 (aside from a blog post for 5.7 as a whole), OS-specific releases (especially for SwiftUI), Xcode removing old toolchains when it upgrades (making me re-download tvOS 15.4 runtime for no reason), and all these other little things are starting to weigh on me.

Turns out the fix is only on Ventura. I was also on Monterey. I updated the blog post to include this.

But that's my question. Similar to the other comment at https://news.ycombinator.com/item?id=33848354, I have 5.7.1 on Monterey. 5.7 isn't restricted to Ventura. Is the problem that the fix in 5.7/5.7.1 didn't actually fix it?

The 5.7 compiler runs on Monterey, but the runtime is still 5.6, AIUI.

The bug is apparently in the Swift runtime. You may be compiling with Swift 5.7.1, but you must be picking up the older runtime distributed with macOS 12.6. I think you can still run locally against a more recent Swift runtime though:

https://news.ycombinator.com/item?id=33848354

Ah, I forgot that compiling with an SDK version doesn't necessarily mean you get the runtime with it. Dynamic linking instead of static linking. Sometimes, software development gets too complicated; too many things to keep in mind.

I'm doing AoC in ChatGPT this year:

https://news.ycombinator.com/item?id=33821092

I picked go for my language this year, which doesn't have good support for sets. May end up writing my own buggy implementation of this.

What if you used a map and stored the value as a key? Then get all keys? Could work as a simple alternative and you could check if values are in it.

Requires thinking if you want to implement set difference or intersection. I just figured depending on needs using existing built-in types may be fun.

You don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.

Great idea!

Could you expand on this, ideally with a python implementation?

Here you go. https://pastebin.com/raw/BzEQ1bfe

For the problem we don't care how many instances of each letter occurs. We just need to know if there is 0 or 1 instance of a given letter. A set is a pretty good way to do this. Store a set of each "compartment", intersect the two sets, and you should have one value.

We can do the same thing except instead of a set we use an integer and set bits. a-z are bits 0-26 and A_Z are bits 27-52. We can set a bit with bitwise-or. We can intersect two masks with bitwise-and.

My code is probably a little too verbose. I'm not super familiar with python so I wasn't sure the best way to deal with characters and integers. But it's functional.

Intersections are the reason you'd want a set, as the original post indicates. See the problem here: https://adventofcode.com/2022/day/3 (sets are even more of a fit for part 2, which is hidden for an anonymous viewer).

Sure, but intersections are straightforward to write with Go maps:

  for key, _ := range first {
      if _, found2 := second[key]; found2 {
        if _, found3 := third[key]; found3 {
          // This is the intersection of 3 sets
        }
      }
    }

That's pretty much how every one emulates them, with a `map[{TYPE}]struct{}` or possibly `map[{TYPE}]bool` if the space isn't a problem, and you find it easier to read (or if you want to be able to check for membership by indexing instead of using the comma ok idiom).

Right, that's exactly what I've done and is, I think, the idiomatic way to do it in Go. I meant for things like intersection, union, etc I will have to write my own implementations, but that's part of the fun!

I hear you. That's part of the joy I seek with AoC.

Most years I choose a language I've never worked with commercially (e.g. Fennel in 2022) and rather than reach for prebuilt libs for timesaving fancy array or set or string ops, I'll invent those wheels myself without dependencies and I find a ton of satisfaction in it. Unwise commercially but ideal for learning and play. And, yeah, bugs!

IMO, when it's not a customer paying for my learning curve, there's a lot to be said for rewalking old paths with new boots (or no boots and funky coloured glasses). Also, a terrible way to get onto the leaderboard IME!

It is great fun to try and build as much as possible yourself. Last year I ended up with a pretty good A* implementation in Clojure cos it kept coming up in the puzzles and I learnt a ton from doing it.

Related: It's possible to simplify things using bitmaps: https://github.com/antirez/adventofcode2022/blob/main/day-3/...

Hey, just noticed our impls. for Day 2 look very similar. If you’re curious, Day 2 can be further improved by using modulo + 2 (or 1 if compiler is smart enough) branches instead of lookup table: https://github.com/neon-sunset/AOC2022/blob/main/Day2/Progra...

In which way do you reckon doing modular arithmetic is an improvement over two 3x3 look-up tables?

The rationale is as following - if the compiler cannot fold the lookup table, then math with 1-2 branches will be much cheaper because it involves no memory access and has constant (low) latency (keep in mind that when for example selecting a literal, a conditional select might be emitted which is usually cheaper than a regular branch e.g. Aarch64).

In addition, unlike in C, in many other languages indexing into array will involve bounds check if the compiler cannot prove that the access is always in bounds. Obviously most branches will be predicted but branch retire throughput is always lower than math operations throughput.

Thanks for the reply. The bounds checking is a valid reason I haven't thought of. In my case, using 3x3 array is roughly 3-4 times faster.

I'm doing AoC in Rust and Go. Go, because I got cozy with it during this year. With Rust, however, I never did. I tried, though. So let's try again.

> The bug is fixed in Swift 5.7, but my computer is running macOS Monterey (12.6) and thus using an earlier version of Swift. I have since confirmed that the code works as expected on macOS Ventura.

I guess the bug is apparently in the Swift runtime itself, and since Swift 5.0 and ABT stability, the runtime version is tied to the OS version.

https://www.swift.org/blog/abi-stability-and-apple/

But I think that only applies to deployments via the App Store. I think for local development you can run against the current runtime by setting the TOOLCHAINS environment variable (you may also need to set SDKROOT).

https://www.swift.org/getting-started/#on-macos

ETA. Apple does not make it easy to replace the runtime, but I got it to work like this:

    $ sw_vers
    ProductName: macOS
    ProductVersion: 12.6
    BuildVersion: 21G115
    
    $ cat foo.swift
    let a = "gnmCjzwnmCPTPhBwPjzBgqPjllJJSWlhfhQDSrpJRhDSlfJl"
    let b = "rLHNHrLHVNbVHMMctZFHsbcsDSDWpSDSGfSRsRWSRllfGSSG"
    let c = "NNtdMVrLNdZNvLvLZrzCndqBgwwPmwgjggBn"
    
    var s1 = Set(a)
    s1.formIntersection(b)
    s1.formIntersection(c)
    print(s1)
    
    var s2 = Set(a)
    s2.formIntersection(Set(b))
    s2.formIntersection(Set(c))
    print(s2)
    
    $ swiftc -version
    swift-driver version: 1.62.15 Apple Swift version 5.7.1 (swiftlang-5.7.1.135.3 clang-1400.0.29.51)
    Target: arm64-apple-macosx12.0
    
    $ swiftc foo.swift
    $ ./foo
    ["P", "r", "C", "z", "w", "m", "B", "q", "j", "g", "n"]
    ["r"]
    
    $ otool -L foo
    foo:
     /usr/lib/libobjc.A.dylib (compatibility version 1.0.0, current version 228.0.0)
     /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1319.0.0)
     /usr/lib/swift/libswiftCore.dylib (compatibility version 1.0.0, current version 
    $ DYLD_LIBRARY_PATH=/Library/Developer/Toolchains/swift-5.7.1-RELEASE.xctoolchain/usr/lib/swift/macosx ./foo
    ["r"]
    ["r"]

Note that I had to download and install Swift 5.7.1 from swift.org. Trying to use libswiftCore.dylib from Xcode-14.1 is no bueno:

    $ /Applications/Xcode.app/Contents/Developer/usr/bin/xcodebuild -version
    Xcode 14.1
    Build version 14B47b
    $ DYLD_LIBRARY_PATH=/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift/macosx ./foo
    ["B", "P", "q", "C", "r", "n", "j", "w", "m", "z", "g"]
    ["r"]

Oh, it's because /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/swift-5.0/macosx/libswiftCore.dylib is x86_64 only for some reason and I'm testing on an MBA M1.

The dylibs under /Library/Developer/Toolchains/swift-5.7.1-RELEASE.xctoolchain/usr/lib/swift/macosx are arm64 and x86_64.

WTF Apple?

Not only that but here is some of my output:

    $ otool -L AdventOfCode2022
    AdventOfCode2022:
        /usr/lib/libobjc.A.dylib (compatibility version 1.0.0, current version 228.0.0)
        /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1319.0.0)
        /usr/lib/swift/libswiftCore.dylib (compatibility version 1.0.0, current version 5.7.1)
        /usr/lib/swift/libswiftCoreFoundation.dylib (compatibility version 1.0.0, current version 120.100.0, weak)
        /usr/lib/swift/libswiftDarwin.dylib (compatibility version 1.0.0, current version 0.0.0, weak)
        /usr/lib/swift/libswiftDispatch.dylib (compatibility version 1.0.0, current version 17.0.0, weak)
        /usr/lib/swift/libswiftIOKit.dylib (compatibility version 1.0.0, current version 1.0.0, weak)
        /usr/lib/swift/libswiftObjectiveC.dylib (compatibility version 1.0.0, current version 6.0.0, weak)
        /usr/lib/swift/libswiftXPC.dylib (compatibility version 1.0.0, current version 6.0.0, weak)
        /usr/lib/swift/libswiftFoundation.dylib (compatibility version 1.0.0, current version 1.0.0, weak)

Not only does it say that libswiftcore is 5.7.1, but that /usr/lib/swift folder doesn't have any of those files there. Very very confusing. I don't like any of this.

I appreciate your write-up and research into all of this though! I tried googling for what runtime version of Swift is installed in Monterey and couldn't find anything. This is incredibly opaque.

Use DYLD_LIBRARY_PATH and DYLD_PRINT_LIBRARIES when running the compiled binary to see what's actually being loaded. It doesn't appear that DYLD_LIBRARY_PATH influences the output of otool -L.

I wasn't able to get `swift repl` to use anything but the system runtime, maybe because it's signed. Maybe it can be made to work by stripping the out the signing but to be quite honest, I'm done with this at this point.

I've been happily using Python to solve AoC. Y'all gluttons for punishment doing this in Swift:

    def part2():
        total = 0
        group = []
        for line in INPUT.splitlines():
            group.append(line.strip())
            if len(group) < 3:
                continue
            common = list(set(group[0]) & set(group[1]) & set(group[2]))
            group = []
            assert len(common) == 1
            c = common[0]
            p = ascii_letters.index(c) + 1
            # print(c, p)
            total += p
        print(total)

The Truth Matters and Secular Humanists Should Defend It <-- The ADVENT of TRUTH!

Wait, that would actually be a good thing...

Adventures in Advent of Code <-- For people who really BELIEVE in the CODE! WTF HN?

No I won't be participating in Advent of Code, and no, it is not one of the highlights of my holiday season.

The highlights of my holiday season are stepping away from the keyboard and spending time with friends and family. The highlights of my holiday season do not include doing leetcode exercises, much as a I realize the need for leetcode exercises.

So, no. I will not be participating in your Advent of Code.

Is this relevant to the post/discussion though?

Me neither, though it's a great exercise for learning a new language. I'm planning to do it in Haskell some time next year, but certainly not now, as the end-of-year period is already stressful enough.

Reply on news.ycombinator.com