Quantcast
Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
    1. Welcome to GTAForums!

    1. GTANet.com

    1. GTA Online

      1. The Cayo Perico Heist
      2. Find Lobbies & Players
      3. Guides & Strategies
      4. Vehicles
      5. Content Creator
      6. Help & Support
    2. Red Dead Online

      1. Frontier Pursuits
      2. Find Lobbies & Outlaws
      3. Help & Support
    3. Crews

    1. Red Dead Redemption 2

      1. PC
      2. Help & Support
    2. Red Dead Redemption

    1. Grand Theft Auto Series

      1. St. Andrews Cathedral
    2. GTA VI

    3. GTA V

      1. Guides & Strategies
      2. Help & Support
    4. GTA IV

      1. The Lost and Damned
      2. The Ballad of Gay Tony
      3. Guides & Strategies
      4. Help & Support
    5. GTA San Andreas

      1. Guides & Strategies
      2. Help & Support
    6. GTA Vice City

      1. Guides & Strategies
      2. Help & Support
    7. GTA III

      1. Guides & Strategies
      2. Help & Support
    8. Portable Games

      1. GTA Chinatown Wars
      2. GTA Vice City Stories
      3. GTA Liberty City Stories
    9. Top-Down Games

      1. GTA Advance
      2. GTA 2
      3. GTA
    1. GTA Mods

      1. GTA V
      2. GTA IV
      3. GTA III, VC & SA
      4. Tutorials
    2. Red Dead Mods

      1. Documentation
    3. Mod Showroom

      1. Scripts & Plugins
      2. Maps
      3. Total Conversions
      4. Vehicles
      5. Textures
      6. Characters
      7. Tools
      8. Other
      9. Workshop
    4. Featured Mods

      1. Design Your Own Mission
      2. OpenIV
      3. GTA: Underground
      4. GTA: Liberty City
      5. GTA: State of Liberty
    1. Rockstar Games

    2. Rockstar Collectors

    1. Off-Topic

      1. General Chat
      2. Gaming
      3. Technology
      4. Movies & TV
      5. Music
      6. Sports
      7. Vehicles
    2. Expression

      1. Graphics / Visual Arts
      2. GFX Requests & Tutorials
      3. Writers' Discussion
      4. Debates & Discussion
    3. Gangs

    1. Announcements

    2. Support

      1. Court House
    3. Suggestions

Advent of Code


Edmachine

Recommended Posts

Greetings, coders of GTAForums!

 

I bestow upon you a great programming challenge! 'Tis called Advent of Code. For 25 days in December, each day there's a new programming challenge unlocked, much like an advent calendar, but instead of chocolate, it's a puzzle. And it's all part of a Christmas story. Find the answer(s) however you like, use whatever programming language you want, a pen and paper, or Excel.

Each new puzzle is unlocked at midnight UTC-5 (so, 5 AM UTC 0). If you want to score points for the global leaderboard, you have to be very quick, because only the first 100 people get points.

 

So, whether you want to do some casual coding, improve your programming skills, maybe learn a new language, or learn how to optimise the sh*t out of your code, Advent of Code is an awesome challenge. Come, join!

 

Personally, this will be my 3rd year participating. Since I use Kotlin daily, that's what I code in for AoC. I've set up a nice little project for myself, if anyone wants any inspiration (or solutions).

 

Happy coding!

Link to post
Share on other sites
2 hours ago, K^2 said:

First day was a bit of a disappointment, but I'll see how it goes from here.

Too easy or the leaderboards stuff? First days are generally quite easy, makes it more approachable for newcomers (and/or new developers).

 

What's your weapon of choice?

Link to post
Share on other sites
17 hours ago, Edmachine said:

Too easy or the leaderboards stuff?

A bit of both. But while I get the easing-in bit, the 2-star variant wasn't a complication on top of original at all. Absolute dumbest algorithm has to check 8 million combinations, and that's still instant even if you do this with Excel, let alone any programming language. IMO, the 2-star variant could have asked for something like 5-6 numbers, which would mean you either have to get clever or spend some time waiting for the result. (For example!) Of course, the pruning strategy here is still very simple, but that feels about right for a warm-up. "Realizing you can do the same dumb approach again," seems a little meh for two stars.

 

