• Light/Dark
  • Ever wanted an RSS feed of all your favorite gaming news sites? Go check out our new Gaming Headlines feed! Read more about it here.
  • We have made minor adjustments to how the search bar works on ResetEra. You can read about the changes here.

Advent of Code 2019...save Santa and Xmas with programming!

Deleted member 10234

User requested account closure
Banned
Oct 27, 2017
2,922
Day 4 was definitely more straightforward than day 3. Finally started pushing my solutions (super basic C++) on Github too, here's day 4.

I'm thinking of also doing my solutions in a language I'm not familiar with. Rust would be an interesting choice.
 
Post Reply

Post Reply

Member
Aug 1, 2018
4,511
Wooooooooooooow, today was way more straight forward than yesterday, haha

NumberThree said:
Day 4 was definitely more straightforward than day 3. Finally started pushing my solutions (super basic C++) on Github too, here's day 4.

I'm thinking of also doing my solutions in a language I'm not familiar with. Rust would be an interesting choice.
Click to expand...
Click to shrink...

Yeah, this is kind of perfect for messing with a language you're unfamiliar with. I have to get proficient with Python by the start of next month, so I've been using these puzzles as a way of helping with that and it's been great so far.
 
AstralTurfWarrior

AstralTurfWarrior

Member
Oct 27, 2017
1,147
Finland
Thanks for the thread. Started doing these yesterday and blasted through day 1 and 2 pretty easily in the evening. The puzzles were pretty fun. Day 3 seems like way harder and had to think about it over night but it's definitely doable.
 
Qronicle

Qronicle

Member
Oct 27, 2017
719
Belgium
It's been a while since I did some non-work related coding, so I hopped onto this :)

Did the first four days today, day 3 was definitely the hardest one for me, although to my surprise my solutions were correct from the first time. (Had the first part of day 4 wrong though, off by 1.) For now I'm just doing these in PHP since I started at my lunchbreak at work, and that was the easiest to get going immediately. Might switch to another language during the weekend.

If anyone's interested, here's my repo: https://github.com/Qronicle/advent-of-code-2019
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,735
Today was slightly simpler than yesterday, yeah. Some people will still be tripped by small details. It happens.

I expect shit to get real by the weekend; in 2018, day 7 was the first tough problem for me. Don't get discouraged if a problem any given day is difficult, we can get through this together. It's not a race; last year I finished around january cause I skipped some problems (my grandma died in december 11th and these damn problems were one of the few things that distracted me).

If you are using this to learn or get more proficient with a language, don't be afraid to switch to whatever you are more confident with in during a tough problem day. Last year I did nim (https://nim-lang.org/) but switched to Java when the going got tough. This year I am doing python cause I want to become better at it to use kivy.

Apparently doing these to practice a language is pretty common. You may watch the presentation the organizer did earlier this year about how he prepares the damn thing

 
Pedro

Pedro

The Fallen
Oct 25, 2017
1,967
Thank you for creating this thread! I found it a couple of days ago and I thought it would be a good idea (and from previous posts, one that came to other people too) to play with languages I don't really know to make these puzzles, but in between finals and the end of the semester I don't have much free time to configure my PC for and learn the syntax and structures of 25 new languages so I'm only starting Day 3 so far.

Hope to get more done during the weekend! https://github.com/pcdateixeira/aoc19 Messed with Go and Julia so far.
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
ElFly said:
I feel it's better than doing a giant matrix

tho the giant matrixes will come
Click to expand...
Click to shrink...

Giant matrix is insanity - I don't even know how long that would take or how inefficient it would be, not to mention the fact that it would only work if your matrix was the right size.

Giant list of points takes half a minute or so to run.

A list of lines, which I've just implemented, is pretty much instant.

Edit: Exact timings for my data - list of points takes 40623ms and list of lines takes 10ms. I'd say that's a worthwhile upgrade. :D
 
Last edited:
Pedro

Pedro

The Fallen
Oct 25, 2017
1,967
iapetus said:
Giant matrix is insanity - I don't even know how long that would take or how inefficient it would be, not to mention the fact that it would only work if your matrix was the right size.

Giant list of points takes half a minute or so to run.

A list of lines, which I've just implemented, is pretty much instant.

Edit: Exact timings for my data - list of points takes 40623ms and list of lines takes 10ms. I'd say that's a worthwhile upgrade. :D
Click to expand...
Click to shrink...

Unlike the first 2 challenges, this one I had to spend time modelling the solution first before coding, and I thought about using a list of lines but kept thinking there must be a better way that I couldn't come up with... but now that I read your post I'll go with that 😅
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
Pedro said:
Unlike the first 2 challenges, this one I had to spend time modelling the solution first before coding, and I thought about using a list of lines but kept thinking there must be a better way that I couldn't come up with... but now that I read your post I'll go with that 😅
Click to expand...
Click to shrink...

I went with diving in, and a list of points seemed a sane start, but the length of the lines in the real data compared to the test data makes it crazily inefficient. Felt like cheating to have a solution taking over half a minute when we're told all problems have a solution that should weigh in under 15s. By sticking to lines, you can keep the number of comparisons way down. My lazy and messy implementation may miss some edge cases (it assumes two lines can only intersect at a single location), but it's good for my input data at least.
 
RiOrius

RiOrius

Member
Oct 27, 2017
6,081
New problem's up. More intcode stuff. Good times. Although I got annoyed at how opcodes 3 and 4 ignore the parameter business and just use immediates.

...man, the leaderboard is brutal. Zero points unless you can get in the top one hundred. Rough. Maybe I'll do better tomorrow...
 

Deleted member 10234

User requested account closure
Banned
Oct 27, 2017
2,922
I have a long weekend coming so I'll probably continue with day 5 onwards then. Looks fun!
iapetus said:
Giant matrix is insanity - I don't even know how long that would take or how inefficient it would be, not to mention the fact that it would only work if your matrix was the right size.

Giant list of points takes half a minute or so to run.

A list of lines, which I've just implemented, is pretty much instant.

Edit: Exact timings for my data - list of points takes 40623ms and list of lines takes 10ms. I'd say that's a worthwhile upgrade. :D
Click to expand...
Click to shrink...
Yeah that's pretty much how I did it. I stored the endpoints of each line, so for the input U5, R4, D3 I'd store (0,0), (0,5), (4,5) and (4,1). Then I looped through the points of the first wire building a line of each individual section, and for each section I similarly looped through the second wire to see if there's an intersection between the two.

Storing just the instructions (like up 5) and keeping track of current location in the loop would have been similarly fast I guess.
 
Cyberclops

Cyberclops

Member
Mar 15, 2019
1,444
Oooh, I just started trying to learn Python because I was bored and work and haven't coded since I graduated. Probably won't get around to doing a lot of it but I'll give it a crack.
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
NumberThree said:
I have a long weekend coming so I'll probably continue with day 5 onwards then. Looks fun!

Yeah that's pretty much how I did it. I stored the endpoints of each line, so for the input U5, R4, D3 I'd store (0,0), (0,5), (4,5) and (4,1). Then I looped through the points of the first wire building a line of each individual section, and for each section I similarly looped through the second wire to see if there's an intersection between the two.

Storing just the instructions (like up 5) and keeping track of current location in the loop would have been similarly fast I guess.
Click to expand...
Click to shrink...

Why deal in points at all?

Two lines intersect if the constant X of the vertical line is between the X values of the horizontal line and vice versa for Y values. The point at which they intersect is defined by the two constant values.

So a reasonable approach might be:
1. Parse your data into Line objects which contain absolute x1, y1, x2, y2 values for the endpoints and a cumulative length to the start of the line.
2. For each line in list 1, iterate through the lines in list 2.
3. If they intersect, calculate the Manhattan distance of the intersection point and add the cumulative length of the two lines together plus the distance from the start of each line to the intersection point. Store these values iff they're smaller than your current minimum values.
4. Once you're done, print out your minimum values.
Mine isn't quite that neatly implemented (currently I just walk the list again to calculate cumulative lengths). You might want to make the intersection code handle the couple of the edge cases this doesn't too - lines running along each other and lines that come together to a single point from opposite directions - but that wasn't required for my input data.
 
Last edited:

Deleted member 10234

User requested account closure
Banned
Oct 27, 2017
2,922
iapetus said:
Why deal in points at all?

Two lines intersect if the constant X of the vertical line is between the X values of the horizontal line and vice versa for Y values. The point at which they intersect is defined by the two constant values.

So a reasonable approach might be:
1. Parse your data into Line objects which contain absolute x1, y1, x2, y2 values for the endpoints and a cumulative length to the start of the line.
2. For each line in list 1, iterate through the lines in list 2.
3. If they intersect, calculate the Manhattan distance of the intersection point and add the cumulative length of the two lines together plus the distance from the start of each line to the intersection point. Store these values iff they're smaller than your current minimum values.
4. Once you're done, print out your minimum values.
Mine isn't quite that neatly implemented (currently I just walk the list again to calculate cumulative lengths). You might want to make the intersection code handle the couple of the edge cases this doesn't too - lines running along each other and lines that come together to a single point from opposite directions - but that wasn't required for my input data.
Click to expand...
Click to shrink...
The only thing I do differently is when parsing the input I store just the points and make them into a line runtime instead of storing lines - a line is just two points anyway. I guess technically my solution is optimized for memory usage and your solution for run speed, though I'm sure after the compiler has worked its magic it won't make much of a difference one way or the other when it comes to C++ at least.

If I store (0,0), (5,0) (5,4) you would store ((0,0), (5,0)), ((5,0), (5,4)). When I search for intersections I take the first two points and make the line ((0,0), (5,0)) and after that it's exactly the same.

And yeah my code automatically discards any pair of lines that aren't a combination of horizontal and vertical, doesn't seem like handling lines of the same orientation was needed.
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
NumberThree said:
The only thing I do differently is when parsing the input I store just the points and make them into a line runtime instead of storing lines - a line is just two points anyway.
Click to expand...
Click to shrink...

Ah, misunderstood you - thought you were walking *all* the points rather than the endpoints. Makes far more sense, then, and yes it's pretty similar in that case.

NumberThree said:
And yeah my code automatically discards any pair of lines that aren't a combination of horizontal and vertical, doesn't seem like handling lines of the same orientation was needed.
Click to expand...
Click to shrink...

Could probably make things slightly more performant by splitting the lines into horizontal and vertical on parsing, and only iterating through the relevant ones. For larger datasets might be worthwhile depending on how you're storing the values...

At least today's a day off from having to think - just a case of updating the VM. Took the opportunity to refactor a few bits to make opcode implementations simpler and clearer and handle parameter modes simply - I'm guessing from what people are saying that we'll be coming back to this one again, so better to leave it in a tidy state for future extension...
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,735
RiOrius said:
New problem's up. More intcode stuff. Good times. Although I got annoyed at how opcodes 3 and 4 ignore the parameter business and just use immediates.

...man, the leaderboard is brutal. Zero points unless you can get in the top one hundred. Rough. Maybe I'll do better tomorrow...
Click to expand...
Click to shrink...

All the top scores are for people dedicated to competitive programming. The video I posted upthread talks about it.
 

Interested Observer

