Created
July 14, 2025 15:46
-
-
Save leg7/399078bd33f8dc561fa6b3dde8a15cbb to your computer and use it in GitHub Desktop.
xor-trick
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module Main where | |
| import Data.Bits | |
| import Data.List | |
| import Data.Function | |
| -- Code implementing https://florian.github.io/xor-trick/ | |
| -- Inspired by watching Prime's video https://youtu.be/YNObatXvhZc | |
| findMissing :: [Int] -> [Int] -> Int | |
| findMissing set domain = a `xor` b | |
| where a = foldr xor 0 set | |
| b = foldr xor 0 domain | |
| find2Missing :: [Int] -> [Int] -> (Int, Int) | |
| find2Missing set domain = (findMissing subset1 subdomain1, findMissing subset2 subdomain2) | |
| where lsb = countLeadingZeros uv | |
| uv = findMissing set domain | |
| (subset1, subset2) = partition (testBit lsb) set | |
| (subdomain1, subdomain2) = partition (testBit lsb) domain | |
| main :: IO () | |
| main = | |
| do | |
| print $ find2Missing set domain | |
| where set = delete 5 domain & delete 8 | |
| domain = [1..10] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment