Learning CPP via Advent of Code 2024 [Days 1 to 5]

Learning CPP via Advent of Code 2024 [Days 1 to 5]#

I’ve decided to use Advent of Code 2024 as a platform to improve my C++ skills. With a background in C, having worked on Embedded Systems for the past two years, and over five years of experience in Python where I consider myself between intermediate and advanced, I felt it was time to dive into C++. While I’m familiar with core programming concepts like loops, functions, and Object-Oriented Programming (OOP) from my experience in C and Python, I wanted a more practical and engaging way to learn C++ without retreading the basics.

Advent of Code, with its daily coding challenges, seemed like a good way to get hands-on with C++.

This is my attempt to document my learning journey through Advent of Code 2024. Instead of cluttering with each post for each day’s challenge, I’ll be grouping my progress into consolidated posts. This page is the first part of my progress log covering Days 1 to 5.

Full solutions are available on GitHub: ABD-01/AoC2024.

Updated on 21 February 2025

Added next part for Days 10 and 11.

Updated on 15 February 2025

Added next part for Day 9.

Updated on 18 January 2025

Added next part for Days 6 to 8.

Day 1: Historian Hysteria#

Solution Overview#

Part 1: Sorting and Pairing Numbers#

Given two lists of numbers.

Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.

Sort both lists, take absolute difference of the values elementwise and sum it up.

37    std::sort(vec1.begin(), vec1.end()); // sorts in ascending order
38    std::sort(vec2.begin(), vec2.end());
39    //std::ranges::sort(vec2);
40
41    int result = 0;
42    for (std::size_t i = 0; i < vec1.size(); i++)
43        result += abs(vec1[i] - vec2[i]);

Part 2: Calculating Similarity Scores#

Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.

48    for (std::size_t i = 0; i < vec1.size(); i++)
49    {
50        /**
51        int count = 0;
52        for (std::size_t j = 0; j < vec1.size(); j++)
53            if (vec1[i] == vec2[j])
54                count++;
55        */
56        int count = std::count(vec2.begin(), vec2.end(), vec1[i]);
57        //int count = std::ranges::count(vec2, vec1[i]);
58        result += (count * vec1[i]);
59    }

Now here using std::count inside a loop results in a time complexity of \(O(n^2)\). This could be optimized further using a hash map (std::unordered_map) to count occurrences in \(O(n)\) time.

Concepts Learned#

Reading from a file#

Use file streams defined in header <fstream>

  • ifstream: Input file stream for reading files.

  • ofstream: Output file stream for writing files.

  • fstream: Input-output file stream for both reading and writing.

String Streams (<sstream>): Used to read from or write to strings.

  • istringstream: For input operations from a string.

  • ostringstream: For output operations to a string.

  • stringstream: For both input and output operations on a string.

standard input/output streams (<iostream>)

Vectors#

 1// 1. Creates a vector 'a' with 'count' elements
 2vector<int> a(count); 
 3
 4// 2. Creates a vector 'v' with 'count' elements, all initialized to 'value'
 5vector<int> v(count, value); 
 6
 7// 3. Looping over a vector and printing its elements
 8for (auto i : vec) std::cout << i << " "; 
 9
10// 4. Iterators
11std::vector<int>::iterator it = vec.begin();
12auto it = vec.end();
13
14// 5. Methods
15a.size()
16a.push_back // adds an element to the end
Example
 1#include <iostream>
 2#include <fstream>
 3#include <sstream>
 4#include <vector>
 5
 6int main() {
 7    std::ifstream file("input.txt");
 8    if (!file.is_open()) {
 9        std::cerr << "Error opening file!" << std::endl;
10        return 1;
11    }
12
13    std::vector<int> a, b;
14    std::string line;
15    while (std::getline(file, line)) {
16        std::istringstream iss(line);
17        int num1, num2;
18        if (!(iss >> num1 >> num2)) {
19            std::cerr << "Error parsing line!" << std::endl;
20            continue;
21        }
22        a.push_back(num1);
23        b.push_back(num2);
24    }
25
26    file.close();
27
28    return 0;
29}

Ranges#

for ranges, use -std=c++20 during compilation

  1. std::ranges::count

    1. count(v, target2);

    2. Same as std::count(v.begin(), v.end(), target1);

  2. std::ranges::sort Same as std::sort(vec2.begin(), vec2.end());

Initializer List#

# TODO

explicit specifier#

When a constructor is marked as [explicit](explicit specifier - cppreference.com), the compiler will not use that constructor for implicit type conversions or copy-initialization, meaning it will not automatically convert or create an object from a single argument when the compiler thinks it’s needed (for example, in assignments or function calls).

Example
 1#include <iostream>
 2
 3class MyClass {
 4public:
 5    explicit MyClass(int x) { std::cout << "Constructor called with " << x << std::endl; }
 6};
 7
 8void display(MyClass obj) {
 9    std::cout << "In display function\n";
10}
11
12int main() {
13    // display(10);  // Error: no implicit conversion from int to MyClass
14    display(MyClass(10));  // Must explicitly create MyClass
15    return 0;
16}

Insertion Sort#

Code
 95template<typename T>
 96void insertionSort(T& vec)
 97{
 98    typename T::iterator first = vec.begin();
 99    typename T::iterator last = vec.end();
100
101    for(auto current = first + 1; current != last; current++)
102    {
103       auto key = *current;
104       //auto position = current - 1;
105       auto position = current;
106       for (; position != first && *(position-1) > key; position--)
107       {
108            //*(position+1) = *position;
109            *(position) = *(position-1);
110       }
111       //*(position+1) = key;
112       *(position) = key;
113    }
114    return;
115}

References and Resources#


Day 2: Red-Nosed Reports#

Solution Overview#

Part 1: Count Safe Reports#

For a given list of numbers check if

  • it is all increasing or all decreasing.

  • Any two adjacent values differ by at least one and at most three.

17bool isReportSafe(const std::vector<int>& v)
18{
19	if (v.size() < 2) return true; // A single-element or empty list is trivially safe.
20
21    bool isSafe = true;
22    // Must be all increasing or all decreasing.
23    bool isSorted = (v[0] > v[1]) // If first element is greater than second, assume it should be decreasing
24        ? std::is_sorted(v.begin(), v.end(), std::greater<int>{})
25        : std::is_sorted(v.begin(), v.end()); 
26
27    if(!isSorted) return false;
28
29    for (std::size_t i = 1; i < v.size(); ++i)
30    {
31       int diff = abs(v[i]-v[i-1]); 
32       // Any two adjacent values must differ by at least one and at most three.
33       if (!(1 <= diff && diff<= 3)) 
34       {
35            isSafe = false;
36            break;
37       }
38    }
39    // Could also use std::adjacent_find 
40    return isSafe;
41}

Part 2: Tolerate a Single Unsafe Report#

For a given list, remove one element and check is it safe or not

64bool part2(const std::vector<int>& vec)
65    for(std::size_t i = 0; i < vec.size(); ++i)
66    {
67        std::vector<int> temp = vec;
68        temp.erase(temp.begin() + i);
69        if (isReportSafe(temp)) 
70            return true;
71    }

Key Takeaways#

Vector of Vectors#

std::is_sorted and std::greater#

std::adjacent_find#

Source: gcc-mirror/gcc/libstdc++-v3/include/bits/stl_algo.h

Code
 1bool funct(const std::vector<int>& vec)
 2    
 3    std::vector<int> v{1, 2, 3, 4, 4, 5};
 4	auto it = std::adjacent_find(v.begin(), v.end());
 5	if (it != v.end())
 6		std::cout << "First pair of repeated elements: " << *it << '\n';
 7		
 8	// Solution using adjacent_find
 9    return std::adjacent_find(v.begin(), v.end(), 
10        [](int a, int b) {
11            int diff = std::abs(b - a);
12            return diff < 1 || diff > 3;
13        }) == v.end();

std::count_if#

Example
 1bool funct(const std::vector<int>& vec)
 2#include <algorithm>
 3
 4bool isSorted = (v[0] > v[1]) 
 5	? std::is_sorted(v.begin(), v.end(), std::greater<>{})
 6	: std::is_sorted(v.begin(), v.end());
 7
 8return std::adjacent_find(v.begin(), v.end(), 
 9	[](int a, int b) {
10		int diff = std::abs(b - a);
11		return diff < MIN_DIFF || diff > MAX_DIFF;
12	}) == v.end();
13
14static int countSafeReports(const std::vector<std::vector<int>>& reports)
15{
16	return std::count_if(reports.begin(), reports.end(), isReportSafe);
17}

References and Resources#


Day 3: Mull It Over#

Solution Overview#

Part 1: Multiplication in Trash#

Parse the given corrupted string and look for pattern mul(X,Y), where X and Y are each 1-3 digit numbers. Add up all the results of the multiplications of X and Y.

36    std::istreambuf_iterator<char> it(file), end;
37    auto first = it;
38    auto second = it;
39
40	std::vector<std::pair<int, int>> mulVec;
41    unsigned int result(0);
42
43    for(first = it; it != end; ++it)
44    {
45        if (
46            (char)*first == 'm' && 
47            (char)*++first == 'u' &&
48            (char)*++first == 'l' &&
49            (char)*++first == '('
50        )
51        {
52            bool secondNum = false;
53            unsigned int num1(0), num2(0); 
54
55            for(second=++first; second != end; ++second)    
56            {
57                if(std::isdigit(*second))
58                {
59                    if(secondNum)
60                        num2 = num2*10 + (*second - '0');
61                    else
62                        num1 = num1*10 + (*second - '0');
63                }
64                else if ((char)*second == ',')
65                    secondNum=true;
66                else if ((char)*second == ')' && secondNum)
67                {
68                    mulVec.emplace_back(num1, num2);
69                    result += (num1*num2);
70                    break;
71                }
72                else
73                    break;
74            }
75        }
76
77    }

Part 2: Do/Don’t Multiply#

There are two new instructions you’ll need to handle:

  • The do() instruction enables future mul instructions.

  • The don't() instruction disables future mul instructions.

 96    std::regex regex(R"((mul\(\d{1,3},\d{1,3}\))|(do\(\))|(don't\(\)))");
 97    
 98    std::sregex_iterator start{ std::sregex_iterator(contents.begin(), contents.end(), regex) };
 99    std::sregex_iterator end{ std::sregex_iterator() };
100
101    unsigned int result(0);
102
103    int mulEnabled(1);
104    for (auto i = start; i != end; ++i)
105    {
106        //std::smatch match = *i;
107        std::string match = (*i).str();
108
109        if(match.compare("don't()") == 0)
110            mulEnabled = 0;
111
112        else if (match.compare("do()") == 0) 
113            mulEnabled = 1;
114
115        else
116        {
117            int num1(0), num2(0);
118            auto j = 4;
119            while(match[j] != ',')
120                num1 = num1*10 + (match[j++] - '0'); 
121            ++j;
122            while(match[j] != ')')
123                num2 = num2*10 + (match[j++] - '0');
124
125            result += (mulEnabled * num1 * num2); 
126        }
127    }

Concepts Learned#

Stream Iterators#

  1. std::istream_iterator

  2. std::istreambuf_iterator

  3. Read entire file into a string:

1std::ifstream file(filename);
2std::string contents{std::istreambuf_iterator<char>(file), std::istreambuf_iterator<char>()};
3// or into a vector of strings

Tip

When reading characters, std::istream_iterator skips whitespace by default (unless disabled with std::noskipws or equivalent), while std::istreambuf_iterator does not. In addition, std::istreambuf_iterator is more efficient, since it avoids the overhead of constructing and destructing the sentry object once per character.

Regex#

  1. std::cmatch for std::match_results<const char*>: cannot be used with iterators.

  2. std::smatch for std::match_results<std::string::const_iterator> to be used with iterators

  3. std::regex_match for entire sequence

  4. std::sregex_iterator for iterators, which dereferences to std::smatch

Examples
1std::regex pattern(R"(mul\(\d{1,3},\d{1,3}\))");
2std::string input = "mul(123,456)";
3if (std::regex_match(input, pattern)) {
4    std::cout << "Pattern matched!" << std::endl;
5}
 1    std::regex regex(R"((mul\(\d{1,3},\d{1,3}\))|(do\(\))|(don't\(\)))");
 2    
 3    std::sregex_iterator start{ std::sregex_iterator(contents.begin(), contents.end(), regex) };
 4    std::sregex_iterator end{ std::sregex_iterator() };
 5
 6    for (auto i = start; i != end; ++i)
 7    {
 8        std::smatch match = *i;
 9        cout << match.str() << endl;
10    }

Strings#

  1. std::string::compare: returns 0 if equal

  2. std::stoi - String to Int

References and Resources#


Day 5: Print Queue#

Solution Overview#

Part 1: Check Page Order#

The first part of the input contains a list of rules X|Y which states that page X must be printed at some point before page Y. Next part have list page sequences, identify which one of those are in right order.

  • Iterates over all pairs (i,j) in the given page sequence where i<j.

  • For each pair, checking if it violates any of the rule.

  • If no rule violated, the order is valid.

126bool isOrderValid(const std::vector<int>& o, const std::vector<std::pair<int, int>>& rule)
127{
128    for(auto i=0; i < o.size()-1; ++i) 
129    {
130        for(auto j=i+1; j < o.size(); ++j) 
131        {
132            for(auto r: rule)
133            {
134                if(o[i] == r.second && o[j] == r.first) // incorrect order
135                {
136                    return false;
137                }
138            }
139        }
140    }
141    return true;
142}

