• 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 2018

 
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I lost my code to day 8. I use the Git staging area to temporarily save code that I don't want to commit yet. I deleted my day 8 code because of reasons, but apparently the Git plugin for NetBeans automatically adds changes to the staging area, so it deleted the day 8 code I had saved there as well. I will definitely have to find out how to suppress this automatic staging.

Day 9 looks tedious to me as well, but I think I'll start by writing a circular buffer class.
 
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
Oh my. Day 9 Part 1 was straight forward enough, but part 2 is a real test to your algorithm efficiency. I believe a data structure rethink is in order here.
 
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
My initial day 9 part 1 solution used an array, but with insertions and removals mid list it was not efficient. Using this solution part 1 completed in around 0.6 seconds which was ok. Then came part 2. Just increasing the marble count by 100 with my original algorithm really highlighted the problem. After a half an hour I aborted the run and went back to the drawing board. I replaced the array with a python deque (double ended queue), jigged the algorithm to suit it, and viola! 2.5 seconds to the part 2 solution.

If you're wondering how I did mid list inserts and deletions from a queue, well it turns out that a python deque has a rotate function that allows you to quickly rotate the list so that a popleft or appendleft achieves the desired action.
 
Marshal
Posts: 8856
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
I'm just now going from shopping mall, so well behind you guys. Hopefully tonight will have a chance to sit down and crack day 8 first.  Sounds like day 9 offers even more challenge.
 
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 10 was a fun one. It's a pleasant change of tact when you have to use your eyes to solve it rather than getting the computer to do it. The trick was having the computer present you visibly decipherable information but not too much or too little of it. Part 2 was a doddle.
 
Liutauras Vilda
Marshal
Posts: 8856
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
Trying to catch up.

Day 8 Part 1 done (if anyone still remember it), indeed was shouting for a recursive (which I like a lot) solution, except that initial approach ended up with StackOverflowException So had to do plan B - opt-in for tail call optimized solution.

Scala has @tailrec annotation which gives you a compile error if your function isn't tail recursion. So it is nice, I like it.

I must say it is damn too complicated to follow who hasn't spent a good amount of time on it, most likely there are simpler approaches, but I just ended up somewhere deep down in recursion mind with this one, so even coffee got cold.

 
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
Recursion and using variables declared outside of the recursive method Liutauras?

I managed to get part 1 done by simply processing the input sequence from left to right also using recursion to collect all the meta values. It was quite tidy even. But then along came part 2 and blew my design out the water and I had to start again
 
Liutauras Vilda
Marshal
Posts: 8856
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

Tim Cooke wrote:Recursion and using variables declared outside of the recursive method Liutauras?


Which variables? Oh c'mon , just file (list) and toProcessChildrenOfLevel (map) , more optimism, please! instead of dealing with 4 parameters, need to cope only with 2. I kept them as fields of mutable data structures   so really to pass them as parameters didn't make sense that moment, except that doesn't make sense to have them as mutable and fields in the first place. Ok, let's call it a lazy (very) tackle of a problem, which at any given moment in time can (i'm sure it will) stab you to the back  
 
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
Tee hee Bear successfully poked.

I can say nothing, some of my code is truly a crime against the profession.
 
Liutauras Vilda
Marshal
Posts: 8856
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

Tim Cooke wrote:I managed to get part 1 done by simply processing the input sequence from left to right also using recursion to collect all the meta values. It was quite tidy even.


Just had a look What?!? Recursion + Loop(s)? What is the feel of going down the root cheap way  
 
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
Ha Ha! You got me
 
Stephan van Hulst
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
All I had to do to solve part 2 of yesterday's puzzle was to swap out the ArrayList my data structure was based on for a LinkedList.

The problem was that my data structure has two constructors and I only swapped it out in one of them. I assumed I was using a LinkedList and couldn't understand why it was taking so long. I even fired up my profiler only to find out that the NetBeans profiler doesn't work with Java 9+. Eventually I let it run the entire night and this morning I found out that after running for 10(!) hours, it had given me the incorrect answer because I used int instead of long.

After thinking about it for a bit today, I couldn't imagine that the list was so slow, and that's when I found out my mistake. *Actually* using the LinkedList reduced the runtime from 10 hours to a bit over a second.

I really liked that one, because it's the first real example I've seen of a case where a LinkedList greatly outperforms an ArrayList.

Today's puzzle was also really fun. I just let it run until the bounding rectangle of the points has a height and width that fits on my screen and then I visually inspect the message. Sadly it doesn't work well with the testing framework I wrote for AoC, unless I extended my solution with some sort of optical character recognition.
 
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
Oh man that's really frustrating Stephan. I liked yesterday's puzzle too as a demonstration that your choice of data structure can really really really make a difference to your application performance. I couldn't find a linked list in Python so ended up with a little hack using a queue that had very fast head insertion and deletion operations.

For today's puzzle I wrote a function that would generate and print the grid of dots and hashes but I made the mistake of having it print out every single iteration and it took so long generating the first grid (approx 100000 by 100000 item grid) that I quickly abandoned that before any output was generated at all. I took a similar approach to you and only printed anything out when the difference in y values was 10 or less. A guess that turned out to be spot on as it only printed one image and was the one I wanted.
 
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I really liked that one, because it's the first real example I've seen of a case where a LinkedList greatly outperforms an ArrayList.



Really?  That's a little surprising - I would guess that may just mean that the list lengths aren't usually big enough to notice how big the difference can be.  But as an example, my first solution to day 5 part 2 used a LinkedList, and part 2 runs in 0.25 seconds.  Replacing the LinkedList with an ArrayList causes the code to run in 3.2 seconds.  If you make the input string longer, it gets much worse, as it's fundamentally an O(N^2 ) operation to delete from the ArrayList anywhere but the end.

To be clear, I wasn't using the Lists as stacks, but rather, removing from the list as I went.  I eventually refactored to use a stack instead, which didn't seem to change performance substantially from the original 0.25 seconds - though other changes have gotten it down to about 0.18 seconds.  Hard to tell how much the stack itself contributed really.

Unfortunately I'm way behind since then on the other challenges.  Don't you people have anything else you need to be doing? ;)  I look forward to catching up over time.  Thanks for posting about it and bringing it to my attention.
 
Stephan van Hulst
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:it's fundamentally an O(N^2 ) operation to delete from the ArrayList anywhere but the end.


Removing from an ArrayList is an O(n) operation. Removing from a LinkedList is an O(1) operation, but ONLY if you already have a pointer to the node you want to remove. That's why LinkedList is rarely useful. Most of the time an ArrayList outperforms a LinkedList even when removing from the middle of the list, because moving half the elements in an array may be faster than searching for the node to remove in a chain of links.

OperationPerformance
arrayList.remove(int)O(n)
linkedList.remove(int)O(n)
arrayListIterator.remove()O(n)
linkedListIterator.remove()O(1)
 
Mike Simmons
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry, I misspoke - I meant that doing it kN times, proportionate to the length, becomes O(N^2) overall.  Each individual remove in an ArrayList is indeed O(N), unless it's at the end.

Of course this can also be slightly improved by using an ArrayDeque, O(1) at both ends, but that still doesn't solve the problem in the middle, which is what was needed for day 5.

And obviously, to use LinkedList effectively here you have to use its ListIterator, not any indexed method.  That's precisely why it worked so much better than ArrayList here.
 
Greenhorn
Posts: 13
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tim Cooke wrote:Day 10 was a fun one. It's a pleasant change of tact when you have to use your eyes to solve it rather than getting the computer to do it. The trick was having the computer present you visibly decipherable information but not too much or too little of it. Part 2 was a doddle.



My solution watches for convergence across the Y axis.  Then when it began to diverge again step back 1 second and draw the result.  I ended up with exactly 1 result printed out.  My part 2 answer was available as part of the output from part 1 as I was keeping track of the seconds in my $DEBUG output.  So, I just made it part of the STDOUT.  Only thing I forgot was to step back the seconds counter by 1 to correlate with the result I was printing.  So, my first submission was 1 second too high.
 
Michael Mraz
Greenhorn
Posts: 13
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Originally I had thought to check the distance from each point to the others and keep moving until they were all within 1 of another point.  But, that ended up being overkill.
 
Stephan van Hulst
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm pleased with how my score caught up after missing the first few days. I've managed to temporarily overtake Tim, but that will only last until he's finished today.
 
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
I think my Day 11 Part 2 needs some revision as it's been running for quite some time now.....
 
Tim Cooke
Sheriff
Posts: 5555
326
IntelliJ IDE Python Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Part 2 was a bit of an odd one. I still could not get my program to finish in any reasonable time but I got lucky. I had it print out any new highest power level as it found them and after about 5 seconds the output dried up but the program kept running. As it turned out the most recent output was the puzzle solution. I totally got lucky.
 
Mike Simmons
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Tim, I had the same experience for day 11 part 2.  I let version 1 keep running while I worked on some speed enhancements for part 2... but then it eventually completed before I was done with the revisions.  I lost motivation to continue optimizing after that since I'm behind on other problems.

But I don't think it's luck, exactly, that the answer is found early on.  More like regression to mean - as the rectangles get bigger and bigger, they become more "average" in a sense, taking in more of a mix of positive and negative values.  Still, it's at least theoretically possible a max could occur later, so we need to complete the search I guess.
 
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 12 Part 1, yup no problem. Part 2, dang I got nothing that doesn't take a bunch of time to run. I do have a hunch though, so I'll be back
 
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
My hunch was that the plant state would repeat so didn't need to compute all the generations, but no
 
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
Yes, done. My hunch was right but not exactly as I first imagined it.
 
