3 ms·
You don't need a map for AoC 2022 day 3. There's only 52 elements. Which means a 64-bit bitmask is sufficient.
by forrestthewoods 4y ago
You 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.