17 hours ago, Edmachine said:

What's your weapon of choice?

I might have to mix it up a bit given time constraints, but I'll probably stick to C++ as core. I'll switch to Python if I need anything from heavy statistics, NN, or linear programming.

Link to post
Share on other sites
11 hours ago, K^2 said:

A bit of both. But while I get the easing-in bit, the 2-star variant wasn't a complication on top of original at all. Absolute dumbest algorithm has to check 8 million combinations, and that's still instant even if you do this with Excel, let alone any programming language. IMO, the 2-star variant could have asked for something like 5-6 numbers, which would mean you either have to get clever or spend some time waiting for the result. (For example!) Of course, the pruning strategy here is still very simple, but that feels about right for a warm-up. "Realizing you can do the same dumb approach again," seems a little meh for two stars.

I get what you mean, yeah. Sometimes it's basically about making the input 10000 times larger or something, but then the trick is choosing a better solution. Part 1 of Day 22     last year was easy enough. But the 2nd part made the deck a lot larger, which my algorithm couldn't handle. I didn't see it, but plenty of people knew that it was a number theory puzzle and came up with some really neat solutions that run very, very quickly (by doing some smart calculations rather than brute-forcing it).

11 hours ago, K^2 said:

I might have to mix it up a bit given time constraints, but I'll probably stick to C++ as core. I'll switch to Python if I need anything from heavy statistics, NN, or linear programming.

Do you try to find the most efficient algorithm or are you satisfied with something that just works?

 

Did you do Day 2 yet?

Link to post
Share on other sites
14 hours ago, Edmachine said:

Do you try to find the most efficient algorithm or are you satisfied with something that just works?

For challenges like these, the most efficient solution is the one that gives you the answer fastest. So I only optimize if I expect a long run-time or if optimization is so trivial as to not take me longer to code.

 

I like optimization challenges as well, but they inherently have to be conducted differently, with solutions executed on the same machine and timed over multiple runs.

 

14 hours ago, Edmachine said:

Did you do Day 2 yet?

Yeah. Screwed up time zones, though, so not even a chance at leader board.

 

Kind of same problem as before. The hard part in this challenge is parsing. Of course, if you know how to use regex, that's suddenly not a problem at all - again, performance hardly matters, so a canned regex solver works. And once you have it parsed, the difference between part 1 and part 2 is two lines of code.

 

I did lose a lot of time debugging the problem when my first submission was wrong only to find that I was counting instances that fail and challenge asked for these that pass. And then on second part I OF COURSE forgot to account for positions not being zero-indexed. So yeah, took me almost 20 minutes. I'll have to make sure I read conditions more carefully in the future. XD

 

Edit: 3rd day challenge is actually even easier than 2nd. Problem with part-2 bringing absolutely nothing new persists. Also, still messing up start time. I'll set an alarm.

Link to post
Share on other sites
12 hours ago, K^2 said:

For challenges like these, the most efficient solution is the one that gives you the answer fastest. So I only optimize if I expect a long run-time or if optimization is so trivial as to not take me longer to code.

 

I like optimization challenges as well, but they inherently have to be conducted differently, with solutions executed on the same machine and timed over multiple runs.

The way I typically do it is to get the answer as quickly as, whatever the run time or however the code might look like. And then optimize the code or just clean it up, so I don't feel bad about putting it on my GitHub. It's always a bit of a fight - make it efficient, don't use extraneous classes, or make it a bit slower, but easier to read.

 

12 hours ago, K^2 said:

I did lose a lot of time debugging the problem when my first submission was wrong only to find that I was counting instances that fail and challenge asked for these that pass. And then on second part I OF COURSE forgot to account for positions not being zero-indexed. So yeah, took me almost 20 minutes. I'll have to make sure I read conditions more carefully in the future. XD

Hah, yeah, I've lost plenty of time because of that. Always in a hurry to get the answer quickly.

 

Day 3 was pretty fun. Finally could use a single function for both parts this year. :D

Link to post
Share on other sites

Oh, I haven't bothered with pretty, and I usually just modify code in place for pt2. This one's a good example where you can see how code "evolved", since I haven't bothered fixing indent.

 

    size_t total = 1;
    
    for (size_t j = 0; j < 5; ++j) {
    
    size_t x = 0;
    size_t count = 0;
    for (size_t i = 0; i < n; ++i)
    {
        count += (strs[i][x]) == '#';
        x = (x + slopes[j]) % w;
        if (j == 4) ++i;
    }
    
    std::cout << count << std::endl;
        
    total *= count;
        
    }

And sure, it can easily be made to accept arbitrary rational slopes, but putting in an if statement for account for the only case of 1/2 is just faster. 🤷‍♂️

 

I'd never let anyone check in code like that, but then I don't really see much reason to keep it around, so it hasn't been a concern.

 

 

Edit: Started on time for day 4. There were 1500+ other gold stars by the time I got mine, so I need to be a little faster. This one would definitely go by quicker with Python.

 

Edit2: Day 5. 12 minutes and I'm barely in top 1,000 for the day. Lost some time creating row/column pairs rather than just encoding ID from the start. Started building up utility library to make better use of STL to better compete against Python.

Link to post
Share on other sites

Yeah, getting on the leaderboards is tough. Especially if you love sleep like I do. (timezone doesn't help much either)

 

Day 4 was fun. The most annoying part (after getting the answers) was finding a neat way to group the passport fields. A regular for loop meant having to repeat some code after the loop. Eww. Did it with a fold, much nicer. Though not nearly as quick.

 

Day 5 was cool, too. Kinda ashamed of myself that I didn't figure out you could just convert F and L to 0, and B and R to 1, convert it to a number and there's your ID, and that's all you need. But it's what I put in my solution. :D

Link to post
Share on other sites

Yeah, I caught that part, but I wasted time actually counting cols and rows separately rather than just returning the result as is.

 

Day 6 - still not getting any harder. I definitely should have been doing this with Python. I was expecting some of these to at least remotely start getting algorithmically heavy, but it's all just parsing exercises. If you're good with regex and map-reduce, these are speed-reading and speed-typing challenges, honestly. And you can be more concise in Python. I'm managing reliable sub-15 minutes runs, except for day 4. That took almost half an hour - partially because you can't do switch/when on strings in C++. I realized after the fact that I could have done a switch on hash values and it'd be basically the same thing, but as it was, I wasted a lot of time writing that ugly if/else if chain.

 

I did set up essentially a mini-library for converting inputs into arrays so I can do map/reduce way more efficiently, as well as tokenizer and key-value mapper. Tokenizer helped me on day 6, as I was able to turn input into array of arrays of strings, and then map-reduce it with minimal effort, but it's still a lot of typing in C++, so it took 12 minutes and 1600 submissions were already in when I finished.

 

Honestly, if the challenges themselves aren't going to get to the point where it requires _some_ thinking, I'll be disappointed. But I also feel like I've invested enough to finish the set and at least TRY to get into top 100 on one of these. Top 1k is my best so far, though, so that's a lot of improvement to make.

 

By the way, @Edmachine. I took a look at your day 4 solution. You write very clean Python. You use it in work/education at all?

Link to post
Share on other sites

Yeah, I'm a bit surprised, really. But maybe it's due to the growing popularity of AoC, that the puzzles are easier. But, hey, I'm not complaining, this is still fun at least (for me). 2018, Day 13 I couldn't figure out on the same day, so I essentially stopped doing AoC for that year. Last year I decided to just skip the ones I can't do (and did some of them a few days ago).

 

How would you have done a switch on hash values? Like, write code once to hash and print all fields, then use those hashes in the switch?

 

Sounds like you need to rewrite a whole lot of what Python/Kotlin can already do out of the box. What does your day 6 look like?

 

4 hours ago, K^2 said:

By the way, @Edmachine. I took a look at your day 4 solution. You write very clean Python. You use it in work/education at all?

 

Hah, mate, the only thing I know about Python is that you define functions with the def keyword. And I'm not even sure that's completely correct either. I only really know Kotlin (and Java). Been thinking about expanding my knowledge and learning some backend stuff, but that's a different topic and one that I haven't really touched either.

 

Day 6 was fun again, I think. I mean, yeah, it's easy, but it was fun to write. :)

 

 

Link to post
Share on other sites
2 hours ago, Edmachine said:

Sounds like you need to rewrite a whole lot of what Python/Kotlin can already do out of the box. What does your day 6 look like?

I'm starting to see patterns, so I have been adding some utility functions to make things cleaner. So day 6 isn't looking too bad. The only thing is that I had to pull union/intersection into a C-style loop. Rest is handled at high level.

Spoiler
int main()
{
    auto data = GetInput();
    std::cout << data.size() << std::endl;
    std::vector<std::string> v;
    v.resize(data.size());
    std::transform (data.begin(), data.end(), v.begin(), [](std::string str) {
        auto vec = Tokenize(str, ' ');
        std::string s;
        for (char c = 'a'; c <= 'z'; ++c)
        {
            bool pass = true;
            for (auto& ss : vec)
            {
                /*if (ss.find(c) != ss.npos)
                {
                    s.push_back(c);
                    break;
                }*/
                if (ss.find(c) == ss.npos)
                    pass = false;
            }
            if (pass)
                s.push_back(c);
        }
        return s;
    });
    size_t count = std::accumulate(v.begin(), v.end(), 0, [](size_t n, std::string s) { return n + s.size(); });
    std::cout << count << std::endl;
    return 0;
}

 

The std::transform is C++ version of map operation and lambda inside handles the union(commented out) or intersection by looping over the alphabet. There's a cleaner way to handle unions with sets, but intersection would have to be ugly regardless, and this didn't take long to type out, so that's fine.

 

The heavy lifting is all in how I'm parsing data now. I did use a regex tool to convert input into a comma separated list of strings. Each string is space-separated entries for a single group. That way, I can use Tokenize utility to convert it into a vector of strings and work from there.

 

The thing about C++ is that its standard libraries try to make very few assumptions about what type of data you're going to be working with. So it doesn't give you something simple like array.map(/*lambda*/). Instead, you have std::transform, which can operate over any container. You just have to tell it how to iterate over all of the elements of input and output. That's what the begin() and end() methods do under the hood.

 

Not great for speed programming, but it's not horrible either. In principle, it wouldn't take me very long to write wrappers that can work just like Python/Kotlin/ES6 maps. Might help shave some time off...

 

2 hours ago, Edmachine said:

Hah, mate, the only thing I know about Python is that you define functions with the def keyword. And I'm not even sure that's completely correct either. I only really know Kotlin (and Java). Been thinking about expanding my knowledge and learning some backend stuff, but that's a different topic and one that I haven't really touched either.

Oh, wow. Shows you how much attention I'm paying to syntax, doesn't it? You'd think curly brackets would be a dead giveaway. For some reason, that looked very Python to me, and I just assumed Kotlin is a derivative of some sort. I just took a look at a Wiki, and I can see now that it's rather different.

 

But either way, very clean structured code.

 

 

Edit: Done. Now I can do stuff like this to compute, for example, sum of squares.

 

    Container array{std::vector{1, 2, 3, 4, 5}};
    std::cout << array.Map([](auto x){ return x * x; }).Reduce(0, [](auto a, auto b){ return a + b; }) << std::endl;

Not a HUGE change, but if it saves me even 30 seconds, I'm happy with it.

Link to post
Share on other sites

I don't know much at all about C++, so let me take some guesses.

transform takes the starting location and the ending location of the string array, a location where to put the transformed values and an anonymous function that... I don't get the [](std::string str) syntax. Is that the parameter in the parenthesis? Anyway, and in the function you split each line by a space? Then loop through all chars a to z and each existing substring in the vector and adding each character to the return string, if it has been found in all substrings. And then similarly for the accumulate, starting location, end location, initial accumulator value and an anonymous function for the accumulator? Basically a fold, right? Sh*t, I'd like to try my hand at writing something like this. :D Looks fun!

 

9 hours ago, K^2 said:

 

Oh, wow. Shows you how much attention I'm paying to syntax, doesn't it? You'd think curly brackets would be a dead giveaway. For some reason, that looked very Python to me, and I just assumed Kotlin is a derivative of some sort. I just took a look at a Wiki, and I can see now that it's rather different.

 

 

But either way, very clean structured code.

Haha, I wouldn't blame you if you thought it was Swift, the syntax is rather similar. Thanks! I like writing clean code, sometimes to a fault. Always excited for a good refactoring task!

 

Gonna switch to Python moving on? It's bound to get trickier from here. Maybe not tomorrow perhaps, but eventually for sure.

Link to post
Share on other sites
10 hours ago, Edmachine said:

transform takes the starting location and the ending location of the string array, a location where to put the transformed values and an anonymous function

Yeah. This is almost a convention more than language spec (except for the use in for loops). Basically, all of the standard library functions dealing with iterable collections assume that you provide the begin() and end() functions that return start and end iterators. So if you want to create a completely custom collection that works with range loops and algorithms like std::sort, all you have to do is provide these functions.

 

10 hours ago, Edmachine said:

I don't get the [](std::string str) syntax. Is that the parameter in the parenthesis?

You got it. The only special bit is the square brackets that let you capture context. Unlike lambdas in something like ES6 that do auto-capture, you have to be explicit in C++, because programmer is responsible for memory management. You can tell the compiler to capture everything by value [=] or reference [&], but that's generally discouraged in any complex scenarios. It's better to be explicit about capture modes for anything you're interested in. You also absolutely have to be explicit if you want to pass ownership to the lambda, which is super useful in multi-threaded code.

 

This is one of these things that makes a lot more sense if you learn a bit more about how C++ manages variables and function arguments.

 

10 hours ago, Edmachine said:

Sh*t, I'd like to try my hand at writing something like this. :D Looks fun!

Yeah, modern C++ is actually far more exciting a language than it used to be. Starting with C++11 it's been kind of a renaissance. You can write stuff that looks almost as elegant as Python or ES6 code, while sacrificing almost nothing of performance. And knowing C++ gets you high paying jobs around here and probably doesn't hurt elsewhere either, so it's always good to know.

 

There's the whole aspect of templates and metaprogramming, though. A metaprogram is a program you write in templates that compiler evaluates as it compiles your code and produces customized version of your code to fit particular purpose. You don't HAVE to understand it to write in C++, but it gives you power to effectively extend the language and create new syntax. If you're interested in writing elegant-looking code, it might be a sort of thing that draws you in.

 

10 hours ago, Edmachine said:

Gonna switch to Python moving on?

I think I'm rusty enough with Python where it's only going to be a handicap until I refresh myself. I'd spend more time looking up syntax on stack overflow than actually writing code. XD So I'll stick to C++ and see how close to top 100 I can get. And hey, maybe there'll be something more complex in the future that will give me performance edge. With C++, I can throw AVX on 8 cores at a problem, effectively giving me 64x the computation speed. If I can brute-force in 10 minutes something it'd take half an hour on Python to optimize, I'll have my vengeance! Unlikely, but that's basically my only chance of getting onto daily leaderboard by now.

 

 

Edit: Day7 saved by recursion. Did take me 27m to implement, most of it for the parser.

Link to post
Share on other sites
20 hours ago, K^2 said:

Yeah. This is almost a convention more than language spec (except for the use in for loops). Basically, all of the standard library functions dealing with iterable collections assume that you provide the begin() and end() functions that return start and end iterators. So if you want to create a completely custom collection that works with range loops and algorithms like std::sort, all you have to do is provide these functions.

So, how do you provide the size of the element within the thing you're mapping? transform(v.begin(), v.end(), ...) just gives two pointers, but not the size of the thing they're pointing to. Unless it's dynamic arrays (dynamic memory?), but even then... It's been 6 years or so since I last touched C++ (and even then it was just the first year of uni), I have no idea. :D Aah, ooh, does it get the size of the array element based on the parameter you declare in the lambda [](std::string str)?

20 hours ago, K^2 said:

You got it. The only special bit is the square brackets that let you capture context. Unlike lambdas in something like ES6 that do auto-capture, you have to be explicit in C++, because programmer is responsible for memory management. You can tell the compiler to capture everything by value [=] or reference [&], but that's generally discouraged in any complex scenarios. It's better to be explicit about capture modes for anything you're interested in. You also absolutely have to be explicit if you want to pass ownership to the lambda, which is super useful in multi-threaded code.

How much context are we talking about here? I don't quite follow.

20 hours ago, K^2 said:

There's the whole aspect of templates and metaprogramming, though. A metaprogram is a program you write in templates that compiler evaluates as it compiles your code and produces customized version of your code to fit particular purpose. You don't HAVE to understand it to write in C++, but it gives you power to effectively extend the language and create new syntax. If you're interested in writing elegant-looking code, it might be a sort of thing that draws you in.

Sounds awesome! And also years above my paygrade, if I ever even decide to take a stab at C++. Is it similar to code generation in Java, for example? I've dabbled with that; my Bachelor's thesis used it extensively.

 

Day 7, very recursive, yeah. Was a bit slowed down by an off-by-one error (well, I just subtracted 1 and submitted my answer). Curious, how did you handle parsing the input on this one?

Link to post
Share on other sites
8 hours ago, Edmachine said:

So, how do you provide the size of the element within the thing you're mapping? transform(v.begin(), v.end(), ...) just gives two pointers, but not the size of the thing they're pointing to.

C/C++ are type-strong languages. So a pointer isn't just an address. The type of the pointer tells you what sort of an object it points to and its size. And C/C++ leverage that by having it so that when you increment a pointer, you don't go to the next byte in memory, but advance by a block of the size that makes sense for the type. So a pointer to int will advance by 4 bytes, etc.

 

But it gets even better. begin()/end() can return whatever type of object you want, not just a pointer. So a linked list, for example, has a custom iterator that follows the links to go to the next node. And you also provide a custom dereference operator which retrieves the actual address of underlying data. So you can get quite fancy with this and have it work with dictionaries, hash maps, etc.

 

8 hours ago, Edmachine said:

How much context are we talking about here? I don't quite follow.

Well, just for example, the following won't compile.

int x = 7;
[](){ std::cout << x << std::endl; }();

Because the stuff in curly brackets has no idea what that variable x that you're referencing is. So you fix it by capturing x.

int x = 7;
[x](){ std::cout << x << std::endl; }();

So that will run and print 7 to console. And you can rename the variables, control whether they're copied by value or by reference, and so on. There are also ways to get lazy and say, "Capture everything you need, assuming names are the same."

8 hours ago, Edmachine said:

Is it similar to code generation in Java, for example?

Sort of? It's built into the language and rather than running like a script, it resolves with substitution rules that are more similar to Prolog than most other languages.

 

8 hours ago, Edmachine said:

Curious, how did you handle parsing the input on this one?

Regex to parse into a dictionary mapping bag type to rule, each rule split by comma, and another regex to turn it into a dictionary of bag type to count. So the whole thing turns into dictionary of dictionaries that's very easy to walk recursively.

 

Also had that off-by-one error, by the way. Worst part is that with the way my recursion was set up, I consciously had to make the choice to count the rule for gold bag as one of the results.

 

 

Edit: Well, I'm consistent. Day 8 - 18 minutes. Less than 1,500 people finished faster.

Link to post
Share on other sites
19 hours ago, K^2 said:

C/C++ are type-strong languages. So a pointer isn't just an address. The type of the pointer tells you what sort of an object it points to and its size. And C/C++ leverage that by having it so that when you increment a pointer, you don't go to the next byte in memory, but advance by a block of the size that makes sense for the type. So a pointer to int will advance by 4 bytes, etc.

 

But it gets even better. begin()/end() can return whatever type of object you want, not just a pointer. So a linked list, for example, has a custom iterator that follows the links to go to the next node. And you also provide a custom dereference operator which retrieves the actual address of underlying data. So you can get quite fancy with this and have it work with dictionaries, hash maps, etc.

Ah, right. But a pointer to a pointer will always be 4 bytes, right? Unless you have 64-bit address space. Of course, that makes sense, you point to a specific kind of thing, so you know how big one thing is. You can see I'm not used to thinking about pointers, what with working with the JVM only.

The iterator sh*t, though, is black magic.

 

Re: context. Cool! So, if you capture everything, you're basically working with lambdas in Java or Python.

 

20 hours ago, K^2 said:

Sort of? It's built into the language and rather than running like a script, it resolves with substitution rules that are more similar to Prolog than most other languages.

Mm, Prolog. I had homework in uni to write something in Prolog (part of a course on programming languages, also had SmallTalk and Haskell). Was such a functional programming noob. Anyway, I digress. Templates are more similar to inline functions then, aren't they?

 

20 hours ago, K^2 said:

Regex to parse into a dictionary mapping bag type to rule, each rule split by comma, and another regex to turn it into a dictionary of bag type to count. So the whole thing turns into dictionary of dictionaries that's very easy to walk recursively.

 

Also had that off-by-one error, by the way. Worst part is that with the way my recursion was set up, I consciously had to make the choice to count the rule for gold bag as one of the results.

Wouldn't it be faster to find everything by delimiting with substrings? I.e., "foo bar bags contain 2 baz xyz bags, 1 alice bob bag." - take until first " bags", then take everything after "contain ", split by comma, take all before " bag". Without regex. I don't imagine regexing would be quite as fast.

 

Day 8 was interesting. Was kinda surprised brute-forcing part 2 was the only feasible option. You could backtrack from the loop point, undoing all instructions, changing the ops, checking from there, and so on. But the worst-case time complexity would still be the same. Anyway, computers again. We had Intcode last year, that was quite something. :)

Link to post
Share on other sites
14 minutes ago, Edmachine said:

Ah, right. But a pointer to a pointer will always be 4 bytes, right? Unless you have 64-bit address space.

C/C++ are intended to be cross-platform, so language standard doesn't guarantee it. In practice, yeah, anything on modern machine will have 8 byte pointers, but it's better not to assume it. sizeof(void*) will give you size of pointer at compile time, so you can use it instead of integer literal. This is particularly tough with int type, which can be 2, 4, or 8 bytes. But modern C++ provides you with int16_t, int32_t, and int64_t if you want to be explicit about it.

 

19 minutes ago, Edmachine said:

Templates are more similar to inline functions then, aren't they?

Template functions are usually inlined, but they don't have to be. They do have a calling convention, and it's up to the compiler to decide whether they are inlined or called.

 

You can also templatize structs and classes, which is where templates really take off, because you can have specialized and partially specialized templates. So for example, there is std::unordered_map. It's a dictionary backed by a hash table. So whatever you use as a key must be hashable. There is a struct called std::hash which can generate hashes for you, but it's only specialized for certain types. If you want to use something else for a key, you have to get creative. Here is a working example. It's extremely artificial, you'd never actually do anything like this, and would probably use a user ID to locate things, but it shows how templates can work.

Spoiler
#include <iostream>
#include <chrono>
#include <string>
#include <unordered_map>

struct UserAccount
{
    std::string name;
    std::string address;
    bool operator==(const UserAccount&) const = default;
};

struct UserRecord
{
    std::chrono::time_point<std::chrono::system_clock> registrationTime;
    float balance;
};

namespace std
{
template <>
struct hash<UserAccount>
{
    size_t operator()(const UserAccount& account) const
    {
        return std::hash<std::string>{}(account.name) ^ std::hash<std::string>{}(account.address);
    }
};
} //namespace std

int main()
{
    std::unordered_map<UserAccount, UserRecord> users;
    users[UserAccount{ "Jane Doe", "123 Nowhere Lane" }] = UserRecord{ std::chrono::system_clock::now(), 0.0f };
    
    for (auto& [account, record] : users)
    {
        std::cout << account.name << " -> " << record.balance << std::endl;
    }
    
    return 0;
}

 

 

46 minutes ago, Edmachine said:

Was kinda surprised brute-forcing part 2 was the only feasible option.

Yeah, I don't think there's anything terribly practical you could do there. You could optimize the hell out of code execution by creating a jump table and compiling the "program" into op codes, but again, entirely unnecessary when you only have a few hundred lines of code to deal with.

Link to post
Share on other sites
On 12/9/2020 at 12:05 AM, K^2 said:

[templates]

