• 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
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Indeed. My line count were 20.5 on average so far, this time got it in under 10. I'm looking for the ways to half it.

Surprisingly easy day, got a bad feeling about tomorrow. Back in 2017 we were solving Day 7 (especially part 2, remember?) for quite some time each some of us.

-----
This might refresh your memories:

Tim C. - "My brain is having a lot of bother with Day 7 Part 2."

Stephan - "More difficult than expected."

Liutauras - "A bit stuck, created mess, now deleted everything and going to pool for a swim to relax and will start over."

and then...
Piet - "No particular problems, exercise 7 was more tedious than difficult."  <--
 
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
It seems JetBrains sponsoring AoC, and of course encouraging to solve puzzles with their language, and so you can even win prizes by joining to their leaderboard and I presume topping up the board https://blog.jetbrains.com/kotlin/2022/11/advent-of-code-2022-in-kotlin/

Next year I'm doing it in Kotlin! Not for the prize reason of course.
 
Sheriff
Posts: 17734
302
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just saw that again earlier today, too. Should have remembered they had a template solution but I'm kind of happy with the template I came up with on my own. Been refining it since day 1 and (re)learning things about Kotlin in the process. Hopefully by Christmas, I'll have it in really good shape to use as a template for next year's AoC -- I'll still do it in Kotlin. Maybe I'll have enough mastery of the language to actually compete for a prize.
 
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
Well, a language which loves Advent of Code is worth being loved itself.

To be honest I very good remember the very beginning of Kotlin and with Kotlin. When I was having a module in uni back in 2016 called "Programming Language Paradigms", teacher was using multiple languages to introduce to multiple paradigms, those languages were: Racket, Kotlin and Prolog. This was the first time I encountered those languages (Racket, Kotlin).

Racket of course is much older language, while Kotlin's first official stable release 1.0 was back in 2016 (exactly the same year I had a module), and so our professor sent us to Kotlin Night conference held in London, I posted it here => https://coderanch.com/t/672791/languages/Kotlin-Night-recordings (of course you can see me in those recordings   ) where couple of guys from JetBrains and other known guys in our field i.e. Nat Pryce and Duncan McGregor who were first to apply it in industry in production systems. They were championing and telling us about this cool new language.

Interesting to see how much it evolved and traction it got actually in a fairly short period of time.

I started being itchy myself and am considering to start with it sooner rather than later in AoC.
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Day 7 was fun. I love puzzles where you have to parse and execute commands (although day 7 was more about analyzing commands than executing them).
 
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
Hmm.... again not difficult, but with a snag. I created a Map<String, File>, in order to be able to look up a file or directory given the name. That worked perfectly in the given test, but failed for the real thing. I thought all names were unique... be warned.
 
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

Liutauras Vilda wrote:(...) and then...
Piet - "No particular problems, exercise 7 was more tedious than difficult."  <--


Just looked it up. I have absolutely no clue as to what I was doing there.
 
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:That worked perfectly in the given test, but failed for the real thing.


Exactly the same thing happened to me 7 minutes ago. Trying to make sense out of it what's the problem.
 
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 didn't realize the input would have duplicate file names, but I didn't run into any issues because I started building a tree structure right away, with a separate map of children per directory node.
 
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
Not duplicate filenames, but dirs (you could argue they are filenames).

i.e.

/
- dir a
    - dir b (size 10)  <-- duplicate name
- dir c
   - dir b (size 20) <-- duplicate name

So my initial solution also suffered from this issue, as I putted all dir names into a hash table, and of course duplicated dir names overrode previously added dirs under the same name just with different sizes.

So I changed my technique and this time built composite keys.

Shout out to Piet who did warn about the duplicate dirs pitfall. Probably would have taken + 1 or 2 hours extra to figure myself if at all.

I finally got both parts solved. After almost giving up.

Going to clean up the code, but man, it's bad.
 
Marshal
Posts: 5800
371
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'm running nearly a day behind already as I've just finished day 7. I went straight into building a tree data structure for the directories and files, it's messy but functional.

Haven't even read day 8 yet, but here goes.
 
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
The next (minimized) post contains a very small spoiler for day 8.
 
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
Whatever you think part 2 is going to be based on part 1, it's not. Don't waste time writing a generalized solution for part 1.
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
What do you mean by 'generalized solution'?
 
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 just mean that if you have a quick and dirty solution that is fast enough to give you the correct answer for part 1, then don't bother cleaning it up or optimizing it just for the sake of reusing that bit of code for part 2. The outward visibility of the trees is no longer used in the second part.
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
day 9: the nicest one sofar.

Two hints: take your time for part 1, you need it in part 2. And pay attention to the warning given in part 2!
 
Tim Cooke
Marshal
Posts: 5800
371
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
Agreed, day 9 was a really nice puzzle to solve. I enjoyed it very much. And yes, the part 2 "gotcha" was a nice twist that took me a second to realise what it was.
 
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

Tim Cooke wrote:I'm running nearly a day behind


Same here. Just finished yesterday's. Will have to look today's later in the day, after football maybe. But I saw something about the dog and its tail not knowing where it is going.
 
Tim Cooke
Marshal
Posts: 5800
371
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 10 also quite a nice puzzle.

Kotlin is getting a lot of love from you guys, and a bunch of others whose opinions I value in my local community, so I'm beginning to think I should take a look at it.
 
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
Nice problem indeed. Took me a few readings to understand part B. The biggest problem is getting your indices synchronized.

I do notice that the pace of the spoilers has decreased, the last days.
 
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 9 here only. Part 2.

Even though I didn't like it, but Part 1 got solved.

Part 2 story is different. So for both test inputs smaller and larger I get the correct output. And verified that my snake in each phase ends up correctly.

On real input however, part 2 still doesn't work, never finishes in fact. Have no idea where the bug is. Not sure even if I'm interpreting that warning correctly.

 
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 haven't solved it by the time I wake up tomorrow, I'll run my own code against the input in your repository and give you a couple of snapshots of what the field is supposed to look like after the first couple of instructions. Maybe from that you can debug the issue.
 
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
Thanks Stephan.

Driving home from the kid's party came to my mind that I might be missing to cover one more case, just got back home and coded it in - it worked!

I worked my part2 solution on top of part1, so I broke my part1 of course, but I have it in git history, so I may recover it later. Overall, I over-complicated this puzzle, I should be able to reduce rules to fewer.

Have to work on the backlog of yesterday's problem (Day 10), and then depending on how it goes, I may also do today's.

 
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 11: it seems the easy days are over.

Part 1 is tedious, probably better to do the input manually. Part 2 is hard. Although I know how to do it, I am facing a bug that I have not been able to track yet.
 
Tim Cooke
Marshal
Posts: 5800
371
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 11 part 2 is currently causing my some frustration. First it was type problems, now I have time problems.
 
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 10 here.

Will start looking to Day 11. From you I see it is not fun there.
 
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 11 part 1 done. I actually liked it.

Got stuck for a while though due to misread instruction:
"rounded down to the nearest integer" misread as "rounded to the nearest integer".

And they of course just wait you to slip on these type of things, because quite a few rounds outcomes were correct, so had to track each step and do some calculations by hand to understand what has happened.

Will do part 2 tomorrow as it is almost 3am here, will fall asleep by thinking about part 2 though.
 
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
Ok, by reading Day 11 part 2 and thinking for a while, I got one idea which potentially could reduce an amount of items inspected during the rounds.

So I think the idea is, that when monkey's turn finished, i.e. monkey-0, then monkey-1 starts inspecting items, so basically on the item worry level need to come up with the number to divide, so the item would get thrown to one of previous monkeys, so the iteration cycles would reduce for the upcoming monkeys.

Am I on the right thinking track?
 
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

Liutauras Vilda wrote:So I think the idea is, that when monkey's turn finished, i.e. monkey-0, then monkey-1 starts inspecting items, so basically on the item worry level need to come up with the number to divide, so the item would get thrown to one of previous monkeys, so the iteration cycles would reduce for the upcoming monkeys.


Actually not really. Because looking at the example data inspection times after 1st round, the outcome doesn't suggest this above idea.
 
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 have yet to start on part 2 of day 11, but my first impulse is to see if there is a pattern in the sequence of monkeys that a single item is passed between.

If there is a repeating pattern, you no longer need to keep track of the worry level.
 
Tim Cooke
Marshal
Posts: 5800
371
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
The problem with monkeys part 2 is the size of the integer worry values and the time it takes to perform operations on them. Look for a way to keep the integer values small.
 
Tim Cooke
Marshal
Posts: 5800
371
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 12 was quite tough. It took me quite a long time to complete part 1 but I'm nearly sure there's a better way to do part 2 as mine takes nearly 3 minutes to complete. The AoC about page states all puzzles have a solution that will complete within 15 seconds on 10 year old hardware.
 
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 12. Used the old breath-first search, both for part 1 and part 2, both finished almost instantaneously.

My idea for day 11, part 2 was, that 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. That should give the exact same effect as if you had sent that 200. Simple idea, but I do not get the same result as in the example given. So, either I have some bug in my code, or my idea is simply wrong. So far I have not yet been able to figure out why my idea is wrong, or what my bug could be. Still thinking and debugging.

edit: for day 12, part 2, be aware that not all starting points 'a' will lead to the finish 'E'.
 
Tim Cooke
Marshal
Posts: 5800
371
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
You're close Piet, and your 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 money tests?

I might need to look up that "breadth first search" technique and see if I can do better than 3 minutes.
 
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
Well, Monkey 1 receives a number x, then applies a mapping to ax + b, and then checks (ax+b) % d. But that gives the same result as checking (a(x %d) + b) % d, and that's why I thought to send x%d.

But admitted: it was over 40 years ago that I was teased with modulo-stuff, so chances are that I completely screwed up. And that primes are used may have to do that primes do not have zero-divisors with mods, but what that has to do with it is beyond me.

Every year a feast, that advent....    
 
Master Rancher
Posts: 5120
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For problem 12, I used Dijkstra's algorithm (which can be thought of as breadth-first, probably what Piet used as well).  Basically, find all points with distance 0, then all points with distance 1, then all points with distance 2, etc. until you first find the target.  It requires only a minor modification from part 1 to part 2, and spits out the answer to both in about 0.12 seconds.  I use it in multiple problems each year.  

Now I just have to go back and do 10 and 11.  
 
Tim Cooke
Marshal
Posts: 5800
371
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 get it Mike, I have done the opposite depth first approach with recursion. It's fun but clearly inefficient.
 
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

Tim Cooke wrote:The problem with monkeys part 2 is the size of the integer worry values and the time it takes to perform operations on them. Look for a way to keep the integer values small.


Big numbers (they don't even overflow in racket) isn't a problem for part two (real input), those 10000 rounds finish almost instantly for me. So that's not a direct issue. But it requires a different algorithm which produces a different inspection times - and that is apparent even after one round/iteration as the examples show.

I find problem description a bit lacking there. But continue looking...
 
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 tried another idea, by specifying a preferred test outcome for each monkey, so basically I could massage worry level (if no longer decreases by 3, thought maybe I can increasing it) until I reach a worry level which matches a preferred test condition.

For example, given the test data:
  • Monkey-0 would always prefer to throw an item to Monkey-3, because its operation is least expensive, i.e. slower increasing worry level among the two.
  • Monkey-1 would always prefer to throw an item to Monkey-0, because again, to throw to Monkey-1 would increase only old*19, while Monkey-2 operation is old*old.
  • Monkey-2 would always prefer to throw an item to Monkey-3 (as opposed to Monkey-1), because Monkey-3 operation is old+3, while Monkey-1 is old+6.
  • ...

  • Unfortunately this theory didn't quite work out too
     
    Mike Simmons
    Master Rancher
    Posts: 5120
    82
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Liutauras Vilda wrote:Big numbers (they don't even overflow in racket) isn't a problem for part two (real input), those 10000 rounds finish almost instantly for me.


    To be honest, this suggests to me that there's a bug in your implementation.  If you perform the worry level calculations as they have been described for part 2, they grow exponentially, and it simply takes more and more time to complete each round.  For me it took 30-60 minutes to get past 1100-round mark, and I don't want to know how long it would take to get all the way to 10_000.  I'm not familiar with Racket, but I really doubt it has such incredible numerics that it can overcome this exponential growth.  Try printing out some of the values along the way - are they ever negative?  They shouldn't be.  That's a big clue if overflow is occurring somewhere.

    Tim C's hints are exactly on target for this one.
     
    We're being followed by intergalactic spies! Quick! Take this tiny ad!
    We need your help - Coderanch server fundraiser
    https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
    reply
      Bookmark Topic Watch Topic
    • New Topic