[Community Puzzle] 1D Spreadsheet

https://www.codingame.com/training/easy/1d-spreadsheet

Send your feedback or ask for help here!

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
Trouvé : 20
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
ADD $1 20
VALUE 32 _

Il y a donc 2 cellules, $0 = $1 + 20 et $1 = 32, d’oĂč $0 = 52.

2 Likes

OK, je vois :thinking: 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
ADD $1 $2
SUB $4 $2
ADD $4 $4
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.

Capture%20d%E2%80%99%C3%A9cran%20de%202019-07-12%2012-33-08

7 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
ADD $1 20
ADD 32 4

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)
ADD 5 10
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
Le dĂ©lai d’exĂ©cution du processus a Ă©tĂ© dĂ©passĂ©. Cela peut signifier que votre solution n’est pas suffisamment optimisĂ©e pour traiter certains cas."
Une idée pour optimiser ?
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 :slight_smile:

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?

Really scratching my head lol :frowning:

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.

thank you for reading.

6 Likes