From 122958c8f385b047294dc99feb2cc86703f252c6 Mon Sep 17 00:00:00 2001
From: kaiwu <kaiwu2004@gmail.com>
Date: Mon, 4 Apr 2022 16:56:32 +0800
Subject: 2020 day1 two sum

---
 src/2020/day1/README.md |  6 ++++++
 src/2020/day1/aoc.cpp   | 37 ++++++++++++++++++++++++++++++++++++-
 src/2020/day1/aoc.h     |  1 +
 3 files changed, 43 insertions(+), 1 deletion(-)

(limited to 'src')

diff --git a/src/2020/day1/README.md b/src/2020/day1/README.md
index 69132f0..6f88a87 100644
--- a/src/2020/day1/README.md
+++ b/src/2020/day1/README.md
@@ -23,4 +23,10 @@ In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying the
 
 Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?
 
+--- Part Two ---
 
+The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.
+
+Using the above example again, the three entries that sum to 2020 are 979, 366, and 675. Multiplying them together produces the answer, 241861950.
+
+In your expense report, what is the product of the three entries that sum to 2020?
diff --git a/src/2020/day1/aoc.cpp b/src/2020/day1/aoc.cpp
index a57fb7c..87972e7 100644
--- a/src/2020/day1/aoc.cpp
+++ b/src/2020/day1/aoc.cpp
@@ -1,3 +1,38 @@
 #include "aoc.h"
+#include <set>
+#include <vector>
 
-namespace aoc2020 {}
+namespace aoc2020 {
+
+int get_number(const char* p) {
+  int d{0};
+  while (*p >= '0' && *p <= '9') {
+    d = d * 10 + *p - '0';
+    p++;
+  }
+  return d;
+}
+
+int two_sum(const std::vector<int>& is, int target) {
+  std::set<int> pairs;
+  for (auto i : is) {
+    auto it = pairs.find(i);
+    if (it == pairs.end()) {
+      pairs.insert(target - i);
+    } else {
+      return i * (target - *it);
+    }
+  };
+  return 0;
+}
+
+int day1(line_view file, int target) {
+  std::vector<int> is;
+  per_line(file, [&is](line_view lv) {
+    is.emplace_back(get_number(lv.line));
+    return true;
+  });
+  return two_sum(is, target);
+}
+
+} // namespace aoc2020
diff --git a/src/2020/day1/aoc.h b/src/2020/day1/aoc.h
index c5ad3d1..d876d13 100644
--- a/src/2020/day1/aoc.h
+++ b/src/2020/day1/aoc.h
@@ -3,4 +3,5 @@
 
 namespace aoc2020 {
 
+int day1(line_view, int);
 }
-- 
cgit v1.2.3