Advent of Code 2018

[Cups]

For all of the programmers that are celebrating the festive season, the Advent of Code is here! If you wish to talk about some of the challenges or participate, please visit the website at ! The input (and hence answers) are different for everyone, but you can still share the code you used to solve them. There is no API for the site so you'll need to read your input from a file.

Best of luck to all! Let me know how you go! Please keep discussions to English only! If you post code on elitepvpers please make sure its in spoiler tags - click Hastebin / Github links at your own discretion knowing that it may contain spoilers!

My solutions -

[florian0]

Wow ... Day 1 Part 2 really took a lot of cycles (142). I even considered my input to be broken.

[Cups]

Originally Posted by florian0

Wow ... Day 1 Part 2 really took a lot of cycles (142). I even considered my input to be broken.

I updated my post - feel free to post your solutions as long as they're in a spoiler tag (if it's a code block on the forum), or feel free to just post a link to your Github repository / Hastebin if you feel like sharing your answers! I've updated the main post to include a link to my solutions.

Glad you found the puzzles challenging, things like this keep the mind active!

[florian0]

Originally Posted by Cups

Glad you found the puzzles challenging, things like this keep the mind active!

I chose std::list, which was not a good choice regarding speed. So finding the frequency initially took roughly 1:30min. Thats why I considered my set to be wrong ;D

I'm now using unordered_set, which is way faster in this case.

 Day 1 Part 2 Solution inside

#include <cstdio>
#include <unordered_set>

int main()
{
	typedef int num_t;

	num_t freq = 0;
	int inp = 0;

	std::unordered_set<num_t> freqs;

	FILE* f = fopen("advent_1_2.txt", "r");

	while (1)
	{
		while(fscanf(f, "%d", &inp) == 1)
		{
			freq += inp;

			if (freqs.find(freq) != freqs.end())
			{
				printf("freq is %d\n", freq);
				return 0;
			}

			freqs.emplace(freq);
		}

		rewind(f);
	}

	return 1;
}

[Cups]

Originally Posted by florian0

I chose std::list, which was not a good choice regarding speed. So finding the frequency initially took roughly 1:30min. Thats why I considered my set to be wrong ;D

I'm now using unordered_set, which is way faster in this case.

 Day 1 Part 2 Solution inside

#include <cstdio>
#include <unordered_set>

int main()
{
	typedef int num_t;

	num_t freq = 0;
	int inp = 0;

	std::unordered_set<num_t> freqs;

	FILE* f = fopen("advent_1_2.txt", "r");

	while (1)
	{
		while(fscanf(f, "%d", &inp) == 1)
		{
			freq += inp;

			if (freqs.find(freq) != freqs.end())
			{
				printf("freq is %d\n", freq);
				return 0;
			}

			freqs.emplace(freq);
		}

		rewind(f);
	}

	return 1;
}

You can make the code even simpler by using the return values of std::unordered_list#emplace - it returns a pair of <Iterator, bool>. The bool value will be false if a duplicate entry exists as a set only allows one of each element in its collection

[sk8land​]

 Spoiler

#include <iostream>
#include <iterator>
#include <numeric>

int main(int argc, char *argv[])
{
    std::istream_iterator<int> is(std::cin);
    std::istream_iterator<int> eos;
    int result = accumulate(is, eos, 0);
    std::cout << result << std::endl;
    return 0;
}

 Spoiler

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <unordered_set>
#include <vector>


int main(int argc, char *argv[])
{
    std::istream_iterator<int> is(std::cin);
    std::istream_iterator<int> eos;
    std::vector<int> v;
    copy(is, eos, std::back_inserter(v));

    int s = 0;
    std::unordered_set<int> m;
    while (true) {
        for (const int x : v) {
            if (!m.insert(s).second) {
                std::cout << s << std::endl;
                return 0;
            }
            s += x;
        }
    }
    return 0;
}

[Cups]

Repository has been updated with solutions for day 2! No cheating now :P

[sk8land​]

Originally Posted by Cups

Repository has been updated with solutions for day 2! No cheating now :P

I consider LINQ to be cheating.

 Spoiler

#include <iostream>
#include <string>
#include <unordered_map>

int main(int argc, char *argv[])
{
    std::string line;
    int twice = 0;
    int thrice = 0;
    while (std::getline(std::cin, line)) {
        std::unordered_map<char, int> m;
        bool b_twice = false;
        bool b_thrice = false;
        for (char &c : line) {
            auto it = m.find(c);
            if (it != m.end()) {
                (it->second)++;
            } else {
                m.insert({c, 1});
            }
        }
        for (auto &kv : m) {
            if (kv.second == 2 && !b_twice) {
                twice++;
                b_twice = true;
            }
            if (kv.second == 3 && !b_thrice) {
                thrice++;
                b_thrice = true;
            }
        }
    }
    std::cout << twice * thrice << std::endl;
    return 0;
}

 Spoiler

#include <iostream>
#include <iterator>
#include <string>
#include <vector>

int main(int argc, char *argv[])
{
    std::istream_iterator<std::string> is(std::cin);
    std::istream_iterator<std::string> eos;
    std::vector<std::string> v;
    copy(is, eos, std::back_inserter(v));
    for (auto it1 = v.begin(); it1 != v.end(); ++it1) {
        for (auto it2 = it1 + 1; it2 != v.end(); ++it2) {
            std::string s1 = *it1;
            std::string s2 = *it2;
            if (s1.length() != s2.length()) {
                continue;
            }
            int diff = -1;
            for (int i = 0; i < s1.size(); ++i) {
                if (s1[i] != s2[i]) {
                    if (diff != -1) {
                        diff = -1;
                        break;
                    }
                    diff = i;
                }
            }
            if (diff != -1) {
                std::cout << s1.substr(0, diff) <<
                    s1.substr(diff + 1, s1.size()) <<
                    std::endl;
                return 0;
            }
        }
    }
    return 0;
}

[Cups]

Originally Posted by sk8land​

I consider LINQ to be cheating.

 Spoiler

#include <iostream>
#include <string>
#include <unordered_map>

int main(int argc, char *argv[])
{
    std::string line;
    int twice = 0;
    int thrice = 0;
    while (std::getline(std::cin, line)) {
        std::unordered_map<char, int> m;
        bool b_twice = false;
        bool b_thrice = false;
        for (char &c : line) {
            auto it = m.find(c);
            if (it != m.end()) {
                (it->second)++;
            } else {
                m.insert({c, 1});
            }
        }
        for (auto &kv : m) {
            if (kv.second == 2 && !b_twice) {
                twice++;
                b_twice = true;
            }
            if (kv.second == 3 && !b_thrice) {
                thrice++;
                b_thrice = true;
            }
        }
    }
    std::cout << twice * thrice << std::endl;
    return 0;
}

 Spoiler

#include <iostream>
#include <iterator>
#include <string>
#include <vector>

int main(int argc, char *argv[])
{
    std::istream_iterator<std::string> is(std::cin);
    std::istream_iterator<std::string> eos;
    std::vector<std::string> v;
    copy(is, eos, std::back_inserter(v));
    for (auto it1 = v.begin(); it1 != v.end(); ++it1) {
        for (auto it2 = it1 + 1; it2 != v.end(); ++it2) {
            std::string s1 = *it1;
            std::string s2 = *it2;
            if (s1.length() != s2.length()) {
                continue;
            }
            int diff = -1;
            for (int i = 0; i < s1.size(); ++i) {
                if (s1[i] != s2[i]) {
                    if (diff != -1) {
                        diff = -1;
                        break;
                    }
                    diff = i;
                }
            }
            if (diff != -1) {
                std::cout << s1.substr(0, diff) <<
                    s1.substr(diff + 1, s1.size()) <<
                    std::endl;
                return 0;
            }
        }
    }
    return 0;
}

Then I'd go so far as to say you're being rather silly, especially in this scenario! Firstly, it's important to make the distinction that the Advent of Code is by no means a programming challenge, but a problem solving exercise.

Second, LINQ in this use case is not providing any functionality that any other language with high order functions like Map, Reduce, Fold and Zip would provide. Would you consider it cheating if I wrote my answers in Haskell? The code would be much more concise and be using the exact same functions that LINQ provides.

Edit: After writing that response I decided to try a functional language for the first time ever. Could probably be improved a lot and isn't totally idiomatic F# but it's my first program ever using the language. I don't fully understand the functional idioms just yet :P

[sk8land​]

Originally Posted by Cups

Then I'd go so far as to say you're being rather silly, especially in this scenario! Firstly, it's important to make the distinction that the Advent of Code is by no means a programming challenge, but a problem solving exercise.

Second, LINQ in this use case is not providing any functionality that any other language with high order functions like Map, Reduce, Fold and Zip would provide. Would you consider it cheating if I wrote my answers in Haskell? The code would be much more concise and be using the exact same functions that LINQ provides.

Edit: After writing that response I decided to try a functional language for the first time ever. Could probably be improved a lot and isn't totally idiomatic F# but it's my first program ever using the language. I don't fully understand the functional idioms just yet :P

Calm down, kangaroo. It was just a joke.

 Spoiler

#include <iostream>
#include <iterator>
#include <regex>
#include <set>
#include <string>
#include <vector>

int main(int argc, char *argv[])
{
    std::vector<std::vector<std::pair<int, int>>> v;
    std::vector<int> ids;
    std::set<int> non_overlapped;
    std::set<std::pair<int, int>> intersections;
    std::string line;
    std::regex re("^#\\s*(\\d+)\\s*@\\s*(\\d+),(\\d+):\\s*(\\d+)x(\\d+)$");
    std::smatch match;
    while (std::getline(std::cin, line)) {
        std::regex_match(line, match, re);
        int id = std::stoi(match[1]);
        ids.push_back(id);
        non_overlapped.insert(id);
        std::vector<std::pair<int, int>> s;
        for (int i = std::stoi(match[2]); i < std::stoi(match[2]) + std::stoi(match[4]); ++i) {
            for (int j = std::stoi(match[3]); j < std::stoi(match[3]) + std::stoi(match[5]); ++j) {
                s.emplace_back(i, j);
            }
        }
        int j = 0;
        for (const auto &s2 : v) {
            std::vector<std::pair<int, int>> intersection;
            std::set_intersection(s.begin(), s.end(),
                                  s2.begin(), s2.end(),
                                  std::back_inserter(intersection));
            intersections.insert(intersection.begin(), intersection.end());
            if (!intersection.empty()) {
                non_overlapped.erase(id);
                non_overlapped.erase(ids[j]);
            }
            ++j;
        }
        v.push_back(s);
    }
    std::cout << intersections.size() << std::endl;
    if (!non_overlapped.empty()) {
        std::cout << *non_overlapped.begin() << std::endl;
    }
    return 0;
}

Edit: I would like to solve one of those with Haskell as well, but it's been ages since I was exposed to Haskell in uni and I forgot the whole syntax. The last time I tried to get into Haskell again it gave me autism.

[florian0]

Had to skip Day 2, got a bad headache.

Reading is definitely not one of my strengths. I didn't read day 3 to the end and "accidentally" build an algorithm to find the largest single rectangle of all overlapping claims. lol.

[0xFADED]

My take on Day 3:

Probably overcomplicated af, but it works

[Cups]

Originally Posted by 0xFADED

My take on Day 3:

Probably overcomplicated af, but it works

Hey what matters is that it works :P

Updated repository with solutions to day 4 -

[sk8land​]

 Spoiler

#include <algorithm>
#include <iostream>
#include <map>
#include <regex>
#include <string>
#include <unordered_map>
#include <vector>

int main(int argc, char *argv[])
{
    std::vector<std::string> v;
    std::string line;
    while (std::getline(std::cin, line)) {
        v.push_back(line);
    }
    std::sort(v.begin(), v.end());
    std::unordered_map<int, std::vector<int>> minutes_asleep;
    std::regex re("^\\[(\\d+)-(\\d+)-(\\d+)\\s+(\\d+):(\\d+)\\]\\s+Guard #(\\d+) begins shift$");
    std::regex re2("^\\[(\\d+)-(\\d+)-(\\d+)\\s+(\\d+):(\\d+)\\].*$");
    std::smatch match;
    int id;
    int minute = -1;
    for (const std::string &line : v) {
        std::regex_match(line, match, re);
        if (!match.empty()) {
            id = std::stoi(match[6]);
        } else {
            std::regex_match(line, match, re2);
            int m = std::stoi(match[5]);
            if (minute == -1) {
                minute = m;
            } else {
                auto x = minutes_asleep.insert({id, std::vector<int>()});
                for (int i = minute; i < m; ++i) {
                    x.first->second.push_back(i);
                }
                minute = -1;
            }
        }
    }
    auto max = std::max_element(minutes_asleep.begin(), minutes_asleep.end(),
                                [](std::pair<int, std::vector<int>> a,
                                   std::pair<int, std::vector<int>> b) {
                                    return a.second.size() < b.second.size();
                                });
    std::unordered_map<int, int> m;
    for (int x : max->second) {
        auto y = m.insert({x, 0});
        y.first->second++;
    }
    int max_minute = std::max_element(m.begin(), m.end(),
                                      [](std::pair<int, int> a,
                                         std::pair<int, int> b) {
                                          return a.second < b.second;
                                      })->first;
    std::cout << max->first * max_minute << std::endl;
    std::map<std::pair<int, int>, int> m2;
    for (const auto &x : minutes_asleep) {
        for (int y : x.second) {
            auto z = m2.insert({{x.first, y}, 0});
            z.first->second++;
        }
    }
    auto max_id_minute = std::max_element(m2.begin(), m2.end(),
                                          [](std::pair<std::pair<int, int>, int> a,
                                             std::pair<std::pair<int, int>, int> b) {
                                              return a.second < b.second;
                                          })->first;
    std::cout << max_id_minute.first * max_id_minute.second << std::endl;
    return 0;
}

I would appreciate any tips on how to simplify this.

Day 5:

 Spoiler

#include <cctype>
#include <stack>
#include <string>
#include <iostream>
#include <iterator>

template<class iterator_type>
int f(iterator_type begin, iterator_type end, char skip = 0)
{
    std::stack<char> s;
    for (auto it = begin; it != end; ++it) {
        if (skip == std::tolower(*it)) {
            continue;
        }
        if (!s.empty() && *it != s.top() && std::toupper(*it) == std::toupper(s.top())) {
            s.pop();
        } else {
            s.push(*it);
        }
    }
    return s.size();
}

int main(int argc, char *argv[])
{
    std::string s;
    std::cin >> s;
    std::cout << f(s.begin(), s.end()) << std::endl;
    int min = s.size();
    for (char c = 'a'; c <= 'z'; ++c) {
        min = std::min(min, f(s.begin(), s.end(), c));
    }
    std::cout << min << std::endl;
    return 0;
}