[Community Puzzle] 1D Spreadsheet

CommunityBot · June 21, 2019, 12:26pm

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.

Shinzeo · July 5, 2019, 9:36am

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… ?

JBM · July 5, 2019, 1:36pm

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.

akaliphen · July 6, 2019, 1:27pm

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 ?

Niako · July 6, 2019, 2:12pm

@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.

akaliphen · July 6, 2019, 2:17pm

OK, je vois Merci

Shinzeo · July 10, 2019, 1:55pm

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 ?

java_coffee_cup · July 10, 2019, 4:08pm

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

neve7 · July 12, 2019, 10:18am

C’est vraiment ce qui est attendu.
Il semble que la somme ne soit pas faite… un problème de d’assignation/retour?

JBM · July 12, 2019, 10:37am

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

Shinzeo · July 17, 2019, 2:05pm

My code give the following answer :

0
0
0
0
0

Because all cells are initialized at 0
Is that correct ?

PolyB · July 17, 2019, 2:42pm

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

blakestone · August 6, 2019, 2:28am

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

Niako · August 6, 2019, 9:30am

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

Elwithien · August 6, 2019, 7:11pm

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

Niako · August 6, 2019, 9:00pm

@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).

blakestone · August 8, 2019, 12:30am

Thank you

DirtySocrates · August 12, 2019, 12:20am

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

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!

Elwithien · August 12, 2019, 8:47am

Merci beaucoup @Niako , après quelques recherches sur la mémoïsation j’ai réussi à terminer ce niveau.

Lesmana · August 14, 2019, 9:28pm

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.