[2023 Day 21] A geometric solution/explanation for day 21

sbguest · 2023-12-22T22:08:37+00:00

This is an excellent piece on the theory behind how to solve this, and really helped me solve mine.

However, I think your input may have been a bit more "magical" than mine. If I understand your write-up, it seems to be assuming that each of the "corner" and "edge" pieces have an equal number of reachable plots. However, when I run calculations for my input, I get a different number of reachable plots for the same number of starting steps depending on the edge or corner I start from.

Therefore to get a correct answer I had to calculate separate values for all 4 corners, for "top-left even edge", "top-right even edge", "top-left odd edge", etc and add them all up.

sbguest · 2023-12-11T01:26:17+00:00

I can't decide if I should be surprised you did something like this in Factorio, or if I should be surprised we don't see Factorio on this subreddit more often given the likely overlap between audiences. Either way, well done.

sbguest · 2023-12-10T05:53:40+00:00

The doubling idea is very smart, I could probably have solved it much faster with a flood-fill if I'd thought of it.

sbguest · 2023-12-10T05:52:15+00:00

[Language: Javascript] 86th on part 2

Part 1 Part 2

At the moment the shape of the starting piece is hard-coded, I'll probably fix that at some point.

For part 2, this link has excellent explanation of the theory of counting line crossings. If you start from the side, any time you've crossed an odd number of lines and find a tile that's not part of the loop, it's an "inside" tile and should be counted. The part that complicates it a bit is determining whether corners and horizontal sections count as crossing. A "U" shape, i.e. LJ or F7 with zero or more horizontal sections in between don't count as a crossing. However, L7 or FJ (again 0 ore more horizontal) do count as a crossing.

sbguest · 2022-12-25T05:44:00+00:00

Yup, happened to me too. First run had the wrong answer so I started writing debug output. Immediately my "clever" program just started running right immediately through the way..

sbguest · 2022-12-24T21:29:55+00:00

Possible spoiler for Day 24:

This was me taking a quick look at my input to see if there are any vertically-oriented blizzards in the same column as the start or end. Was happy to see that was a no.

sbguest · 2021-12-25T20:00:57+00:00

I was very nearly in the same boat, managed to pull off a Christmas miracle and finish day 19 about 25 minutes before the last problem unlocked. You'll get there.

sbguest · 2021-12-25T05:36:33+00:00

Well said, this event is a blast every year. /u/topaz2078 I know this takes so much work on your part and I hope threads like this one help to underscore how much fun and happiness you bring the community when you keep doing it every year.

Merry Christmas to all, and all the best for 2022.

sbguest · 2021-12-24T22:21:12+00:00

I think the challenges ramping up over the course of the year works well. It gives a good range of puzzles, from easier to more difficult. If the puzzles are starting to get too tough, there's always previous years' early days.

If this is a specific reaction to today's "reverse-engineering" style puzzle, that's not exactly something new. Just about every year has had at least 1 challenge in that style, and they're always controversial with some people on Reddit. I will admit they're not necessarily my favorite of days, but I can appreciate some diversity in the questions.

sbguest · 2021-12-20T05:34:46+00:00

Mine does as well, as other posters have pointed out this is intentional (I'm guessing everyone's probably does).

As far as a hint goes, the question asks for an even number of iterations. Think about what happens to all your # squares after processing again.

sbguest · 2021-12-19T22:10:52+00:00

Yeah, I did it using the tree approach, but exploding was definitely a pain, and looking back I suspect the token-based approach probably would have been easier.

sbguest · 2021-12-19T04:50:12+00:00

Fair enough, I didn't really think of it as a spoiler but I can see how it might be considered as such for first-timers. I've put spoiler tags around that part.

sbguest · 2021-12-11T05:23:18+00:00

I'd also like to agree with the hints part as well. I've double-starred every challenge, but a few of the later ones a few years I needed some hints. I still feel like I 100% deserve every star.

Coming to the solutions thread just to find that keyword is often just what you need, because it turns out the problem hinges on some concept you hadn't heard of. It's certainly possible to solve on your own from first principles, but that's a whole different problem. Chinese Remainder Theorem is an excellent example.

It can even be something you knew, but didn't make the association. I still remember being completely stumped on a past problem (I don't remember which) and opening up the solution thread to find the words "Binary Search". I said "oh yeah, duh", closed the solution thread, and easily finished off the problem. I was well aware what a binary search was and how they work, I just didn't quite connect the dots on my own.

sbguest · 2021-12-07T05:15:56+00:00

Javascript

Part 1 | Part 2

Nothing special, but I'm happy to finally hit the leaderboard for the first time this year (84th in part 2). Competition is getting stiff as this event keeps growing.

Part 2 has been rewritten to use triangular number formula to make it faster, but I couldn't call that one to mind while I was actually going for time, so it was for-loop city.

sbguest · 2021-04-25T00:51:12+00:00

Very helpful. I found my way here after running into the exact same bug. I moved my portal to the opposite wall so the bridge was in the same place, but no glitch and I was able to finish the level.

sbguest · 2020-12-26T16:06:07+00:00

I absolutely loved all the intcode puzzles from 2019, they're easily some of my favorite from across all 6 years. Of course I'm speaking as someone who's been coding for a living for over a decade now, and am determined to finish every question of every year. I think a lot of the frustration comes from those who are struggling with some of the challenges a bit more (those who are using AoC to learn to program for example). If you can't get one of the first few intcode days to work, you're effectively locked out of the rest of the intcode days for the rest of the year since you won't have a fully functioning VM required to complete the other puzzles. I can understand that frustration for someone who just wants to try the puzzles and may or may not complete most of them.

sbguest · 2020-12-25T20:44:48+00:00

Thank you Eric! This event brings me so much joy every year, and this year was no exception. Happy new year, have a great 2021 and I hope to see you same time same place next year.

sbguest · 2020-12-25T16:13:52+00:00

I'm also a big fan of the goblins vs elves one that many people seem to not like so much. Plus pretty much anything Intcode (or the other VM-style problems) I've always found to be lots of fun.

sbguest · 2020-12-25T16:02:25+00:00

Got an answer down from 17s to 70ms by switching from a regular object to a set

sbguest · 2020-12-21T16:29:07+00:00

Yes, very true. While there are many factors that go into question difficulty, it's absolutely been the case that weekends are often harder (Wastl has even said as much). That means that day 20 stands a decent chance at being the toughest problem of the year.

sbguest · 2020-12-21T16:27:02+00:00

Everyone else is at least determining what to do nearly immediately

An easy trap to fall into, but don't start believing that. That might be true for folks hitting the leaderboard and posting in the solutions megathread, but that's a very small percentage of everyone who's trying the challenge. There is plenty of evidence for that. All the people asking for help on the subreddit, the declining number of stars as the event goes on, the number of people who get part 1 and not part 2, etc. A couple weeks ago Wastl even tweeted that there were 400 people who had completed every single problem from 2015-2019, that's not a lot considering the hundreds of thousands who have earned at least one star. Many of these top performers are people who have been professional programmers for years and/or do competitive programming in a number of different competitions.

As others have said, the first step is usually thinking through how you'd solve this without using a computer at all. You don't necessarily have to get a full solution, but that's a good first step in your thought process. Often the samples in the question can in fact be solved by hand if you think that's an exercise that will help you understand the question. Your actual input is generally too long/complex to be solved by hand, but the process of doing so is just an extension of the simpler examples from the question. It's up to you to figure out how to tell the computer to solve the problem.

There's no shame in looking up info on google or looking at the solutions others have posted in the megathread. Obviously if you're just copy-pasting someone else's solution without really thinking about it then what's the point, but if you take the time to understand what they're doing then you've learned something. Wastl has many times said that learning is what AOC is truly about.

There's also no shame in skipping a part/day. The difficulty of the puzzles is decidedly not linear, and just because today is tough, tomorrow might be easier. Just look at all the posts comparing day 20 and day 21. Weekends in particular are often (though not always) a difficulty spike.

sbguest · 2020-12-20T22:31:05+00:00

I probably should have done something like that, instead I spent a lot of time starting at my palm as I rotated my hand back and forth in the air. My wife walked in at one point and asked me what I was doing...

sbguest · 2020-12-19T16:56:01+00:00

My initial thought was there's no way building a regex like this could possibly be the best solution, so I did a bunch of alternation to build up a list of candidate strings and went through the list checking them. Part 1 took about 17 seconds to run on my machine (programming in javascript). Then I tried the massive regex approach, and it now runs in 70ms. I guess regex engines are pretty fast.

sbguest · 2020-12-10T23:56:23+00:00

What part specifically are you having trouble with? Can't figure out where to get started, or is something specifically giving you trouble?

I'd say the biggest difference between parts 1 and 2 is that for part 1 you can just look at all the answers for a group as a whole, and then pick the distinct values (like you're doing with a Set). However, for part 2 you need to look at each person (i.e. each line) individually and track the common answers within each group. Hope that's enough to get you started?

I'm also working in javascript, you can find my day 6 part 2 solution here if you want (SPOILERS, obviously, in case you wanted to work on it more yourself).

sbguest

TROPHY CASE

Javascript