Can't say I fully comprehend the example, but... just looks like implementing an interface, really. :D

 

Day 9 was a nice mix of functional and imperative. Though, I've gotten a bit used to the functional style. And while loops like that seem ugly now. :(

Link to post
Share on other sites
7 hours ago, Edmachine said:

Can't say I fully comprehend the example, but... just looks like implementing an interface, really. :D

Interfaces are run-time. C++ has that too via virtual tables. Templates are explicitly compile-time, so you CAN make interface-like systems that don't ruin your optimization, but you can also do general computation with them.

 

7 hours ago, Edmachine said:

Day 9 was a nice mix of functional and imperative. Though, I've gotten a bit used to the functional style. And while loops like that seem ugly now. :(

Yeah, I wasn't happy with the general look of my code.

 

Day 10's interesting. Part 2 had me stop and think. Took me 22 minutes, and I was still in the top 1k. So I guess harder puzzles work in my favor. XD

Link to post
Share on other sites
12 hours ago, K^2 said:

Day 10's interesting. Part 2 had me stop and think. Took me 22 minutes, and I was still in the top 1k. So I guess harder puzzles work in my favor. XD

Took me a while. Part 1 was easy. Part 2, well, I had to work as well. But I came up with a pretty decent solution - count eligible adapters the current one can jump to, and then work backwards to get the number of different paths. How did you do it?

 

