Win a copy of Mastering Corda: Blockchain for Java Developers this week in the Cloud/Virtualization forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Advent of Code 2020

 
Saloon Keeper
Posts: 283
42
Firefox Browser MySQL Database Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:JJ, I see yesterday's second part gave you some pause. Need any pointers?



I don't know what I'm missing, but I'm struggling to get my brain around the problem . I don't know how much maths or algorithm knowledge is required
 
Marshal
Posts: 7933
548
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

Tim Cooke wrote:The puzzles are definitely easier this year.


I found this problem most annoying so far.

Partially because got lost in parentheses, secondly, because didn't write unit tests and made a bunch of copy/paste mistakes across my conditionals which were hard to spot on my side.

Anyway, just found last bug in a second part. Interestingly, but test data was so small, so it worked with all the bugs present, just not with an actual input.

Both parts solved.

Tomorrow as a first thing will prepare Racket's unit testing framework and I don't care it will add extra time at first.
 
Bartender
Posts: 4272
160
  • 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 hate that my brain has such problems dealing with the range [-ūĚúč, ūĚúč] of the angle ūĚúÉ that atan2(y,x) returns, even though the math is exactly the same it would be when the polar angle ūĚúÉ of my coordinates was expressed in the range [0, 2ūĚúč]. (...)


Easier is to remember that the Matrix of a 90 degree left rotation aroud the origin is

( 0  -1)
( 1   0)


You just need a few translations too.
 
Saloon Keeper
Posts: 12608
273
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Partially because got lost in parentheses


I spent a day learning racket to solve the problem with the nested bags. I stopped at some point because I got really angry with the language and because my stress level at work was rising. I still intend to continue so I can show you how I would solve that problem, but Racket has reinforced my belief that LISP-like languages are only academically interesting, and suck in practice.

What editor are you using? I've found that DrRacket makes matching parentheses very easy.
 
Stephan van Hulst
Saloon Keeper
Posts: 12608
273
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:Easier is to remember that the Matrix of a 90 degree left rotation aroud the origin is

...

You just need a few translations too.


My first solution would have been a simple switch statement that flips the signs and x/y coordinates, but I like your approach of using a rotation matrix. Very elegant. I wanted to practice my trig though, so I opted for the solution that uses polar coordinates.
 
Sheriff
Posts: 4961
318
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 blaming you Liutauras for my current inability to get day 13 part 2 solved...
 
Liutauras Vilda
Marshal
Posts: 7933
548
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

Tim Cooke wrote:I'm blaming you Liutauras for my current inability to get day 13 part 2 solved...


I am in a musseum with kid. But on the way I was reading problem's 2nd part, didnt find it complicated. Well, will see in an evening.

Emoloyed racket structs (objects) for the first time, so much improved experience.

Stephan, will reply later.
 
Tim Cooke
Sheriff
Posts: 4961
318
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
Getting the examples to work are no problem, but getting the actual input to solve in a reasonable amount of time is going to need a different approach altogether. I'm pretty sure there's a mathematical solution but I haven't figured it out yet.
 
Liutauras Vilda
Marshal
Posts: 7933
548
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 see where you coming from, perhaps wont sleep much tonight.
 
Stephan van Hulst
Saloon Keeper
Posts: 12608
273
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I didn't like today's puzzle. After spending half the evening on the second part I figured out what theorem to use, but I haven't applied it yet. Maybe tomorrow.

I'm not a fan of the puzzles where you have to dig into number theory. I'm not a math buff.
 
Stephan van Hulst
Saloon Keeper
Posts: 12608
273
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Today's puzzle was a breeze.
 
Liutauras Vilda
Marshal
Posts: 7933
548
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 dropped the ball with yesterday's part 2. Couldn't get crack on it.

If let's say increasing buses traveled minutes just by 1 all the time, able to sole all given test inputs in a reasonable time except last one (where answer should be nine 0's). Last one actually am able to solve by increasing travel minutes by the number as the very first ID in the list is.

However, for an actual input that's not enough, so I presume need to progress travel minutes number further at runtime, just couldn't figure out the formulae.
 
Stephan van Hulst
Saloon Keeper
Posts: 12608
273
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's a hint:

