[Community Puzzle] 1D Spreadsheet

@migsilvan2211 If your code is too slow, then try memoizing.

@Dinesh20
@Chronx
I “lost” a few hours fighting with it.
In my case: ‘-3’.isdigit() was the problem.
Unbelievable.

This puzzle seems to me a better fit for the medium category that for the easy one. Add the keyword Memoization in the Details under the section What I'll learn? would be really useful as well. Thanks to the ones that pointed out the Memoization technique. That really helped me to solve this puzzle.

2 Likes

Good idea indeed. Done.

1 Like

Solved subject without Memoization and recursion. Solution was event-driven. Dependency chains “auto” solved after cell calculation by subscription to solved event.
Each cell calculated one time.

2 Likes

Thanks Niako!

recursive it until it can be a number ?

I’m trying to solve this in Bash. I managed to pass all tests except the last one. I’m also trying to run it directly on my computer so that I don’t hit the time limit. Unfortunately, it seems to go on forever.
My solution uses function recursion. This function actually stores the result of every completed cell, so I would say Memoization is implemented (it still needs 1 function call to retrieve the value). However, say it takes 60 levels before my code hits an operation with only values, then the function will have been called 2^60 = 1 152 921 504 606 846 976 times.

PS: I agree with others that this exercise should not be in the “Easy” section.

That’s what I did, but the final test will fail because the number of function calls will be huge.

I can’t see you received an answer yet, but maybe you figured it out already cause it’s been a year ago.
Still, for completeness, for the last test you need memoization. Or else your program will resolve the same cell over and over again for many many times, resulting in a timeout.

Bonjour à tous,

J’ai cette erreur au test 11.

Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 262144 bytes) in the answer code

Comment puis-je ajouter de la mémoire si je n’ais ni accès au php.ini ni au htacces !!!

Où alors la solution est autre part ?
Quelqu’un peut il me donner des indications ou des pistes.

Good morning all,

I have this error in test 11.

Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 262144 bytes) in the answer code

How can I add memory if I have neither access to php.ini nor htacces !!!

Where else is the solution elsewhere?
Can someone give me directions or leads.

@Rodier78 That’s most likely a stack overflow. The solution to that problem is already mentioned many times in this forum.

Thank for your help.
But I don’t find the answer or direction in the forum.
I already use memorisation.

Actually I did not remember correctly the size of the input, but, after verification, it’s much smaller than what I thought and you should definitely not stack overflow, even without memoization. I guess there must be a bug somewhere in your code that causes some recursive calls to loop for instance.
You can send it to me in PM if you don’t find the problem, I’ll have a look.

1 Like

Well after 3 days of research on test 11, I give up.
Can someone give me the solution, thanks in advance.

It is all about recursion. To calculate the value of a cell (e.g. Eval(i) ) calculate the value of each cell it refers to (e.g. Eval(arg1) + Eval(arg2)). That way it will always find the result as long as there is no cycles.

The solutions to testcases are available in the IDE (click on the button in the top-right corner of the testcases box).

Thanks a lot, i was trying so hard to find a totally different solution… but with this “Mémorisation” thingy all i had to do is add an if statement and a value saving solution, thx again.

I am currently working on this puzzle using Python. I am not that familiar with memoization so I have been looking up resources to help my understanding. Before trying to implement memoization, my code only failed at “Deep Birecursion.” That was due to the process timing out. I used recursion to solve the puzzle and before trying to implement a separate form of memoization, my code continually updated and checked against a dictionary to see if a value existed already. After trying to implement a separate form of memoization, my code seems to have gotten worse and doesn’t pass other tests as well now. Can anybody point me to some good resources on memoization? All of the ones I have come across seem to talk about utilizing it in a Fibonacci sequence which has helped my understanding quite a bit, however, I believe I may not be utilizing it or accessing it correctly given the extent of my code. Or if anybody is willing to give a look at my code to see if they can find a way to help optimize, I can send my code as well.

Lemme try and be resourceful. Here comes:

Memoization is the art of trading space for time, by remembering a function’s return value so as to compute it only once, hoping it be requested more.

Did I say art? I meant act.

Certainly not me.