Today was the first day that I gave up getting up at 5 am and tried the challenge with a good night's sleep. Before tackling the problem, I looked at the stats of the fastest solvers and saw, that the best approaches from the speed kings range between 1-3h. When reading the problem, I realized what they must have done and decided: Let's go simple. No double iterative macros, no iterative / batch combination. Let's analyze the problem and go for just one iterative - but very manual - non-scaling macro. I will go to hell for it and will definitely come back to it in the future and go for the double iterative + batch macro solution - I simply wasn't in the mood today and treated it like a one-time consulting question: You need to get the answer, no matter how and you need it fast.
Macro
Part 2I think similar to everyone, I tried to simply increase the data type for part 2 to Int64 and afterward to FixedDecimal 50.0. Obviously, it failed, but it was worth a try. When thinking about it more carefully, I thought about last year: It had to be a mathematical solution, and there had to be a clever way to do it. I did the first iteration for the Monkey 0 on paper and simplified the problem. I spend roughly ten minutes trying an approach that would get rid of my part 1 macro entirely and replace it with a single formula but realized, I'm not JB and still not fully up. Attempt 2 was more successful and required only smaller changes to my part 1 macro - so small, that the whole macro is still exactly the same on the screenshot. For everyone working on part 2 and looking for help here: Take the sample they provide and work through it on paper and look for a mathematical pattern.
Too many loops for Part 2!!!
Not pretty today but got there without too much trouble.
Macro:
I initially misunderstood the question's counting mechanism but eventually figured out my mistake(s).
Otherwise, part 1 is not too difficult.
For part 2, I did not realise at first that there was an overflow issue and even went so far as to built and Excel simulator to debug my workflows. Once figured out that it was an overflow issue, then I solved it with a mathematical formula (hint: Smallest Common Multiplier) to reduce the dimension.
My solution involves using 2 iterative macros. On my laptop, it takes ~10min to run... and we are only D11...😂
My parsing is still really ugly. Bummed I worked from 12pm-5am called it a night running in the background for part 2 to finish at 6am.
Day 11 done ! ✅
I used some help for the mathematics because I couldn't figure it out on my own. Besides that, I built something terribly inefficient using nested iterative macros.
Workflow
Macro 1
Macro 2
Took a bit for P1 to figure out, but framework set up P2 was set. Just needed integer overflow fixed with mod function in spoiler
.
Well, got some heads up from others, part 2 become a bit more manageable.
It's NOT BaseA, but my version of the Abacus can solve part 2 in 20 seconds without a macro. Now that i've gotten used to it, I find it easier to solve this way than an iterative macro.
Generate Rows (It's reading a variable that is being update in the following formula tool).
Some of The VarNum/VarText Formulas:
Adding modular arithmetic to my list of math to study for fun someday
split item to rows and
macro:
Finally had the time to sit down and finish off day 11 - found this one really fun... even if I did spend ages trying to diagnose my calcs, only to realise I was doing 1k iterations instead of 10k!
'Rounds' iterative:
'Turns' iterative:
Part 1 complete, still struggling with Part 2. Long way ahead...
Inner Macro
So - only 11 days late, part 2 of day 11 is finally solved. It took about 4 hours to run, and is kinda messy but it's solved. This one is tricky because it's not just a coding challenge, you need to think about the fundamental math involved (not complex math).
This took a long time for 2 reasons:
- Day 1 only took a few hours.
- lost 3 days trying out different ideas to combat the very-large-number issue in day 2 - by the end of day 3 I had a proof of the method that would work
- then lost a few days with work
- When I finally got down to it - it was only about 3 hours of work to get this done.
Below is the dirty solution - I'll clean this up when I do the refactoring.
the work gets done in 2 main places - the parser and the solver. The parser takes the input and generates 3 outputs.- One is the items and the monkeys - this way you get a list of items associated with each Monkey with a unique ID on each.- the second is the operation that is done - e.g. multiply by 19- the third is the decision criterion about when to change monkeys - e.g. if divisible by 23 then Monkey 2 else Monkey 3As you can see by the number of green tools - this is largely a parsing exercise - not trivial but not too tough - more just messy.
The next part is the solver. This has 3 layers:Layer 1: Iterate for every round, and stop when the round limit is reached Layer 2: Within this round - iterate for every item that is moved until all monkeys have been dealt with Layer 3: Make 1 move for 1 monkey for 1 itemHere are the 3 layers:Layer 1: Round by Round iterator:
Nothing all that fancy here - just running htrough every round, passing them through to the one that moves by monkey - and adding an iteration number and trapping for the iteration cap.Layer 2: Within Round IteratorThis does look a bit messy - but what it's doing is going through the items with a Monkey in an order so that you don't keep on going round again and again - and so that if something is allocated to an earlier Monkey then this is left to Layer 1 to process in a later round. Again - messy but not too rough once you get your head round it.
Layer 3: 1 Monkey 1 throw:This is where the complexities lie.
Firstly - every throw requires a dynamic formula because you have to do a different operation - so used a Dynamic Replace which takes a little bit of work to get comfortable with.Then - to deal with the large numbers you need to change the way you think a little.Instead of focussing on the number itself (which keeps on getting bigger and bigger and bigger) - instead focus on the remainders when a number is divided by X.If you notice - all the "divisible by" numbers are all primes - so you can set up your data so that you store a list of "what is the remainder when I divide by 9; 13; 17" etc.The fun thing about remainders is that if you have a number and multiply it by 10 - the remainder when dividing by 13 also multiplies by 10.e.g. number is 15. 15 mod 13 is 2.Now if you multiply 15 by 10 - you get 150. If you want to figure out the remainder when dividing by 13 - just take the original remainder, multiply by 10; eliminate multiples of 13 and you're done.so 2* 10 = 2020 mod 13 is 7So: 150 mod 13 is also 7.this becomes obvious if you think about the number 15 as ax+b type structure. - So 15 is 1x13 + 2- if you multiply 15 by 10 - then you get (1x13 + 2) * 10- which is 1x13x10 + 2x10- which is 10x13 + 20- we know that 10x13 is divisible by 13, so no need to store this - the only interesting number is 20- now 20 is 1x13 + 7- which means that 15x10 now equals (10x13 + 1x13 + 7)- or... 11x13 + 7 or remainder 7So the trick here is - do the same operation on the remainders for each of the prime numbers up to ~23 or so - and you don't have to store the very big numbers if you want to know which Monkey to send it to.