You need to figure out timestamp t, where:

  • t % buslines[0]   ==  0,
  • t % buslines[1]   == -1,
  • ...
  • t % buslines[n-1] == -n-1,


  • In congruence modulo notation, for example input 7,13,x,x,59,x,31,19:

    Now that you have represented the problem as a system of congruences, you can solve for t using the Chinese Remainder Theorem.
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Thanks Stephan. That looks complicated.

    I've been thinking for a while actually and came up with another idea, did some testing, and I think that should work.

    Let's say there are buses: [17,x,13,19]

    So the algorithm would work as such:
    1. First find the solution for 2 numbers subset, i.e. [17,x,13] (by iterating minutes by 1)
    1.1. Find at which minute further solution happens for the same subset above (they start repeating at exact increase of minutes starting from 2nd solution. Let's assume every 100 minutes)

    2. Increase subset size to: [17,x,13,19]
    2.1 We found that every 100 minutes there is a required solution for subset [17,x,13]
    2.2 To find the solution with further number [17,x,13,19], every time increase minutes by 100 plus check the gap solution(s), in this case gap is just 1, so 100 and 101. If there were gap of two ([17,x,13,x,19], then would need to check 100, 101 and 102

    3. If solution not found, increase minutes to 200 (since occurs every 100 minutes) and check gap solution(s), 200 and 201 in this case.

    4. Increase minutes to 300 and check 300 and 301.

    If there were bigger subset, repeat steps by adding numbers one by one plus increasing minutes for solutions you know already how often they occur for previous subset.


    Might be a bit tiring implementation.


    I'll read more Stephan about theory you mentioned. I'm not familiar with it at the moment.
     
    Piet Souris
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Didn't dare to look here, since I could not think of anything useful for day 13, part 2. Just found something called "Chinese remainder theorem", that seems the thing to use. I see that Stephan mentioned this already.

    Now looking at the example in Wikipedia, thinking about that the ri and si are not unique there. For instance, the example is about the (relative) primes 3, 4, 5, and they give -13 * 3 + 2 * 20, but why not 7 * 3 - 1 * 20? And how that would affect the minimum solution? Well, some study to do. Agree with Stephan: this makes this exercise dreadful.

    Had a look at the first part of day 14 too. Looks like horrible bitjuggling. Not my favorite. But first day 13.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12608
    273
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Piet Souris wrote:Now looking at the example in Wikipedia, thinking about that the ri and si are not unique there.


    Correct. The Bézout coefficients x and y of the identity ax + by = gcd(a,b) do not have to be unique values. It doesn't matter what values you pick for x and y, as long as they satisfy Bézout's identity.

    For instance, the example is about the (relative) primes 3, 4, 5, and they give -13 * 3 + 2 * 20, but why not 7 * 3 - 1 * 20? And how that would affect the minimum solution?


    It won't affect anything. You use whatever coefficients satisfy the identity to calculate a congruence relation for the product N of the moduli n[1], n[2], ... , n[k]. If you make sure to calculate x mod N in the end, it will always result in the minimal solution.
     
    Piet Souris
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thanks, it really was a doddle.

    Now some catchup to do...
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Likewise, thanks to Stephan, no way I could have figured out formulae/theory to use.

    I didn't do an actual heavy lifting though, I was successfull in finding Racket's standard math/number-theory library with an exact solve-chinese function which does that, and I was too tired, went to sleep 4am as I still wanted to clear day 14th backlog - enjoyed it that one.

    Not sure yet whether I'll attempt today a today's (15th) problem, might be tomorrow. But I might still do if that's not too involved.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12608
    273
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Day 15 is an easy one. You should be able to complete it fairly quickly.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12608
    273
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    For anyone interested, here's my solution to day 13.
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Today's second part was... well, nasty. I solved it 50/50, with racket and text editor. Didn't bother to write the rest of the code once I understood what's the matter. Input in general was horrible to parse, so I used text editor to pre-process it to most extent.

    Cleared all the backlog. Except that I couldn't take credit for what Stephan hinted yesterday (I think that was before yesterday, buses problem).
     
    Tim Cooke
    Sheriff
    Posts: 4961
    318
    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 feel like part 2 today should be straight forward but my brain just can't do it. Approaching burn out....
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    If you ever want hint, just let know, I felt like you few times already. There is only one word to be "hinted" and that would work I think.
     
    Tim Cooke
    Sheriff
    Posts: 4961
    318
    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
    Ok hit me
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Sudoku
    Content minimized. Click to view
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Minimized previous post on purpose. Whoever wants can expand.
     
    Tim Cooke
    Sheriff
    Posts: 4961
    318
    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
    Thanks. However I've never written a solver for that so still dunno
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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

    Tim Cooke wrote:Thanks. However I've never written a solver for that so still dunno


    I did in the past, but not this time, that‚Äôs why I said I used text editor after I printed out ‚Äúsomething‚ÄĚ with the little function I prepared. Remember how you solve it by hand in a newspaper - essentially same is here.

     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Perhaps you are just a bit too tired. Other day probably you wont find it confusing.
     
    Piet Souris
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    For part 2, I have a TicketField with name and two ranges. Problem is that when ordering all these TFs according to the inputfile, I get doubles in my ordered list, meaning more than one TF meets all the numbers in a line, although that should be unique. Breaking my head to find the bug.
     
    Master Rancher
    Posts: 3754
    48
    • Likes 2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Think of it this way - if you find any rule that only matches one column, or any column that only matches one rule, then you know those two match up, and the remaining problem becomes simpler...
     
    Tim Cooke
    Sheriff
    Posts: 4961
    318
    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
    Thank you Mike and Liutauras, your hints were just enough to jolt my brain into gear.

    Now..... on to today's puzzle.
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    Yup, didn't want to elaborate too much yesterday, but Sudoku's algorithm for primitive problems is exactly that.

    Basically for each square you create a set with numbers [1..9], and those starting point (pre-filled) numbers are singleton sets just with one number in it.

    Then repeatedly do the following:
    1.   Find a location containing a singleton set (a set containing just one number).
    1.1 For every other set in the same row, the same column, or the same box (3x3), remove that number (if present).

    2.   Find a number in a set that does not occur in any other set in the same row or column or box.
    2.1 Reduce that set to a singleton containing that one number.

    3.  Go back to step 1 and repeat.

    And it is solved when every set is a singleton, or when no more numbers can be removed from any set.

    I yesterday went through all ranges and tickets and collected (and printed) positions which all tickets satisfy a particular range.

    For instance:

    departure-location - all ticket's 1st position satisfy that range, all ticket's 2nd position satisfy that range.. etc.
    for each range did the same...

    And then the starting point was, that one range was satisfied only by a singular position among all tickets. And that was where I recognized Sudoku problem, but instead of implementing algorithm which I knew before, done about 7 years ago, interestingly, but with Racket too , except that this time I just dumped output to text editor and solved it by hand in 1 minute.


    Didn't look to today's probem yet, actually just sneaked lightly, I remember something similar from 2017 where we had to do certain amount of iterations applying certain rules to the patterns and that way after N amount of iterations there appeared some Text which was essentially the puzzles answer.

    I remember it was involved problem, probably will look in an evening.
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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

    Earlier, I wrote:Didn't look to today's probem yet, actually just sneaked lightly, I remember something similar from 2017 where we had to do certain amount of iterations applying certain rules to the patterns and that way after N amount of iterations there appeared some Text which was essentially the puzzles answer.


    I didn't read carefully, just looked at visuals and assumed... that's not that at all!

    Yet again Conway's game of life, this time just 3D version... to begin with
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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 see today's going to be an annoying one again. Not my cup of tea these type of exercises.
     
    Piet Souris
    Bartender
    Posts: 4272
    160
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Finally solved day 16, part 2. After the hints from Liutauras and Mike about my wrong assumpton that the nearbyticket-columns matched the ticket fields 1-1, and after repairing the mistake of sending the sum instead of the product, my answer was finally accepted.

    Day 17 part 1 is a 3D GoL, but I must confess of getting a little fed up with these exercises full of nasty user traps...
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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 must confess of getting a little fed up with these exercises full of nasty user traps...


    Yeah. Similar here..

    Really wasn't up for writing stack based expressions parser today (Tim, don't tell you wrote one actually?), so pulled out heavy artillery. Booted up Prolog (used in uni) and overrode operators precedences

    For part 1 bumped up + to a level of *

    and for part 2 swapped precedences of + and *

    And then just loaded *.pl file with expressions to evaluate, like:
     
    Liutauras Vilda
    Marshal
    Posts: 7933
    548
    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
    In general probably need to stop for me too since many of you seem to be pulled off by other things as I see backlog grows.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic