4 ms·
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.
by shaftoe444 4y ago
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.
- angrais 4y agoWhat 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.
- forrestthewoods 4y agoYou don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
- shaftoe444 4y agoGreat idea!
- angrais 4y agoCould you expand on this, ideally with a python implementation?
- forrestthewoods 4y agoHere you go. https://pastebin.com/raw/BzEQ1bfe 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.
- wging 4y agoIntersections are the reason you'd want a set, as the original post indicates. See the problem here: https://adventofcode.com/2022/day/3 https://adventofcode.com/2022/day/3 (sets are even more of a fit for part 2, which is hidden for an anonymous viewer).
- Arainach 4y agoSure, 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 } } }
- deleted 4y ago[deleted]
- Kamq 4y agoThat'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).
- shaftoe444 4y agoRight, 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!
- deleted 4y ago[deleted]
- emptybits 4y agoI 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!
- shaftoe444 4y agoIt 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.