• 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
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Advent of Code 2022

 
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sure, I must've been executed with 10_000 without removing division by 3 when tried multiple things. Indeed running long now that I did.

Ok, trying further.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:if monkey 0 processes value 200, and should send it to monkey 1, that has a dividableBy 13, then you do not need to send that 200, but 200 % 13 = 5



Tim Cooke wrote:...idea does work for the very next monkey but not for other monkeys after that. Might there be something else you can do to the worry level that will work for all monkey tests?



Mike Simmons wrote:Tim C's hints are exactly on target for this one.


Ok guys, finally, after reading it and re-reading (multiple times) those hints and inspecting input data, eventually got it. Unfortunately, but hints were key. Perhaps I should have just left this one out unresolved.
 
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But why?  It's still a fun, worthwhile exercise - hints or no.

Based on past years, expect this sort of solution becomes more common in the later problems, usually part 2.  That is, not this specific trick necessarily.  But the idea that the thing you're asked to calculate just takes too much time, so is there a way to get the answer you actually need, without actually calculating all the details that you think you need?  Stephen's comment about looking for patterns is another technique that comes up - e.g. if you can determine that a computation repeats itself after n iterations, and you need some much larger number of iterations, then you can skip past actually doing most of those iterations, with a little careful thought.  I don't think that technique actually helps here (though it might) - but it will probably come up in one or more future problems.

For my part, I'm annoyed that the beautiful code I wrote last night for day 13 was marred by one simple failure to notice that indices were supposed to start at 1.  I was too tired to see that before I went to bed.  Oh well.  All good now.
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Mike, how come didn't you submit a solution for day 10?
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was busy over the weekend, and to catch up, I went in reverse, more or less.  Still coming.  It didn't look difficult, but you all had already solved it, so I figured I should go elsewhere first.
 
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Falling a bit behind here and I'm still picking at day 13. I don't think it's particularly difficult but have been short on time to think about it properly and form a complete picture in my mind about it. Today, day 14, doesn't look too bad either (which is often the preamble to some of the hardest of hard problems).
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I drew a picture of what my cave looks like at the end of part 1:
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Very cool
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Catching up slowly. Finished day 12. Also used BFS, had a chance to revise my old uni slides.
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I used A* search for day 12, not because it was necessary but because I expect to use it for later puzzles.

Had I known ahead of time what was needed for part 2, I would have used Dijkstra as well.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ah, I was wondering where that 3-min run time came from.  That makes sense.

Re: Day 14: Nice job, Stephan!  I had posted my own picture for part 2, but later saw you have already done that in another thread, so now I've removed it.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:But why?  It's still a fun, worthwhile exercise - hints or no.


Sorry I missed your message. I hadn't enough sleep in the past days, so got a bit annoyed when stuck. All good now, it is fun

 
Bartender
Posts: 5584
213
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Spent two days finding out why my day-11 solution didn't work, and when I finally found out, shame on me.
Well, the idea was ok, but I should have used a much larger value for the modulo base.

Just finished day 14. I too made a png of the result of part 2. Now see if I have time to do day 15 as well.
 
Piet Souris
Bartender
Posts: 5584
213
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A pity that that picture was removed. Here is another picture of day 14 part 2, resembles the pyramid of Cheops.
uitdraaidag14.png
[Thumbnail for uitdraaidag14.png]
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 15 is nasty. My part A takes two seconds, so it is impossible to do that 4M times for part B. Therefor I am thinking of a way to reduce the points that are outside the distance of two sensors. If I think of a way, and take the collection of all these points, then exactly one of them must ly outside the range of all sensors, as is given. But tomorrow is another day.
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I haven't implemented it yet, but this afternoon I realized how I'm going to solve part 2. (Next post)
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If there is only one position that is unscanned, it must necessarily straddle the scanning range of at least one sensor.

