Advent of Code 2022 Day 11 (BaseA Style)

[AlteryxCommunityTeam]

Discussion thread for day 11 of the Advent of Code - https://adventofcode.com/2022/day/11

[clmc9601]

Adding modular arithmetic to my list of math to study for fun someday

Spoiler

For part 1, I spent the most time debugging my iterative macro. For part 2, I *knew* there had to be a mathematical principle involved. I returned the next morning and looked at the Reddit hints to find the right math. 

Workflow:

 

Iterative macro:

 

[PangHC]

Spoiler

for part2: mod result by common mod (i.e., simply multiple all of them), explanation get from reddit.

split item to rows and

use dynamic replace function to evaluate the operation easier for random input.

workflow:

macro:

[DataNath]

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!

Spoiler

'Rounds' iterative:

'Turns' iterative:

[Yoshiro_Fujimori]

Part 1 complete, still struggling with Part 2. Long way ahead...

Spoiler

Main

Macro

Inner Macro

[DaisukeTsuchiya]

Spoiler

I did initial preparation in Excel for study. It took 5min to process in my laptop.

 

[SeanAdams]

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.

Spoiler

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 3

As 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 item


Here 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 Iterator
This 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 = 20
20 mod 13 is 7
So: 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 7

So 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.