Link to post
Share on other sites
11 hours ago, Edmachine said:

How did you do it?

Pretty much the same. It's a good example of a dynamic programming problem, but it's well disguised. I started estimating how many different paths I'd have to take to brute-force it, and saw that the number's running away into impractical, but I saw that I would be essentially re-using results of branches, which is when the light bulb clicked. Actually writing the code was pretty fast. Though, by that point I didn't even try for elegant and wrote a series of dumb loops.

 

Also, yeah, this is the first problem where brute-force was not the right answer. Probably still doable, but not at all practical.

 

Edit: Day 11 was messy. Back to nothing fancy algorithmically, but I misunderstood the second part. I thought they wanted to look for first _occupied_ seat in any of the eight directions, rather than just first seat (skipping floor) in these directions. So I ended up with a very sparse room.

Link to post
Share on other sites
On 12/11/2020 at 3:57 AM, K^2 said:

Pretty much the same. It's a good example of a dynamic programming problem, but it's well disguised. I started estimating how many different paths I'd have to take to brute-force it, and saw that the number's running away into impractical, but I saw that I would be essentially re-using results of branches, which is when the light bulb clicked. Actually writing the code was pretty fast. Though, by that point I didn't even try for elegant and wrote a series of dumb loops.

It took me a good while to wrap my head around how to properly count the branches. I knew what I wanted to achieve, but found it hard to put to paper for some reason.

 

