aoc(2313): Point of Incidence

4 files changed, 205 insertions, 0 deletions

diff --git a/2023/13/Makefile b/2023/13/Makefile
new file mode 100644
index 0000000..af6a294
--- /dev/null
+++ b/2023/13/Makefile
@@ -0,0 +1,19 @@
+CXXFLAGS := -std=c++17
+CPPFLAGS := -I../include
+EXE := part1 part2
+
+.PHONY: all clean configure
+
+all: $(EXE)
+
+configure:
+        bear -- $(MAKE) all
+
+%.o: %.cpp
+        $(CXX) -c $(CPPFLAGS) $(CXXFLAGS) $< -o $@
+
+clean:
+        rm -rf $(EXE) src/*.o compile_commands.json
+
+%: src/%.o
+        $(CXX) $^ -o $@
diff --git a/2023/13/resources/input_small.txt b/2023/13/resources/input_small.txt
new file mode 100644
index 0000000..3b6b5cc
--- /dev/null
+++ b/2023/13/resources/input_small.txt
@@ -0,0 +1,15 @@
+#.##..##.
+..#.##.#.
+##......#
+##......#
+..#.##.#.
+..##..##.
+#.#.##.#.
+
+#...##..#
+#....#..#
+..##..###
+#####.##.
+#####.##.
+..##..###
+#....#..#
diff --git a/2023/13/src/part1.cpp b/2023/13/src/part1.cpp
new file mode 100644
index 0000000..2a043c2
--- /dev/null
+++ b/2023/13/src/part1.cpp
@@ -0,0 +1,76 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <tuple>
+
+using Grid = std::pair<std::vector<int>, std::vector<int>>;
+
+std::vector<Grid> parse(const char* file)
+{
+    if (std::ifstream input{ file }; input.is_open())
+    {
+        std::vector<int> rows, cols;
+        std::vector<Grid> grids;
+
+        std::string line;
+        while (not std::getline(input,line).eof())
+        {
+            if (cols.size() < line.size())
+            {
+                cols.resize(line.size(), 0);
+            }
+
+            if (line.empty())
+            {
+                grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
+                rows = cols = std::vector<int>{};
+                continue;
+            }
+
+            int num{};
+            for (int i = 0; i < line.size(); ++i)
+            {
+                num *= 2;
+                num += line[i] == '#';
+                cols[i] *= 2;
+                cols[i] += line[i] == '#';
+            }
+            rows.push_back(num);
+        }
+        grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
+
+        return grids;
+    }
+    return {};
+}
+
+int find_symmetry(const std::vector<int>& v)
+{
+    for (int i = 1; i < v.size(); ++i)
+    {
+        if (v[i-1] == v[i])
+        {
+            bool sim{true};
+            for (int j = 1; j < std::min(i, (int)v.size() - i); ++j)
+            {
+                sim = sim && v[i-1-j] == v[i+j];
+            }
+            if (sim) return i;
+        }
+    }
+    return 0;
+}
+
+int main(int argc, char* argv[])
+{
+    int answer{};
+
+    for (const auto& grid : parse(argv[1]))
+    {
+        answer += find_symmetry(grid.first);
+        answer += 100 * find_symmetry(grid.second);
+    }
+
+    std::cout << answer << std::endl;
+    return 0;
+}
diff --git a/2023/13/src/part2.cpp b/2023/13/src/part2.cpp
new file mode 100644
index 0000000..db14f0a
--- /dev/null
+++ b/2023/13/src/part2.cpp
@@ -0,0 +1,95 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <tuple>
+
+using Grid = std::pair<std::vector<uint32_t>, std::vector<uint32_t>>;
+
+std::vector<Grid> parse(const char* file)
+{
+    if (std::ifstream input{ file }; input.is_open())
+    {
+        std::vector<uint32_t> rows, cols;
+        std::vector<Grid> grids;
+
+        std::string line;
+        while (not std::getline(input,line).eof())
+        {
+            if (cols.size() < line.size())
+            {
+                cols.resize(line.size(), 0);
+            }
+
+            if (line.empty())
+            {
+                grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
+                rows = cols = std::vector<uint32_t>{};
+                continue;
+            }
+
+            int num{};
+            for (int i = 0; i < line.size(); ++i)
+            {
+                num *= 2;
+                num += line[i] == '#';
+                cols[i] *= 2;
+                cols[i] += line[i] == '#';
+            }
+            rows.push_back(num);
+        }
+        grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
+
+        return grids;
+    }
+    return {};
+}
+
+bool equal(uint32_t a, uint32_t b, bool& smudge)
+{
+    if (a == b) return true;
+
+    if (not smudge)
+    {
+        int smudges{};
+        uint32_t diff = a ^ b;
+        while (diff > 0)
+        {
+            smudges += diff % 2;
+            diff /= 2;
+        }
+        return smudge = smudges == 1;
+    }
+    return false;
+}
+
+int find_symmetry(const std::vector<uint32_t>& v)
+{
+    for (int i = 1; i < v.size(); ++i)
+    {
+        bool smudge{ false };
+        if (equal(v[i-1], v[i], smudge))
+        {
+            bool sim{true};
+            for (int j = 1; j < std::min(i, (int)v.size() - i); ++j)
+            {
+                sim = sim && equal(v[i-1-j], v[i+j], smudge);
+            }
+            if (sim && smudge) return i;
+        }
+    }
+    return 0;
+}
+
+int main(int argc, char* argv[])
+{
+    int answer{};
+
+    for (const auto& grid : parse(argv[1]))
+    {
+        answer += find_symmetry(grid.first);
+        answer += 100 * find_symmetry(grid.second);
+    }
+
+    std::cout << answer << std::endl;
+    return 0;
+}