Start of 2020

6 files changed, 399 insertions, 0 deletions

diff --git a/2020/.gitignore b/2020/.gitignore
new file mode 100644
index 0000000..be8d42d
--- /dev/null
+++ b/2020/.gitignore
@@ -0,0 +1,28 @@
+obj/
+.depend_hs
+1
+1a
+2
+3
+4
+5
+6
+7
+8
+9
+10
+11
+12
+13
+14
+15
+16
+17
+18
+19
+20
+21
+22
+23
+24
+25
diff --git a/2020/1.hs b/2020/1.hs
new file mode 100644
index 0000000..c7e9d02
--- /dev/null
+++ b/2020/1.hs
@@ -0,0 +1,19 @@
+module Main where
+
+import Data.List (find)
+import Data.Maybe (fromJust)
+import qualified Data.Set as Set
+
+import Input
+
+
+main :: IO ()
+main = do
+    input <- map read <$> getInput 1 :: IO [Int]
+
+    let num1 = fromJust (find ((`Set.member` Set.fromList input) . (2020 -)) input)
+    print (num1 * (2020 - num1))
+
+    let pair = snd (fromJust (find ((`Set.member` Set.fromList input) . (2020 -) . fst)
+                                   [(a + b, (a, b)) | a <- input, b <- input]))
+    print (fst pair * snd pair * (2020 - fst pair - snd pair))
diff --git a/2020/1.in b/2020/1.in
new file mode 100644
index 0000000..734029f
--- /dev/null
+++ b/2020/1.in
@@ -0,0 +1,200 @@
+1833
+1949
+1745
+1863
+1422
+1980
+1695
+1233
+1407
+1971
+1486
+1922
+1802
+1689
+214
+1864
+1091
+1395
+1772
+1901
+1542
+1730
+1782
+1815
+1818
+1236
+1604
+1219
+1834
+1813
+1532
+1963
+2003
+1149
+1577
+1408
+1871
+1417
+1727
+1155
+1953
+1287
+1259
+1548
+1126
+1927
+1225
+1172
+11
+1301
+1869
+1808
+1238
+1989
+1027
+321
+1564
+636
+1847
+1877
+1716
+1275
+1738
+1054
+1966
+1019
+1256
+1940
+1821
+1914
+1556
+1389
+1020
+1293
+1935
+1804
+1945
+508
+1856
+1674
+1721
+1541
+1435
+1852
+1394
+2006
+1366
+1473
+1274
+623
+1701
+1842
+1954
+1999
+1195
+1246
+1967
+1153
+1851
+1294
+1152
+1812
+1732
+1030
+1956
+1132
+1948
+1865
+1835
+1231
+1975
+1759
+1843
+1379
+1657
+1267
+1062
+1850
+1817
+1543
+1805
+1252
+1974
+1161
+876
+1647
+1796
+1634
+1177
+1519
+1527
+1249
+1158
+2007
+1702
+1714
+1040
+1826
+1837
+1361
+1814
+1858
+1828
+1951
+1140
+1845
+1476
+1337
+1262
+1923
+1397
+1025
+1412
+1930
+1164
+1300
+1369
+1777
+1591
+1919
+1874
+1482
+2010
+1957
+1897
+1854
+1992
+1735
+1786
+1661
+1404
+1254
+1803
+1794
+1614
+1711
+1007
+1979
+1928
+1505
+2001
+1094
+2005
+1297
+1933
+1976
+1104
+1279
+1012
+1943
+1679
+1958
+1841
+1623
+1809
+1800
+919
+1620
+1936
+1209
diff --git a/2020/1a.cpp b/2020/1a.cpp
new file mode 100644
index 0000000..179598b
--- /dev/null
+++ b/2020/1a.cpp
@@ -0,0 +1,90 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <bitset>
+#include <functional>
+#include <cstdlib>
+#include <climits>
+#include <ctime>
+#include <cassert>
+
+
+static double time_func(std::function<void()> func) {
+	const double minmeasure = 2.0;
+	const double factor = 1.5;
+
+	for (int reps = 1;
+			reps < INT_MAX / factor;
+			reps = std::max<int>(reps + 1, reps * factor)) {
+		const clock_t t_start = clock();
+		for (int k = 0; k < reps; k++) func();
+		const clock_t t_end = clock();
+		const double time_taken = (double)(t_end - t_start) / CLOCKS_PER_SEC;
+		std::cerr << reps << "x -> " << time_taken << "s" << std::endl;
+		if (time_taken >= minmeasure) return time_taken / reps;
+	}
+
+	assert(false);
+}
+
+static std::string read_input() {
+	std::ios::sync_with_stdio(false);
+
+	std::ifstream file{"1.in"};
+	file.seekg(0, std::ios::end);
+	size_t filesize = file.tellg();
+	file.seekg(0);
+
+	std::string input(filesize, '\0');
+	size_t cursor = 0;
+	while (cursor < filesize) {
+		file.read(&input[cursor], filesize - cursor);
+		cursor += file.gcount();
+	}
+
+	return input;
+}
+
+static std::pair<int, int> solve(const std::string &input) {
+	std::vector<int> numbers;
+	numbers.reserve(input.size() / 2);
+
+	std::bitset<2021> have;
+
+	char *endp = nullptr;
+	const char *cursor = input.data();
+	while (true) {
+		int val = strtol(cursor, &endp, 10);
+		if (endp == cursor) break;
+		numbers.push_back(val);
+		have[val] = true;
+		cursor = endp;
+	}
+
+	int ans1 = -1;
+	for (int n : numbers) {
+		if (2020 - n >= 0 && have[2020 - n]) {
+			ans1 = n * (2020 - n);
+			break;
+		}
+	}
+
+	for (int n : numbers) {
+		for (int m : numbers) {
+			const int k = 2020 - (n + m);
+			if (k >= 0 && have[k]) {
+				return std::make_pair(ans1, n * m * k);
+			}
+		}
+	}
+
+	assert(false);
+}
+
+int main() {
+	const std::string input = read_input();
+	auto out = solve(input);
+	std::cout << out.first << '\n' << out.second << std::endl;
+	std::cout << time_func([&input](){ solve(input); }) << std::endl;
+}
diff --git a/2020/Input.hs b/2020/Input.hs
new file mode 100644
index 0000000..afce44e
--- /dev/null
+++ b/2020/Input.hs
@@ -0,0 +1,20 @@
+module Input where
+
+import System.Environment
+import System.IO
+
+
+getInput :: Int -> IO [String]
+getInput day = do
+    let fname = show day ++ ".in"
+
+    args <- getArgs
+    str <- case args of
+        ["-"] -> getContents
+        [] -> readFile fname
+        _ -> do
+            hPutStrLn stderr $ "WARNING: Unrecognised command-line parameters " ++ show args ++
+                               ", reading from " ++ fname
+            readFile fname
+
+    return (lines str)
diff --git a/2020/Makefile b/2020/Makefile
new file mode 100644
index 0000000..b48727b
--- /dev/null
+++ b/2020/Makefile
@@ -0,0 +1,42 @@
+GHC = ghc
+GHCFLAGS = -Wall -O2 -threaded
+CXX = g++
+CXXFLAGS = -Wall -Wextra -std=c++17 -O2
+
+OBJDIR = obj
+
+HASKELL_AUX := Input.hs
+CPP_AUX     :=
+HASKELL_SRC := $(filter-out $(HASKELL_AUX),$(wildcard *.hs))
+CPP_SRC     := $(filter-out $(CPP_AUX),$(wildcard *.cpp))
+HASKELL_BIN := $(HASKELL_SRC:.hs=)
+CPP_BIN     := $(CPP_SRC:.cpp=)
+
+BINARIES := $(HASKELL_BIN) $(CPP_BIN)
+
+.PHONY: all clean
+
+
+all: $(BINARIES)
+
+clean:
+	rm -f $(BINARIES) .depend_hs
+	rm -rf $(OBJDIR)
+
+$(HASKELL_BIN): %: %.hs | $(OBJDIR)/%
+	$(GHC) $(GHCFLAGS) -odir $(OBJDIR)/$* -hidir $(OBJDIR)/$* -o $@ $<
+
+$(CPP_BIN): %: %.cpp $(CPP_AUX) | $(OBJDIR)
+	$(CXX) $(CXXFLAGS) -o $@ $<
+
+$(OBJDIR)/%:
+	mkdir -p $@
+
+
+.depend_hs: $(HASKELL_SRC) $(HASKELL_AUX)
+	ghc -dep-suffix '' -dep-makefile $@ -M $(HASKELL_SRC)
+	rm -f .depend_hs.bak
+	sed 's/\.o *:/:/; s/\.hi$$/.hs/g; s/\.hi[ \t]/.hs/g' <$@ >$@.tmp
+	mv $@.tmp $@
+
+-include .depend_hs