This is simply brute force and horrible time complexity of \(O(n^2\times m)\) where \(n\) is length of the page sequence (o.size()) and \(m\) is a number of rules(rule.size()).

Optimization#

A faster solution (aoc2024/day05/solution.cpp at main · UnicycleBloke/aoc2024) (\(O(m\times n)\)) I found on Reddit:

  • Iterate over rules \(O(m)\)

  • For each rule find its first and second elements in the sequence (Linear search \(O(2n)\), might short-circuit if first not found \(O(n + n/2)\))

  • check if both finds follow the rule, based on position they appear in the sequence. Else order is not valid.

More optimized solution would require a Hash Map:

145bool isOrderValid(const std::vector<int>& o, const std::vector<std::pair<int, int>>& rule) {
146    // Map elements in 'o' to their indices for fast lookup
147    std::unordered_map<int, int> indexMap;
148    for (int i = 0; i < o.size(); ++i) {
149        indexMap[o[i]] = i;
150    }
151
152    // Check if any rule is violated
153    for (const auto& r : rule) {
154        if (indexMap.find(r.first) != indexMap.end() && indexMap.find(r.second) != indexMap.end()) {
155            if (indexMap[r.first] > indexMap[r.second]) {
156                // Order is invalid
157                return false;
158            }
159        }
160    }
161    // Order is valid
162    return true;
163}

Bringing time complexity to \(O(m + n)\) as find in Hash Map is \(O(1)\) operation.

// Before
[100%] Built target day5
Part 1: 4790
Elapsed time: 7330 us
Part 2: 6319
Elapsed time: 9174 us
Elapsed time: 45189 us
[100%] Built target run5

// After Optimization
[100%] Built target day5
Part 1: 4790
Elapsed time: 2959 us
Part 2: 6319
Elapsed time: 3437 us
Elapsed time: 38453 us
[100%] Built target run5

Part 2: Sort pages as per the Rules#

For each of the incorrectly-ordered updates, use the page ordering rules to put the page numbers in the right order.

Implemented a bubble sort such that while not sorted keep swapping the elements in incorrect order.

 93    for(std::vector<int>& o: incorrect_orders)
 94    {
 95        while(true)
 96        {
 97            bool order_valid = true;
 98
 99            for(auto r: rule)
100            {
101                auto i=0,j=0;
102                for(; i < o.size(); ++i)
103                {
104                    if(o[i] == r.first) break;
105                }
106                for(; j < o.size(); ++j) 
107                {
108                    if(o[j] == r.second) break;
109                }
110
111                if(i==o.size() || j==o.size()) continue;
112                if(j < i)
113                {
114                    std::swap(o[i], o[j]);
115                    order_valid = false;
116                    break;
117                }
118            }
119
120            if (order_valid) break;
121        }
122    }

Found a more optimized solution on the internet, using \(m\times m\) matrix data, where data[a][b] == true means a must come before b in any valid sequence.

Key Takeaways#

std::move#

Example std::move
 1    while (std::getline(file, line))
 2    {
 3        cout << line << endl;
 4        std::istringstream iss(line);
 5        std::vector<int> pages;
 6        std::string page;
 7        while (std::getline(iss, page, ','))
 8        {
 9            pages.push_back(std::stoi(page));
10        }
11        order.push_back(std::move(pages));
12        /**
13        order.push_back(pages);           - Copies the content of pages into order
14        order.push_back(std::move(pages)) - Moves the contents, no copying, ownership of interal is transferred
15        When use std::move??
16        -> Don't need the original vector
17        -> performance optimization
18		*/
19    }

for loop with pass by reference#

  1. for(auto o: orders): The copy constructor of std::vector<int> is called for each element of orders.

1    for(std::vector<int> o: incorrect_orders)
2    {
3	    // some condition
4        std::swap(o[i], o[j]);
5	}
6	// Does NOT change the original
7	// Instead do
8	for(std::vector<int>& o: incorrect_orders) 
Fun#

Ref: 2024 Day 5 (part 2) Non-Transitivity, non-schmansitivity : r/adventofcode

References and Resources#


This marks the first part of my Advent of Code 2024 journey. More updates soon. If you’re also learning C++ or participating in Advent of Code, I’d love to hear about your experiences! Share your thoughts, tips, or solutions in the comments below. Feel free to check out my solutions on GitHub.”

Comments