Search...
FAQs Subscribe
Pie
FAQs
Recent topics Flagged topics Hot topics Best topics
Search...
Search within Programming Diversions Search Coderanch
Advance search Google search
Register / Login
granny thread boost book review grid polymorphism advertise on coderanch
  • 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
advertise on coderanch book review grid thread boost meaningless drivel building better world book
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Liutauras Vilda
  • Ron McLeod
Sheriffs:
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Saloon Keepers:
  • Scott Selikoff
  • Tim Holloway
  • Piet Souris
  • Mikalai Zaikin
  • Frits Walraven
Bartenders:
  • Stephan van Hulst
  • Carey Brown

[SPOILER ALERT] Advent of Code: Day 14 solutions

 
Stephan van Hulst
Bartender
Posts: 15737
368
posted 2 years ago
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
    Send
  • Quote
  • Report post to moderator
It's possible to brute force part 2 by simulating every unit of sand dropped. I will draw a complete picture in my next (minimized) post.

The brute force solution takes about 12 seconds on my machine, but the image it produces clearly hints at a much faster solution that determines the size of the "shade" that each platform casts below it.
 
Stephan van Hulst
Bartender
Posts: 15737
368
posted 2 years ago
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
    Send
  • Quote
  • Report post to moderator
Content minimized. Click to view
 
Mike Simmons
Rancher
Posts: 5100
82
posted 2 years ago
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
    Send
  • Quote
  • Report post to moderator
How do you minimize a post, anyway?

I posted my own part 2 image in the main AoC 2022 thread, before seeing this thread.  If someone wants to minimize it there for me, or delete it, feel free, and I will put it in this thread instead.

I didn't really think of this as "brute force", and I can run parts 1 and 2 combined in 0.3-0.4 sec.  Is it possible you're printing too many intermediate results?  Output along the way can slow things down - especially giant ASCII images.  

Having said that, yes it's true that it seems like an even faster algorithm is possible, for part 2.  I may have to work that out too, for fun.  Good catch.

This was the most fun puzzle so far, for me.  
 
Mike Simmons
Rancher
Posts: 5100
82
posted 2 years ago
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
    Send
  • Quote
  • Report post to moderator
OK, this new method speed up part 2 from about 0.4 sec to just under 0.1 sec:

This uses my previous code to populate the grid based on the input file (including the infinite floor for part 2) - the fill method just fills in the sand and returns the amount sand used. This was actually simpler than the original fill method, as well as faster.  Though the original had the advantage of being usable for part 1 and part 2.  This one only works for part 2.

[Edited to add:] Note that Vector here is not a java.util.Vector (ugh!), but a typealias for a custom class of mine, IntVector2D, that represents an actual vector in the traditional match/science sense, a quantity with two or more dimensions, e.g. x and y.   With some overloaded methods that allow me to add vectors easily with a + operator, things like that.  So "queue += p + it " actually means "queue.addLast(p.plus(it))".  I was previously calling this class Point (or IntPoint2D), but decided Vector is better since that's a more generalized term.  Sometimes it represents a delta between two points  rather than a point, for example.  I feel it's time to reclaim the term vector for its proper math/science usage.
 
Stephan van Hulst
Bartender
Posts: 15737
368
posted 2 years ago
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
    Send
  • Quote
  • Report post to moderator
I believe my performance issues stem from the fact that i made my Cave class immutable, and each time a new unit of sand is added, the entire Cave is copied.
 
Grow your own food... or this tiny ad:
We need your help - Coderanch server fundraiser
https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
reply
reply
    Bookmark Topic Watch Topic
  • New Topic
Boost this thread!
Similar Threads
More...