On 12/11/2020 at 3:57 AM, K^2 said:

Edit: Day 11 was messy. Back to nothing fancy algorithmically, but I misunderstood the second part. I thought they wanted to look for first _occupied_ seat in any of the eight directions, rather than just first seat (skipping floor) in these directions. So I ended up with a very sparse room.

Well, that's Covid-safe at least. :)

I did a brute-force approach for Day11, so it all takes 700ms to run. Trying to optimize it, but not having much luck with it. I'm caching the neighboring points (Map<Point, List<Point>>), but it does f*ck all for part 1 for some reason. I don't know what else to optimize.

 

Day12 was fun, made very good use of Point and Direction classes from previous years. Looks a bit messy, but oh well. Should probably refactor it.

Link to post
Share on other sites
  • 3 weeks later...
On 1/2/2021 at 5:58 AM, K^2 said:

Got bored of it after day 11. Anything good I should take a look at in the rest of it?

Hah. Day 18 had infix equation parsing with a twist. I got a solution for part 1, but didn't write a proper one that would work for part 2. Day 17 had points in 3 dimensions. Day 15 was fun. Day 14 was rather interesting as well. Had a lot of work on my plate so I put AoC aside (and promptly didn't pick it up again).

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • 2 Users Currently Viewing
    0 members, 0 Anonymous, 2 Guests

×
×
  • Create New...

Important Information

By using GTAForums.com, you agree to our Terms of Use and Privacy Policy.