diff options
Diffstat (limited to '2020')
| -rw-r--r-- | 2020/.gitignore | 28 | ||||
| -rw-r--r-- | 2020/1.hs | 19 | ||||
| -rw-r--r-- | 2020/1.in | 200 | ||||
| -rw-r--r-- | 2020/1a.cpp | 90 | ||||
| -rw-r--r-- | 2020/Input.hs | 20 | ||||
| -rw-r--r-- | 2020/Makefile | 42 |
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 |