Created by @PolyB,validated by @bbb000bbbyyy,@JBM and @Zorg1.
If you have any issues, feel free to ping them.

I managed the 10 first tests but then I donât, I noticed that there could be an order in the execution of operations (VALUE first) but there may be others that I didnât found. So I wonder : Is there some rules I missed ? Is there some priority between ADD, SUB and MULT or according to the cells \$0, \$1âŠ ?

There is no need for precedence, as each cell can only have a single operation. On the other hand, you obviously canât compute a cellâs value before you have computed the operands it depends on.

Mon code passe tous les tests sauf âBackward dependencyâ. Le premier argument donnĂ© fait rĂ©fĂ©rence Ă  une cellule inexistante, que je positionne alors Ă  0.
Mais il semble que le rĂ©sultat attendu soit dans ce cas un mĂ©lange des arguments de 2 lignes de calcul, comme on peut voir si dessous :
Sortie standard :
'cells : â
âarg1 : \$1 OP : ADD et arg 2 : 20â
âcells : 20â
âarg1 : 32 OP : VALUE et arg 2 : _â
20
32
Ăchec
Attendu : 52
Est-ce vraiment ce qui est attendu, ou sâagit-il dâune erreur dans le jeu de donnĂ©es de test ?

@akaliphen Lâinput est :

``````2
VALUE 32 _
``````

Il y a donc 2 cellules, `\$0 = \$1 + 20` et `\$1 = 32`, dâoĂč `\$0 = 52`.

2 Likes

OK, je vois Merci

I donât understand how we can predict the value of a cell if the ones it refers have no value except 0 because of initialization. As I said I canât manage the tests after 11 even if I putted values in cells for operation with either VALUE or any other operation with only numbers and no references. Please could anyone give me an advice ?

You are already doing very well to have passed 10 test cases.
Ever think of a spreadsheet having no VALUE at all? Try this:

5
SUB \$4 \$2
MULT \$0 \$1
SUB \$3 \$3

Câest vraiment ce qui est attendu.
Il semble que la somme ne soit pas faiteâŠ un problĂšme de dâassignation/retour?

Hereâs a Google Sheets transcription of the âDiamond Dependencyâ test case, just to show how you could solve the test cases even if you didnât understand the algorithm behind.

6 Likes

My code give the following answer :

0
0
0
0
0

Because all cells are initialized at 0
Is that correct ?

2 Likes

The rules of the puzzle say

There wonât be any cyclic references: a cell that reference itself or a cell that references it, directly or indirectly.

So the test written by java_coffee_cup is not valid and wonât be tested.

However java_coffe_cup is right that a spreadsheet can have no VALUE at all like this:

``````2
``````

The expected result here is
56
36

I am passing test cases 1-10 and failing the rest.
In my below example what would be the correct answer for each line?

``````4
SUB \$3 3       // would this be (5 - 3) or (15 - 3)
MULT \$0 \$0     // would this be (5 * 5) or (15 * 15)  or (12 * 12)
ADD \$1 \$1      // would this be (25 + 25) or (225 + 225) or (144 + 144)
1 Like

@blakestone `\$3 = 15`, then `\$0 = 12`, then `\$1 = 144`, finally `\$2 = 288`.

1 Like

Bonjour,
Jâutilise Python, 2 fonctions : une qui dĂ©termine lâopĂ©ration Ă  effectuer et lâautre qui dĂ©termine les valeurs.
Mon code passe tous les tests sauf le 13Ăšme (Deep Birecursion) :
" Ăchec
Merci dâavance

@Elwithien MĂ©moriser les valeurs calculĂ©es (mĂ©moĂŻsation) pour ne plus avoir Ă  les recalculer par la suite (câest un peu plus quâune âoptimisationâ cela dit, cela garantit une complexitĂ© linĂ©aire O(n) et non plus exponentielle O(2^n) dans le pire cas).

5 Likes

Thank you

Does anyone have any tips? Having a hard time wrapping my head around how to solve this one. Do we need recursion to solve the cells that other cells are dependent on first?

So I got it, but it took about 2-3 hours of thinking on. Man I feel dumb.

Also, javascript is weird. -0 is a thing!

1 Like

Merci beaucoup @Niako , aprĂšs quelques recherches sur la mĂ©moĂŻsation jâai rĂ©ussi Ă  terminer ce niveau.

i tried to solve this puzzle in bash. the dependency graph was to be solved by parallel processes waiting for their dependencies to finish. similar to how systemd solved the daemon dependencies during system startup using sockets (http://0pointer.de/blog/projects/systemd.html).

sadly it did not work for the last three test cases. the codingame environment has a hard limit of 200 file descriptors (`ulimit -Hn`). 100 parallel processes need a bit more than that. maybe it would have worked if i could have used bash coproc. but for now coprocs are limited to one background process (https://wiki-dev.bash-hackers.org/syntax/keywords/coproc).

my script uses background processes for concurency, mkfifo to manage synchronization, flock to manage critical sections, and the filesystem to store state.

i tried to reduce the number of parallel processes by preprocessing the input using awk and delaying the start of the processes. but to no avail. also too much preprocessing and i would have end up solving the dependency graph in awk instead of letting the parallel processes solve it themselves. all the beautiful syncing and locking would be of no use.

i am sad that i cannot publish the script since it does not pass the validation because of the last three test cases. i am writing this to mourn a bit for my script. and to brag a bit for my idea. and maybe the codingame devs take pity on my plea and raise the file descriptor limit. although i do not know how many i would need. i was not able to determine the file descriptor count. `lsof` is a beast.

it also irks me a bit that this puzzle is categorized as easy. it seems more like a medium for me. but maybe my strive for this concurrent bash script solution biased my perception of the difficulty.