Liutauras Vilda
Marshal
Posts: 8856
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
Slowly but catching up. The current outstanding balance is only 3.5 unsolved days. Tonight planning to be left with 2. That means tomorrow morning will be 3 again. Hm... Kind of slow.
 
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
I've dropped a day behind so today I have 4 outstanding puzzles, this is it, the beginning of my inevitable AoC demise.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hopelessly behind, but I have less time to spend that I thought. The mrs doesn't allow me to sit hours behind the laptop.

I stayed away from this topic, to not watch solutions that may have been given.

So, this goes without having seen possible solutions.

For 9B I was unable to come up with a function that could predict the situation after N rounds. I therefore used an ArrayList of maximum length LinkedLists,  with an optimal setting of 2500 max length.
and on my I5 computer it took arpound 7 minutes.

10 was funny, I used a Bufferedimage, saved as png, and viewed in a Windows Photo program.

But I am stuck with 12B. I have two ways to calculate the sum: a formula that determines which pots contain flowers after N generations, and then a simple Stream.sum,
and a method that determines the sum directly, with a straight line, as a function of N. Up to 500, I determined all generations, in a Game Of Life way, and checked my two functions with it. All correct.
But when I apply the two functions to 50B, my answer is too low, according to the website. No idea how to proceed. Anyone a suggestion?

 
Stephan van Hulst
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you remembering to use long instead of int, Piet?
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, I have, longs all over the place.

There must be some error in my code that doesn't show up in the first 20 generations. But I do get simple patters after about 90 generations, so that seems somehow ok. I'm giving up on this one.

I finished day 13, busy now with day 16. A nice exercise, I got the example ok, but my initial attempt failed once more. Getting very tired of all this testing and bug finding. Takes ages.
 
Stephan van Hulst
Saloon Keeper
Posts: 15488
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I believe for the particular puzzle input, you only need to perform 185 iterations. After that, you can calculate the answer by hand.

This week I'll be making an attempt at catching up, I've been preoccupied with clearing out my house in Enschede, which I have to deliver tomorrow.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, I hope you will thoroughly enjoy your new home and city(?).

Meanwhle, I need some advice. I'm busy with 16A, using a HashMap<String, TriConsumer<...>> to juggle with the registers. Now, my answer was replied with: too low, and that my answer is equal to the answer of some other input (again the suggestion of cheating).

Well, I've checked my 16 instructions, manually, for three examples, all oke. I've checked my input, got all 782 input cases, and the processing is also fine as far as I could check, So my question is: what else can I do? I'm in for any suggestion.
 
Mike Simmons
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Piet - regarding Day 12, I had a similar problem, kept getting "too small" for my answer.  Finally discovered that for "fifty billion" I had typed 50000000 rather than 50000000000.  Not to imply that anyone *else* would ever be so foolish... but don't forget to recheck the little things that seem obvious.

The thing about day 12 is, I was actually pretty proud of the nice efficient implementation that I had, which will calculate each new generation with a minimum of computation.  Except... it turned out to be no help at all in the actual problem. :| . Classic example of premature optimization.

As for the rest, I'm way behind.  I expect to be coming back to these for some time though - they're pretty fun.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Mike,

Java allows you to write 50_000_000_000, to prevent all possible misery  ;) So, that is not my problem with day 12.

Anyway, I just managed to finish day 16. I knew I was a dumbo, but not that I was tht much dumbo. In the test cases, I forgot to re-initialize the registers. Unfortunately, it only showed up at testcase 7, very hard to find.
I really don't know how all these scoreboard leaders manage to come up with their answers so quickly. Hat off for these people!

Hoping that day 14 is a little easier...
 
Mike Simmons
Master Rancher
Posts: 4796
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:Java allows you to write 50_000_000_000, to prevent all possible misery  ;



Well,  that still wouldn't prevent me from mixing up "million" and "billion" in my head, which I believe was the issue here.  But it's a good point nonetheless
 
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
Copy and Paste is your friend for that one Mike.

Playing catch up here, got day 13 and 14 done today. Day 15 looks like a zinger and might be a little while before I'm ready to code anything at all.
 
Piet Souris
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 14 as well. Pretty easy, but I had two problems:

first of all, I thought that after reaching the end of the recipes list, a player would then count backwards, instead of jumping to the start of the array, making it hard to follow the example given...
And secondly, the description of part two was unclear to me. Took a while to understand.
 
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
I also found day 14 relatively straight forward, but even so it always takes me a few reads through the instructions to understand it properly.

Day 15 is officially a zinger
 
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
The wheels have come off...
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic