• 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:
  • Tim Cooke
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Rob Spoor
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
  • Scott Selikoff
Bartenders:
  • Piet Souris
  • Jj Roberts
  • fred rosenberger

Advent of Code 2017 - Any interest for a CodeRanch leaderboard?

 
Saloon Keeper
Posts: 13981
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The three parameter version of the reduce() method probably seems unclear because you're using the Point class to represent a translation. I guess this is fine, but then an instance of Point should instead be taken as an element of a two dimensional vector space. The combiner operation then simply becomes vector addition (the same operation you used as the accumulator in your second code snippet). Since vector addition is associative, you can use a parallel stream to perform the reduction concurrently.

My solution is similar, except I used separate types to represent locations and translations. Your code with my types would have looked like this:

The combine() function would have treated a Location like a vector relative to the origin anyway, so I guess in this context the terms Point, Location and Vector are interchangeable.
 
Stephan van Hulst
Saloon Keeper
Posts: 13981
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How are you coming along Tim?
 
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • 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'm actually a little bit disappointed that most of the problems aren't prohibitively expensive to crack if your solution isn't within some time complexity class.


A bit happier now?

Wasn't major, but I had to do some tweaks to the algorithm which initially came to my mind.

Not sure how you guys solved it, but I had a hash table where I recorded layers, ranges and scanners positions.
So for the second part I just cached the latest state of setup for the next picosecond tick with some packet delay.
 
Stephan van Hulst
Saloon Keeper
Posts: 13981
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I calculate the position of a scanner after x picoseconds in constant time. No need to record the positions, only the ranges per layer.

The complete algorithm for the second part operates in O(m²), where m is the number of layers. I try every layer (linear time) to see if the scanner is at the top (constant time). If the packet is blocked, I increase the delay and try again.

https://github.com/Nibsi/Advent-of-Code/blob/master/src/main/java/nl/nibsi/aoc/y17/d13/Firewall.java
 
Stephan van Hulst
Saloon Keeper
Posts: 13981
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I guess your complete solution runs in amortized O(m²+n) time, Liutauras, where m is the number of layers and n is the maximum range. The downside is that your space complexity is O(m*n).
 
Marshal
Posts: 5362
325
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'm still playing catch up Stephan. I'm on Day 10 currently. The two guys from my team at work who are at the top of the leaderboard are almost certainly in competition with eachother, however I don't think each has admitted it to the other yet. There has been some >1am (Chicago time) efforts put in I know for a fact.

I'll get there.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm missing something in Day 14 part 1.

Knot hashing works for me otherwise day 10 wouldn't have passed. So combining my input with -0 ...127, hashing them, converting to binary and counting 1's. But it seems my answer is not being accepted. Most likely missing something, but not sure what. Will go with my team for dinner tonight, and later tonight will sit down to look for what I overlooked.

How goes for you this puzzle?
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Haven't solved yet, but I'm sure i found a bug. And that is why global variables are dangerous.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 14 part 1 done. However, part 2 still not. Will take a stab at it with Kotlin probably as having one idea in mind where Kotlin going to be more comfortable to work with than Racket in this case.

Apart from that, we have Day 15 released already, so it seems we are all having a bit of backlog. I'm planning to clear it today, hopefully...
 
Stephan van Hulst
Saloon Keeper
Posts: 13981
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Really busy at the office the last few days. I'll probably do days 14, 15 and 16 tomorrow.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Up-to-date.

For Day 14 part 2 I decided to go with Kotlin, to be honest did't use much Kotlin specific features, just wanted to pick up some OO language for this task. Puzzle may look more complicated than really is at the beginning (well, according to stats, least people solved that part as of now). Not sure how others, but the approach I came up with I found some similarities with a well known problem, but will keep this for myself for now. As with most of my approaches I employed recursion.

Day 15 part 1. I'd say the wording in the description could be done better. So I fell into the trap at first.
Day 15 part 2. Was trivial.
 
Bartender
Posts: 4981
186
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I might be mistaken, but I get the impression that we slowly but surely go into regions where brute force isn't going to be of any use.
I used brute force at 17-2, but after two hours of calculation the code was busy with 4.3M, and had to go to 50M. That would have taken weeks this way. So I had to think of something more clever, and now the whole exercise takes less than 1 second.

Wonder where this is going to.....
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:I might be mistaken, but I get the impression that we slowly but surely go into regions where brute force isn't going to be of any use.


At least something similar to that.

Yeah. Knowing how long my first part took to run, let's say around 1 second, and knowing how many times more such operations need to be performed, it was easy enough to understand that it may take ages to run second part running it in the same way as the first part. However, knowing what most likely is the bottle neck, was the key in my case. It was a growing size of the list. Since lists are immutable in Racket, everytime to insert a value is expensive, and becomes especially expensive when that list grows bigger and bigger. So rather than populating a jumbo size list, I just mimic doing that and actually carrying its provisional size (in order to define next insertion index) and recording only the numbers of possible interest, that way I get around 4-5s of execution time. Not as good as Piet's though, but acceptable.
 
Tim Cooke
Marshal
Posts: 5362
325
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'm so far behind, way back on Day 10 And now I have some technical review work for a publisher which means I have even less spare time for this. Sad times Well I'm the only one from my team in the office next week so may get to place catch up Just don't tell my boss... although he's on the leaderboard too so I'm defo going to get busted.

Rivalling Liutauras for top of the Advent of Excuses board now  
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Stuck on Day 18 part 2. For sure have a bug somewhere, but with my implementation with several recursion calls it became quite difficult to debug, will try again later today. How you find this one?
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Solved Day 18 part 2.

Well, contraversial feelings about the puzzle. Don't know if it was that difficult or not, but it took fair amount of time to come up with solution which gave the right answer. I think story got repeated, meaning exercise went in some chaotic way, or the approach I chose wasn't obvious, so it helped me to lose control and confidence about what I was doing. However, had a chance to play with Dr.Racket (Racket IDE) debugger, which is few light years back from Eclipse's or Intellij IDEA's.

Now we have Day 19 which I didn't want to start unless I finish Day 18. Yet again reading instructions don't have any idea at the moment how I'm going to solve it. Never did nor see any similar problem. But let's take some break and see later tonight what's there.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Up-to-date.

Didn't manage with Kotlin to populate array of arrays of strings, so went with Java. And that is the downside of new languages, they don't have decent documentation and examples.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 21 puzzle is annoying one, that is why only one guy solved it up till now.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Day 21 puzzle is annoying one, that is why only one guy solved it up till now.


Solved Day 21 both parts. There were in particular one thing very annoying, to assemble back an image out of the enhanced individual squares. Finally, most of the time took me writting test cases, but that proved to be the way to go rather than blindly write a code and expect it to work in the way one would expect it to work.

I still have backlog though, Day 22 and Today (Day 23). Might will be able to solve them tonight, but I do have very limited amount of time these days, and the one I have, I have no control of. Tomorrow early morning I'm travelling, so might will have to finish them up some time later - if the adventofcode site won't block this ability after the Day 25.
 
Liutauras Vilda
Marshal
Posts: 8296
592
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A bit stuck on Day 23 part 2. It is indeed more challenging than the other days. Putted laptop aside for this and debugging it on a piece of paper now.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic