adventOfCode2023/day11.cpp at main · tekking/adventOfCode2023 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include "day11.h"
#include "helpers.h"

#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <ranges>
#include <string>
#include <vector>

namespace day11
{
    long long solvePart1(std::ifstream& file);
    long long solvePart2(std::ifstream& file);

    void run_day(bool example)
    {
        std::cout << "Running day 11 " << (example ? "(example)" : "") << '\n';

        const std::string fileName{ example ? "inputs/day11_example.txt" : "inputs/day11_real.txt" };
        std::ifstream file{ fileName };

        std::cout << "Part 1 answer: " << solvePart1(file) << '\n';

        file.close();
        file.open(fileName);

        std::cout << "Part 2 answer: " << solvePart2(file) << '\n';
    }

    struct Galaxy
    {
        int x{};
        int y{};
        int originalX{};
        int originalY{};
    };

    std::vector<Galaxy> parseInput(std::ifstream& file)
    {
        std::vector<Galaxy> result{};
        int y{};
        while (!file.eof())
        {
            std::string line;
            std::getline(file, line);
            for(size_t x = 0; x < line.size(); x++)
            {
                if (line[x] == '#')
                {
                    result.push_back(Galaxy{ static_cast<int>(x), y, static_cast<int>(x), y});
                }
            }

            y++;
        }

        return result;
    }

    void expandGalaxies(std::vector<Galaxy>& galaxies, const int expandFactor)
    {
        int maxX{};
        int maxY{};
        for (auto& galaxy : galaxies)
        {
            maxX = std::max(maxX, galaxy.x);
            maxY = std::max(maxY, galaxy.y);
        }

        // Expand the empty space, by moving galaxies with higher x/y out, first on y, then x
        // Don't modify original so we can keep using that for comparison
        for (int y = 0; y < maxY; y++)
        {
            if (!std::ranges::any_of(galaxies, [y](Galaxy g) {return g.originalY == y; }))
            {
                for (auto& galaxy : galaxies)
                {
                    if (galaxy.originalY > y)
                    {
                        galaxy.y += (expandFactor - 1);
                    }
                }
            }
        }

        for (int x = 0; x < maxX; x++)
        {
            if (!std::ranges::any_of(galaxies, [x](Galaxy g) {return g.originalX == x; }))
            {
                for (auto& galaxy : galaxies)
                {
                    if (galaxy.originalX > x)
                    {
                        galaxy.x += (expandFactor - 1);
                    }
                }
            }
        }
    }

    long long solvePart1(std::ifstream& file)
    {
        auto galaxies{ parseInput(file) };
        expandGalaxies(galaxies, 2);

        long long distanceSum{};
        for(size_t outer = 0; outer < galaxies.size(); outer++)
        {
            for(size_t inner = outer + 1; inner < galaxies.size(); inner++)
            {
                // Shortest path is just manhattan distance
                distanceSum += std::abs(galaxies[inner].x - galaxies[outer].x) + std::abs(galaxies[inner].y - galaxies[outer].y);
            }
        }

        return distanceSum;
    }

    long long solvePart2(std::ifstream& file)
    {
        // Same as part 1, but just different amount added to x/y when expanding.
        auto galaxies{ parseInput(file) };
        expandGalaxies(galaxies, 1000000);

        long long distanceSum{};
        for (size_t outer = 0; outer < galaxies.size(); outer++)
        {
            for (size_t inner = outer + 1; inner < galaxies.size(); inner++)
            {
                // Shortest path is just manhattan distance
                distanceSum += std::abs(galaxies[inner].x - galaxies[outer].x) + std::abs(galaxies[inner].y - galaxies[outer].y);
            }
        }

        return distanceSum;
    }
}