old*old is scary though
#AoC 2022 | Day 11 | Solutions & Spoilers
jaunty dome
thin oxide
yep. i realized i made an error in my parsing for that case and it just didn't break anything
thin oxide
rofl
jaunty dome
a fun exercise in learning to write rust macros
so the squaring is scary because is grows like
b**(2**n)
and that will kill python pretty quickly
even for the smallest reasonable b and a small n
In [4]: %time s = 2**(2**30)
CPU times: user 3.6 s, sys: 325 ms, total: 3.92 s
Wall time: 3.92 s
naughty square monkey
twilit shell
yeah what I was saying before applies to the squaring case
I just got confused
my bad
jaunty dome
counter-example: the answer to part 2 sample is bigger than int32 😛
(would fit in unsigned though)
spark skiff
How did you all parse the operation?
I did it like this which worked quite well but... I don't know if its "good"
ops = {
'*': lambda a, b: a * b,
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'/': lambda a, b: a / b,
}
operation = monkey[2].split(': ')[-1]
operation = operation.split(' ')
a = operation[-3]
b = operation[-1]
op = operation[-2]
def operation_func(x, a=a, b=b, op=op):
return ops[op](
x if a == 'old' else int(a),
x if b == 'old' else int(b),
)
lol, I could share my code but it wouldn't be helpful 😛
twilit shell
you don't need a subtraction or division parser
thin oxide
(would fit in unsigned though)
that still counts as an int :P
twilit shell
division would've made part b so much more difficult
jaunty dome
more like impossible
at least to get it to run at any sense of speed
oh no, I'm significantly above 1ms 😭
I don't think I can easily speed things up with like 5-6x :/
thin oxide
just write it in a faster language /s
twilit shell
just do import speed
jaunty dome
just do ``import speed``
😭
dapper dune
How can I make looping 10000 times faster?
twilit shell
don't loop is usually the answer to that
jaunty dome
I hope that should be read as
How can I make "looping 10000 times" faster?
and not
How can I make looping "10000 times faster"?
dapper dune
I hope that should be read as
> How can I make "looping 10000 times" faster?
and...
it should be the first one, yes.
twilit shell
i thought you meant the latter lmao
dapper dune
no lol
torpid tusk
I hope that should be read as
> How can I make "looping 10000 times" faster?
and...
The first quote should be moved back a word; "looping 10000 times"
dapper dune
11 part 2 requires 10000 loops lol
jaunty dome
you will need to loop a bunch regardless, you probably should focus on optimizing what's in the loop
twilit shell
yeah
dapper dune
im really tempted to just download py 3.11 and see if it goes faster
jaunty dome
The first quote should be moved back a word; "looping 10000 times"
fair
twilit shell
trust me if you aren't doing anything to reduce the size of the numbers 3.11 won't help
jaunty dome
what are you doing in the loop currently?
I hope you didn't just remove the //3 and hoped that would work
as the statement says
You'll need to find another way to keep your worry levels manageable.
dapper dune
I hope you didn't just remove the `//3` and hoped that would work
I entirely did
worthy coyote
I hope you didn't just remove the `//3` and hoped that would work
Nothing wrong with that
dapper dune
but I don't know what it wants for keeping them "manageable"
wait
hang on
worry levels dont matter at all
its just the inspection number
well shit
jaunty dome
worry levels dont matter at all
it does
it determines how things move
so you still need to be able to do the divisibility checks
twilit shell
I hope you didn't just remove the `//3` and hoped that would work
i wonder if there's anyone out there that did this and is still waiting for their code to run
jaunty dome
lol, I was looking at a flamegrph to see what the heavy parts of the program is, and was confused for a second why I couldn't see part 1 anywhere
dapper dune
i wonder if there's anyone out there that did this and is still waiting for thei...
that was me.
I got through about 120 loops and said screw this
jaunty dome
lol, I was looking at a flamegrph to see what the heavy parts of the program is,...
it is there, they tiny sliver on the left
twilit shell
but I don't know what it wants for keeping them "manageable"
try to find something that you can do to the numbers to make them smaller, but still keep their divisibility under all of the monkeys' divisors
dapper dune
god this is a fuckin wild issue
I add res/=2 (trying to test stuffs or something) and I get an error in a function that runs when res doesnt even exist (at that point in time)
I remove the res/=2 and that function runs fine.
res = self._evaluate(op)
res /= 2 # putting this line in makes _evaluate error
this wild
jaunty dome
any rust people here that know if drain resets capacity?
dapper dune
god this is a fuckin wild issue
I add `res/=2` (trying to test stuffs or somethi...
ok it seems that only dividing res breaks it
thats honestly fucking wild
torpid tusk
//= is your friend
dapper dune
maybe, but how would that cause a regex in another function to return None, when it returns something
torpid tusk
any rust people here that know if `drain` resets capacity?
No drain doesn't reset capacity
That's actually the reason it borrows the thing you're draining
It's reusing the same store
dapper dune
def _evaluate(self,math:str) -> Union[float,int]:
match = re.match("(\d+) ([\+\*]) (\d+)",math)
groups = match.groups()
...
def processTest(self,item:int) -> bool:
# here we must parse the test string.
op = self.operation.replace("old",str(item))
res = self._evaluate(op)
...
res = res // 2
...
``` Dividing `res` where the `res // 2` is causes the `match = re.match()` inside of `_evaluate` to return `None`.so my particular question is, if I v.drain(..) does v still have the capacity it had before?
dapper dune
res literally does not exist inside of _evaluate lmao
ruby snow
so my particular question is, if I `v.drain(..)` does `v` still have the capacit...
it should, yes, it's the same as v.clear()
jaunty dome
```py
def _evaluate(self,math:str) -> Union[float,int]:
match = re.match("...
you must have some weird data dependencies going on that we can't see here
then I'm confused why push is like 1/3 of my runtime 
if the capacity is always there
ruby snow
it should, yes, it's the same as `v.clear()`
you can check it:
fn main() {
let mut v: Vec<_> = (0..100).collect();
println!("{}, {}", v.len(), v.capacity()); // 100, 100
v.clear();
println!("{}, {}", v.len(), v.capacity()); // 0, 100
}
same output with drain(..)
thin oxide
how are you doing the appending? ig something like items.drain.for_each?
jaunty dome
yes
ruby snow
consider target.extend(items.drain(..))
jaunty dome
consider `target.extend(items.drain(..))`
it's pushing to different vectors though
ruby snow
oh, right, nevermind - drain.foreach is a good way then
thin oxide
since you only have 2 targets, maybe partition?
i'm not sure how efficient it would be though 🤔
lone flame
class Monkey:
barrel = []
magic = 1
def __init__(self, d: tuple) -> None:
self.items = list(map(int, d[1].partition(":")[-1].split(",")))
self.op = eval(f"lambda old: {d[2].partition('= ')[-1]}")
self.div = int(d[3].partition("by ")[-1])
self.throw = tuple(int(_.partition("monkey")[-1]) for _ in d[4:])
self.count = 0
self.__class__.magic = self.magic * self.div
self.barrel.append(self)
def __call__(self, divisor: int) -> None:
self.count += len(self.items)
while self.items:
w = self.op(self.items.pop()) // divisor
self.barrel[self.throw[bool(w % self.div)]].items.append(w % self.magic)
@classmethod
def business(cls, rounds: int, divisor: int, data: str) -> int:
for g in get_groups(data):
cls(g)
for _ in range(rounds):
for m in cls.barrel:
m(divisor)
try:
return prod(sorted(m.count for m in cls.barrel)[-2:])
finally:
cls.barrel.clear()
cls.magic = 1
def part_one(data="input.txt"):
return Monkey.business(20, 3, data)
def part_two(data="input.txt"):
return Monkey.business(10000, 1, data)
implement it with manually written vector intrinsics smh 🥴
jaunty dome
oh right, there are only two targets, maybe that could be useful
I really hope the mod isn't the slow part
thin oxide
also if resizing vectors is an issue can't you just set all the vectors to have enough at the start?
jaunty dome
I can reserve, but it doesn't really help
ruby snow
it really shouldn't be an issue, though
also, does the profiling say what part of pushing takes the time?
e.g. does it mention resizing?
jaunty dome
no
gloomy oxide
My solution today: https://paste.pythondiscord.com/ivacihisal.py
ruby snow
the resizing seems to be done by https://doc.rust-lang.org/src/alloc/raw_vec.rs.html#379
jaunty dome
actually, the mods for that part are compile time known, so they should be optimized already
gloomy oxide
I hope you didn't just remove the `//3` and hoped that would work
Worth a punt ¯_(ツ)_/¯
thin oxide
aka "i'll just run this while i try to solve it just in case"
jaunty dome
I guess if I see push actually being a significant part of runtime, maybe it's pretty well optimized already
thin oxide
possibly, yeah
that just means you should push less
also, the order of the items doesn't actually matter 🤔. cause you use all of them each time
jaunty dome
8 for everyone I'm pretty sure
tall needle
Cycle detection seems highly worthwhile
jaunty dome
I was about to mention that yeah
tall needle
item 0 in my items vector enters its first loop at jump 149 (corresponding to approx. round 75)
jaunty dome
oh lol, you're posting in the rust aoc thread as well?
tall needle
yes hi
jaunty dome
define cycle here? same monkey and same value?
jaunty dome
well yeah, same value modulo the lcm
rewriting to do each item on its own is an intriguing idea to begin with
tall needle
rewriting to do each item on its own is an intriguing idea to begin with <:pithi...
That was actually my first approach 😄
It's not that complicated, you can pop a while new_monkey_index > current_monkey_index inside your loop and it Just Works ™️
gloomy oxide
rewriting to do each item on its own is an intriguing idea to begin with <:pithi...
Each item probably eventually gets into a loop.
jaunty dome
yes, very likely
gloomy oxide
So with caching, this approach could be pretty fast.
jaunty dome
and probably a short loop
tall needle
each item will eventually get into a loop since there are only finitely many states, but the interesting part is that it happens very fast
jaunty dome
That was actually my first approach 😄
It's not that complicated, you can pop a...
it took me actually implementing it until I understood what you meant there 😛
just going item by item gives some speed boost, neat
wait...I get the wrong answer...
debugging time
oh nvm
twilit shell
def parser(filename: str):
with open(filename, 'r') as file:
return [[i[18:].split(', '),
get_op(*re.search(r'([*+]) (old|\d+)', o).groups()),
int(re.search(r'(\d+)', d).group(1)),
tuple(int(j) for j in re.findall(r'(\d+)', p1 + p2))]
for _, i, o, d, p1, p2 in
(line.split('\n') for line in file.read().split('\n\n'))]
def get_op(operator: str, operand: str) -> tuple[Callable[[np.ndarray], np.ndarray], int | None]:
if operand == 'old':
return np.square, None
return {'+': np.add, '*': np.multiply}[operator], int(operand)
def part_b_solver(monkeys: list[list[list[int], tuple[int | None, Callable[[np.ndarray], np.ndarray]], int, tuple[int, int]]]):
inspect_counter = Counter()
lcm = np.lcm.reduce([d for _, _, d, _ in monkeys])
for _ in range(10000):
for n, (items, (operator, operand), divisor, (t, f)) in enumerate(monkeys):
tm, fm = monkeys[t], monkeys[f]
items = np.array(items, dtype=int)
inspect_counter[n] += items.size
new_items = (operator(items) if operand is None else operator(items, operand)) % lcm
partition = new_items % divisor == 0
tm[0] = tm[0] + new_items[partition].tolist()
fm[0] = fm[0] + new_items[~partition].tolist()
monkeys[n][0].clear()
return np.prod(np.array(inspect_counter.most_common(2))[:, 1])
decided to clean up my code with numpy instead of a custom Monkey class
a bit inelegant during the item throwing phase since numpy doesn't like adding arrays together, but i think it turned out pretty nice
the typing is monstrous tho
mortal cosmos
Damn. I knew I was going to be in trouble for Part 2 when I saw the word "rounds"! 😦
Had to go find a hint. Even then it was mostly throwing things at the wall to see what stuck. I don't understand why ||modulo-ing the value over the product of all the test divisors|| works. :/
Very definitely not a maths person.
jaunty dome
Damn. I knew I was going to be in trouble for Part 2 when I saw the word "rounds...
for each individual monkey you could mod with their divisor and it wouldn't change their behavior
importantly you could mod by any multiple of their divisor before calling their operation
it doesn't change the result
sadly we need a modulo that fits with all monkeys at once, so it will need to be some higher multiple of the divisor
turns out this higher multiple that fits all divisor is a well known thing, the lcm
lowest common multiple
dapper dune
I'm trying to figure out how to make the lcm work, but im getting a final monkey business level that way too small
mortal cosmos
Ah I think I get it. If you multiply all the divisors, you're guaranteed to always be a multiple regardless of what each monkey's divisor is, since each monkey's divisor was used in the product.
jaunty dome
Ah I think I get it. If you multiply all the divisors, you're guaranteed to alwa...
yes
the product might be bigger than what you need, but the product will for sure work
mortal cosmos
And it doesn't really matter that this number large... since your worry value will either stay the same... o r be drastically cut down if it gets larger than the max value/product
jaunty dome
well, you ideally want to keep it small
mortal cosmos
well yes, but it's going to be small compared to what the numbers would otherwise reach.
jaunty dome
in our input we actually have prime divisors, so after removing duplicates the product is the lcm
but in general the product is some multiple of the lcm
ruby snow
yeah, the optimal thing to do is the lcm and the product is less efficient - but for all-prime divisors it's the same
jaunty dome
e.g. consider 6 and 10
product is 60
lcm is 30
lcm = product/gcd
if gcd is familiar to you
mortal cosmos
greatest common denominator?
torpid tusk
Divisor
jaunty dome
mortal cosmos
boo. F
torpid tusk
lcm = product/gcd
Also math.gcd is available in earlier versions of Python than math.lcm
slim mason
Were there inputs with non-prime factors?
mortal cosmos
all mine were prime
jaunty dome
Were there inputs with non-prime factors?
not that I know of
I'm just trying to teach the general case as well 😛
I thought I had duplicates...let me check
slim mason
Oh, the question was not related to your explanation; just interest
jaunty dome
oh, maybe not
slim mason
I noticed the prime numbers and just went with the product. I don't think I had duplicates.
jaunty dome
!e
print(2*3*5*7*11*13*17*19)
vapid swiftBOT
@jaunty dome :white_check_mark: Your 3.11 eval job has completed with return code 0.
9699690
That's quite easy to remember lmao
torpid tusk
Two groups of 969 followed by a 0
dapper dune
<@133944101929222144> :white_check_mark: Your 3.11 eval job has completed with r...
hey i have the same number, does everyone have the same input on this day?
torpid tusk
Yeah primorial is apparently properly represented as p₈#
jaunty dome
hey i have the same number, does everyone have the same input on this day?
same divisors
torpid tusk
Or 'product of the first 8 primes'
twilit shell
Damn. I knew I was going to be in trouble for Part 2 when I saw the word "rounds...
my intuition for it is that i have some number x that I don't know, and I can get more information about it by querying its residues modulo n
if i query it mod 2 for example, I only get that it's either 0 or 1, but if i query it mod 4, then i would know if it's 0, 1, 2 or 3 mod 4, and I could use that to figure out what it is mod 2 as well (0, 2 means 0 mod 2 and 1, 3 means 1 mod 2), so taking mod 4 gives the information mod 2 gives and more, and in general taking mod a*b*c... gives the information that mod a, mod b, mod c... gives
for this case we want to preserve the worry numbers mod a, mod b, mod c, etc. By taking mod a*b*c..., we obviously preserve the residues mod a*b*c..., and so we get the information that mod a*b*c... gives us about the worry number. And so from above, we also get the information about the worry number mod a, mod b, mod c, etc, which is what we want (we want to know if those residues are 0).
torpid tusk
same divisors
But presumably not in the same order or with the same targets
dapper dune
ah
yeah im just having a real hard time trying to figure out how to use the divisor product thing
I'm trying to figure out where I can stick my supermodulo to make it work, can anyone help me out?
def processTest(self,item:int) -> bool:
# here we must parse the test string.
op = self.operation.replace("old",str(item))
res = self._evaluate(op)%supermodulo
match = re.match("divisible by (\d+)",self.test)
div = int(match.group(1))
return res%div==0,res%supermodulo
def processInventory(self) -> None:
for item in self.inv:
ok,worry = self.processTest(item)
if ok:
monkies[self.test_t].inv.append(worry)
self.inv.remove(item)
self.inspected += 1
else:
monkies[self.test_f].inv.append(worry)
self.inv.remove(item)
self.inspected += 1
the heck is a supermodulo
torpid tusk
'supermodulo' lmao
dapper dune
the product of all my divisors
dapper dune
<@133944101929222144> :white_check_mark: Your 3.11 eval job has completed with r...
this number
torpid tusk
I called mine the 'loop_factor' lol
twilit shell
i called mine "lcm"
dapper dune
eh.. different names for different people
torpid tusk
i called mine "lcm"
Despite the fact that technically it might not be :P
dapper dune
I'm just getting a final monkey business number thats too small
slim mason
I did not call mine anything because I just dumped it in there as a literal
twilit shell
Despite the fact that technically it might not be :P
nah i specifically took the lcm
torpid tusk
I'm just getting a final monkey business number thats too small
Make sure your brackets to your sorted call are in the right place, that cost me like 5 minutes
(I was sorting the last 2 elements instead of taking the last two elements of the sorted list)
dapper dune
i dont have a sorted call?
I'm just calling inspection.sort(reverse=True) (where inspection is the list of each monkey's inspected items count)
twilit shell
make sure you actually use the supermodulo/loop_factor/lcm/9699690 and not just the monkey divisor
i did that by accident
twice
the second time i got the wrong answer i was like 'wait a sec i swear i got this error before"
dapper dune
I'm trying to figure out where I can stick my `supermodulo` to make it work, can...
the last line of processTest uses the monkey divisor, but also returns the worry number modulo the supermodulo/loop/whatever
jaunty dome
have you verified against the sample input?
torpid tusk
i dont have a sorted call?
I'm just calling `inspection.sort(reverse=True)` (whe...
That would have stopped me from making the mistake I made lol
jaunty dome
which has the counts at some iterations in the statement
dapper dune
it does not work correctly on the sample input, no.
twilit shell
you don't need to res%supermodulo again in the return statement
you already took % supermodulo earlier
dapper dune
you don't need to res%supermodulo again in the return statement
ive been trying a lot of different things lol
zinc birch
how on earth am i supposed to do part 2 without frying my pc?
dapper dune
keep the worry number small
zinc birch
and then multiply it by the factor?
twilit shell
scroll up an arbitrary amount and you'll probably find some conversation discussing how to do it
zinc birch
🥳
twilit shell
are you sure the mistake isn't in your _evaluate() function
dapper dune
def _evaluate(self,math:str) -> Union[float,int]:
match = re.match("(\d+) ([\+\*]) (\d+)",math)
groups = match.groups()
x,y = int(groups[0]),int(groups[2])
match groups[1]:
case "+":
return x+y
case "*":
return x*y
``` it is basically just a safe `eval` lolchanging res = self._evaluate(op) for res = eval(op) returns the same number.
dapper dune
what do you mean?
twilit shell
the inputs would be of the form
old + 9
or something
the first bit shouldn't be a digit
dapper dune
no no, before I pass to _evaluate I do replace("old",str(item))
twilit shell
ah
dapper dune
i hate myself
i found the issue
it was an issue i already solved in 11-1, but i somehow reintroduced it
dapper dune
I'm trying to figure out where I can stick my `supermodulo` to make it work, can...
I needed to do for item in self.inv.copy() in processInventory
I already knew about this issue from 11-1, but somehow i deleted that part in 11-2
what the fuck
zinc birch
wait how
gentle grove
https://www.reddit.com/r/adventofcode/comments/zifqmh/comment/izshhm9/?utm_source=share&utm_medium=web2x&context=3
Rust solution :
Part 1: 28.2us
Part 2: 12.593us
insane
jaunty dome
wait, I'm confused, my initial solution is basically that
and almost 1000x slower
oh nvm
you misrad
high latch
dayum why is my code so slow
jaunty dome
https://www.reddit.com/r/adventofcode/comments/zifqmh/comment/izshhm9/?utm_sourc...
12593us
aka 12.6ms
(my thing is faster than that)
(granted, my thing is arguably cheating by doing the input parsing with a macro)
high latch
(granted, my thing is arguably cheating by doing the input parsing with a macro)
how is dat cheating?
jaunty dome
because it happens at compile time
high latch
but compile time is negligible
jaunty dome
negligible how?
jaunty dome
one can run the whole thing at compile time in C++
twilit shell
if you do it by hand technically the runtime is 0ms
jaunty dome
that's definitely in the cheating territory 😛
twilit shell
python is just kinda slow
twilit shell
ok not that slow
jaunty dome
lol, are you hoping that just removing //3 would work?
gentle grove
but taking minutes for single iterations?
huh? mine runs in 2.5s
high latch
lol, are you hoping that just removing //3 would work?
yea, why?
slim mason
Oh, oh, good luck
twilit shell
mine runs both parts in 0.75s
high latch
but why?
jaunty dome
the numbers grow way too large
high latch
but what should I do instead?
jaunty dome
you have a monkey that squares the number every time
twilit shell
main chokepoint is np.array() so probably not gonna optimize further
jaunty dome
which will grow so large
twilit shell
stupid square monkey
jaunty dome
but what should I do instead?
Unfortunately, that relief was all that was keeping your worry levels from reaching ridiculous levels. You'll need to find another way to keep your worry levels manageable.
twilit shell
ruining the lives of all the brute forcers
jaunty dome
find some other way to keep the levels down
slim mason
You will need to think of a way to reduce the number in way that keeps all the modulo results the same for each monkey test
high latch
You will need to think of a way to reduce the number in way that keeps all the m...
hmmm...
lcm
twilit shell
yeah
zinc birch
i still have no idea how to change the algorithm so it doesnt need years to give me an answer with 10000 rounds
;-;
high latch
i still have no idea how to change the algorithm so it doesnt need years to give...
math.lcm
high latch
the only thing taking long in C is malloc()
zinc birch
wot
jaunty dome
wdym too large?
twilit shell
you run out of memory
thin oxide
wdym "what happens"
twilit shell
is MemoryError a thing in python?
thin oxide
yes
zinc birch
just replace //3 with % 9699690
wait??? how?? can you please explain?
jaunty dome
yeah, memory is the constraining factor for ints (that and actually doing computations)
jaunty dome
wait??? how?? can you please explain?
you need the divisors for the monkeys to still be the same, modding by the lowest common multiple does that and allows you to keep the actual value low
twilit shell
wait??? how?? can you please explain?
zinc birch
you need the divisors for the monkeys to still be the same, modding by the lowes...
thats too much big brain
goodayum
tysm
wow
ruby snow
are python bigints that bad?
the length of the numbers doubles every turn (or ~7 turns at least) because there's a square operation there, so the lengths grow roughly exponentially with turns
zinc birch
math 🤓
high latch
the length of the numbers doubles every turn (or ~7 turns at least) because ther...
yep
ruby snow
and, well
high latch
and as the length of a number grows with it's logarithm
ruby snow
!timeit
x = 10**100
x**2
@ruby snow :white_check_mark: Your 3.11 timeit job has completed with return code 0.
500000 loops, best of 5: 716 nsec per loop
a new realloc is needed frequently
jaunty dome
10**100 is cheap
high latch
also I just realized
ruby snow
for 10**1000 it's 10 mus
jaunty dome
squaring 100 times isn't
10**2**100
high latch
on linux, VSC auto-focuses itself when an error occurs
twilit shell
squaring 100 times isn't
`10**2**100`
i wonder if it's actually still possible to do it without taking modulo lcm
jaunty dome
!timeit
i_hope_there_is_a_timeout = 10**2**100
because you could do fermat's little theorem/euler's theorem on that
vapid swiftBOT
@jaunty dome :warning: Your 3.11 timeit job timed out or ran out of memory.
[No output]
that's a really neat feature
jaunty dome
because you could do fermat's little theorem/euler's theorem on that
how would that help?
high latch
because you could do fermat's little theorem/euler's theorem on that
which one?
twilit shell
you could evaluate the residue mod p without having to actually evaluate the entire thing
jaunty dome
it's not like we're actually computing something like the think I wrote, you multiply/add with a bunch of stuff
twilit shell
yeah that's the main problem
you could maybe expand with a^2+2ab+b^2 and then do it on each individual term
that'll still blow up with a lot of terms but not as much as exponential i think?
it's definitely not worth it but it'd be interesting to see if it's possible
twilit shell
which one?
they're the same thing in this case since we're dealing with primes
well you'd have to check if the worry number is coprime ig
but that'd just be like if not coprime: 0
high latch
long boi ```py
def day11(inp: str) -> tuple[int, int]:
class Monke:
def init(self) -> None:
self.items: list[int] = []
self.op: str = ""
self.id: int = -1
self.div: int = -1
self.throw_ids: list[int] = [-1, -1]
self.monkeys: list[Monke] = []
self.inspect: int = -1
self.lcm = -1
def ready(self):
self.stack = self.items[:]
self.inspect = 0
def fire(self, div = True):
for i in self.stack:
wglob = {"new": None, "old": i}
exec(self.op, wglob)
worry = wglob["new"]
if div:
worry = int(worry / 3)
else:
worry %= self.lcm
if worry % self.div == 0:
self.monkeys[self.throw_ids[0]].stack.append(worry)
else:
self.monkeys[self.throw_ids[1]].stack.append(worry)
self.inspect += 1
self.stack = []
def str(self) -> str:
return "Monke " + str(self.dict)
def repr(self) -> str:
return str(self)
monkeys = []
for i in inp.strip().split("\n\n"):
mnk = Monke()
mnk.monkeys = monkeys
for i in i.strip().split("\n"):
match i.strip().split(" "):
case "Monkey", i:
mnk.id = int(i[:-1])
case "Starting", "items:", *i:
for j in i:
mnk.items.append(int(j.removesuffix(",")))
case "Test:", "divisible", "by", i:
mnk.div = int(i)
case "Operation:", *ops:
mnk.op = " ".join(ops)
case "If", "true:", "throw", "to", "monkey", i:
mnk.throw_ids[0] = int(i)
case "If", "false:", "throw", "to", "monkey", i:
mnk.throw_ids[1] = int(i)
mnk.ready()
monkeys.append(mnk)
for i in range(20):
for j in monkeys:
j.fire()
tops = list(sorted(monkeys, key=lambda m: m.inspect))[-2:]
a = tops[0].inspect * tops[1].inspect
for i in monkeys:
i.ready()
i.lcm = math.lcm(*map(lambda i: i.div, monkeys))
for i in range(10000):
for j in monkeys:
j.fire(div = False)
tops = list(sorted(monkeys, key=lambda m: m.inspect))[-2:]
return (a, tops[0].inspect * tops[1].inspect)```
zinc birch
long boi ```py
def day11(inp: str) -> tuple[int, int]:
class Monke:
def __ini...
godayum that monke thicc
you can use a dataclass for the monke
high latch
you can use a dataclass for the monke
I am lazy
jaunty dome
dataclasses allows for more lazy
zinc birch
I am lazy
thats why you should use them
:))
you just put the attributes and properties you want and it also provides a repr for you
from dataclasses import dataclass
@dataclass
class Monkey:
id: int
items: list[int]
op: str
test: int
true: int
false: int
inspect_count: int = 0
@property
def first(self) -> int:
return self.items[0]
def test_worry_level(self) -> bool:
return (self.first % self.test) == 0
def operation(self) -> int:
op, value = self.op.split(" ")
old = self.first
operand = old if (value == "old") else int(value)
result = old + operand if(op == '+') else old * operand
self.items[0] = result
return result
@staticmethod
def get_monkey_business(monkeys):
two_most_active = sorted(monkeys, key=lambda m: m.inspect_count, reverse=True)[:2]
monkey_business = two_most_active[0].inspect_count * two_most_active[1].inspect_count
return monkey_business
my monke
ive been using dataclasses in almost all puzzles
ashen forge
first property seems a bit overkill otherwise pretty neat
zinc birch
yeah true but i was tired of always doing monkey.items[0]
twilit shell
I prefer attrs
ashen forge
yeah makes sense but you probably cleaned up a bit and now you're saving 3 characters a whole 2 times with 3 lines of code 😄
ashen forge
ah ok yea that makes more sense then
zinc birch
from monkeys import *
monkeys = parse_input()
rounds = 20
for _ in range(rounds):
for monkey in monkeys: # each round
while len(monkey.items) > 0:
monkey.operation()
monkey.items[0] //= 3
if monkey.test_worry_level():
monkeys[monkey.true].items.append(monkey.first)
else:
monkeys[monkey.false].items.append(monkey.first)
monkey.inspect_count += 1
monkey.items = monkey.items[1:]
monkey_business = Monkey.get_monkey_business(monkeys)
print(monkey_business) # 58794
and also in part 2
it is not very efficient but its just for the sake of simplicity
:)
ashen forge
yeah that makes sense, you could maybe do references to the respective next monkey inside the monkey class as well so you can do a toss method or something
zinc birch
yea
ruby snow
Here's how fast numbers grow with the naive solution. Note that the y-axis is logarithmic and the curves are of the logarithms. So the length of numbers grows exponentially with turns.
zinc birch
nice
jaunty dome
that do be how squaring works
ruby snow
it is
jaunty dome
without the squaring monkey the growth would look very different
ruby snow
yeah, length would be merely linear with turns
glass basin
now i dont want to advocate for animal abuse but
ashen forge
jaunty dome
for some reason my cycle detecting version gives me the right answer for 2 of the monkeys in the sample 🥴
but completely wrong for the other 2
ruby snow
huh
interestingly, looking at timings, it looks like time per turn grows like exp(turns**2) rather than exp(turns)
ashen forge
the whole old = old*+ whatever is annoying, I feel like there should be a more straightforward solution than lambda but can't find one
ruby snow
interestingly, looking at timings, it looks like time per turn grows like exp(tu...
so in conclusion, the naive solution would take roughly..
.wa 1.88e264 seconds wrong, see below
wide lindenBOT
ruby snow
oh wait, I messed up, that's only for 1000 turns
it's actually, uhh
.wa 1e64187 seconds EDIT: still wrong, see below
wide lindenBOT
ruby snow
lol, wolfram doesn't want to handle that
jaunty dome
what would you even want as an answer to that?
ruby snow
around 10^64170 ages of the universe
thin oxide
lmao
ruby snow
actually, I messed up again, it's only e^64187, so 10^27876 seconds
jaunty dome
not that is matters 😛
ruby snow
or 10^27859 ages of the universe 😛
ashen forge
already did more than last year 
ruby snow
the squared exponential thing might actually be just a fluke
like, because it's hard to measure how quick the first turns are
if so, if it's linear, it's "only" 10^494 s for 10000 turns
ruby snow
the total time is roughly e^(0.127*turns - 15) s
short leaf
is this an easy problem compared to problems in later days from the past years?
near badge
man part 2 is super interesting
I have no idea how to proceed tho
I'll think about it while I go to sleep
brisk edge
Here's how fast numbers grow with the naive solution. Note that the y-axis is lo...
what library are you using for these visualisations
brisk edge
zamn
short leaf
oops
temp = (len(file) + 1) // 7
file= amount of lines
this should be the amount of monkeys per input right?
ruby snow
so much for "multiple times"
also it uses time instead of perf_counter
pathetic, first year CS student level of programming 😛
pine light
i just specified again "run each value of N multiple times" and it fixed the code
also can ask it to "use perf_counter" and it modifies it
it's very conversational, I like it
"use the dark theme"
ruby snow
Yeah, the way chatgpt grokks code is actually terrifying; I haven't seen any past model show this level of understanding
it seems inplausible it saw enough examples to just memorize all these weird programs; that's real understanding here
pine light
yeah copilot is good at like few lines, but this can just like understand code and convert english to code shockingly well
jaunty dome
@tall needle <500us with cycle detection, <250us with a better hash function to speed the hash table up 😍
tall needle
ivory dagger
That would have been more helpful as a codepaste than a screen shot.
gentle grove
lol i love it
pine light
it would have but I was more illustrating the fact that it can do it rather than the code
ivory dagger
ah
pine light
(there's more code anyway for the line fitting etc)
short leaf
only operations are * and + right?
torpid tusk
Think so
ivory dagger
only operations are * and + right?
yes, but not always on a number
short leaf
yea sometimes old*old
ivory dagger
if you name your variable old though, eval still works just fine. 🙂
old = eval(self.op)
if "*" in var:
int1, int2 = map(int,var.split("*")
int1*int2```eval sounds dangerous
ivory dagger
how'd you even do that? did you build the var string by combining the worry and the op ?
short leaf
how'd you even do that? did you build the var string by combining the worry and ...
wait
ivory dagger
eval is only dangerous when you don't have control of the input. 🙂
ok, have to run back in an hour
short leaf
first line is a list with operations and second list is the action after doing the operation in format :
- val = dvisor, 2.val = if true, 3.val = if false
for index, i in enumerate(file):
if "Starting" in i:
temp_list = i.replace(",", "").split()
for o in temp_list:
if o.isnumeric():
items[temp].append(int(o))
temp += 1
elif "Operation" in i:
_, operation = i.split("=")
operations.append(operation.strip())
elif "Test:" in i:
for p in range(3):
temp_list = file[index+p].split()
actions[temp_2] += f"{temp_list[-1]} "
temp_2 += 1
``` and thats how i got the listsroom for improvements
short leaf
how'd you even do that? did you build the var string by combining the worry and ...
for i in range(monkey_num):
cur_score[i] += len(items[i])
for index, item in enumerate(items[i]):
temp = operations[i]
temp = temp.replace("old", str(item))
yea i couldve just done temp=operations[i].replace ....
ashen forge
i think today was fairly simple, the input parsing was the trickiest part right?
the hardest thing i remember from previous years was the water simulation
well that was the trickiest for me anyways
jaunty dome
realizing the lcm for part 2 is probably the hard part for most people
ashen forge
i guess yea that one either comes via gut feeling or just knowing the math
jaunty dome
it was cool to see you can actually do it faster than actually simulating all 10000 steps
short leaf
why is he dividing
tawdry helm
why is he dividing
it always get divided by 3 after they inspect it in part 1
short leaf
oh
i thought that only if it breaks which never happenbs
and the worry level//3 is always before its checked to who its going to be thrown right?
median lagoon
yes
short leaf
ah oh
thats why my code didnt work
i thought i got something wrong with my loops and index variables
ValueError: Exceeds the limit (4300) for integer string conversion ?
is that why i need LCM?
jaunty dome
well, in part
the numbers will get very very very large
which is why you need the lcm
(the string conversion limit is a recent change I'm not fond of...)
short leaf
if i switch to an older version of py would that fix the issue
jaunty dome
what issue exactly?
short leaf
the valueerror
jaunty dome
even if you can print larger ints that won't help you solve the problem, the values get way too large for that
short leaf
oh
tawdry helm
ValueError: Exceeds the limit (4300) for integer string conversion ?
why are you converting numbers that large from string to int in the first place? You can convert the items once you parse them and then keep them as ints
sullen stream
I cannot get my code to work 😦
For P2, it works for the first 20 rounds
but the example it gets off somewhere between then and round 1000
ashen forge
would require the algorithm to comment
sullen stream
yeah of course. Just venting for now
Here's my monkey.inspect method
def inspect(self, p2=False):
while self.items:
self.inspected += 1
item = self.items.pop(0)
if self.val == 'old':
item = (item % lcm) * 2
else:
item = ops[self.op](item, self.val)
if not p2:
item //= 3
if item > lcm:
item = item % lcm
self.throw_to(item, self.if_true if self.do_test(item) else self.if_false)
ops is just a dict
ops = {
'+': add,
'*': mul
}
if self.val == 'old':
item = (item % lcm) * 2
This part i wasn't 100% sure about
sullen stream
lcm is what value?
Just all the div's multiplied together
ashen forge
how are you implementing item = item*item with that
sullen stream
ok i got it. I just treated the old * old normally
was trying to be tricky with it
ashen forge
you can be tricky with old + old but i don't think ^2 can be ignored
sullen stream
how are you implementing item = item*item with that
I figured the remainder of old/lcm would be just added in that case?
It's probably incorrect lol
ashen forge
does it work now? because i think you have to do the %lcm after the true/false check
sullen stream
Yeah it works
ashen forge
huh
sullen stream
I think it wouldn't matter when you do the %= lcm
ashen forge
thats so strange, doesn't work for me in another order but i guess
ashen forge
item = item % lcm```thats redundantwhat does your do_test do? just a simple % div right?
sullen stream
class Monkey():
def __init__(self, items, op, val, test):
self.items = items
self.op = op
self.val = val
self.test = test
self.if_true = None # set to other monkey obj
self.if_false = None
self.inspected = 0
def do_test(self, item):
return (item % self.test) == 0
def throw_to(self, item, other):
other.items.append(item)
def inspect(self, p2=False):
while self.items:
self.inspected += 1
item = self.items.pop(0)
if self.val == 'old':
item = item ** 2
else:
item = ops[self.op](item, self.val)
if not p2:
item //= 3
item %= lcm
self.throw_to(item, self.if_true if self.do_test(item) else self.if_false)
Yeah not totally necessary
but i like it 😄
same with throw_to
i was anticipating it needing to do more when reading through the problem
ashen forge
yeah I'm just asking because i don't get why this doesn't work for me
sullen stream
you do the test first?
the whole point of the %= is that it doesn't impact the test right?
so idk why yours wouldn't work
ashen forge
next_monkey = x if item % div == 0 else y
monkeys[next_monkey].items.append(item % 9699690)``` this worksyou don't need to check if item > lcm, you can just do item % lcm and it'll be the same... although I don't think it actually changes much
ashen forge
next_monkey = x if item == 0 else y
monkeys[next_monkey].items.append(item % 9699690)``` this does notwhy wouldn't it?
ashen forge
ah nvm you changed that part completely
tawdry helm
I think the best place to apply item % lcm is right after doing the operation
ashen forge
i thought you managed to make it work with (item % lcm) this somehow
but that doesnt work for me
i get different results
i mean it can't work now that i think about it, that would totally defeat the purpose of % 9699690
tawdry helm
```item = op(item)% div
next_monkey = x if item == 0 else y
monkeys[next_monkey]...
ah right, now I understand. item % div == 0 is only to check the condition, it shouldn't actually affect the item
ember torrent
fucking part 2 has expanded my math comprehension levels
had to read a lot of what other people had to say in here to get it
tawdry helm
```item = op(item)% div
next_monkey = x if item == 0 else y
monkeys[next_monkey]...
item = op(item) % 9699690
next_monkey = x if item % div== 0 else y
monkeys[next_monkey].items.append(item)
something like this should work
ashen forge
yea that does
ivory dagger
i think today was fairly simple, the input parsing was the trickiest part right?
it was pretty easy with regex
ivory dagger
i mean it can't work now that i think about it, that would totally defeat the pu...
note that % 9699690 is only for the input, and won't work with the testdata
test data is 13*17*19*23 where as input data is 2*3*5*7*11*13*17*19
turbid matrix
I'm stumped on part 2. I know it has to do with modulo and LCM of the monkey's divisors, but I can't figure out how to get around the problem of the ever-increasing item worry levels. Since the monkeys can multiply OR add to the item's worry level, I don't see how I can get around tracking the worry levels. The only thing that comes to mind is only to track the modulus (remainder? I don't remember the proper terms...) of the items instead of the actual worry level, but then I think that would massively change the outcome of the multiplication operations, so errors would creep in over time.
Am I wrong about any of that or am I missing something else?
Hmmm only one of my input monkeys square the worry level, and only 2 of them multiply it (both by primes...) I feel like that's significant in some way
torpid tusk
I'm stumped on part 2. I know it has to do with modulo and LCM of the monkey's d...
Keeping the modulo won't affect your multiplication values, as long as your modulo is correct wrt every individual monkey's divisibility check
The simplest way of observing that is in the simplest case where you only have one divisor to check
turbid matrix
Keeping the modulo won't affect your multiplication values, as long as your modu...
That sounds plausible, but I think I need to try it out a bunch to really understand it. Thanks!
turbid matrix
The simplest way of observing that is in the simplest case where you only have o...
Oooh good idea! That'll help me understand it much faster thanks
tawdry helm
I'm stumped on part 2. I know it has to do with modulo and LCM of the monkey's d...
there's a modulo values that won't introduce errors (there's infinite ig, but there's one that's the smallest)
brisk quest
it is almost the hour of choking again
turbid matrix
Yeah I just went and watched a video on modular arithmetic on YouTube and:
- I now have a much better understanding of what modulo actually means in mathematical terms
- it seems closely related to the concept of number bases, like binary, decimal, hexadecimal etc, which is one of my favourite concepts in the universe, so yay X2
3)I think I sorta get how it works now on a deeper level, and in doing so, I have learned a better appreciation for math than I had before. - in a way, the LCM+modulo approach almost turns it into fizzbuzz
stone root
somehow on part1 I get the right answer for the example but not for the actual input
slim arch
It just doesn't work on their test, because the test is for the "divide by three" version. Which irritated the shit out of me honestly
stone root
It just doesn't work on their test, because the test is for the "divide by three...
what's lcm in this context ?
twilit shell
lowest common multiple
also lcm should still work for the test
as long as you didn't hardcode 9699690
stone root
lowest common multiple
why woudl you need lcm ?
twilit shell
taking residues modulo the lcm of a group of numbers preserves the residues of the number modulo every number in the group
since (x % np) % p = x % p
slim arch
because anything divisible by 3 % 3 is still divisible by 3
slim arch
Lets just say I got numbers with tens of thousands of digits before I lcm'd it
Can python do it? Maybe, you might run out of ram
twilit shell
python definitely can't do it
slim arch
will python do it in time? no
Yeah, you'd need..
19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
bytes of ram
which is a nonstarter it seems
stone root
so this is why my code isn't working
twilit shell
^
stone root
it was working on the example but not the actual input
slim arch
the whole old = old*+ whatever is annoying, I feel like there should be a more s...
I just did exec() tbh
primal gazelle
i went in and changed the input to old ** 2
ruby snow
if so, if it's linear, it's "only" 10^494 s for 10000 turns
I now believe it's only this much ^
gentle grove
if so, if it's linear, it's "only" 10^494 s for 10000 turns
ah, that's just 10^432 years more than the age of the universe if it was planck time instead of seconds. tiny
torpid tusk
19950631168807583848837421626835850838234968318861924548520089498529438830221946...
This feels like an incorrect number
At the same time with the squared bit maybe
ruby snow
19950631168807583848837421626835850838234968318861924548520089498529438830221946...
I'm getting that the log of the numbers after 10k turns will be very roughly 1.5e217
torpid tusk
Oh wow ok
ruby snow
so the log2 will be around 1e313. so around 1e313 bits of memory per median number.
and bast's number is 3010-digit, so that's way too high actually
winged musk
Remove the % and just try. Python handles big integers but all operations become really slow
I was doing it after a night of no sleep, so I first didn't notice the "you have to find other way to manage your worry levels", I just deleted the //3 and it couldn't even do 1k loops in manageable time. 20 was doable, although it was slower than part 1. 😛
I assume the 10k looping was specifically done so that people wouldn't just let the no-mod solutions run for a long time
jaunty dome
Remove the % and just try. Python handles big integers but all operations become...
the point was that the number that was mentioned was actually managable
the number you get from the repeated squaring isn't
if the squaring wasn't there I think things would have worked with not modding
winged musk
The code/python doesn't break after several minutes. So it's "manageable", just not in good time.
I lost my code because I didn't post it here and my phone died when I went to sleep, so I cannot measure speed of each loop and see where it becomes absurd
ruby snow
The code/python doesn't break after several minutes. So it's "manageable", just ...
see about, it will take around 1e494 seconds for 10000 turns
since the length of the numbers involved grows exponentially
jaunty dome
with the squaring, yes
winged musk
!e
from datetime import timedelta
print(timedelta(seconds=1e494))
vapid swiftBOT
@winged musk :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "<string>", line 2, in <module>
003 | OverflowError: cannot convert float infinity to integer
did anyone try with replacing the square with something else? my guess is that one would be reasonable
winged musk
Oops XD
ruby snow
yeah, if not for the squaring, 10000 turns would only take roughly (500)^2 = 250000 times longer than 20 turns
jaunty dome
squaring grows as base**2**n which is...not great 😛
vapid swiftBOT
@jaunty dome :white_check_mark: Your 3.11 eval job has completed with return code 0.
69.44444444444444 hours
I doubt it would actually be that long
jaunty dome
or maybe I'm underestimating how slow python is at actually running this
I was down to ~5ms in rust before doing fancy stuff
twilit shell
depends a lot on your implementation i'd think
jaunty dome
so I assumed python wouldn't be more than 10-100x slower
is there any good solution to test with?
I don't have any python solution of my own
twilit shell
wow
i took away the % lcm bit and replaced old * old with old * 19 and it finished in 1.56 seconds
wait disregard that
something is wrong
jaunty dome
oh wow, most solutions I see here are quite slow
xelf's takes almost 3s
oh, that solution uses eval
that could explain some slowness
twilit shell
hmm
ohh
yeah i don't think i can test with my solution
since i used numpy
which uses int64
jaunty dome
how is numpy helpful for this task?
twilit shell
just quick vectorized operations
def part_b_solver(monkeys: list[list[list[int], tuple[int | None, Callable[[np.ndarray], np.ndarray]], int, tuple[int, int]]]):
inspect_counter = Counter()
lcm = np.lcm.reduce([d for _, _, d, _ in monkeys])
for _ in range(10000):
for n, (items, (operator, operand), divisor, (t, f)) in enumerate(monkeys):
tm, fm = monkeys[t], monkeys[f]
items = np.array(items, dtype=int)
inspect_counter[n] += items.size
new_items = (operator(items) if operand is None else operator(items, operand)) % lcm
partition = new_items % divisor == 0
tm[0] = tm[0] + new_items[partition].tolist()
fm[0] = fm[0] + new_items[~partition].tolist()
monkeys[n][0].clear()
return np.prod(np.array(inspect_counter.most_common(2))[:, 1])
i'm getting around 1s for both parts with time.time()
idk if that's the proper way to time functions
jaunty dome
time.perf_counter is the better fit
twilit shell
1.0672482980880886
1.4777922849170864
1.2932897110003978
probably something with caching or smthing
but all seem to be below 1.5s
short leaf
for yesterday
day 11
can i just try to item_worry % product_of_divisors
and if that equation == 0 then set item value to 0 else keep value
0%any_divisor would be 0
the same as any common multiplay of all divisors
oh the lcm isnt always the product of all values right?
short leaf
oh but the divisors are all primes
sullen stream
and if that equation == 0 then set item value to 0 else keep value
You're close...
did you figure it out yet? you posted 2 hrs ago
short leaf
nah
i just waited like 70minutes until the answer was calculated which was correct
did other stuff while waiting
but ill try to fix it tomorrow
stray sequoia
I got the right answer with enough hints, but I have no idea why it works. Guess I gotta learn me about modulo
sullen stream
I got the right answer with enough hints, but I have no idea why it works. Guess...
If something is divisible by a multiple of A, it is also divisible by A
if something is divisible by a number that's a multiple of A and of B, then it's also divisible by A and B individually
Extend that to a multiple of A, B, C, D, E, F, and G
tawdry helm
I got the right answer with enough hints, but I have no idea why it works. Guess...
with modular arithmetic I think it's useful to think about cycles in numbers:
0 % 2 = 0 0 % 3 = 0
1 % 2 = 1 1 % 3 = 1
2 % 2 = 0 2 % 3 = 2
3 % 2 = 1 3 % 3 = 0
4 % 2 = 0 4 % 3 = 1
5 % 2 = 1 5 % 3 = 2
6 % 2 = 0 6 % 3 = 0
as you can see, modulo 2 and modulo 3 have cycles that "synchronise" every 6 numbers (which is the lcm between 2 and 3)
If you had more numbers (for example the numbers that each monkey checks), you could extend this logic to find how many numbers it takes for their cycles to align.
stray sequoia
If you had more numbers (for example the numbers that each monkey checks), you c...
Oooh, so by finding a common multiple between all of them, the remainder of anything divided by the multiple is congruent to the original number?
tawdry helm
Oooh, so by finding a common multiple between all of them, the remainder of anyt...
yup, for the purposes of checking divisibility against all the required numbers it will be the same
which means that you can do modulo lcm to avoid the items from growing past that number, which keeps the problem manageable
tawdry helm
vapid swiftBOT
Hey @timid spoke!
timid spoke
https://paste.pythondiscord.com/utidoquluf
any critiques for my day-11? 🙂
torpid tusk
Not sure what DIV is for, and you can just use math.lcm
twilit shell
f strings let you print out expression=
like
print(f"{58-7=}")
would print out
58-7=51
torpid tusk
!e ```py
print(f"{58-7=}")
@torpid tusk :white_check_mark: Your 3.11 eval job has completed with return code 0.
58-7=51
i was gonna do that but the wolfram alpha bot declined me last time
torpid tusk
Lol
twilit shell
i was too afraid of rejection
twilit shell
https://paste.pythondiscord.com/utidoquluf
any critiques for my day-11? 🙂
for the last step you should try to avoid sorting the list twice
sort the list once and save the result
and index that
torpid tusk
Or math.prod(sorted(counts)[-2:])
timid spoke
Not sure what DIV is for, and you can just use math.lcm
thank you, the DIV is to get the lcm of all the numbers 🙂
mortal stratus
I feel rather clever for seeing how to limit the endless squaring from making the problem explode
jaunty dome
@winter fiber what do you think applies if I looked at only divisibility by 5?
winter fiber
Mod 5
jaunty dome
if I cared about divisibility by 3, I could mod the value by 3, 6, 9, 12, 15, ... and I would still get the right thing when modding by 3
that's what I mentioned earlier
e.g.
n % 12 % 3 == n % 3
what if we looked at 5 instead?
what values could I mod by without messing the value mod 5 up?
jaunty dome
right 5, 10, 15, 20, 25, ...
winter fiber
All multiples
winter fiber
15?
jaunty dome
we know what values play well with 3, we know what values play well with 5
yes
15 works with both
winter fiber
Ah i see
jaunty dome
because it's a multiple of both
winter fiber
Yh
jaunty dome
so...we could easily generalize this to any number of divisors
we just need the mod to be divisible by all the divisors
winter fiber
Thé LCM?
jaunty dome
yep
in this case we are given primes as divisors, so the product is the same as the lcm
but yes, this is the key to solving part 2
winter fiber
A sec please. You mentioned reducing the « old » but how?
When I add prints I see that the value becomes extremely big. And hence my program can’t even reach the i=1000
How could I reduce that
« Old » times « old » seems costly for the pc
Speaking of resources
jaunty dome
How could I reduce that
by applying what we discussed just above
winter fiber
Huh
jaunty dome
if I had a value n and I had monkeys that checked divisibility by 2, 3, 5
I could keep only n%30
which is small
since lcm(2, 3, 5) = 30
(just 2*3*5 in this case)
winter fiber
Ahhhh alright. Let me try that. 🥹 thanks.
winter fiber
if I had a value `n` and I had monkeys that checked divisibility by 2, 3, 5
Hey @jaunty dome it worked !
Thanks a lot for the hint!
granite cedar
Well, I am behind a bit, but here is my solution 😄
from dataclasses import dataclass
from re import findall
from math import lcm
@dataclass(kw_only=True)
class Monkey:
id: int
items: list[int]
operation: list[str]
test: int
true_throw_to: int
false_throw_to: int
inspection_count: int = 0
@property
def get_inspection_count(self):
return self.inspection_count
def perform_operation(self, part1: bool = True, lcm: int=1) -> tuple([int, int]):
self.inspection_count += 1
val: int = self.items.pop(0)
match self.operation:
case ['+', v]:
val += int(v) if v.isdigit() else val
case ['-', v]:
val -= int(v) if v.isdigit() else val
case ['*', v]:
val *= int(v) if v.isdigit() else val
case ['/', v]:
val //= int(v) if v.isdigit() else val
if part1:
val //= 3
else:
val %= lcm
if val % self.test == 0:
return (val, self.true_throw_to)
else:
return (val, self.false_throw_to)
def solve(part1: bool = True, amt: int = 20) -> int:
actions: list[str] = [x.strip() for x in open("input.txt").read().split("\n\n")]
monkeys: list[Monkey] = list()
for i, action in enumerate(actions):
lines = action.strip().split("\n")
id = i
items = list(map(int, [x for x in findall(r"(\d+)", lines[1])]))
operation = lines[2].split()[-2:]
test = list(map(int,findall(r"(\d+)", lines[3])))[0]
true_throw_to = int(findall(r"(\d+)", lines[4])[0])
false_throw_to = int(findall(r"(\d+)", lines[5])[0])
mnk = Monkey(id=id, items=items, operation=operation, test=test, true_throw_to=true_throw_to, false_throw_to=false_throw_to)
monkeys.append(mnk)
lcm_: int = lcm(*[m.test for m in monkeys])
for _ in range(amt):
for i in range(len(monkeys)):
mnk = monkeys[i]
for _ in range(len(mnk.items)):
val, to_monkey = mnk.perform_operation(part1, lcm_)
monkeys[to_monkey].items.append(val)
total_monkey_inspections: list[int] = sorted([x.get_inspection_count for x in monkeys], reverse=True)
return total_monkey_inspections[0] * total_monkey_inspections[1]
print(f"Part 1: {solve(True, 20)}")
print(f"Part 2: {solve(False, 10000)}")```Had fun trying the dataclasses out. Quite like it
twilit shell
why have a property instead of just accessing it
sinful prism
I am behind as well- just did day 11 p 2 after needing a hint to do it (plus needing to be off work as well lol)
sleek scroll
I got a hint on the thing for part 2 but for some reason my solution isn't working. I'm using the product, but for some reason it's not moving the items correctly.
floral cypress
i just waited like 70minutes until the answer was calculated which was correct
70 mins?
i started running mine
i hhope i get the correct answer