Banned
Oct 27, 2017
3,654
I got stuck on day 3 :(

What's the best way to represent a grid in Python? I was trying a list of lists, and wrote code that accurately placed the first wire from the example on the grid, but it didn't work for the second wire. I was having trouble with the indexes for any subsequent section of wire after the first one, couldn't come up with a universal solution. Oh well.
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,735
Interested Observer said:
I got stuck on day 3 :(

What's the best way to represent a grid in Python? I was trying a list of lists, and wrote code that accurately placed the first wire from the example on the grid, but it didn't work for the second wire. I was having trouble with the indexes for any subsequent section of wire after the first one, couldn't come up with a universal solution. Oh well.
Click to expand...
Click to shrink...

I don't recommend doing a grid for this one; if you really want to, lists of lists is the way, OR using the "numpy" module's matrixes.
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
Interested Observer said:
What's the best way to represent a grid in Python? I was trying a list of lists, and wrote code that accurately placed the first wire from the example on the grid, but it didn't work for the second wire. I was having trouble with the indexes for any subsequent section of wire after the first one, couldn't come up with a universal solution. Oh well.
Click to expand...
Click to shrink...

If you're looking for some partly spoilery advice on one decent way of implementing this, check the first spoiler under "Why deal in points at all?" in my post a few up. There's a second spoiler inside it which you should avoid unless you want a more full description of how to implement this.

The least-spoilerific version of the advice would be this:

You don't need to work out every point on any line - if you look at the input data and the length of its lines you'll see that would be quite a task. Focus on the lines themselves instead.
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
Scoring is, as always, regionally biased. I'd have to be up ridiculously early in the morning to have a shot at scoring any points - as it is I've been doing most of the tasks after work in the evenings, which means I've lost 18 hours before I even start...
 
Satanic Saint

Satanic Saint

Member
Oct 27, 2017
140
iapetus said:
Scoring is, as always, regionally biased. I'd have to be up ridiculously early in the morning to have a shot at scoring any points - as it is I've been doing most of the tasks after work in the evenings, which means I've lost 18 hours before I even start...
Click to expand...
Click to shrink...

Yeah no point in even trying for the leaderboard. My goal is to just complete it since it's my first time doing this. I'm guessing it gets harder down the line.
 

Interested Observer

Banned
Oct 27, 2017
3,654
ElFly said:
I don't recommend doing a grid for this one; if you really want to, lists of lists is the way, OR using the "numpy" module's matrixes.
Click to expand...
Click to shrink...
iapetus said:
If you're looking for some partly spoilery advice on one decent way of implementing this, check the first spoiler under "Why deal in points at all?" in my post a few up. There's a second spoiler inside it which you should avoid unless you want a more full description of how to implement this.

The least-spoilerific version of the advice would be this:

You don't need to work out every point on any line - if you look at the input data and the length of its lines you'll see that would be quite a task. Focus on the lines themselves instead.
Click to expand...
Click to shrink...

Ah thanks, just needed that tiny hint. I'll have another go.
 
the_bromo_tachi

the_bromo_tachi

The Fallen
Oct 25, 2017
1,367
Japan
This is cute. I've only done day one in Swift. Definitely room for performance improvement but wanted to finish these within a few minutes since I'll be watching a movie soon.
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,735
Day 5 was easy for me, although I got stuck a couple of times by fucking up the indexes of my instructions.

Only had to use one of the test programs to realize the error of my ways.
 
Qronicle

Qronicle

Member
Oct 27, 2017
719
Belgium
Day 5: The refactoring has begun :)

My new IntCode class: https://github.com/Qronicle/advent-of-code-2019/blob/master/common/IntCode.php

I guess I just did the obvious thing of having classes for each of the operations, extending from one abstract Operation class that defines the number of arguments, calculates the next address and whether the application should halt. I didn't really tackle the output yet, but I guess that will come back into play later.

So if I understand correctly, the score is based on the time it took you to complete the question (starting from when it became available), and not whether you had many wrong answers or whatever?
 
Satanic Saint

Satanic Saint

Member
Oct 27, 2017
140
Qronicle said:
So if I understand correctly, the score is based on the time it took you to complete the question (starting from when it became available), and not whether you had many wrong answers or whatever?
Click to expand...
Click to shrink...

Yup. It's pointless to even try for the leaderboard unless you are in the proper timezone.

Just completed Day 4 and Day 5. Day 4 was as easy as Day 1 for me. So far Day 3 was the one I spent most time at.
 
Izkda

Izkda

Member
Oct 25, 2017
124
I had completely forgotten about this, gonna try to catch up on the weekend.
 
KKRT

KKRT

Member
Oct 27, 2017
1,544
Replying just to get into private leaderboard, though i'm quite behind :)
 
Post Reply

Post Reply

Member
Aug 1, 2018
4,511
Just finished Day 5... I actually really enjoyed today's puzzle and today was the first day that I really felt comfortable using Python, haha

I'm glad I decided to go object-oriented on day 2
 
iapetus

iapetus

Member
Oct 26, 2017
3,078
Randdalf

Randdalf

Member
Oct 28, 2017
4,167
iapetus said:
Isn't your part two crazily overengineered?

Just make a list of planets from YOU and SAN up to the center point. Work from YOU towards the center - stop at the first value that's in the SAN list and add the indices of that item in the two lists together (and subtract two).
Click to expand...
Click to shrink...

It may be: but I knew I already had a shortest path algorithm implemented, so I copied that instead of thinking about it 😆
 
OP
OP
ElFly

ElFly

Member
Oct 27, 2017
2,735
mmm

day 6 prompt's is interesting

e: did it. I was scared it was gonna be like the steps requirements calculation of day 7 last year, but nope

edit: the spoilered answer is my solution too
 
Last edited:
Qronicle

Qronicle

Member
Oct 27, 2017
719
Belgium
Also finished day 6 earlier today, but just realized I have a bug in my "find first different orbiting object" code, since I do it based on a long string value with all nodes, comparing each character, but I should compare the whole object code of course.
Oh well, solution was correct ¯\_(ツ)_/¯
 
NetMapel

NetMapel

Member
Oct 25, 2017
3,412
I have just begun working on this and finished day 2. Is there any more elegant solution to the second part of day 2 other than just brute force loop through two lists? I kept wanting to do something smarter like adjusting both noun and verb individually up and down one depending on the result till it hit the solution... but that feels like a lot of effort 🙈
 
JeTmAn

JeTmAn

Banned
Oct 25, 2017
3,825
NetMapel said:
I have just begun working on this and finished day 2. Is there any more elegant solution to the second part of day 2 other than just brute force loop through two lists? I kept wanting to do something smarter like adjusting both noun and verb individually up and down one depending on the result till it hit the solution... but that feels like a lot of effort 🙈
Click to expand...
Click to shrink...

Haven't done it yet but brute force will be my solution. If the noun and verb limits were higher I'd try working my way backwards from the ending number.
 
ChrisR

ChrisR

Member
Oct 26, 2017
6,798
Day #1 was fun to do drunk as heck in my hotel room, can't wait to try the rest of this stuff
 
RiOrius

RiOrius

Member
Oct 27, 2017
6,081
NetMapel said:
I have just begun working on this and finished day 2. Is there any more elegant solution to the second part of day 2 other than just brute force loop through two lists? I kept wanting to do something smarter like adjusting both noun and verb individually up and down one depending on the result till it hit the solution... but that feels like a lot of effort 🙈
Click to expand...
Click to shrink...
I did brute force, but now that I think about it, presumably you could just do a handful of data points, and use that to try to algebra out a formula for the end result. Maybe.

Alternatively you could try to have your computer understand algebra and derive the formula itself. That seems hard, but could be fun.

I'd say do it brute force for now, and maybe come back to it to try something fancy if you feel like it.
 
You must log in or register to reply here.