• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Advent of Code 2019

 
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As is becoming tradition here at CodeRanch, it's that time of year again for Advent of Code 2019. A bunch of us had a go back in 2018 and 2017 and I'm up for it again.

adventofcode.com wrote:Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.
You don't need a computer science background to participate - just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.


Anyone else having a go?
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yep, thanks for reminding me!

Are we using this leaderboard again?
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yea go for it.
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If anyone wants to join in that leaderboard the code is 60807-1a2fc49d
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm really enjoying the puzzles so far. I don't find them particularly difficult yet, but today's second part had a couple of gotchas that made me try some wrong answers.
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Part 2 today (day 3) also made me sit and think for a while too. My initial solution to part 1 did not translate well to part 2 and needed a bit of a refactor which is actually a lot like real life software development where you have to adapt your code to accommodate new requirements.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 3 was the most fun so far.  I had a slightly over-engineered solution to part 1 with a subtle off-by-one error that was hard to catch because I obfuscated it... but once I fixed that, the solution also worked pretty well for part 2 as well with minor adaption.  @Tim, thanks for reminding us about Advent.
 
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh, I miss all that so much...!
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 4 was relatively straight forward I thought.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just finished day 3. Thought to be clever by eliminating duplicates with a TreeSet with manhattan distance comparator... took me some time to find out why my answer wasn't correct. And had an off-by-two error in 3B.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So I analyzed the IntCode given for day 5. I'm not sure if it's helpful to anyone, but it was fun to do.

Content minimized. Click to view
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I really like the graphics that the creator uses for the calendars. I just noticed that the highlighted dots for day 2 and day 4 probably represent Earth and Venus, going by the flavor text for the puzzles of those days. It appears that we'll be arriving at Mercury tomorrow, after which we'll be shot towards the outer planets. I'm guessing more stuff will become visible as the puzzles are solved, such as the asteroid belt and planets like Jupiter and Saturn.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 7 was tough! I wonder how many people will complete it compared to the later puzzles.
 
Liutauras Vilda
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Guys, would you mind to share repositories where you store the code?

I think some members possibly would be interested to have a look at solutions.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sure, I can probably push my solutions to my existing repository tomorrow.

I might need to clean up some of them though, in my haste I wrote stuff I'm not proud of.  
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you doing the puzzles as well Liutauras? Why don't you join Tim's leaderboard?
 
Liutauras Vilda
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Are you doing the puzzles as well Liutauras? Why don't you join Tim's leaderboard?


Unfortunately, but no. Have other commitments related to academia, so couldn't balance relatively well and be competitive in both areas, hence decided to skip this year.

But I'm watching this thread as it is interesting for me. So far get an impression that puzzles get slightly harder over the recent years.
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tim Cooke wrote:Part 2 today (day 3) also made me sit and think for a while too. My initial solution to part 1 did not translate well to part 2 and needed a bit of a refactor which is actually a lot like real life software development where you have to adapt your code to accommodate new requirements.


Just started on these problems. From what you’re saying, I’m guessing you used streams to read in the input for day 1 and found that approach wouldn’t work for the day 2 input. That’s what happened with me at least. Edit: misread what you wrote (day 3, not day 2). Well, anyway...

I have a workshop to facilitate this week, a training to do the week after that, and a book review to submit so I doubt I’ll have time to spare for this but will try.

Good luck to everyone doing it though.
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Junilu, I'm delighted you're having a go this year. You are very welcome to join my leaderboard if you want to (code in a previous post).

Day 7 part 2 is a zinger. It took me a few days to get part 1 done and now my head is truly pickled.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm going to minimize posts that contain possible spoilers. My next one will be about day 7 part 2.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have a Computer class that is responsible for the fetch-decode-execute cycle. It has a Decoder that converts an opcode into an Instruction an it has a LongSupplier and a LongConsumer that act as input and output.

The trick to the second part of day 7 is to create 5 computers and 5 queues. Now use queues[0]::add for the output of computers['A'], and queues[0]::remove for the input of computers['B']. Keep doing this until you've used queues[4]::add for the output of computers['E'] and queues[4]::remove as the input of computers['A'].

Encapsulate this entire setup in a Pipeline and initialize the pipeline with a setting: 5 long values that each go into a different queue. After each queue has a phase value from the setting, also add the value 0L to queues[0].

Instead of running each computer until it halts, step through its instructions until it has executed an output instruction. Then move to the next computer. When all computers have reached a halt instruction, the pipeline is finished.

Create, initialize and run a pipeline for each possible phase setting. Then you can determine which setting caused its pipeline to output the highest result.
Content minimized. Click to view
 
Liutauras Vilda
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Likes 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Advent of Code 2019: Tim Cooke wrote:Day 7 part 2 is a zinger. It took me a few days..



Advent of Code 2017: Tim Cooke wrote:My brain is having a lot of bother with Day 7 Part 2.



You seem to be consistent.

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm so confused about the format here... Am I replying to just the last message or the whole thread??

Anyways - @Tim, I wanted to let you know that I started Advent of Code at my current company and got like 20% of the tech team involved so far! I switched from Java to ruby and it's definitely been a lot more challenging haha
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to CodeRanch, Sree!

You are replying to the whole thread. Your message just gets appended to it. A good convention is to quote a small part of a previous message if you're responding to a message that isn't the last one.

Are you perchance the "Sree P" from Tim's leaderboard? My hat's off to you, I don't know how you do it so quick.
 
Sree Vi
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks!

Are you perchance the "Sree P" from Tim's leaderboard?


Yup, I am that Sree

I hope I make it to the global leaderboard this year
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sree, I'm so so pleased to see you here! I went to email you last week but realised I only had your CME email address which is obviously long retired.

Great job getting some of your new team signed up. Sten is running a bounty again this year and he has 70 people signed up to his leaderboard! No small achievement. Like yourself I'm no longer eligible so will have to settle for those sweet sweet internet points
 
Sree Vi
Greenhorn
Posts: 8
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Same! I could've sworn I saved an email somewhere about passing the torch on the CME leaderboard

Wow that's a huge turnout - about the size of my engineering team now!

Hey, internet points are great - Eric Wastl, the creator of AOC retweeted a post for a meetup I used to co-organize in Chicago
https://twitter.com/ChicagoPython/status/1202777235536666624?s=20
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:You seem to be consistent.


I think they call this public shaming...  

Sree are you still in Chicago? Have you been waiting up to 1am for these every day? Do let us know if you make it on the global leaderboard.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmm I don't really know how I'm going to approach Day 12 part 2. Maybe I should first make a plot of the total energy of the system for each step, and see if I can find a pattern that will help me calculate the solution somehow?
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wow. Suddenly part 2 clicked and the solution was relatively simple. Part 1 was probably set up to deliberately put you on the wrong track.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Who's still in?

Today was the hardest so far for me. I'm not a big fan of puzzles where the solution works only for a class of inputs and not for all inputs that are valid according to the problem description.

I started out with a general solution for the first part, which worked quite well for all example inputs.

Then I had to rewrite my solution several times as I worked on the second part and using more and more tricks such as dynamic programming and caching. I even ran a profiler to see where the bottlenecks in the program were.

In the end I decided to start all over and analyze the input string itself. I solved it with a simple piece of code, but it doesn't work fast enough for all inputs, and I don't think it is possible to write such a solution.

Tomorrow is likely another IntCode puzzle. I enjoy those.
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Currently stalled on Day 7 Part 2. My actual job got a real monopoly on my brain cells but hopefully back on it again shortly.

Stephan you're doing a solid job on the leaderboard, are you aiming to knock Malcolm and Sree off the top spots?
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No. I'm aiming at maintaining my third spot. If I stay on the ball, I think I can maybe beat Andrew Jones.

I don't think it's even possible to beat Sree and Malcolm anymore, even if I finish every remaining puzzle before them, unless they start missing solutions. I lost a lot of points on the first two days, because I had a late start. Even so, the two of them are more than my match.

I currently have holiday, with no real plans before Christmas, so I think third place is feasible.

The puzzles are released at 6 in the morning where I live, which is early, but not so early that I can't fit it in my schedule. As a matter of fact, it allowed me to get some solutions in before Sree, because I could do them before I started my day job.
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good to see Andrew keeping you on your toes. He and I did our masters degree together nearly 15 years ago. Now I'm thinking about it he was the one who encouraged me to explore linux and I'm very thankful that he did as it opened up a whole new world of computing for me.
 
Sree Vi
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sree are you still in Chicago? Have you been waiting up to 1am for these every day? Do let us know if you make it on the global leaderboard.



Nope! I moved to California a few months ago - so I get to start the problems at 9pm. I'm totally stumped on yesterday's part 2. I got as far as figuring out the paths but I dont know how to compress them.

You can see who makes the global leaderboard by "Ordering" on "Global Score". The closest I got was 227 on yesterdays
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sree Vi wrote:I'm totally stumped on yesterday's part 2. I got as far as figuring out the paths but I dont know how to compress them.


It turns out you can do this by hand once you've generated a picture of the scaffolding. First create a string that represents the simple path across the scaffolding, i.e. go straight across intersections instead of making corners at intersections. Replace each combination of a rotation and a forward move with a token. For instance, a path like:
becomes:

Do this for the entire path. Now the trick is to realize that because of the memory limitations, this entire token string must be cut up in at most 10 substrings, each substring consisting of no more than 4 or 5 tokens (depending on the number of forward moves that the tokens encode that are greater than or equal to 10, because those tokens use up an extra output character).

Here is what my solution looked like:

As you can see, the longest substring takes no more than 4 tokens, there are no more than 10 substrings, and there are exactly 3 distinct substrings: A = VWWX, B = XWX and C = YXZ.
 
Sree Vi
Greenhorn
Posts: 8
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Wow, thanks! I didnt realize I could go straight through the intersections - turns out my paths were wrong and my compression algorithm was correct
 
Liutauras Vilda
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Tim, do you know when AoC give some clues whether event will happen or no? I couldn't see any news on their site.

I guess asking, how did you figure in past years that it is going to be?
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic