trail pelican
I could not make my code work solving part 2. Because when I ran it, it took a long time and finally python gave up with printing killed.
I found this solution: https://hamatti.org/adventofcode/2024/solutions/day-11
And he sayes:
If something is likely to grow exponentially, my Advent of Code experience tells me to go recursive.
Now, my solution is not recursive. So I'm wondering. Why did the execution end with killed?
Did my array become too big? Or why does it fail?
rare merlinBOT
I could not make my code work solving part 2. Because when I ran it, it took a l...
@trail pelican
Python help channel opened
trail pelican
def turnToOne():
return 1
def split(number):
middle = len(number) // 2
left = number[:middle]
right = number[middle:]
left = str(int(left))
right = str(int(right))
return left,right
def getInputNumbers(filename):
line = ""
with open(filename, 'r') as f:
line = f.read()
return line
def strategyDecider(number):
if len(number) % 2 == 0:
return split(number)
elif int(number) == 0:
return '1'
else:
return str(int(number) * 2024)
def runStrategies(input_list):
res_list = []
for each in input_list:
res = strategyDecider(each)
if isinstance(res,tuple):
res_list.extend(res)
else:
res_list.append(res)
return res_list
def runBlinkTimes(blinks,input_list):
result = []
for blink in range(blinks):
res = runStrategies(input_list)
input_list = res
return input_list
blinks = 75
input_line = getInputNumbers('puzzleinput11.txt')
input_line = input_line.strip()
input_list = input_line.split()
res = runBlinkTimes(blinks,input_list)
print(len(res))
sour horizon
Let me check the problem and my code. Unfortunately I wrote it in Rust and I’ve mostly forgotten that language lol
Ok I’ve reminded myself of the problem
And yes your issue is the list
sour horizon
```python
def turnToOne():
return 1
def split(number):
middle = len(num...
The exponential growth is a killer. After 75 blinks, res length is a number that has around 15 digits in it
No matter how much recursion you want to do, it means nothing if you try to make a list that big. You just don’t have enough memory for that, period
I can see where recursion would works. But there’s a bit of tendency to jump to recursion as the primary solution - in this case, I’m not convinced it’s the simplest solution. I think there are easier solutions out there
Anyhow let me know if you’d like to talk through the problem more.
still patrol
I think that it is quite natural to solve it recursively
you just have to make sure that you're not calculating the same thing more than once unnecessarily
sour horizon
For me I find an iterative bottom-up approach with an explicit cache more natural. But appreciate they are two sides of the same coin
trail pelican
Sorry, I went down a rabbit hole on the side and missed your answers.
First of, Im thinking of only using integers in the list, instead of keeping them as strings. Because that takes less space.
Im also looking for some "magic" fancy ways to check for number of digits, to see if they are odd or even.
Instead of turning to string, then check length of it, and see if "characters" of number are odd or even.
I can use log base 10 to do that.
so basically math.log10(123) turns to:
2.089905111439398
then remove the fraction.
and + 1 = number of digits
BUT!
cannot find a reliable way to just keep the integer part of the resulting float.
I tried math.floor, and math.trunc and someone mentioned decimal module. But cant make it work.
my tries copied from the terminal...
trail pelican
>>> int(0.9999999999999999999999999)
1
>>> int(0.9999)
0
>>> math.floor(0.9999999999999999999999999)
1
>>> math.floor(0.9999)
0
>>> math.trunc(0.9999999999999999999999999)
1
>>> math.trunc(0.9999)
0
>>> import decimal
>>> d = decimal.Decimal(0.9999999999999999999999999)
>>> print(d)
1
>>> decimal.getcontext().rounding = decimal.ROUND_FLOOR
>>> print(round(d))
1
>>> d.to_integral_exact(rounding=decimal.ROUND_FLOOR)
Decimal('1')
>>> d.to_integral_exact()
Decimal('1')
>>> decimal.round(0.9999999999999999999999999)
>>> d.to_integral_exact(rounding=decimal.ROUND_DOWN)
Decimal('1')
>>> d.to_integral_exact()
Decimal('1')
```py
int(math.log10(n)) + 1
```
Exactly what I thought as well. But I dont want to erm... just cant find the word
still patrol
the float 0.9999999999999999999999999 is actually the same thing as 1.0
trail pelican
basically int cannot be trusted as you see from my terminal output xD
still patrol
floats don't have infinite precision
try d = decimal.Decimal('0.9999999999999999999999999')
trail pelican
Ok. But how can I be shure int(math.log10(n)) + 1 gonna return correct number if the int() function itself might get it wrong due to precision stuff?
shrewd jay
yeah, because that's actually a string that is being converted, not a float to begin with
will log10 return such floats?
still patrol
Ok. But how can I be shure `int(math.log10(n)) + 1` gonna return correct number ...
it is highly improbable that you'd come across a situation like that
trail pelican
it is highly improbable that you'd come across a situation like that
yeah, probably. No pun intended. heh. But wanna be a "real programmer" not like "meh mostly works, on my computer etc"
still patrol
it is possible that radiation from the sun will flip one of the bits inside your computer's RAM
but, obviously, accounting for that would be silly
trail pelican
d = decimal.Decimal('0.9999999999999999999999999')
>>> d.to_integral_exact()
Decimal('0')
A "real programmer" would just turn the int into a string to begin with :P
trail pelican
Now it works. So I need to turn into string first?
Its what I did first. But since I thought Id just use numbers to save memory as mentioned above, I went into this rabbithole to do most with just numbers and no int to str conversions xD
still patrol
I think you're okay doing floor(log10(n)) + 1
sour horizon
When the list is a length of 15 digits long, nothing you will do will help you with that
trail pelican
Ok. So just using integers in list instead of strings is pretty much nothing compared to the shear size of the list is what I understand you saying.
I guess then cache thing is the way to go.
sour horizon
The length of the list to 1 sig fig is 300000000000000
trail pelican
Way to tired now, should have gone to bed like 2 hours ago haha. I would love to let you walk me through it some other time. Im really sorry. I appreciate you guys just to tired now. -_-. Might we continue some other day?
sour horizon
If I'm around, sure.
Basically what I am trying to say is that number is 3 x 10^15
To put into perspective, 1 TB drive has 1 x 10^12 bytes
trail pelican
Yeah. Im guessing the OS has a "guard" and it sigterms the script even way before that.
checked mem, and it used 8000Mb + before it "Killed"
sour horizon
not even close :)
trail pelican
yeah
sour horizon
this is the classic AoC problem of Part 1 can be solved naively but Part 2 you don't have a hope in hell unless you find the true solution
trail pelican
I just don know how cache thing works. i just know cache from javascript where one saves already computed results and just retrieve them. Seems similar when I checked the docs. But I cannot wrap my head around why that would help because cashing results should only save time spent in cpu. Since one is cashing results, hence saving them, it would rather spend more ram. But yeah. really tired now. Bye, take care and hope to see you again. PS. Am I allowed to DM you about the question? Some day?
acoustic shuttle
familiarize yourself with: https://en.wikipedia.org/wiki/Memoization
sour horizon
I just don know how cache thing works. i just know cache from javascript where o...
I don't do DMs, but if you want, I can send you my solution which might help things
shrewd jay
have a look through https://docs.python.org/3/library/functools.html or maybe implement it yourself with a hash/dictionary or something like that
sour horizon
it ain't a recursive one but I think you'll understand it better, and then you can consider looking at the recursive solution
acoustic shuttle
it's not a super complex thing, you could build your own memoization by simply storing return values in a global dict where your function input is the key and output is the value. When your function is called, check if the dict already has the given input, if it does then just return it; otherwise, compute, store it, return it. IT's a good exercise for understanding how functools stuff works
trail pelican
otherwise, compute, store it...
Thats what messes with me. Its stored in RAM no? And ram exhaustion is the reason it fails.
I trust you and the dude in the link I passed. It just doesnt compute in my head hehe.
Gotta sleep. thanks again! ❤️
rare merlinBOT
Python help channel closed for inactivity