A neat XOR trick
mattkeeter.com
A neat XOR trick
1–10 of 181 posts
Re: A neat XOR trick
#2I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it.
There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to every edge from every square would be O(N^3) but still execute just fine.
I'm a couple of days behind but so far this year hasn't yet had lanternfish style problems where the naive solution blows up completely, but hopefully they will come as they are a lot more interesting.
Re: A neat XOR trick
#3gamozolabs benchmarked this kind of stuff in a recent stream: https://www.youtube.com/watch?v=ru97E9xA0s4
Re: A neat XOR trick
#4[deleted]
Re: A neat XOR trick
#5One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)
Re: A neat XOR trick
#6I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it. There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to…
Arguably day 11 part 2 is such a "lanternfish" problem, although it essentially tells you to watch out for it.
Re: A neat XOR trick
#7One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)
Looking at ASCII decimal values, a-z correspond to 97-122 so if you want to use a 32 bit bitmap you remap 97-122 to 0-25 by subtracting 97 ('a').
If you can use a 128 bit bitmap for the same cost then you could indeed directly index by ASCII values.
You can also get rid of the 'if' on window size in the main loop by partially unrolling it and taking those cases (start and end of string) outside.
Re: A neat XOR trick
#8One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)
I assume the author is realigning to get only one bit for each letter. This relies on having an alphabet of 26 characters where 26 is less than the 32 available in a u32. In most real-world problems, you need to allow for the full ASCII or Unicode range and this wouldn't be possible.
Using codepoints directly, there is overlap. 'f' ^ 'd' will give you the same bit pattern as 'b'. You could keep an xor value for each window size smaller than the full window but that effectively brings back the inner loop that using xor is avoiding and you could just use equality. With codepoints, there may be a solution similar to a bloom filter so efficiently determine whether a duplicate is possible but I've not thought through that fully.
Re: A neat XOR trick
#9I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined).
Does this technique catch letters duplicated more than once?
In a Python 3 shell:
>> 2 ^ 4
6
>> 2 ^ 4 ^ 2
4
>> 2 ^ 4 ^ 2 ^ 2
6
Re: A neat XOR trick
#10This is basically the prefix sum technique in disguise: the sum over an interval is the difference between the prefix sums to the endpoints. The summation can be substituted with any group operation, in this case modulo-2 addition of 26-long vectors.
Many leetcode-type problems are amenable to O(n) speedups using this technique.