Therefore, calculate the positions that are all just outside the range of each sensor, and then filter those positions based on whether they are in range of another sensor.
Content minimized. Click to view
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just thought of a way myself, that looks promising. It is just a matter of having one or more rectangles, and subtracting from these another rectangle.

I will read your solution after I'm done.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just finished Day 13.

Part 1 was a bit iffy.

Initially decided to take the input data and with text editor to replace [ to ( and ] to ) and get rid off commas, so could parse input directly into racket list of lists data structure. But that didn't get me much farther than having all tests pass for test input and for real input had to create a heavily recursive method which found too complicated to handle - so ditched that approach in the middle.

Then considered using couple of stacks to load pairs and that way get something out of it - avoided that idea before started implementing it.

And then thought will try simply with char integer values comparison. The only problem was value 10 in the real input, which caused some trouble, but then I converted it to ':' character and its value is 58, which is greater than '9's is.

And the Part 2 was the most effortless part 2 so far. Simply just used sort function with my created custom comparator in-order? which I used in part 1. So the code to sort got just like:


Will start looking into Day 14.
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm still picking at day 13. The problem I have is lack of time to form a proper attack strategy rather than wild stabs in the dark. As they say "hope" is not a design pattern.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I hadn't heard the "hope" quote before.  I like it

Just solved day 15 part 2, w00t!  Both parts combined run in 3 seconds.  I kind of overthought this one - I was confident I knew what part 2 was going to ask before I actually read it, and I spent time thinking of clever approaches to this problem (while I couldn't actually write code).  But the actual part 2 was somewhat different than my expectation, and had a simpler solution - if you think about where to look.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 14 done! The price for that - burnt pizza while I was reading instructions.

My solution isn't the fastest, but not terrible either, finishes both parts in 2-3 seconds, varying per run, but Racket in general is slower given that most data types/structures are immutable.

I was using hash table to store rocks coordinates and the sand in rest

Day 15 next. Probably just not today as it is 2am already.
 
Piet Souris
Bartender
Posts: 5584
213
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just finished part 2 of day 15. I've had some very bad ideas in my life, but the idea of rotating the plane for this exercise easily topped them all. Then I tried to apply a transform, where (1, 0) is transferred to (1, 1) and (0, 1) to (-1, 1). We get nice rectangles instead of diamonds, and distances are dubbeled, but the mess I got into couldn't possibly be what this exercise is about.

Then I thought of using Segments. If you have an Y-value, and determine all the segments on the corresponding line that cannot be reached by any sensor, and have a method to map all these segments to a minimal set of segments, then it turned out to be a pretty fast method. I used brute-force, and if there was an Y such that I got two segments, then bingo. It ran in just over 4 seconds on my pc.

Today, exercise 16. Just gave it a read, hmmm, for part A the hardest problem looks like getting the timing oke. But that is just first impression.
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Right, I've some beef with the example description of day 13.

It says

If exactly one value is an integer, convert the integer to a list which contains that integer as its only value, then retry the comparison. For example, if comparing [0,0,0] and 2, convert the right value to [2] (a list containing 2); the result is then found by instead comparing [0,0,0] and [2].


ok, fine so far. So what about comparing two lists

If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.


yea no problem with that, and looking specifically at the statement I've put in bold.

Then the example input goes on to say this

== Pair 2 ==
- Compare [[1],[2,3,4]] vs [[1],4]
 - Compare [1] vs [1]
   - Compare 1 vs 1
 - Compare [2,3,4] vs 4
   - Mixed types; convert right to [4] and retry comparison
   - Compare [2,3,4] vs [4]
     - Compare 2 vs 4
       - Left side is smaller, so inputs are in the right order


Whoa whoa whoa whoa now. Comparing left [2,3,4] to right [4] is in the right order? What about " If the right list runs out of items first, the inputs are not in the right order"?

I can only derive from this that the criteria about the left or right list running out of items first only applies to the very top level list?

It's ambiguous to me. Am I reading it wrong?
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comparing [2, 3, 4] with 4 means comparing [2, 3, 4] to [4], so we start with comparing 2 and 4. Since 2 <  4, the list is ordered. The length-issue comes into play when comparing, say, [2, 3, 4] with 2
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh I see. Once a comparison is made that results in ordered or not ordered then the whole comparison ends. That makes a lot more sense.

I thought you had to compare everything as undetermined or ordered for the overall result to be ordered, and only if you encountered a not ordered result could you exit early.

Thank you Piet.
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You're welcome!
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have now formed a plan and I hope I can translate it into code. Wish me luck.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring 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 Cooke wrote:...and I hope..


As they say, "Hope" is not a design pattern
 
Piet Souris
Bartender
Posts: 5584
213
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And beware of Brecht in his threepennyopera:

Mach nur einen Plan
Und sei ein grosses Licht
Mach dann noch einen zweiten Plan
Gehn tun sie beide nicht!

 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Tim - I agree with you that the text explanation seems at odds with the example.  At best, the text is unclear whether you compare individual elements first, or lengths.  At worst, it sounds like the length comparison is first.  Which is contradicted in the example, yes.  But it you treat the example as the way to resolve ambiguity in the text, then you are good.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Piet - congratulations!  Yeah, I was planning to use rotated coordinates to resolve intersections rectangles.  Back when I thought I would have to count all the excluded points.  But decided I could skip that for the question they actually asked.
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ha ha, very good Liutauras. Yes you got me

As it turns out my idea was flawed. I had made a fundamental mistake in that I foolishly thought I could convert the input into an array using String.split(",") but of course that makes no distinction between commas in the sublists so everything after that is destined to fail.

I think my next strategy will be to take the inputs a character at a time instead of trying to parse them as a whole.

Sigh.......

Ok, here we go.
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 13, I got there eventually. Oh boy what a mess, but it works thank goodness.

I took a great deal of satisfaction in wrapping my part 1 solution in a Comparator to sort the packets in part 2. That was a nice little exercise.
 
Tim Cooke
Marshal
Posts: 5817
374
IntelliJ IDE Python TypeScript Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 14 no bother.

Day 15 doesn't look too bad either, but not tonight.
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just finished day 18 (I skipped 16 and 17 for the time being). A very nice one, but very tedious as well! Part 1 is easy, but part 2 made me develop a tedious method, that worked fine with the example, but failed for real, to my big misery. While being awake for some time last night, I thought of another, very fine, way that I just implemented. But again: tedious and it took me a long time to fix what looked like an infinite loop.

All in all, these exercises tend to take more and more time.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Had just a short break and the backlog got doubled.

Day 15 part 1 done, but part 2 I see already it will be a troublesome.
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you need help with part 2, the hint I gave earlier in this topic turned out to work well for me, and it even outperformed the solution I had for part 1.
 
Piet Souris
Bartender
Posts: 5584
213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Never thought I'd ever use a Map<String, Supplier<Integer>>.
 
Liutauras Vilda
Sheriff
Posts: 8988
652
Mac OS X Spring 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:If you need help with part 2, the hint I gave earlier in this topic turned out to work well for me, and it even outperformed the solution I had for part 1.


Thanks Stephan, I'm not looking yet, after I was thinking about this for a day, I got one idea which I'm going to try.

My current thinking is, that that coordinate must be around, or in different words, within Manhattan distance of 1 of some given sensors covered area's rhombus corner. Otherwise, I can't imagine how such only one coordinate could exist, it would be more.

So my approach would be the following, I have 28 sensors which make 28 rhombus (covered areas), those 28 * 4 (corners) will be 112 corners coordinates. Then I need to find those 112 coordinates neighbouring coordinates excluding those which are inside rhombus of respective sensor, so that would make at most 112 * 5 = 560 coordinates if I'm not mistaken. And then, I'd need to check out of those 560, which are outside of sensors reach area.

Will report back if that worked.
 
Time is the best teacher, but unfortunately, it kills all of its students - Robin Williams. tiny ad:
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic