From e0632dd35e0dd6491397514d09ad273f4d1e0392 Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom@tomsmeding.com>
Date: Fri, 3 Dec 2021 20:28:40 +0100
Subject: 3

---
 2021/3.hs |   25 ++
 2021/3.in | 1000 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 1025 insertions(+)
 create mode 100644 2021/3.hs
 create mode 100644 2021/3.in

diff --git a/2021/3.hs b/2021/3.hs
new file mode 100644
index 0000000..98ca15c
--- /dev/null
+++ b/2021/3.hs
@@ -0,0 +1,25 @@
+module Main where
+
+import Data.Bits
+import Data.List
+
+import Input
+
+
+readBin :: [Bool] -> Int
+readBin = sum . zipWith (*) (iterate (*2) 1) . reverse . map fromEnum
+
+main :: IO ()
+main = do
+    inp <- map (map (== '1')) <$> getInput 3
+    let n = length (head inp)
+    let majority s = 2 * length (filter id s) > length s
+    let gamma = readBin $ map majority $ transpose inp
+        epsilon = complement gamma .&. (bit n - 1)
+    print (gamma * epsilon)
+    let filterstep _ _ [x] = [x]
+        filterstep target idx cands = filter ((== target) . (!! idx)) cands
+        perform targetrule = foldl' (\cs i -> filterstep (targetrule cs i) i cs) inp [0 .. n - 1]
+        oxygen = perform $ \cs i -> 2 * length (filter id (map (!! i) cs)) >= length cs
+        co2 = perform $ \cs i -> 2 * length (filter id (map (!! i) cs)) < length cs
+    print (readBin (head oxygen) * readBin (head co2))
diff --git a/2021/3.in b/2021/3.in
new file mode 100644
index 0000000..98d1a26
--- /dev/null
+++ b/2021/3.in
@@ -0,0 +1,1000 @@
+000011110010
+010000100100
+010011111111
+000101001111
+010100011111
+111100111011
+100111011010
+111001000001
+100000100110
+100110011000
+010101010111
+001100100001
+111100111111
+111010001000
+101011101110
+111101001000
+000000111101
+001010111011
+111101100010
+110001100111
+110011011011
+010000000110
+010111100111
+111001111000
+110001101111
+100010011011
+100100110001
+000001100111
+110001110000
+010011011010
+010111110010
+111100101111
+000110111101
+101101101001
+111110000100
+001110100100
+000000110011
+000001010000
+010110000011
+000101010100
+110010010100
+001110011011
+001011110011
+001011000100
+111011100101
+001000011101
+011110001010
+100110100111
+100100101100
+000101101011
+001100000110
+010101000010
+000111001011
+100001110100
+110000110110
+101001110011
+010001111001
+111110111000
+000110011010
+101110000001
+110000100001
+111001000011
+000000101001
+000001100101
+001101110111
+001100000001
+100111100100
+000111000001
+000100111011
+000000110100
+111100100100
+001001000000
+111001100111
+100101110010
+011000110101
+110100110111
+001001110101
+110010011100
+011001011111
+001010110111
+110101000111
+010010011001
+100010110001
+101110101011
+010010011000
+111001000110
+001001100001
+000001110111
+011100011011
+101101011001
+111000011111
+101001110101
+100100110000
+101000001111
+011001110100
+001000100101
+011100111011
+001100101110
+111000111111
+000001100100
+101010010001
+101100110001
+110011001100
+111000100111
+000011000111
+010001000011
+010111100000
+111001000101
+011000001011
+001111100110
+101111110011
+110011000001
+011011011100
+011101000011
+001111100100
+110010110010
+110100110110
+110000001000
+110010001000
+101111101010
+010000001100
+110010010011
+110000011000
+101100011110
+001010010000
+011010011101
+101110100100
+100010011010
+011010011000
+101110000111
+001010100110
+100000000101
+101100100101
+101001111010
+011110010111
+101000111000
+111111010110
+000001111000
+101010111110
+001101100011
+001010111100
+001001100111
+111010100001
+100101101100
+111101110110
+011010111000
+110100000001
+110101000110
+100000010000
+111010100011
+111110001100
+000001101100
+000011011000
+011101000000
+111011111010
+110011100001
+100000111101
+000101010101
+000001110100
+010010000100
+010110110001
+101000100110
+111110010000
+010100111100
+101101000100
+011100001111
+111000001111
+111011111100
+111011001011
+101000010110
+100000011111
+000100010111
+100010111111
+010111000111
+010100111001
+000000000001
+110011111000
+001010001010
+111100011110
+011001001011
+011101101110
+100100110111
+011010010101
+100001111100
+010010111001
+101100000100
+100001000110
+110101101000
+001010000100
+011100111100
+001110010100
+001100001100
+110100100011
+000111010101
+100010011111
+010110110111
+100111010000
+001101111100
+000110011110
+000100101010
+101011001010
+101111010101
+000001000011
+111001000010
+100011100010
+101000000111
+111000010111
+111001110110
+110000100110
+111010011001
+010101110101
+000111010000
+011110100110
+100100010111
+000110001100
+001110111110
+010001001111
+011011110111
+110000111011
+101010110001
+101101010011
+100110101001
+100010010101
+000011111111
+010110110110
+000100110111
+110101011101
+111001100001
+001100110100
+011001010101
+100010101110
+110001011110
+000100101011
+101110100010
+001101000000
+110111110101
+110100010110
+100111000000
+100001000101
+001100111011
+000010001001
+001101001010
+101010001101
+110101101111
+001101011001
+110001000001
+001110100000
+001010010011
+100000010010
+111001101011
+101011000111
+001000010011
+010111111101
+101111000111
+010100100101
+000100000110
+000010110011
+000111011110
+100011110111
+101010110011
+011111001110
+111011110100
+010011000001
+000011101110
+000101010011
+100011110101
+001101001111
+011000010001
+011010010000
+001101011110
+110010010001
+110111111100
+010111001100
+000000111000
+101100110100
+110001111000
+010101110110
+111000101001
+110110010011
+100000101010
+111101100011
+000110100110
+000110100111
+001111111101
+001101110010
+101101100010
+001110001011
+101101001111
+000110100101
+110010011101
+001100011100
+111010101001
+001111001001
+010001100101
+110001101001
+010110011011
+110111110110
+100110001110
+000011010100
+110000001011
+110101110100
+111110101100
+111100100110
+100000100101
+011011010010
+011000000000
+001110001010
+001011110110
+111111010101
+101000011011
+110001110110
+001110010011
+100111111010
+110110011110
+000011101010
+100010011000
+100100001111
+111110001101
+111011111001
+101010011100
+001100000000
+100010000010
+000001110110
+010100110111
+100010100000
+101001101010
+100000011010
+100110111011
+011100010111
+100110101101
+110011010101
+001011110101
+001110010000
+000010101010
+101110001011
+011000010011
+101001011000
+010101101001
+000111110010
+101101111111
+010000011000
+110011101011
+001011101001
+111000001100
+101110100110
+011100101001
+001101011011
+011110101001
+010111101011
+110010000100
+001101010000
+010011011100
+100000110000
+111101100110
+111110110100
+011101111100
+110111110100
+110100010101
+011110110111
+011011011000
+000000100101
+001001010011
+101100001101
+001010101011
+111100011101
+100101101110
+111000001010
+101010011010
+010001111101
+110011001101
+011000111011
+000111101001
+100101100111
+110111111000
+110000000010
+101010111011
+111001110010
+011100110101
+100010111001
+000110110101
+010110101110
+000001101111
+010110110010
+100000110001
+010000001110
+111100110011
+011101101111
+100111000001
+110000000101
+100011010111
+110001001011
+101111001011
+111110010011
+110111111101
+111111111101
+011111001010
+011011001101
+101111000100
+111000101111
+110010000000
+010010111110
+110110110110
+000100001101
+001010001011
+001000010100
+110100001111
+000101000101
+111101101111
+110011111111
+011010011011
+100101110111
+000110000111
+000100110100
+110110101010
+110001110100
+000001111111
+011000000111
+111000100010
+101000010001
+011111000010
+001010001101
+110010100001
+100111101000
+011001101110
+111100111001
+111101110011
+110101110010
+100100010100
+011001111111
+111001011110
+000010100111
+100010101000
+011100111101
+110111011000
+010001111110
+011001001001
+010000011111
+011000001001
+101100000111
+111110000000
+110100101111
+001000100011
+000011100010
+011100110001
+011010000100
+110110000001
+100001010101
+111111111011
+000001010110
+010001110111
+100100111110
+111111011011
+101000111110
+001010011010
+101010011111
+111010000011
+111011011111
+010100111000
+010010110111
+010010100101
+101100101100
+010110110100
+001111001101
+001101101001
+110011010100
+100010100101
+001001010010
+000011000010
+111110000111
+001011010100
+100001000100
+001110001100
+101001110010
+100010000100
+010001010001
+010100110001
+111101001011
+010111000110
+001110101011
+000101011100
+010100101110
+101111111000
+011100111110
+010110111001
+101101001110
+001000011000
+001101100100
+010111011101
+101101101111
+110100110100
+101110111100
+110111110001
+110000100101
+101111110010
+010101111100
+101000100111
+001010101101
+100000010011
+010101010011
+000011101000
+011001000000
+101010110100
+100101101010
+100100011000
+011100110011
+001010100001
+010000111000
+000101100111
+010001111111
+000011000110
+001011011010
+011101110011
+101101010100
+000100000000
+111101100000
+001111110000
+001101111010
+010110100110
+111001001111
+001101110001
+110110000010
+001101101000
+001100100101
+111101110100
+000101110001
+010010111011
+101000110100
+100110111001
+111001010000
+000011001111
+101000011101
+100111111100
+010111100100
+101001101011
+101000101001
+001010001110
+111001111101
+100011001011
+111101101011
+110111001100
+110100111010
+111101111010
+100111110011
+111100010000
+101110000010
+001000111000
+011001110110
+011001101011
+110100110001
+010100110010
+101000111001
+010110010110
+000010000000
+111100011100
+001110111111
+010010100110
+110001010010
+110101101010
+010011111000
+011101010110
+100001101100
+000101100011
+111100011111
+010111111111
+110000101111
+101110111101
+110011000100
+010010000000
+010100110100
+101011111101
+001011001110
+111000011100
+010110000100
+011110001000
+101010001110
+111001010111
+000001101011
+001010011001
+110001000000
+110011100101
+101000011100
+001000101001
+100100100101
+101010000110
+110001011111
+001000110100
+001000100111
+110010011001
+001001111011
+010101100100
+010110101101
+101101000110
+010011111101
+000000111111
+100111111110
+100101111100
+110010000001
+010100010111
+011110110000
+111100110001
+000010101101
+111111010011
+110110100000
+000000010100
+110000110100
+111101111111
+001001100100
+100000001110
+011101001000
+010001101111
+100101110110
+101011101101
+111011110111
+101110011010
+000001101110
+000100011111
+111111101010
+000101011101
+010110001001
+110001000110
+110101011110
+100110100011
+101100111000
+011011001110
+111000110000
+000110001110
+100110011110
+110011101101
+101100011111
+011111000101
+011101000100
+000111110001
+011111110011
+011001100101
+000100001100
+100100011101
+110011101110
+101000000110
+000100001111
+110010101000
+010110000101
+110000010010
+111010111001
+001001000110
+001000011010
+110110001011
+001101001110
+111010011100
+000101010110
+111111001000
+001001110000
+101011100111
+110101101001
+101111110110
+111010001011
+010100101100
+010110110000
+110011010010
+101010111010
+010011001101
+011101000101
+101111111101
+110000000100
+011011011101
+010101011000
+000011001101
+011101110000
+100111011101
+001100101001
+100101100000
+110010011010
+101111011001
+110010111010
+110001100000
+100100010110
+100101010111
+100110111110
+010111011000
+100100101011
+101010011110
+110011001011
+100011101110
+111000000110
+010011000100
+111011100011
+000000011100
+101011011000
+100110001011
+001011101101
+000000000010
+010011001111
+001001110010
+111011100100
+100100010101
+111110000001
+011110100101
+100110000100
+001011101110
+100010011110
+001000110000
+001100001010
+011001001110
+011010011001
+111110011010
+001010011111
+100001100001
+101011110111
+111111001110
+010000000001
+001011110010
+111010011111
+101000110001
+010011010100
+000111000011
+010101001110
+101000110111
+011010110001
+011010100001
+011010011110
+000101101101
+101101100101
+011101101011
+000011001001
+111000111001
+111100111000
+000111100111
+111101111101
+000101011011
+011111000100
+110101000001
+101000111011
+110011010001
+010011110101
+101000000010
+010111110101
+101101101000
+110111010011
+000111111110
+100001110110
+100110001000
+110110000101
+111101100100
+010001101010
+111001000100
+111001010100
+101110001000
+010000010110
+100001100110
+000110100010
+111101010010
+110000001111
+010001100111
+001000001010
+110000011010
+001011100110
+100101101101
+011001011100
+001100101101
+011110111001
+001010001100
+111011000011
+100100000111
+000100001010
+011100101100
+001101110100
+001100011110
+101010001111
+000011001011
+111001010010
+110000101110
+000101000011
+010010000011
+110010101101
+010101011011
+101011110001
+110111100100
+111010011010
+011101010101
+100001011100
+011011100010
+111000010100
+101011011001
+101110101100
+000010011011
+111110101101
+100000101100
+010000101010
+010011111100
+110110100001
+100011001000
+000001000010
+101110010110
+110101111000
+101001101000
+000001100000
+110010011110
+010111010110
+111101010101
+000010111011
+011110111000
+010101111010
+001000000011
+110001101010
+111001011010
+111010110011
+100001010010
+001011101111
+000011101111
+111011110010
+000011011001
+011110101100
+011001111101
+011010010111
+000100100101
+111100111100
+010000001001
+110011110000
+010010010001
+000111101000
+100011001001
+100111001010
+011101111011
+100110011011
+101011111001
+111111100011
+010010111000
+000001111001
+010110011001
+011100001011
+110001110111
+001010100111
+110110100010
+010111000101
+100100001100
+011110101110
+111110111010
+000000010011
+110000101011
+111010100100
+011110011000
+111010110001
+000010001110
+000001000111
+110010101111
+100001011111
+111001100100
+110000000110
+100011101100
+101011001001
+000100101101
+101101101011
+001001110100
+100100111100
+010010101011
+011110100000
+110101100011
+101101101010
+100101010110
+011000100000
+111000101000
+011110010110
+001000010111
+111010010111
+111100000111
+011000100011
+010000111111
+011001010111
+011110011010
+111111011100
+011111101101
+101111011101
+101100100000
+111111000000
+111111111111
+101011011101
+000010101100
+100101001101
+111111001010
+010100000000
+010111001011
+101110010101
+000011011100
+110101011000
+111001101101
+000001011101
+000101011010
+100110000110
+111111001111
+001011111110
+111010011110
+000011010110
+011010111110
+111110001001
+100011001110
+110111001101
+110100100101
+101011100110
+110100000110
+010011100101
+001000010110
+101001100101
+111111110001
+100110111000
+111101001100
+010001101000
+011100100101
+111101010011
+000110011001
+010100010100
+110100100010
+100101100100
+100011001101
+001000100001
+110100100111
+111010011011
+011000010010
+111001100011
+001111101011
+010110111101
+000001011010
+100000010110
+010100011011
+110000110011
+111111111010
+111000100100
+100100011011
+000111110110
+010000000010
+010111110111
+100011100001
+001101000100
+011111011111
+000010011111
+000101011110
+001100100111
+101001000100
+000011011010
+101101001101
+010010010110
+001100001110
+100101000001
+111100000101
+100000111111
+010111111011
+101101110110
+001000010001
+110111101000
+110101001111
+101110000100
+110001110011
+010010011010
+011010101111
+111110001010
+110010110000
+101001000110
+000010000001
+001100011111
+100101000110
+010101100011
+000100111100
+101011010101
+010001110001
+001010011110
+101100001110
+101111010001
+000000010000
+011111001111
+100011101111
+001000111100
+101001011111
+111111010111
+001010110110
+111101101110
+011000101011
+111011100110
+010001001000
+001010111001
+111010111011
+111111110110
+110110001000
+001000100010
+101010101110
+101010100011
+100100111101
+000110010001
+111110010110
+000101100001
+010100100111
+001101100010
+110011110111
+011100110110
+100101011000
+011101011111
+110110000011
+100010110100
+011011001000
+111000101101
+110100000101
+011001000001
+001011000111
-- 
cgit v1.2.3-70-g09d2